1 /*
2 * Elastic Binary Trees - macros and structures for operations on 32bit 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 #ifndef _EB32TREE_H
22 #define _EB32TREE_H
23
24 #include "ebtree.h"
25
26
27 /* Return the structure of type <type> whose member <member> points to <ptr> */
28 #define eb32_entry(ptr, type, member) container_of(ptr, type, member)
29
30 #define EB32_ROOT EB_ROOT
31 #define EB32_TREE_HEAD EB_TREE_HEAD
32
33 /* These types may sometimes already be defined */
34 typedef unsigned int u32;
35 typedef signed int s32;
36
37 /* This structure carries a node, a leaf, and a key. It must start with the
38 * eb_node so that it can be cast into an eb_node. We could also have put some
39 * sort of transparent union here to reduce the indirection level, but the fact
40 * is, the end user is not meant to manipulate internals, so this is pointless.
41 */
42 struct eb32_node {
43 struct eb_node node; /* the tree node, must be at the beginning */
44 MAYBE_ALIGN(sizeof(u32));
45 u32 key;
46 } ALIGNED(sizeof(void*));
47
48 /*
49 * Exported functions and macros.
50 * Many of them are always inlined because they are extremely small, and
51 * are generally called at most once or twice in a program.
52 */
53
54 /* Return leftmost node in the tree, or NULL if none */
eb32_first(struct eb_root * root)55 static inline struct eb32_node *eb32_first(struct eb_root *root)
56 {
57 return eb32_entry(eb_first(root), struct eb32_node, node);
58 }
59
60 /* Return rightmost node in the tree, or NULL if none */
eb32_last(struct eb_root * root)61 static inline struct eb32_node *eb32_last(struct eb_root *root)
62 {
63 return eb32_entry(eb_last(root), struct eb32_node, node);
64 }
65
66 /* Return next node in the tree, or NULL if none */
eb32_next(struct eb32_node * eb32)67 static inline struct eb32_node *eb32_next(struct eb32_node *eb32)
68 {
69 return eb32_entry(eb_next(&eb32->node), struct eb32_node, node);
70 }
71
72 /* Return previous node in the tree, or NULL if none */
eb32_prev(struct eb32_node * eb32)73 static inline struct eb32_node *eb32_prev(struct eb32_node *eb32)
74 {
75 return eb32_entry(eb_prev(&eb32->node), struct eb32_node, node);
76 }
77
78 /* Return next leaf node within a duplicate sub-tree, or NULL if none. */
eb32_next_dup(struct eb32_node * eb32)79 static inline struct eb32_node *eb32_next_dup(struct eb32_node *eb32)
80 {
81 return eb32_entry(eb_next_dup(&eb32->node), struct eb32_node, node);
82 }
83
84 /* Return previous leaf node within a duplicate sub-tree, or NULL if none. */
eb32_prev_dup(struct eb32_node * eb32)85 static inline struct eb32_node *eb32_prev_dup(struct eb32_node *eb32)
86 {
87 return eb32_entry(eb_prev_dup(&eb32->node), struct eb32_node, node);
88 }
89
90 /* Return next node in the tree, skipping duplicates, or NULL if none */
eb32_next_unique(struct eb32_node * eb32)91 static inline struct eb32_node *eb32_next_unique(struct eb32_node *eb32)
92 {
93 return eb32_entry(eb_next_unique(&eb32->node), struct eb32_node, node);
94 }
95
96 /* Return previous node in the tree, skipping duplicates, or NULL if none */
eb32_prev_unique(struct eb32_node * eb32)97 static inline struct eb32_node *eb32_prev_unique(struct eb32_node *eb32)
98 {
99 return eb32_entry(eb_prev_unique(&eb32->node), struct eb32_node, node);
100 }
101
102 /* Delete node from the tree if it was linked in. Mark the node unused. Note
103 * that this function relies on a non-inlined generic function: eb_delete.
104 */
eb32_delete(struct eb32_node * eb32)105 static inline void eb32_delete(struct eb32_node *eb32)
106 {
107 eb_delete(&eb32->node);
108 }
109
110 /*
111 * The following functions are not inlined by default. They are declared
112 * in eb32tree.c, which simply relies on their inline version.
113 */
114 REGPRM2 struct eb32_node *eb32_lookup(struct eb_root *root, u32 x);
115 REGPRM2 struct eb32_node *eb32i_lookup(struct eb_root *root, s32 x);
116 REGPRM2 struct eb32_node *eb32_lookup_le(struct eb_root *root, u32 x);
117 REGPRM2 struct eb32_node *eb32_lookup_ge(struct eb_root *root, u32 x);
118 REGPRM2 struct eb32_node *eb32_insert(struct eb_root *root, struct eb32_node *new);
119 REGPRM2 struct eb32_node *eb32i_insert(struct eb_root *root, struct eb32_node *new);
120
121 /*
122 * The following functions are less likely to be used directly, because their
123 * code is larger. The non-inlined version is preferred.
124 */
125
126 /* Delete node from the tree if it was linked in. Mark the node unused. */
__eb32_delete(struct eb32_node * eb32)127 static forceinline void __eb32_delete(struct eb32_node *eb32)
128 {
129 __eb_delete(&eb32->node);
130 }
131
132 /*
133 * Find the first occurence of a key in the tree <root>. If none can be
134 * found, return NULL.
135 */
__eb32_lookup(struct eb_root * root,u32 x)136 static forceinline struct eb32_node *__eb32_lookup(struct eb_root *root, u32 x)
137 {
138 struct eb32_node *node;
139 eb_troot_t *troot;
140 u32 y;
141 int node_bit;
142
143 troot = root->b[EB_LEFT];
144 if (unlikely(troot == NULL))
145 return NULL;
146
147 while (1) {
148 if ((eb_gettag(troot) == EB_LEAF)) {
149 node = container_of(eb_untag(troot, EB_LEAF),
150 struct eb32_node, node.branches);
151 if (node->key == x)
152 return node;
153 else
154 return NULL;
155 }
156 node = container_of(eb_untag(troot, EB_NODE),
157 struct eb32_node, node.branches);
158 node_bit = node->node.bit;
159
160 y = node->key ^ x;
161 if (!y) {
162 /* Either we found the node which holds the key, or
163 * we have a dup tree. In the later case, we have to
164 * walk it down left to get the first entry.
165 */
166 if (node_bit < 0) {
167 troot = node->node.branches.b[EB_LEFT];
168 while (eb_gettag(troot) != EB_LEAF)
169 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
170 node = container_of(eb_untag(troot, EB_LEAF),
171 struct eb32_node, node.branches);
172 }
173 return node;
174 }
175
176 if ((y >> node_bit) >= EB_NODE_BRANCHES)
177 return NULL; /* no more common bits */
178
179 troot = node->node.branches.b[(x >> node_bit) & EB_NODE_BRANCH_MASK];
180 }
181 }
182
183 /*
184 * Find the first occurence of a signed key in the tree <root>. If none can
185 * be found, return NULL.
186 */
__eb32i_lookup(struct eb_root * root,s32 x)187 static forceinline struct eb32_node *__eb32i_lookup(struct eb_root *root, s32 x)
188 {
189 struct eb32_node *node;
190 eb_troot_t *troot;
191 u32 key = x ^ 0x80000000;
192 u32 y;
193 int node_bit;
194
195 troot = root->b[EB_LEFT];
196 if (unlikely(troot == NULL))
197 return NULL;
198
199 while (1) {
200 if ((eb_gettag(troot) == EB_LEAF)) {
201 node = container_of(eb_untag(troot, EB_LEAF),
202 struct eb32_node, node.branches);
203 if (node->key == (u32)x)
204 return node;
205 else
206 return NULL;
207 }
208 node = container_of(eb_untag(troot, EB_NODE),
209 struct eb32_node, node.branches);
210 node_bit = node->node.bit;
211
212 y = node->key ^ x;
213 if (!y) {
214 /* Either we found the node which holds the key, or
215 * we have a dup tree. In the later case, we have to
216 * walk it down left to get the first entry.
217 */
218 if (node_bit < 0) {
219 troot = node->node.branches.b[EB_LEFT];
220 while (eb_gettag(troot) != EB_LEAF)
221 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
222 node = container_of(eb_untag(troot, EB_LEAF),
223 struct eb32_node, node.branches);
224 }
225 return node;
226 }
227
228 if ((y >> node_bit) >= EB_NODE_BRANCHES)
229 return NULL; /* no more common bits */
230
231 troot = node->node.branches.b[(key >> node_bit) & EB_NODE_BRANCH_MASK];
232 }
233 }
234
235 /* Insert eb32_node <new> into subtree starting at node root <root>.
236 * Only new->key needs be set with the key. The eb32_node is returned.
237 * If root->b[EB_RGHT]==1, the tree may only contain unique keys.
238 */
239 static forceinline struct eb32_node *
__eb32_insert(struct eb_root * root,struct eb32_node * new)240 __eb32_insert(struct eb_root *root, struct eb32_node *new) {
241 struct eb32_node *old;
242 unsigned int side;
243 eb_troot_t *troot, **up_ptr;
244 u32 newkey; /* caching the key saves approximately one cycle */
245 eb_troot_t *root_right;
246 eb_troot_t *new_left, *new_rght;
247 eb_troot_t *new_leaf;
248 int old_node_bit;
249
250 side = EB_LEFT;
251 troot = root->b[EB_LEFT];
252 root_right = root->b[EB_RGHT];
253 if (unlikely(troot == NULL)) {
254 /* Tree is empty, insert the leaf part below the left branch */
255 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
256 new->node.leaf_p = eb_dotag(root, EB_LEFT);
257 new->node.node_p = NULL; /* node part unused */
258 return new;
259 }
260
261 /* The tree descent is fairly easy :
262 * - first, check if we have reached a leaf node
263 * - second, check if we have gone too far
264 * - third, reiterate
265 * Everywhere, we use <new> for the node node we are inserting, <root>
266 * for the node we attach it to, and <old> for the node we are
267 * displacing below <new>. <troot> will always point to the future node
268 * (tagged with its type). <side> carries the side the node <new> is
269 * attached to below its parent, which is also where previous node
270 * was attached. <newkey> carries the key being inserted.
271 */
272 newkey = new->key;
273
274 while (1) {
275 if (eb_gettag(troot) == EB_LEAF) {
276 /* insert above a leaf */
277 old = container_of(eb_untag(troot, EB_LEAF),
278 struct eb32_node, node.branches);
279 new->node.node_p = old->node.leaf_p;
280 up_ptr = &old->node.leaf_p;
281 break;
282 }
283
284 /* OK we're walking down this link */
285 old = container_of(eb_untag(troot, EB_NODE),
286 struct eb32_node, node.branches);
287 old_node_bit = old->node.bit;
288
289 /* Stop going down when we don't have common bits anymore. We
290 * also stop in front of a duplicates tree because it means we
291 * have to insert above.
292 */
293
294 if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
295 (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
296 /* The tree did not contain the key, so we insert <new> before the node
297 * <old>, and set ->bit to designate the lowest bit position in <new>
298 * which applies to ->branches.b[].
299 */
300 new->node.node_p = old->node.node_p;
301 up_ptr = &old->node.node_p;
302 break;
303 }
304
305 /* walk down */
306 root = &old->node.branches;
307 side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
308 troot = root->b[side];
309 }
310
311 new_left = eb_dotag(&new->node.branches, EB_LEFT);
312 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
313 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
314
315 /* We need the common higher bits between new->key and old->key.
316 * What differences are there between new->key and the node here ?
317 * NOTE that bit(new) is always < bit(root) because highest
318 * bit of new->key and old->key are identical here (otherwise they
319 * would sit on different branches).
320 */
321
322 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
323 new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;
324
325 if (new->key == old->key) {
326 new->node.bit = -1; /* mark as new dup tree, just in case */
327
328 if (likely(eb_gettag(root_right))) {
329 /* we refuse to duplicate this key if the tree is
330 * tagged as containing only unique keys.
331 */
332 return old;
333 }
334
335 if (eb_gettag(troot) != EB_LEAF) {
336 /* there was already a dup tree below */
337 struct eb_node *ret;
338 ret = eb_insert_dup(&old->node, &new->node);
339 return container_of(ret, struct eb32_node, node);
340 }
341 /* otherwise fall through */
342 }
343
344 if (new->key >= old->key) {
345 new->node.branches.b[EB_LEFT] = troot;
346 new->node.branches.b[EB_RGHT] = new_leaf;
347 new->node.leaf_p = new_rght;
348 *up_ptr = new_left;
349 }
350 else {
351 new->node.branches.b[EB_LEFT] = new_leaf;
352 new->node.branches.b[EB_RGHT] = troot;
353 new->node.leaf_p = new_left;
354 *up_ptr = new_rght;
355 }
356
357 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
358 * parent is already set to <new>, and the <root>'s branch is still in
359 * <side>. Update the root's leaf till we have it. Note that we can also
360 * find the side by checking the side of new->node.node_p.
361 */
362
363 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
364 return new;
365 }
366
367 /* Insert eb32_node <new> into subtree starting at node root <root>, using
368 * signed keys. Only new->key needs be set with the key. The eb32_node
369 * is returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys.
370 */
371 static forceinline struct eb32_node *
__eb32i_insert(struct eb_root * root,struct eb32_node * new)372 __eb32i_insert(struct eb_root *root, struct eb32_node *new) {
373 struct eb32_node *old;
374 unsigned int side;
375 eb_troot_t *troot, **up_ptr;
376 int newkey; /* caching the key saves approximately one cycle */
377 eb_troot_t *root_right;
378 eb_troot_t *new_left, *new_rght;
379 eb_troot_t *new_leaf;
380 int old_node_bit;
381
382 side = EB_LEFT;
383 troot = root->b[EB_LEFT];
384 root_right = root->b[EB_RGHT];
385 if (unlikely(troot == NULL)) {
386 /* Tree is empty, insert the leaf part below the left branch */
387 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
388 new->node.leaf_p = eb_dotag(root, EB_LEFT);
389 new->node.node_p = NULL; /* node part unused */
390 return new;
391 }
392
393 /* The tree descent is fairly easy :
394 * - first, check if we have reached a leaf node
395 * - second, check if we have gone too far
396 * - third, reiterate
397 * Everywhere, we use <new> for the node node we are inserting, <root>
398 * for the node we attach it to, and <old> for the node we are
399 * displacing below <new>. <troot> will always point to the future node
400 * (tagged with its type). <side> carries the side the node <new> is
401 * attached to below its parent, which is also where previous node
402 * was attached. <newkey> carries a high bit shift of the key being
403 * inserted in order to have negative keys stored before positive
404 * ones.
405 */
406 newkey = new->key + 0x80000000;
407
408 while (1) {
409 if (eb_gettag(troot) == EB_LEAF) {
410 old = container_of(eb_untag(troot, EB_LEAF),
411 struct eb32_node, node.branches);
412 new->node.node_p = old->node.leaf_p;
413 up_ptr = &old->node.leaf_p;
414 break;
415 }
416
417 /* OK we're walking down this link */
418 old = container_of(eb_untag(troot, EB_NODE),
419 struct eb32_node, node.branches);
420 old_node_bit = old->node.bit;
421
422 /* Stop going down when we don't have common bits anymore. We
423 * also stop in front of a duplicates tree because it means we
424 * have to insert above.
425 */
426
427 if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
428 (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
429 /* The tree did not contain the key, so we insert <new> before the node
430 * <old>, and set ->bit to designate the lowest bit position in <new>
431 * which applies to ->branches.b[].
432 */
433 new->node.node_p = old->node.node_p;
434 up_ptr = &old->node.node_p;
435 break;
436 }
437
438 /* walk down */
439 root = &old->node.branches;
440 side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
441 troot = root->b[side];
442 }
443
444 new_left = eb_dotag(&new->node.branches, EB_LEFT);
445 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
446 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
447
448 /* We need the common higher bits between new->key and old->key.
449 * What differences are there between new->key and the node here ?
450 * NOTE that bit(new) is always < bit(root) because highest
451 * bit of new->key and old->key are identical here (otherwise they
452 * would sit on different branches).
453 */
454
455 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
456 new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;
457
458 if (new->key == old->key) {
459 new->node.bit = -1; /* mark as new dup tree, just in case */
460
461 if (likely(eb_gettag(root_right))) {
462 /* we refuse to duplicate this key if the tree is
463 * tagged as containing only unique keys.
464 */
465 return old;
466 }
467
468 if (eb_gettag(troot) != EB_LEAF) {
469 /* there was already a dup tree below */
470 struct eb_node *ret;
471 ret = eb_insert_dup(&old->node, &new->node);
472 return container_of(ret, struct eb32_node, node);
473 }
474 /* otherwise fall through */
475 }
476
477 if ((s32)new->key >= (s32)old->key) {
478 new->node.branches.b[EB_LEFT] = troot;
479 new->node.branches.b[EB_RGHT] = new_leaf;
480 new->node.leaf_p = new_rght;
481 *up_ptr = new_left;
482 }
483 else {
484 new->node.branches.b[EB_LEFT] = new_leaf;
485 new->node.branches.b[EB_RGHT] = troot;
486 new->node.leaf_p = new_left;
487 *up_ptr = new_rght;
488 }
489
490 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
491 * parent is already set to <new>, and the <root>'s branch is still in
492 * <side>. Update the root's leaf till we have it. Note that we can also
493 * find the side by checking the side of new->node.node_p.
494 */
495
496 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
497 return new;
498 }
499
500 #endif /* _EB32_TREE_H */
501