freshlybakedca.ke
Git fork
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
10static 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 */
16static 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 */
30struct 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
54different_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
92struct 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
99static 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
111void 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}