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