]>
Commit | Line | Data |
---|---|---|
92d8ed8a EW |
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 | } |