]>
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 | */ | |
8bff5ca0 | 7 | #include "git-compat-util.h" |
92d8ed8a EW |
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 comparision */ | |
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 | ||
92d8ed8a EW |
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 | } |