1 /*
2 * Elastic Binary Trees - macros to manipulate Indirect String data nodes.
3 * Version 6.0.6
4 * (C) 2002-2011 - Willy Tarreau <w@1wt.eu>
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation, version 2.1
9 * exclusively.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21 /* These functions and macros rely on Multi-Byte nodes */
22
23 #ifndef _EBISTREE_H
24 #define _EBISTREE_H
25
26 #include <string.h>
27 #include "ebtree.h"
28 #include "ebpttree.h"
29 #include "ebimtree.h"
30
31 /* These functions and macros rely on Pointer nodes and use the <key> entry as
32 * a pointer to an indirect key. Most operations are performed using ebpt_*.
33 */
34
35 /* The following functions are not inlined by default. They are declared
36 * in ebistree.c, which simply relies on their inline version.
37 */
38 REGPRM2 struct ebpt_node *ebis_lookup(struct eb_root *root, const char *x);
39 REGPRM2 struct ebpt_node *ebis_insert(struct eb_root *root, struct ebpt_node *new);
40
41 /* Find the first occurence of a length <len> string <x> in the tree <root>.
42 * It's the caller's reponsibility to use this function only on trees which
43 * only contain zero-terminated strings, and that no null character is present
44 * in string <x> in the first <len> chars. If none can be found, return NULL.
45 */
46 static forceinline struct ebpt_node *
ebis_lookup_len(struct eb_root * root,const char * x,unsigned int len)47 ebis_lookup_len(struct eb_root *root, const char *x, unsigned int len)
48 {
49 struct ebpt_node *node;
50
51 node = ebim_lookup(root, x, len);
52 if (!node || ((const char *)node->key)[len] != 0)
53 return NULL;
54 return node;
55 }
56
57 /* Find the first occurence of a zero-terminated string <x> in the tree <root>.
58 * It's the caller's reponsibility to use this function only on trees which
59 * only contain zero-terminated strings. If none can be found, return NULL.
60 */
__ebis_lookup(struct eb_root * root,const void * x)61 static forceinline struct ebpt_node *__ebis_lookup(struct eb_root *root, const void *x)
62 {
63 struct ebpt_node *node;
64 eb_troot_t *troot;
65 int bit;
66 int node_bit;
67
68 troot = root->b[EB_LEFT];
69 if (unlikely(troot == NULL))
70 return NULL;
71
72 bit = 0;
73 while (1) {
74 if ((eb_gettag(troot) == EB_LEAF)) {
75 node = container_of(eb_untag(troot, EB_LEAF),
76 struct ebpt_node, node.branches);
77 if (strcmp(node->key, x) == 0)
78 return node;
79 else
80 return NULL;
81 }
82 node = container_of(eb_untag(troot, EB_NODE),
83 struct ebpt_node, node.branches);
84 node_bit = node->node.bit;
85
86 if (node_bit < 0) {
87 /* We have a dup tree now. Either it's for the same
88 * value, and we walk down left, or it's a different
89 * one and we don't have our key.
90 */
91 if (strcmp(node->key, x) != 0)
92 return NULL;
93
94 troot = node->node.branches.b[EB_LEFT];
95 while (eb_gettag(troot) != EB_LEAF)
96 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
97 node = container_of(eb_untag(troot, EB_LEAF),
98 struct ebpt_node, node.branches);
99 return node;
100 }
101
102 /* OK, normal data node, let's walk down but don't compare data
103 * if we already reached the end of the key.
104 */
105 if (likely(bit >= 0)) {
106 bit = string_equal_bits(x, node->key, bit);
107 if (likely(bit < node_bit)) {
108 if (bit >= 0)
109 return NULL; /* no more common bits */
110
111 /* bit < 0 : we reached the end of the key. If we
112 * are in a tree with unique keys, we can return
113 * this node. Otherwise we have to walk it down
114 * and stop comparing bits.
115 */
116 if (eb_gettag(root->b[EB_RGHT]))
117 return node;
118 }
119 /* if the bit is larger than the node's, we must bound it
120 * because we might have compared too many bytes with an
121 * inappropriate leaf. For a test, build a tree from "0",
122 * "WW", "W", "S" inserted in this exact sequence and lookup
123 * "W" => "S" is returned without this assignment.
124 */
125 else
126 bit = node_bit;
127 }
128
129 troot = node->node.branches.b[(((unsigned char*)x)[node_bit >> 3] >>
130 (~node_bit & 7)) & 1];
131 }
132 }
133
134 /* Insert ebpt_node <new> into subtree starting at node root <root>. Only
135 * new->key needs be set with the zero-terminated string key. The ebpt_node is
136 * returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys. The
137 * caller is responsible for properly terminating the key with a zero.
138 */
139 static forceinline struct ebpt_node *
__ebis_insert(struct eb_root * root,struct ebpt_node * new)140 __ebis_insert(struct eb_root *root, struct ebpt_node *new)
141 {
142 struct ebpt_node *old;
143 unsigned int side;
144 eb_troot_t *troot;
145 eb_troot_t *root_right;
146 int diff;
147 int bit;
148 int old_node_bit;
149
150 side = EB_LEFT;
151 troot = root->b[EB_LEFT];
152 root_right = root->b[EB_RGHT];
153 if (unlikely(troot == NULL)) {
154 /* Tree is empty, insert the leaf part below the left branch */
155 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
156 new->node.leaf_p = eb_dotag(root, EB_LEFT);
157 new->node.node_p = NULL; /* node part unused */
158 return new;
159 }
160
161 /* The tree descent is fairly easy :
162 * - first, check if we have reached a leaf node
163 * - second, check if we have gone too far
164 * - third, reiterate
165 * Everywhere, we use <new> for the node node we are inserting, <root>
166 * for the node we attach it to, and <old> for the node we are
167 * displacing below <new>. <troot> will always point to the future node
168 * (tagged with its type). <side> carries the side the node <new> is
169 * attached to below its parent, which is also where previous node
170 * was attached.
171 */
172
173 bit = 0;
174 while (1) {
175 if (unlikely(eb_gettag(troot) == EB_LEAF)) {
176 eb_troot_t *new_left, *new_rght;
177 eb_troot_t *new_leaf, *old_leaf;
178
179 old = container_of(eb_untag(troot, EB_LEAF),
180 struct ebpt_node, node.branches);
181
182 new_left = eb_dotag(&new->node.branches, EB_LEFT);
183 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
184 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
185 old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
186
187 new->node.node_p = old->node.leaf_p;
188
189 /* Right here, we have 3 possibilities :
190 * - the tree does not contain the key, and we have
191 * new->key < old->key. We insert new above old, on
192 * the left ;
193 *
194 * - the tree does not contain the key, and we have
195 * new->key > old->key. We insert new above old, on
196 * the right ;
197 *
198 * - the tree does contain the key, which implies it
199 * is alone. We add the new key next to it as a
200 * first duplicate.
201 *
202 * The last two cases can easily be partially merged.
203 */
204 if (bit >= 0)
205 bit = string_equal_bits(new->key, old->key, bit);
206
207 if (bit < 0) {
208 /* key was already there */
209
210 /* we may refuse to duplicate this key if the tree is
211 * tagged as containing only unique keys.
212 */
213 if (eb_gettag(root_right))
214 return old;
215
216 /* new arbitrarily goes to the right and tops the dup tree */
217 old->node.leaf_p = new_left;
218 new->node.leaf_p = new_rght;
219 new->node.branches.b[EB_LEFT] = old_leaf;
220 new->node.branches.b[EB_RGHT] = new_leaf;
221 new->node.bit = -1;
222 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
223 return new;
224 }
225
226 diff = cmp_bits(new->key, old->key, bit);
227 if (diff < 0) {
228 /* new->key < old->key, new takes the left */
229 new->node.leaf_p = new_left;
230 old->node.leaf_p = new_rght;
231 new->node.branches.b[EB_LEFT] = new_leaf;
232 new->node.branches.b[EB_RGHT] = old_leaf;
233 } else {
234 /* new->key > old->key, new takes the right */
235 old->node.leaf_p = new_left;
236 new->node.leaf_p = new_rght;
237 new->node.branches.b[EB_LEFT] = old_leaf;
238 new->node.branches.b[EB_RGHT] = new_leaf;
239 }
240 break;
241 }
242
243 /* OK we're walking down this link */
244 old = container_of(eb_untag(troot, EB_NODE),
245 struct ebpt_node, node.branches);
246 old_node_bit = old->node.bit;
247
248 /* Stop going down when we don't have common bits anymore. We
249 * also stop in front of a duplicates tree because it means we
250 * have to insert above. Note: we can compare more bits than
251 * the current node's because as long as they are identical, we
252 * know we descend along the correct side.
253 */
254 if (bit >= 0 && (bit < old_node_bit || old_node_bit < 0))
255 bit = string_equal_bits(new->key, old->key, bit);
256
257 if (unlikely(bit < 0)) {
258 /* Perfect match, we must only stop on head of dup tree
259 * or walk down to a leaf.
260 */
261 if (old_node_bit < 0) {
262 /* We know here that string_equal_bits matched all
263 * bits and that we're on top of a dup tree, then
264 * we can perform the dup insertion and return.
265 */
266 struct eb_node *ret;
267 ret = eb_insert_dup(&old->node, &new->node);
268 return container_of(ret, struct ebpt_node, node);
269 }
270 /* OK so let's walk down */
271 }
272 else if (bit < old_node_bit || old_node_bit < 0) {
273 /* The tree did not contain the key, or we stopped on top of a dup
274 * tree, possibly containing the key. In the former case, we insert
275 * <new> before the node <old>, and set ->bit to designate the lowest
276 * bit position in <new> which applies to ->branches.b[]. In the later
277 * case, we add the key to the existing dup tree. Note that we cannot
278 * enter here if we match an intermediate node's key that is not the
279 * head of a dup tree.
280 */
281 eb_troot_t *new_left, *new_rght;
282 eb_troot_t *new_leaf, *old_node;
283
284 new_left = eb_dotag(&new->node.branches, EB_LEFT);
285 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
286 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
287 old_node = eb_dotag(&old->node.branches, EB_NODE);
288
289 new->node.node_p = old->node.node_p;
290
291 /* we can never match all bits here */
292 diff = cmp_bits(new->key, old->key, bit);
293 if (diff < 0) {
294 new->node.leaf_p = new_left;
295 old->node.node_p = new_rght;
296 new->node.branches.b[EB_LEFT] = new_leaf;
297 new->node.branches.b[EB_RGHT] = old_node;
298 }
299 else {
300 old->node.node_p = new_left;
301 new->node.leaf_p = new_rght;
302 new->node.branches.b[EB_LEFT] = old_node;
303 new->node.branches.b[EB_RGHT] = new_leaf;
304 }
305 break;
306 }
307
308 /* walk down */
309 root = &old->node.branches;
310 side = (((unsigned char *)new->key)[old_node_bit >> 3] >> (~old_node_bit & 7)) & 1;
311 troot = root->b[side];
312 }
313
314 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
315 * parent is already set to <new>, and the <root>'s branch is still in
316 * <side>. Update the root's leaf till we have it. Note that we can also
317 * find the side by checking the side of new->node.node_p.
318 */
319
320 /* We need the common higher bits between new->key and old->key.
321 * This number of bits is already in <bit>.
322 * NOTE: we can't get here whit bit < 0 since we found a dup !
323 */
324 new->node.bit = bit;
325 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
326 return new;
327 }
328
329 #endif /* _EBISTREE_H */
330