blob: 7c375e7ab3e38ea925dab1156a7b6bb6f63c7959 [file] [log] [blame]
Willy Tarreaube384c62007-04-28 14:00:17 +02001/*
2 * tree.h : tree manipulation macros and structures.
3 * (C) 2002 - Willy Tarreau - willy@ant-computing.com
4 *
5 */
6
7#ifndef __TREE_H__
8#define __TREE_H__
9
10#include <import/bitops.h>
11#include <common/memory.h>
12
13/* binary tree node : either 32 bits unsigned long int values, or
14 * 64 bits in two 32 bits unsigned long int values
15 */
16struct ultree {
17 unsigned long low; /* 32 bits low value of this node */
18 unsigned long high; /* 32 bits high value of this node, not used in 32 bits */
19 int level; /* bit level of this node */
20 void *data; /* carried data */
21 struct ultree *left, *right; /* children : left and right. NULL = leaf */
22 struct ultree *up; /* parent node. NULL = root */
23};
24
25/* binary tree node : 64 bits unsigned long long values */
26struct ulltree {
27 unsigned long long value; /* 64 bits value of this node */
28 int level; /* bit level of this node */
29 void *data; /* carried data */
30 struct ulltree *left, *right; /* children : left and right. NULL = leaf */
31 struct ulltree *up; /* parent node. NULL = root */
32};
33
34/* binary tree node : 64 bits in either one ull or two 32 bits unsigned long int values. This
35 * is the common type for all the above trees, which should be cast into it. This makes
36 * pool_free() far simpler since all types share a same pool.
37 */
38struct tree64 {
39 union {
40 struct {
41 unsigned long low; /* 32 bits low value of this node */
42 unsigned long high; /* 32 bits high value of this node */
43 } ul;
44 struct {
45 unsigned long long value; /* 64 bits value of this node */
46 } ull;
47 } value;
48 int level; /* bit level of this node */
49 void *data; /* carried data */
50 struct tree64 *left, *right; /* children : left and right. NULL = leaf */
51 struct tree64 *up; /* parent node. NULL = root */
52};
53
54#define sizeof_tree64 (sizeof (struct tree64))
55extern void **pool_tree64;
56
Willy Tarreaube384c62007-04-28 14:00:17 +020057#define ULTREE_HEAD(l) struct ultree (l) = { .left=NULL, .right=NULL, .up=NULL, .low=0, .level=LONGBITS, .data=NULL }
58#define ULTREE_INIT(l) { (l)->data = (l)->left = (l)->right = NULL; }
59#define ULTREE_INIT_ROOT(l) { (l)->left=(l)->right=(l)->up=(l)->data=NULL; (l)->low=0; (l)->level=LONGBITS; }
60
61#define ULLTREE_HEAD(l) struct ulltree (l) = { .left=NULL, .right=NULL, .up=NULL, .value=0, .level=LLONGBITS, .data=NULL }
62#define ULLTREE_INIT(l) { (l)->data = (l)->left = (l)->right = NULL; }
63#define ULLTREE_INIT_ROOT(l) { (l)->left=(l)->right=(l)->up=(l)->data=NULL; (l)->value=0; (l)->level=LLONGBITS; }
64
65#define UL2TREE_HEAD(l) struct ultree (l) = { .left=NULL, .right=NULL, .up=NULL, .high=0, .low=0, .level=LLONGBITS, .data=NULL }
66#define UL2TREE_INIT(l) { (l)->left = (l)->right = (l)->data = NULL; }
67#define UL2TREE_INIT_ROOT(l) { (l)->left=(l)->right=(l)->up=(l)->data=NULL; (l)->high=(l)->low=0; (l)->level=LLONGBITS; }
68
69/*
70 * inserts necessary nodes to reach <x> in tree starting at <root>. The node
71 * is not created if it exists. It is returned.
72 */
73inline static struct ulltree *__ulltree_insert(struct ulltree *root, unsigned long long x) {
74 int m;
75 struct ulltree *next, *new, *node;
76 struct ulltree **branch;
77 int ffs;
78
79 next = root;
80 ffs = ffs_fast64(x);
81
82 do {
83 root = next;
84
85 if (x == next->value) {
86 return next;
87 }
88
89 if (x & (1ULL << (next->level - 1))) { /* right branch */
90 branch = &next->right;
91 next = *branch;
92 } else {
93 branch = &next->left;
94 next = *branch;
95 }
96
97 if (next == NULL) {
98 /* we'll have to insert our node here */
99 *branch = new = (struct ulltree *)pool_alloc(tree64);
100 ULLTREE_INIT(new);
101 new->up = root;
102 new->value = x;
103 new->level = ffs;
104 return new;
105 }
106
107 /* we'll keep walking down as long as we have all bits in common */
108 } while ((x & ~((1ULL << next->level) - 1)) == next->value);
109
110
111 /* ok, now we know that we must insert between both. */
112
113 /* the new interconnect node */
114 *branch = node = (struct ulltree *)pool_alloc(tree64); /* was <next> */
115 ULLTREE_INIT(node);
116 node->up = root;
117 next->up = node;
118
119 /* we need the common higher bits between x and next->value. */
120
121 /* what differences are there between x and the node here ?
122 * NOTE that m is always < level(parent) because highest bit
123 * of x and next-value are identical here (else they would be
124 * on a different branch).
125 */
126 m = fls_fast64(x ^ next->value) + 1; /* m = lowest identical bit */
127 node->value = x & ~((1ULL << m) - 1); /* value of common bits */
128
129 if (node->value == x) { /* <x> is exactly on this node */
130 /* we must set its real position (eg: 8,10 => m=1 => val=8, m=3)*/
131 node->level = ffs;
132
133 if (next->value & (1ULL << (node->level - 1))) /* right branch */
134 node->right = next;
135 else
136 node->left = next;
137 return node;
138 }
139
140 /* the new leaf now */
141 node->level = m; /* set the level to the lowest common bit */
142 new = (struct ulltree *)pool_alloc(tree64);
143 ULLTREE_INIT(new);
144 new->value = x;
145 new->level = ffs;
146
147 if (x > next->value) {
148 node->left = next;
149 node->right = new;
150 }
151 else {
152 node->left = new;
153 node->right = next;
154 }
155 new->up = node;
156 return new;
157}
158
159/*
160 * inserts necessary nodes to reach <x> in tree starting at <root>. The node
161 * is not created if it exists. It is returned.
162 */
163inline static struct ultree *__ultree_insert(struct ultree *root, unsigned long x) {
164 int m;
165 struct ultree *next, *new, *node;
166 struct ultree **branch;
167 int ffs;
168
169 next = root;
170 ffs = ffs_fast32(x);
171
172 do {
173 root = next;
174
175 if (x == next->low) {
176 return next;
177 }
178
179 if ((x >> (next->level - 1)) & 1) { /* right branch */
180 branch = &next->right;
181 next = *branch;
182 } else {
183 branch = &next->left;
184 next = *branch;
185 }
186
187 if (next == NULL) {
188 /* we'll have to insert our node here */
189 *branch = new = (struct ultree *)pool_alloc(tree64);
190 ULTREE_INIT(new);
191 new->up = root;
192 new->low = x;
193 new->level = ffs;
194 return new;
195 }
196
197 /* we'll keep walking down as long as we have all bits in common */
198 } while ((x & ~((1 << next->level) - 1)) == next->low);
199
200 /* ok, now we know that we must insert between both. */
201
202 /* the new interconnect node */
203 *branch = node = (struct ultree *)pool_alloc(tree64); /* was <next> */
204 ULTREE_INIT(node);
205 node->up = root;
206 next->up = node;
207
208 /* we need the common higher bits between x and next->low. */
209
210 /* what differences are there between x and the node here ?
211 * NOTE that m is always < level(parent) because highest bit
212 * of x and next->low are identical here (else they would be
213 * on a different branch).
214 */
215 m = fls_fast32(x ^ next->low) + 1; /* m = lower identical bit */
216 node->low = x & ~((1 << m) - 1); /* value of common bits */
217
218 if (node->low == x) { /* <x> is exactly on this node */
219 /* we must set its real position (eg: 8,10 => m=1 => val=8, m=3)*/
220 node->level = ffs;
221
222 if (next->low & (1 << (node->level - 1))) /* right branch */
223 node->right = next;
224 else
225 node->left = next;
226 return node;
227 }
228
229 /* the new leaf now */
230 node->level = m; /* set the level to the lowest common bit */
231 new = (struct ultree *)pool_alloc(tree64);
232 ULTREE_INIT(new);
233 new->low = x;
234 new->level = ffs;
235
236 if (x > next->low) {
237 node->left = next;
238 node->right = new;
239 }
240 else {
241 node->left = new;
242 node->right = next;
243 }
244 new->up = node;
245 return new;
246}
247
248
249/*
250 * inserts necessary nodes to reach <h:l> in tree starting at <root>. The node
251 * is not created if it exists. It is returned.
252 */
253inline static struct ultree *__ul2tree_insert(struct ultree *root, unsigned long h, unsigned long l) {
254 int m;
255 struct ultree *next, *new, *node;
256 struct ultree **branch;
257
258 next = root;
259
260 do {
261 root = next;
262
263 if (h == next->high && l == next->low) {
264 return next;
265 }
266
267 branch = &next->left;
268 if (next->level >= 33) {
269 if ((h >> (next->level - 33)) & 1) { /* right branch */
270 branch = &next->right;
Willy Tarreaube384c62007-04-28 14:00:17 +0200271 }
272 }
273 else {
274 if ((l >> (next->level - 1)) & 1) { /* right branch */
275 branch = &next->right;
Willy Tarreaube384c62007-04-28 14:00:17 +0200276 }
277 }
278 next = *branch;
279
Willy Tarreaube384c62007-04-28 14:00:17 +0200280 if (next == NULL) {
281 /* we'll have to insert our node here */
282 *branch = new =(struct ultree *)pool_alloc(tree64);
283 UL2TREE_INIT(new);
284 new->up = root;
285 new->high = h;
286 new->low = l;
287 if (l)
288 new->level = __ffs_fast32(l);
289 else
290 new->level = __ffs_fast32(h) + 32;
291
292 return new;
293 }
294
295 /* we'll keep walking down as long as we have all bits in common */
296 if (next->level >= 32) {
297 if ((h & ~((1 << (next->level-32)) - 1)) != next->high)
298 break;
299 }
300 else {
301 if (h != next->high)
302 break;
303 if ((l & ~((1 << next->level) - 1)) != next->low)
304 break;
305 }
306 } while (1);
307
308 /* ok, now we know that we must insert between both. */
309
310 /* the new interconnect node */
311 *branch = node = (struct ultree *)pool_alloc(tree64); /* was <next> */
312 UL2TREE_INIT(node);
313 node->up = root;
314 next->up = node;
315
316 /* we need the common higher bits between x and next->high:low. */
317
318 /* what differences are there between x and the node here ?
319 * NOTE that m is always < level(parent) because highest bit
320 * of x and next->high:low are identical here (else they would be
321 * on a different branch).
322 */
323 if (h != next->high) {
324 m = fls_fast32(h ^ next->high) + 1; /* m = lower identical bit */
325 node->high = h & ~((1 << m) - 1); /* value of common bits */
326 m += 32;
327 node->low = 0;
328 } else {
329 node->high = h;
330 m = fls_fast32(l ^ next->low) + 1; /* m = lower identical bit */
331 node->low = l & ~((1 << m) - 1); /* value of common bits */
332 }
333
334 if (node->high == h && node->low == l) { /* <h:l> is exactly on this node */
335 /* we must set its real position (eg: 8,10 => m=1 => val=8, m=3)*/
336 if (l) {
337 node->level = ffs_fast32(l);
338 if (next->low & (1 << (node->level - 1))) /* right branch */
339 node->right = next;
340 else
341 node->left = next;
342 }
343 else {
344 node->level = ffs_fast32(h) + 32;
345 if (next->high & (1 << (node->level - 33))) /* right branch */
346 node->right = next;
347 else
348 node->left = next;
349 }
350 return node;
351 }
352
353 /* the new leaf now */
354 node->level = m; /* set the level to the lowest common bit */
355 new = (struct ultree *)pool_alloc(tree64);
356 UL2TREE_INIT(new);
357 new->high = h;
358 new->low = l;
359 if (l)
360 new->level = __ffs_fast32(l);
361 else
362 new->level = __ffs_fast32(h) + 32;
363
364 if (h > next->high || (h == next->high && l > next->low)) {
365 node->left = next;
366 node->right = new;
367 }
368 else {
369 node->left = new;
370 node->right = next;
371 }
372 new->up = node;
373 return new;
374}
375
376
377/*
378 * finds a value in the tree <root>. If it cannot be found, NULL is returned.
379 */
380inline static struct ultree *__ultree_find(struct ultree *root, unsigned long x) {
381 do {
382 if (x == root->low)
383 return root;
384
385 if ((x >> (root->level - 1)) & 1)
386 root = root->right;
387 else
388 root = root->left;
389
390 if (root == NULL)
391 return NULL;
392
393 /* we'll keep walking down as long as we have all bits in common */
394 } while ((x & ~((1 << root->level) - 1)) == root->low);
395
396 /* should be there, but nothing. */
397 return NULL;
398}
399
400/*
401 * finds a value in the tree <root>. If it cannot be found, NULL is returned.
402 */
403inline static struct ulltree *__ulltree_find(struct ulltree *root, unsigned long long x) {
404 do {
405 if (x == root->value)
406 return root;
407
408 if ((x >> (root->level - 1)) & 1)
409 root = root->right;
410 else
411 root = root->left;
412
413 if (root == NULL)
414 return NULL;
415
416 /* we'll keep walking down as long as we have all bits in common */
417 } while ((x & ~((1ULL << root->level) - 1)) == root->value);
418
419 /* should be there, but nothing. */
420 return NULL;
421}
422
423
424/*
425 * walks down the tree <__root> and assigns each of its data to <__data>.
426 * <__stack> is an int array of at least N entries where N is the maximum number
427 * of levels of the tree. <__slen> is an integer variable used as a stack index.
428 * The instruction following the foreach statement is executed for each data,
429 * after the data has been unlinked from the tree.
430 * The nodes are deleted automatically, so it is illegal to manually delete a
431 * node within this loop.
432 */
433#define tree64_foreach_destructive(__root, __data, __stack, __slen) \
434 for (__slen = 0, __stack[0] = __root, __data = NULL; ({ \
435 __label__ __left, __right, __again, __end; \
436 typeof(__root) __ptr = __stack[__slen]; \
437__again: \
438 __data = __ptr->data; \
439 if (__data != NULL) { \
440 __ptr->data = NULL; \
441 goto __end; \
442 } \
443 else if (__ptr->left != NULL) { \
444 __stack[++__slen] = __ptr = __ptr->left; \
445 goto __again; \
446 } \
447 else \
448__left: \
449 if (__ptr->right != NULL) { \
450 __stack[++__slen] = __ptr = __ptr->right; \
451 goto __again; \
452 } \
453 else \
454__right: \
455 if (!__slen--) \
456 goto __end; /* nothing left, don't delete the root node */ \
457 else { \
458 typeof (__root) __old; \
459 pool_free(tree64, __ptr); \
460 __old = __ptr; \
461 __ptr = __stack[__slen]; \
462 if (__ptr->left == __old) { \
463 /* unlink this node from its parent */ \
464 __ptr->left = NULL; \
465 goto __left; \
466 } \
467 else { \
468 /* no need to unlink, the parent will also die */ \
469 goto __right; \
470 } \
471 } \
472__end: \
473 (__slen >= 0); /* nothing after loop */}); )
474
475
476/*
477 * walks down the tree <__root> of type <__type> and assigns each of its data
478 * to <__data>. <__stack> is an int array of at least N entries where N is the
479 * maximum number of levels of the tree. <__slen> is an integer variable used
480 * as a stack index. The instruction following the foreach statement is
481 * executed for each data, after the data has been unlinked from the tree.
482 */
483#define tree_foreach_destructive(__type, __root, __data, __stack, __slen) \
484 for (__slen = 0, __stack[0] = __root, __data = NULL; ({ \
485 __label__ __left, __right, __again, __end; \
486 typeof(__root) __ptr = __stack[__slen]; \
487__again: \
488 __data = __ptr->data; \
489 if (__data != NULL) { \
490 __ptr->data = NULL; \
491 goto __end; \
492 } \
493 else if (__ptr->left != NULL) { \
494 __stack[++__slen] = __ptr = __ptr->left; \
495 goto __again; \
496 } \
497 else \
498__left: \
499 if (__ptr->right != NULL) { \
500 __stack[++__slen] = __ptr = __ptr->right; \
501 goto __again; \
502 } \
503 else \
504__right: \
505 if (!__slen--) \
506 goto __end; /* nothing left, don't delete the root node */ \
507 else { \
508 typeof (__root) __old; \
509 pool_free(__type, __ptr); \
510 __old = __ptr; \
511 __ptr = __stack[__slen]; \
512 if (__ptr->left == __old) { \
513 /* unlink this node from its parent */ \
514 __ptr->left = NULL; \
515 goto __left; \
516 } \
517 else { \
518 /* no need to unlink, the parent will also die */ \
519 goto __right; \
520 } \
521 } \
522__end: \
523 (__slen >= 0); /* nothing after loop */}); )
524
525
526/*
527 * walks down the tree <__root> and assigns <__data> a pointer to each of its
528 * data pointers. <__stack> is an int array of at least N entries where N is the
529 * maximum number of levels of the tree. <__slen> is an integer variable used as
530 * a stack index. The instruction following the foreach statement is executed
531 * for each data.
532 * The tree will walk down only when the data field is empty (NULL), so it
533 * allows inner breaks, and will restart without losing items. The nodes data
534 * will be set to NULL after the inner code, or when the inner code does
535 * '__stack[__slen]->data = NULL';
536 * The nodes are deleted automatically, so it is illegal to manually delete a
537 * node within this loop.
538 */
539#define tree64_foreach(__root, __data, __stack, __slen) \
540 for (__slen = 0, __stack[0] = __root, __data = NULL; ({ \
541 __label__ __left, __right, __again, __end; \
542 typeof(__root) __ptr = __stack[__slen]; \
543__again: \
544 if (__ptr->data != NULL) { \
545 __data = __ptr->data; \
546 goto __end; \
547 } \
548 else if (__ptr->left != NULL) { \
549 __stack[++__slen] = __ptr = __ptr->left; \
550 goto __again; \
551 } \
552 else \
553__left: \
554 if (__ptr->right != NULL) { \
555 __stack[++__slen] = __ptr = __ptr->right; \
556 goto __again; \
557 } \
558 else \
559__right: \
560 if (!__slen--) \
561 goto __end; /* nothing left, don't delete the root node */ \
562 else { \
563 typeof (__root) __old; \
564 pool_free(tree64, __ptr); \
565 __old = __ptr; \
566 __ptr = __stack[__slen]; \
567 if (__ptr->left == __old) { \
568 /* unlink this node from its parent */ \
569 __ptr->left = NULL; \
570 goto __left; \
571 } \
572 else { \
573 /* no need to unlink, the parent will also die */ \
574 goto __right; \
575 } \
576 } \
577__end: \
578 (__slen >= 0); }); ((typeof(__root))__stack[__slen])->data = NULL)
579
580
581
582/*
583 * walks down the tree <__root> and assigns <__node> to each of its nodes.
584 * <__stack> is an int array of at least N entries where N is the
585 * maximum number of levels of the tree. <__slen> is an integer variable used as
586 * a stack index. The instruction following the foreach statement is executed
587 * for each node.
588 * The tree will walk down only when the data field is empty (NULL), so it
589 * allows inner breaks, and will restart without losing items. The nodes data
590 * will be set to NULL after the inner code, or when the inner code does
591 * '__node->data = NULL';
592 * The nodes are deleted automatically, so it is illegal to manually delete a
593 * node within this loop.
594 */
595#define tree64_foreach_node(__root, __node, __stack, __slen) \
596 for (__slen = 0, __stack[0] = __root; ({ \
597 __label__ __left, __right, __again, __end; \
598 typeof(__root) __ptr = __stack[__slen]; \
599__again: \
600 if (__ptr->data != NULL) { \
601 __node = __ptr; \
602 goto __end; \
603 } \
604 else if (__ptr->left != NULL) { \
605 __stack[++__slen] = __ptr = __ptr->left; \
606 goto __again; \
607 } \
608 else \
609__left: \
610 if (__ptr->right != NULL) { \
611 __stack[++__slen] = __ptr = __ptr->right; \
612 goto __again; \
613 } \
614 else \
615__right: \
616 if (!__slen--) \
617 goto __end; /* nothing left, don't delete the root node */ \
618 else { \
619 typeof (__root) __old; \
620 pool_free(tree64, __ptr); \
621 __old = __ptr; \
622 __ptr = __stack[__slen]; \
623 if (__ptr->left == __old) { \
624 /* unlink this node from its parent */ \
625 __ptr->left = NULL; \
626 goto __left; \
627 } \
628 else { \
629 /* no need to unlink, the parent will also die */ \
630 goto __right; \
631 } \
632 } \
633__end: \
634 (__slen >= 0); }); ((typeof(__root))__stack[__slen])->data = NULL)
635
636
637/*
638 * removes the current node if possible, and its parent if it doesn't handle
639 * data. A pointer to the parent or grandparent is returned (the parent of the
640 * last one deleted in fact). This function should be compatible with any
641 * tree struct because of the void types.
642 * WARNING : never call it from within a tree_foreach() because this last one
643 * uses a stack which will not be updated.
644 */
645
646inline static void *__tree_delete_only_one(void *firstnode) {
647 struct tree64 *down, **uplink;
648 struct tree64 *node = firstnode;
649
650 /* don't kill the root or a populated link */
651 if (node->data || node->up == NULL)
652 return node;
653 if (node->left && node->right)
654 return node;
655 /* since we know that at least left or right is null, we can do arithmetics on them */
656 down = (void *)((long)node->left | (long)node->right);
657 /* find where we are linked */
658 if (node == node->up->left)
659 uplink = &node->up->left;
660 else
661 uplink = &node->up->right;
662
663 *uplink = down; /* we relink the lower branch above us or simply cut it */
664 if (down) {
665 down->up = node->up;
666 /* we know that we cannot do more because we kept one branch */
667 }
668 else {
669 /* we'll redo this once for the node above us because there was no branch below us,
670 * so maybe it doesn't need to exist for only one branch
671 */
672 down = node;
673 node = node->up;
674 pool_free(tree64, down);
675 if (node->data || node->up == NULL)
676 return node;
677 /* now we're sure we were sharing this empty node with another branch, let's find it */
678 down = (void *)((long)node->left | (long)node->right);
679 if (node == node->up->left)
680 uplink = &node->up->left;
681 else
682 uplink = &node->up->right;
683 *uplink = down; /* we relink the lower branch above */
684 down->up = node->up;
685 }
686 /* free the last node */
687 pool_free(tree64, node);
688 return down->up;
689}
690
691/*
692 * removes the current node if possible, and all of its parents which do not
693 * carry data. A pointer to the parent of the last one deleted is returned.
694 * This function should be compatible with any tree struct because of the void
695 * types.
696 * WARNING : never call it from within a tree_foreach() because this last one
697 * uses a stack which will not be updated.
698 */
699
700inline static void *__tree_delete(void *firstnode) {
701 struct tree64 *down, **uplink, *up;
702 struct tree64 *node = firstnode;
703
704 while (1) {
705 /* don't kill the root or a populated link */
706 if (node->data || (up = node->up) == NULL)
707 return node;
708 if (node->left && node->right)
709 return node;
710 /* since we know that at least left or right is null, we can do arithmetics on them */
711 down = (void *)((long)node->left | (long)node->right);
712 /* find where we are linked */
713 if (node == up->left)
714 uplink = &up->left;
715 else
716 uplink = &up->right;
717
718 *uplink = down; /* we relink the lower branch above us or simply cut it */
719 pool_free(tree64, node);
720 node = up;
721 if (down)
722 down->up = node;
723 }
724}
725
726#endif /* __TREE_H__ */