lunaix-os/includes/lunaix/ds/btrie.h

   1 #ifndef __LUNAIX_SPARSE_H
   2 #define __LUNAIX_SPARSE_H
   3
   4 #include <lunaix/ds/llist.h>
   5 #include <lunaix/types.h>
   6
   7 #define BTRIE_BITS 4
   8
   9 /**
  10  * key-sorted prefix tree
  11  */
  12 struct btrie
  13 {
  14     struct btrie_node* btrie_root;
  15     unsigned int order;
  16 };
  17
  18 struct btrie_node
  19 {
  20     struct llist_header nodes;
  21     struct btrie_node* parent;
  22     unsigned long index;
  23     void* data;
  24
  25     struct btrie_node** children;
  26     int children_cnt;
  27 };
  28
  29 void
  30 btrie_init(struct btrie* btrie, unsigned int order);
  31
  32 void*
  33 btrie_get(struct btrie* root, unsigned long index);
  34
  35 /**
  36  * Set an object into btrie tree at given location,
  37  * override if another object is already present.
  38  */
  39 void
  40 btrie_set(struct btrie* root, unsigned long index, void* data);
  41
  42 /**
  43  * Map an object into btrie tree, return the index the object
  44  * mapped to
  45  */
  46 unsigned long
  47 btrie_map(struct btrie* root,
  48           unsigned long start, unsigned long end, void* data);
  49
  50 void*
  51 btrie_remove(struct btrie* root, unsigned long index);
  52
  53 void
  54 btrie_release(struct btrie* tree);
  55
  56 #endif /* __LUNAIX_SPARSE_H */