cbtree.h

   1 /*
   2  * crit-bit tree implementation, does no allocations internally
   3  * For more information on crit-bit trees: https://cr.yp.to/critbit.html
   4  * Based on Adam Langley's adaptation of Dan Bernstein's public domain code
   5  * git clone https://github.com/agl/critbit.git
   6  *
   7  * This is adapted to store arbitrary data (not just NUL-terminated C strings
   8  * and allocates no memory internally.  The user needs to allocate
   9  * "struct cb_node" and fill cb_node.k[] with arbitrary match data
  10  * for memcmp.
  11  * If "klen" is variable, then it should be embedded into "c_node.k[]"
  12  * Recursion is bound by the maximum value of "klen" used.
  13  */
  14 #ifndef CBTREE_H
  15 #define CBTREE_H
  16
  17 struct cb_node;
  18 struct cb_node {
  19         struct cb_node *child[2];
  20         /*
  21          * n.b. uint32_t for `byte' is excessive for OIDs,
  22          * we may consider shorter variants if nothing else gets stored.
  23          */
  24         uint32_t byte;
  25         uint8_t otherbits;
  26         uint8_t k[FLEX_ARRAY]; /* arbitrary data, unaligned */
  27 };
  28
  29 struct cb_tree {
  30         struct cb_node *root;
  31 };
  32
  33 enum cb_next {
  34         CB_CONTINUE = 0,
  35         CB_BREAK = 1
  36 };
  37
  38 #define CBTREE_INIT { 0 }
  39
  40 static inline void cb_init(struct cb_tree *t)
  41 {
  42         struct cb_tree blank = CBTREE_INIT;
  43         memcpy(t, &blank, sizeof(*t));
  44 }
  45
  46 struct cb_node *cb_lookup(struct cb_tree *, const uint8_t *k, size_t klen);
  47 struct cb_node *cb_insert(struct cb_tree *, struct cb_node *, size_t klen);
  48
  49 typedef enum cb_next (*cb_iter)(struct cb_node *, void *arg);
  50
  51 void cb_each(struct cb_tree *, const uint8_t *kpfx, size_t klen,
  52                 cb_iter, void *arg);
  53
  54 #endif /* CBTREE_H */