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 #include "git-compat-util.h"
  18
  19 struct cb_node;
  20 struct cb_node {
  21         struct cb_node *child[2];
  22         /*
  23          * n.b. uint32_t for `byte' is excessive for OIDs,
  24          * we may consider shorter variants if nothing else gets stored.
  25          */
  26         uint32_t byte;
  27         uint8_t otherbits;
  28         uint8_t k[FLEX_ARRAY]; /* arbitrary data, unaligned */
  29 };
  30
  31 struct cb_tree {
  32         struct cb_node *root;
  33 };
  34
  35 enum cb_next {
  36         CB_CONTINUE = 0,
  37         CB_BREAK = 1
  38 };
  39
  40 #define CBTREE_INIT { 0 }
  41
  42 static inline void cb_init(struct cb_tree *t)
  43 {
  44         struct cb_tree blank = CBTREE_INIT;
  45         memcpy(t, &blank, sizeof(*t));
  46 }
  47
  48 struct cb_node *cb_lookup(struct cb_tree *, const uint8_t *k, size_t klen);
  49 struct cb_node *cb_insert(struct cb_tree *, struct cb_node *, size_t klen);
  50 struct cb_node *cb_unlink(struct cb_tree *t, const uint8_t *k, size_t klen);
  51
  52 typedef enum cb_next (*cb_iter)(struct cb_node *, void *arg);
  53
  54 void cb_each(struct cb_tree *, const uint8_t *kpfx, size_t klen,
  55                 cb_iter, void *arg);
  56
  57 #endif /* CBTREE_H */