cbtree.c

   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 #include "git-compat-util.h"
   8 #include "cbtree.h"
   9
  10 static struct cb_node *cb_node_of(const void *p)
  11 {
  12         return (struct cb_node *)((uintptr_t)p - 1);
  13 }
  14
  15 /* locate the best match, does not do a final comparison */
  16 static struct cb_node *cb_internal_best_match(struct cb_node *p,
  17                                         const uint8_t *k, size_t klen)
  18 {
  19         while (1 & (uintptr_t)p) {
  20                 struct cb_node *q = cb_node_of(p);
  21                 uint8_t c = q->byte < klen ? k[q->byte] : 0;
  22                 size_t direction = (1 + (q->otherbits | c)) >> 8;
  23
  24                 p = q->child[direction];
  25         }
  26         return p;
  27 }
  28
  29 /* returns NULL if successful, existing cb_node if duplicate */
  30 struct cb_node *cb_insert(struct cb_tree *t, struct cb_node *node, size_t klen)
  31 {
  32         size_t newbyte, newotherbits;
  33         uint8_t c;
  34         int newdirection;
  35         struct cb_node **wherep, *p;
  36
  37         assert(!((uintptr_t)node & 1)); /* allocations must be aligned */
  38
  39         if (!t->root) {         /* insert into empty tree */
  40                 t->root = node;
  41                 return NULL;    /* success */
  42         }
  43
  44         /* see if a node already exists */
  45         p = cb_internal_best_match(t->root, node->k, klen);
  46
  47         /* find first differing byte */
  48         for (newbyte = 0; newbyte < klen; newbyte++) {
  49                 if (p->k[newbyte] != node->k[newbyte])
  50                         goto different_byte_found;
  51         }
  52         return p;       /* element exists, let user deal with it */
  53
  54 different_byte_found:
  55         newotherbits = p->k[newbyte] ^ node->k[newbyte];
  56         newotherbits |= newotherbits >> 1;
  57         newotherbits |= newotherbits >> 2;
  58         newotherbits |= newotherbits >> 4;
  59         newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255;
  60         c = p->k[newbyte];
  61         newdirection = (1 + (newotherbits | c)) >> 8;
  62
  63         node->byte = newbyte;
  64         node->otherbits = newotherbits;
  65         node->child[1 - newdirection] = node;
  66
  67         /* find a place to insert it */
  68         wherep = &t->root;
  69         for (;;) {
  70                 struct cb_node *q;
  71                 size_t direction;
  72
  73                 p = *wherep;
  74                 if (!(1 & (uintptr_t)p))
  75                         break;
  76                 q = cb_node_of(p);
  77                 if (q->byte > newbyte)
  78                         break;
  79                 if (q->byte == newbyte && q->otherbits > newotherbits)
  80                         break;
  81                 c = q->byte < klen ? node->k[q->byte] : 0;
  82                 direction = (1 + (q->otherbits | c)) >> 8;
  83                 wherep = q->child + direction;
  84         }
  85
  86         node->child[newdirection] = *wherep;
  87         *wherep = (struct cb_node *)(1 + (uintptr_t)node);
  88
  89         return NULL; /* success */
  90 }
  91
  92 struct cb_node *cb_lookup(struct cb_tree *t, const uint8_t *k, size_t klen)
  93 {
  94         struct cb_node *p = cb_internal_best_match(t->root, k, klen);
  95
  96         return p && !memcmp(p->k, k, klen) ? p : NULL;
  97 }
  98
  99 static enum cb_next cb_descend(struct cb_node *p, cb_iter fn, void *arg)
 100 {
 101         if (1 & (uintptr_t)p) {
 102                 struct cb_node *q = cb_node_of(p);
 103                 enum cb_next n = cb_descend(q->child[0], fn, arg);
 104
 105                 return n == CB_BREAK ? n : cb_descend(q->child[1], fn, arg);
 106         } else {
 107                 return fn(p, arg);
 108         }
 109 }
 110
 111 void cb_each(struct cb_tree *t, const uint8_t *kpfx, size_t klen,
 112                         cb_iter fn, void *arg)
 113 {
 114         struct cb_node *p = t->root;
 115         struct cb_node *top = p;
 116         size_t i = 0;
 117
 118         if (!p) return; /* empty tree */
 119
 120         /* Walk tree, maintaining top pointer */
 121         while (1 & (uintptr_t)p) {
 122                 struct cb_node *q = cb_node_of(p);
 123                 uint8_t c = q->byte < klen ? kpfx[q->byte] : 0;
 124                 size_t direction = (1 + (q->otherbits | c)) >> 8;
 125
 126                 p = q->child[direction];
 127                 if (q->byte < klen)
 128                         top = p;
 129         }
 130
 131         for (i = 0; i < klen; i++) {
 132                 if (p->k[i] != kpfx[i])
 133                         return; /* "best" match failed */
 134         }
 135         cb_descend(top, fn, arg);
 136 }