1 /*
2 * Elastic Binary Trees - macros and structures for operations on 64bit 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 _EB64TREE_H
22 #define _EB64TREE_H
23
24 #include "ebtree.h"
25
26
27 /* Return the structure of type <type> whose member <member> points to <ptr> */
28 #define eb64_entry(ptr, type, member) container_of(ptr, type, member)
29
30 #define EB64_ROOT EB_ROOT
31 #define EB64_TREE_HEAD EB_TREE_HEAD
32
33 /* These types may sometimes already be defined */
34 typedef unsigned long long u64;
35 typedef signed long long s64;
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 * In case sizeof(void*)>=sizeof(u64), we know there will be some padding after
42 * the key if it's unaligned. In this case we force the alignment on void* so
43 * that we prefer to have the padding before for more efficient accesses.
44 */
45 struct eb64_node {
46 struct eb_node node; /* the tree node, must be at the beginning */
47 MAYBE_ALIGN(sizeof(u64));
48 ALWAYS_ALIGN(sizeof(void*));
49 u64 key;
50 } ALIGNED(sizeof(void*));
51
52 /*
53 * Exported functions and macros.
54 * Many of them are always inlined because they are extremely small, and
55 * are generally called at most once or twice in a program.
56 */
57
58 /* Return leftmost node in the tree, or NULL if none */
eb64_first(struct eb_root * root)59 static inline struct eb64_node *eb64_first(struct eb_root *root)
60 {
61 return eb64_entry(eb_first(root), struct eb64_node, node);
62 }
63
64 /* Return rightmost node in the tree, or NULL if none */
eb64_last(struct eb_root * root)65 static inline struct eb64_node *eb64_last(struct eb_root *root)
66 {
67 return eb64_entry(eb_last(root), struct eb64_node, node);
68 }
69
70 /* Return next node in the tree, or NULL if none */
eb64_next(struct eb64_node * eb64)71 static inline struct eb64_node *eb64_next(struct eb64_node *eb64)
72 {
73 return eb64_entry(eb_next(&eb64->node), struct eb64_node, node);
74 }
75
76 /* Return previous node in the tree, or NULL if none */
eb64_prev(struct eb64_node * eb64)77 static inline struct eb64_node *eb64_prev(struct eb64_node *eb64)
78 {
79 return eb64_entry(eb_prev(&eb64->node), struct eb64_node, node);
80 }
81
82 /* Return next leaf node within a duplicate sub-tree, or NULL if none. */
eb64_next_dup(struct eb64_node * eb64)83 static inline struct eb64_node *eb64_next_dup(struct eb64_node *eb64)
84 {
85 return eb64_entry(eb_next_dup(&eb64->node), struct eb64_node, node);
86 }
87
88 /* Return previous leaf node within a duplicate sub-tree, or NULL if none. */
eb64_prev_dup(struct eb64_node * eb64)89 static inline struct eb64_node *eb64_prev_dup(struct eb64_node *eb64)
90 {
91 return eb64_entry(eb_prev_dup(&eb64->node), struct eb64_node, node);
92 }
93
94 /* Return next node in the tree, skipping duplicates, or NULL if none */
eb64_next_unique(struct eb64_node * eb64)95 static inline struct eb64_node *eb64_next_unique(struct eb64_node *eb64)
96 {
97 return eb64_entry(eb_next_unique(&eb64->node), struct eb64_node, node);
98 }
99
100 /* Return previous node in the tree, skipping duplicates, or NULL if none */
eb64_prev_unique(struct eb64_node * eb64)101 static inline struct eb64_node *eb64_prev_unique(struct eb64_node *eb64)
102 {
103 return eb64_entry(eb_prev_unique(&eb64->node), struct eb64_node, node);
104 }
105
106 /* Delete node from the tree if it was linked in. Mark the node unused. Note
107 * that this function relies on a non-inlined generic function: eb_delete.
108 */
eb64_delete(struct eb64_node * eb64)109 static inline void eb64_delete(struct eb64_node *eb64)
110 {
111 eb_delete(&eb64->node);
112 }
113
114 /*
115 * The following functions are not inlined by default. They are declared
116 * in eb64tree.c, which simply relies on their inline version.
117 */
118 struct eb64_node *eb64_lookup(struct eb_root *root, u64 x);
119 struct eb64_node *eb64i_lookup(struct eb_root *root, s64 x);
120 struct eb64_node *eb64_lookup_le(struct eb_root *root, u64 x);
121 struct eb64_node *eb64_lookup_ge(struct eb_root *root, u64 x);
122 struct eb64_node *eb64_insert(struct eb_root *root, struct eb64_node *new);
123 struct eb64_node *eb64i_insert(struct eb_root *root, struct eb64_node *new);
124
125 /*
126 * The following functions are less likely to be used directly, because their
127 * code is larger. The non-inlined version is preferred.
128 */
129
130 /* Delete node from the tree if it was linked in. Mark the node unused. */
__eb64_delete(struct eb64_node * eb64)131 static forceinline void __eb64_delete(struct eb64_node *eb64)
132 {
133 __eb_delete(&eb64->node);
134 }
135
136 /*
137 * Find the first occurrence of a key in the tree <root>. If none can be
138 * found, return NULL.
139 */
__eb64_lookup(struct eb_root * root,u64 x)140 static forceinline struct eb64_node *__eb64_lookup(struct eb_root *root, u64 x)
141 {
142 struct eb64_node *node;
143 eb_troot_t *troot;
144 u64 y;
145
146 troot = root->b[EB_LEFT];
147 if (unlikely(troot == NULL))
148 return NULL;
149
150 while (1) {
151 if ((eb_gettag(troot) == EB_LEAF)) {
152 node = container_of(eb_untag(troot, EB_LEAF),
153 struct eb64_node, node.branches);
154 if (node->key == x)
155 return node;
156 else
157 return NULL;
158 }
159 node = container_of(eb_untag(troot, EB_NODE),
160 struct eb64_node, node.branches);
161
162 y = node->key ^ x;
163 if (!y) {
164 /* Either we found the node which holds the key, or
165 * we have a dup tree. In the later case, we have to
166 * walk it down left to get the first entry.
167 */
168 if (node->node.bit < 0) {
169 troot = node->node.branches.b[EB_LEFT];
170 while (eb_gettag(troot) != EB_LEAF)
171 troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
172 node = container_of(eb_untag(troot, EB_LEAF),
173 struct eb64_node, node.branches);
174 }
175 return node;
176 }
177
178 if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
179 return NULL; /* no more common bits */
180
181 troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
182 }
183 }
184
185 /*
186 * Find the first occurrence of a signed key in the tree <root>. If none can
187 * be found, return NULL.
188 */
__eb64i_lookup(struct eb_root * root,s64 x)189 static forceinline struct eb64_node *__eb64i_lookup(struct eb_root *root, s64 x)
190 {
191 struct eb64_node *node;
192 eb_troot_t *troot;
193 u64 key = x ^ (1ULL << 63);
194 u64 y;
195
196 troot = root->b[EB_LEFT];
197 if (unlikely(troot == NULL))
198 return NULL;
199
200 while (1) {
201 if ((eb_gettag(troot) == EB_LEAF)) {
202 node = container_of(eb_untag(troot, EB_LEAF),
203 struct eb64_node, node.branches);
204 if (node->key == (u64)x)
205 return node;
206 else
207 return NULL;
208 }
209 node = container_of(eb_untag(troot, EB_NODE),
210 struct eb64_node, node.branches);
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->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 eb64_node, node.branches);
224 }
225 return node;
226 }
227
228 if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
229 return NULL; /* no more common bits */
230
231 troot = node->node.branches.b[(key >> node->node.bit) & EB_NODE_BRANCH_MASK];
232 }
233 }
234
235 /* Insert eb64_node <new> into subtree starting at node root <root>.
236 * Only new->key needs be set with the key. The eb64_node is returned.
237 * If root->b[EB_RGHT]==1, the tree may only contain unique keys.
238 */
239 static forceinline struct eb64_node *
__eb64_insert(struct eb_root * root,struct eb64_node * new)240 __eb64_insert(struct eb_root *root, struct eb64_node *new) {
241 struct eb64_node *old;
242 unsigned int side;
243 eb_troot_t *troot;
244 u64 newkey; /* caching the key saves approximately one cycle */
245 eb_troot_t *root_right;
246 int old_node_bit;
247
248 side = EB_LEFT;
249 troot = root->b[EB_LEFT];
250 root_right = root->b[EB_RGHT];
251 if (unlikely(troot == NULL)) {
252 /* Tree is empty, insert the leaf part below the left branch */
253 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
254 new->node.leaf_p = eb_dotag(root, EB_LEFT);
255 new->node.node_p = NULL; /* node part unused */
256 return new;
257 }
258
259 /* The tree descent is fairly easy :
260 * - first, check if we have reached a leaf node
261 * - second, check if we have gone too far
262 * - third, reiterate
263 * Everywhere, we use <new> for the node node we are inserting, <root>
264 * for the node we attach it to, and <old> for the node we are
265 * displacing below <new>. <troot> will always point to the future node
266 * (tagged with its type). <side> carries the side the node <new> is
267 * attached to below its parent, which is also where previous node
268 * was attached. <newkey> carries the key being inserted.
269 */
270 newkey = new->key;
271
272 while (1) {
273 if (unlikely(eb_gettag(troot) == EB_LEAF)) {
274 eb_troot_t *new_left, *new_rght;
275 eb_troot_t *new_leaf, *old_leaf;
276
277 old = container_of(eb_untag(troot, EB_LEAF),
278 struct eb64_node, node.branches);
279
280 new_left = eb_dotag(&new->node.branches, EB_LEFT);
281 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
282 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
283 old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
284
285 new->node.node_p = old->node.leaf_p;
286
287 /* Right here, we have 3 possibilities :
288 - the tree does not contain the key, and we have
289 new->key < old->key. We insert new above old, on
290 the left ;
291
292 - the tree does not contain the key, and we have
293 new->key > old->key. We insert new above old, on
294 the right ;
295
296 - the tree does contain the key, which implies it
297 is alone. We add the new key next to it as a
298 first duplicate.
299
300 The last two cases can easily be partially merged.
301 */
302
303 if (new->key < old->key) {
304 new->node.leaf_p = new_left;
305 old->node.leaf_p = new_rght;
306 new->node.branches.b[EB_LEFT] = new_leaf;
307 new->node.branches.b[EB_RGHT] = old_leaf;
308 } else {
309 /* we may refuse to duplicate this key if the tree is
310 * tagged as containing only unique keys.
311 */
312 if ((new->key == old->key) && eb_gettag(root_right))
313 return old;
314
315 /* new->key >= old->key, new goes the right */
316 old->node.leaf_p = new_left;
317 new->node.leaf_p = new_rght;
318 new->node.branches.b[EB_LEFT] = old_leaf;
319 new->node.branches.b[EB_RGHT] = new_leaf;
320
321 if (new->key == old->key) {
322 new->node.bit = -1;
323 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
324 return new;
325 }
326 }
327 break;
328 }
329
330 /* OK we're walking down this link */
331 old = container_of(eb_untag(troot, EB_NODE),
332 struct eb64_node, node.branches);
333 old_node_bit = old->node.bit;
334
335 /* Stop going down when we don't have common bits anymore. We
336 * also stop in front of a duplicates tree because it means we
337 * have to insert above.
338 */
339
340 if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
341 (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
342 /* The tree did not contain the key, so we insert <new> before the node
343 * <old>, and set ->bit to designate the lowest bit position in <new>
344 * which applies to ->branches.b[].
345 */
346 eb_troot_t *new_left, *new_rght;
347 eb_troot_t *new_leaf, *old_node;
348
349 new_left = eb_dotag(&new->node.branches, EB_LEFT);
350 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
351 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
352 old_node = eb_dotag(&old->node.branches, EB_NODE);
353
354 new->node.node_p = old->node.node_p;
355
356 if (new->key < old->key) {
357 new->node.leaf_p = new_left;
358 old->node.node_p = new_rght;
359 new->node.branches.b[EB_LEFT] = new_leaf;
360 new->node.branches.b[EB_RGHT] = old_node;
361 }
362 else if (new->key > old->key) {
363 old->node.node_p = new_left;
364 new->node.leaf_p = new_rght;
365 new->node.branches.b[EB_LEFT] = old_node;
366 new->node.branches.b[EB_RGHT] = new_leaf;
367 }
368 else {
369 struct eb_node *ret;
370 ret = eb_insert_dup(&old->node, &new->node);
371 return container_of(ret, struct eb64_node, node);
372 }
373 break;
374 }
375
376 /* walk down */
377 root = &old->node.branches;
378
379 if (sizeof(long) >= 8) {
380 side = newkey >> old_node_bit;
381 } else {
382 /* note: provides the best code on low-register count archs
383 * such as i386.
384 */
385 side = newkey;
386 side >>= old_node_bit;
387 if (old_node_bit >= 32) {
388 side = newkey >> 32;
389 side >>= old_node_bit & 0x1F;
390 }
391 }
392 side &= EB_NODE_BRANCH_MASK;
393 troot = root->b[side];
394 }
395
396 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
397 * parent is already set to <new>, and the <root>'s branch is still in
398 * <side>. Update the root's leaf till we have it. Note that we can also
399 * find the side by checking the side of new->node.node_p.
400 */
401
402 /* We need the common higher bits between new->key and old->key.
403 * What differences are there between new->key and the node here ?
404 * NOTE that bit(new) is always < bit(root) because highest
405 * bit of new->key and old->key are identical here (otherwise they
406 * would sit on different branches).
407 */
408 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
409 new->node.bit = fls64(new->key ^ old->key) - EB_NODE_BITS;
410 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
411
412 return new;
413 }
414
415 /* Insert eb64_node <new> into subtree starting at node root <root>, using
416 * signed keys. Only new->key needs be set with the key. The eb64_node
417 * is returned. If root->b[EB_RGHT]==1, the tree may only contain unique keys.
418 */
419 static forceinline struct eb64_node *
__eb64i_insert(struct eb_root * root,struct eb64_node * new)420 __eb64i_insert(struct eb_root *root, struct eb64_node *new) {
421 struct eb64_node *old;
422 unsigned int side;
423 eb_troot_t *troot;
424 u64 newkey; /* caching the key saves approximately one cycle */
425 eb_troot_t *root_right;
426 int old_node_bit;
427
428 side = EB_LEFT;
429 troot = root->b[EB_LEFT];
430 root_right = root->b[EB_RGHT];
431 if (unlikely(troot == NULL)) {
432 /* Tree is empty, insert the leaf part below the left branch */
433 root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
434 new->node.leaf_p = eb_dotag(root, EB_LEFT);
435 new->node.node_p = NULL; /* node part unused */
436 return new;
437 }
438
439 /* The tree descent is fairly easy :
440 * - first, check if we have reached a leaf node
441 * - second, check if we have gone too far
442 * - third, reiterate
443 * Everywhere, we use <new> for the node node we are inserting, <root>
444 * for the node we attach it to, and <old> for the node we are
445 * displacing below <new>. <troot> will always point to the future node
446 * (tagged with its type). <side> carries the side the node <new> is
447 * attached to below its parent, which is also where previous node
448 * was attached. <newkey> carries a high bit shift of the key being
449 * inserted in order to have negative keys stored before positive
450 * ones.
451 */
452 newkey = new->key ^ (1ULL << 63);
453
454 while (1) {
455 if (unlikely(eb_gettag(troot) == EB_LEAF)) {
456 eb_troot_t *new_left, *new_rght;
457 eb_troot_t *new_leaf, *old_leaf;
458
459 old = container_of(eb_untag(troot, EB_LEAF),
460 struct eb64_node, node.branches);
461
462 new_left = eb_dotag(&new->node.branches, EB_LEFT);
463 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
464 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
465 old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
466
467 new->node.node_p = old->node.leaf_p;
468
469 /* Right here, we have 3 possibilities :
470 - the tree does not contain the key, and we have
471 new->key < old->key. We insert new above old, on
472 the left ;
473
474 - the tree does not contain the key, and we have
475 new->key > old->key. We insert new above old, on
476 the right ;
477
478 - the tree does contain the key, which implies it
479 is alone. We add the new key next to it as a
480 first duplicate.
481
482 The last two cases can easily be partially merged.
483 */
484
485 if ((s64)new->key < (s64)old->key) {
486 new->node.leaf_p = new_left;
487 old->node.leaf_p = new_rght;
488 new->node.branches.b[EB_LEFT] = new_leaf;
489 new->node.branches.b[EB_RGHT] = old_leaf;
490 } else {
491 /* we may refuse to duplicate this key if the tree is
492 * tagged as containing only unique keys.
493 */
494 if ((new->key == old->key) && eb_gettag(root_right))
495 return old;
496
497 /* new->key >= old->key, new goes the right */
498 old->node.leaf_p = new_left;
499 new->node.leaf_p = new_rght;
500 new->node.branches.b[EB_LEFT] = old_leaf;
501 new->node.branches.b[EB_RGHT] = new_leaf;
502
503 if (new->key == old->key) {
504 new->node.bit = -1;
505 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
506 return new;
507 }
508 }
509 break;
510 }
511
512 /* OK we're walking down this link */
513 old = container_of(eb_untag(troot, EB_NODE),
514 struct eb64_node, node.branches);
515 old_node_bit = old->node.bit;
516
517 /* Stop going down when we don't have common bits anymore. We
518 * also stop in front of a duplicates tree because it means we
519 * have to insert above.
520 */
521
522 if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
523 (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
524 /* The tree did not contain the key, so we insert <new> before the node
525 * <old>, and set ->bit to designate the lowest bit position in <new>
526 * which applies to ->branches.b[].
527 */
528 eb_troot_t *new_left, *new_rght;
529 eb_troot_t *new_leaf, *old_node;
530
531 new_left = eb_dotag(&new->node.branches, EB_LEFT);
532 new_rght = eb_dotag(&new->node.branches, EB_RGHT);
533 new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
534 old_node = eb_dotag(&old->node.branches, EB_NODE);
535
536 new->node.node_p = old->node.node_p;
537
538 if ((s64)new->key < (s64)old->key) {
539 new->node.leaf_p = new_left;
540 old->node.node_p = new_rght;
541 new->node.branches.b[EB_LEFT] = new_leaf;
542 new->node.branches.b[EB_RGHT] = old_node;
543 }
544 else if ((s64)new->key > (s64)old->key) {
545 old->node.node_p = new_left;
546 new->node.leaf_p = new_rght;
547 new->node.branches.b[EB_LEFT] = old_node;
548 new->node.branches.b[EB_RGHT] = new_leaf;
549 }
550 else {
551 struct eb_node *ret;
552 ret = eb_insert_dup(&old->node, &new->node);
553 return container_of(ret, struct eb64_node, node);
554 }
555 break;
556 }
557
558 /* walk down */
559 root = &old->node.branches;
560
561 if (sizeof(long) >= 8) {
562 side = newkey >> old_node_bit;
563 } else {
564 /* note: provides the best code on low-register count archs
565 * such as i386.
566 */
567 side = newkey;
568 side >>= old_node_bit;
569 if (old_node_bit >= 32) {
570 side = newkey >> 32;
571 side >>= old_node_bit & 0x1F;
572 }
573 }
574 side &= EB_NODE_BRANCH_MASK;
575 troot = root->b[side];
576 }
577
578 /* Ok, now we are inserting <new> between <root> and <old>. <old>'s
579 * parent is already set to <new>, and the <root>'s branch is still in
580 * <side>. Update the root's leaf till we have it. Note that we can also
581 * find the side by checking the side of new->node.node_p.
582 */
583
584 /* We need the common higher bits between new->key and old->key.
585 * What differences are there between new->key and the node here ?
586 * NOTE that bit(new) is always < bit(root) because highest
587 * bit of new->key and old->key are identical here (otherwise they
588 * would sit on different branches).
589 */
590 // note that if EB_NODE_BITS > 1, we should check that it's still >= 0
591 new->node.bit = fls64(new->key ^ old->key) - EB_NODE_BITS;
592 root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
593
594 return new;
595 }
596
597 #endif /* _EB64_TREE_H */
598