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