memo.h

   1 // Crit-bit tree.
   2 // No parent pointers. No linked list.
   3 //
   4 // Uses pointer casting and different structs instead of unions.
   5 // In a trie, internal nodes never become external nodes, and vice versa.
   6
   7 struct memo_node_s {
   8   char type;
   9   short critbit;
  10   struct memo_node_s *left, *right;
  11 };
  12 typedef struct memo_node_s memo_node_t[1];
  13 typedef struct memo_node_s *memo_node_ptr;
  14
  15 struct memo_leaf_s {
  16   char type;
  17   void *data;
  18   char *key;
  19 };
  20 typedef struct memo_leaf_s memo_leaf_t[1];
  21 typedef struct memo_leaf_s *memo_leaf_ptr;
  22
  23 // Iterator.
  24 typedef memo_leaf_ptr memo_it;
  25
  26 struct memo_s {
  27   memo_node_ptr root;
  28 };
  29 typedef struct memo_s memo_t[1];
  30 typedef struct memo_s *memo_ptr;
  31
  32 void memo_clear(memo_ptr memo);
  33
  34 static inline void memo_init(memo_ptr memo) {
  35   memo->root = NULL;
  36 }
  37
  38 int memo_has(memo_ptr memo, const char *key);
  39 void *memo_at(memo_ptr memo, const char *key);
  40 memo_it memo_put(memo_ptr memo, void *data, const char *key);
  41
  42 void *memo_alloc();
  43
  44 static inline int memo_it_is_off(memo_it it) {
  45   return !it;
  46 }
  47
  48 static inline void* memo_it_put(memo_it it, void *data) {
  49   return it->data = data;
  50 }
  51
  52 static inline void *memo_it_data(memo_it it) {
  53   return it->data;
  54 }
  55
  56 static inline char *memo_it_key(memo_it it) {
  57   return it->key;
  58 }
  59
  60 memo_it memo_it_at(memo_ptr memo, const char *key);
  61
  62 void memo_forall(memo_t memo, void (*fn)(void *data, const char *key));
  63
  64 void *memo_remove(memo_ptr memo, const char *key);
  65 void memo_remove_all(memo_ptr memo);
  66 void memo_remove_all_with(memo_ptr memo, void (*fn)(void *data, const char *key));
  67
  68 static inline void memo_clear_with(memo_ptr memo,
  69     void (*fn)(void *data, const char *key)) {
  70   memo_remove_all_with(memo, fn);
  71 }
  72
  73 memo_it memo_put_with(memo_ptr memo, void *(*fn)(void *), const char *key);
  74
  75 // Alternative mode: all keys are the same length but can contain any data.
  76 // e.g. SHA1 hashes. Do not mix with ASCIIZ keys!
  77 int memo_has_u(memo_ptr memo, const unsigned char *key, int len);
  78 void *memo_at_u(memo_ptr memo, const unsigned char *key, int len);
  79 memo_leaf_ptr memo_put_u(memo_ptr memo, void *data,
  80     const unsigned char *key, int len);
  81
  82 // Finds or creates an entry with the given key and writes it to *it.
  83 // Returns 1 if a new memo_it was created.
  84 int memo_it_insert_u(memo_it *it,
  85     memo_ptr memo, const unsigned char *key, int len);
  86
  87 memo_it memo_it_at_u(memo_ptr memo, const unsigned char *key, int len);
  88
  89 // Faster than memo_at_u if you know that the key is definitely in the tree.
  90 void *memo_sure_at_u(memo_ptr memo, const unsigned char *key, int len);
  91
  92 // Finds or creates an entry with the given key and writes it to *it.
  93 // Returns 1 if a new memo_it was created.
  94 int memo_it_insert(memo_it *it, memo_ptr memo, const char *key);