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