4 * (c) 2002, Robert Spalek <robert@ucw.cz>
6 * Skeleton based on hash-tables by:
8 * (c) 2002, Martin Mares <mj@ucw.cz>
13 * Data structure description:
15 * A red-black tree is a binary search tree, where records are stored
16 * in nodes (may be also leaves). Every node has a colour. The
17 * following restrictions hold:
19 * - a parent of a red node is black
20 * - every path from the root to a node with less than 2 children
21 * contains the same number of black nodes
23 * A usual interpretation is, that leaves are intervals between records
24 * and contain no data. Every leaf is black. This is equivalent, but
29 * This is not a normal header file, it's a generator of red-black trees.
30 * Each time you include it with parameters set in the corresponding
31 * preprocessor macros, it generates a tree structure with the parameters
34 * You need to specify:
36 * TREE_NODE data type where a node dwells (usually a struct).
37 * TREE_PREFIX(x) macro to add a name prefix (used on all global names
38 * defined by the tree generator).
40 * Then decide on type of keys:
42 * TREE_KEY_ATOMIC=f use node->f as a key of an atomic type (i.e.,
43 * a type which can be compared using '>', `==', and '<')
44 * & TREE_ATOMIC_TYPE (defaults to int).
45 * | TREE_KEY_STRING=f use node->f as a string key, allocated
46 * separately from the rest of the node.
47 * | TREE_KEY_ENDSTRING=f use node->f as a string key, allocated
48 * automatically at the end of the node struct
49 * (to be declared as "char f[1]" at the end).
50 * | TREE_KEY_COMPLEX use a multi-component key; as the name suggests,
51 * the passing of parameters is a bit complex then.
52 * The TREE_KEY_COMPLEX(x) macro should expand to
53 * `x k1, x k2, ... x kn' and you should also define:
54 * & TREE_KEY_DECL declaration of function parameters in which key
55 * should be passed to all tree operations.
56 * That is, `type1 k1, type2 k2, ... typen kn'.
57 * With complex keys, TREE_GIVE_CMP is mandatory.
59 * Then specify what operations you request (all names are automatically
60 * prefixed by calling TREE_PREFIX):
62 * <always defined> init() -- initialize the tree.
63 * TREE_WANT_CLEANUP cleanup() -- deallocate the tree.
64 * TREE_WANT_FIND node *find(key) -- find first node with the specified
65 * key, return NULL if no such node exists.
66 * TREE_WANT_FIND_NEXT node *find_next(node *start) -- find next node with the
67 * specified key, return NULL if no such node exists.
68 * TREE_WANT_SEARCH node *search(key) -- find the node with the specified
69 * or, if it does not exist, the nearest one.
70 * TREE_WANT_ADJACENT node *adjacent(node *, uns direction) -- finds next
71 * (direction==1) or previous (direction==0) node.
72 * TREE_WANT_NEW node *new(key) -- create new node with given key.
73 * If it already exists, it is created as the last one.
74 * TREE_WANT_LOOKUP node *lookup(key) -- find node with given key,
75 * if it doesn't exist, create it. Defining
76 * TREE_GIVE_INIT_DATA is strongly recommended.
77 * TREE_WANT_DELETE int delete(key) -- delete and deallocate node
78 * with a given key. Returns success.
79 * TREE_WANT_REMOVE remove(node *) -- delete and deallocate given node.
81 * TREE_WANT_DUMP dump() -- dumps the whole tree to stdout
83 * You can also supply several functions:
85 * TREE_GIVE_CMP int cmp(key1, key2) -- return -1, 0, and 1 according to
86 * the relation of keys. By default, we use <, ==, > for
87 * atomic types and either strcmp or strcasecmp for
89 * TREE_GIVE_EXTRA_SIZE int extra_size(key) -- returns how many bytes after the
90 * node should be allocated for dynamic data. Default=0
91 * or length of the string with TREE_KEY_ENDSTRING.
92 * TREE_GIVE_INIT_KEY void init_key(node *,key) -- initialize key in a newly
93 * created node. Defaults: assignment for atomic keys
94 * and static strings, strcpy for end-allocated strings.
95 * TREE_GIVE_INIT_DATA void init_data(node *) -- initialize data fields in a
96 * newly created node. Very useful for lookup operations.
97 * TREE_GIVE_ALLOC void *alloc(unsigned int size) -- allocate space for
98 * a node. Default is either normal or pooled allocation
99 * depending on whether we want deletions.
100 * void free(void *) -- the converse.
102 * ... and a couple of extra parameters:
104 * TREE_NOCASE string comparisons should be case-insensitive.
105 * TREE_ATOMIC_TYPE=t Atomic values are of type `t' instead of int.
106 * TREE_USE_POOL=pool Allocate all nodes from given mempool.
107 * Collides with delete/remove functions.
108 * TREE_GLOBAL Functions are exported (i.e., not static).
109 * TREE_CONSERVE_SPACE Use as little space as possible at the price of a
111 * TREE_MAX_DEPTH Maximal depth of a tree (for stack allocation).
113 * If you set TREE_WANT_ITERATOR, you also get a iterator macro at no
116 * TREE_FOR_ALL(tree_prefix, tree_pointer, variable)
118 * // node *variable gets declared automatically
119 * do_something_with_node(variable);
120 * // use TREE_BREAK and TREE_CONTINUE instead of break and continue
121 * // you must not alter contents of the tree here
125 * Then include "lib/redblack.h" and voila, you have a tree suiting all your
126 * needs (at least those which you've revealed :) ).
128 * After including this file, all parameter macros are automatically
134 #if !defined(TREE_NODE) || !defined(TREE_PREFIX)
135 #error Some of the mandatory configuration macros are missing.
138 #define P(x) TREE_PREFIX(x)
140 /* Declare buckets and the tree. */
142 typedef TREE_NODE P(node);
144 #if defined(TREE_WANT_FIND_NEXT) || defined(TREE_WANT_ADJACENT) || defined(TREE_WANT_ITERATOR) || defined(TREE_WANT_REMOVE)
145 # define TREE_STORE_PARENT
148 typedef struct P(bucket) {
149 struct P(bucket) *son[2];
150 #ifdef TREE_STORE_PARENT
151 struct P(bucket) *parent;
153 #if !defined(TREE_CONSERVE_SPACE) && (defined(TREE_GIVE_EXTRA_SIZE) || defined(TREE_KEY_ENDSTRING))
157 #if !defined(TREE_CONSERVE_SPACE) && !defined(TREE_GIVE_EXTRA_SIZE) && !defined(TREE_KEY_ENDSTRING)
164 uns height; /* of black nodes */
168 typedef struct P(stack_entry) {
173 #define T struct P(tree)
175 /* Preset parameters */
177 #if defined(TREE_KEY_ATOMIC)
179 #define TREE_KEY(x) x TREE_KEY_ATOMIC
181 #ifndef TREE_ATOMIC_TYPE
182 # define TREE_ATOMIC_TYPE int
184 #define TREE_KEY_DECL TREE_ATOMIC_TYPE TREE_KEY()
186 #ifndef TREE_GIVE_CMP
187 # define TREE_GIVE_CMP
188 static inline int P(cmp) (TREE_ATOMIC_TYPE x, TREE_ATOMIC_TYPE y)
199 #ifndef TREE_GIVE_INIT_KEY
200 # define TREE_GIVE_INIT_KEY
201 static inline void P(init_key) (P(node) *n, TREE_ATOMIC_TYPE k)
202 { TREE_KEY(n->) = k; }
205 #elif defined(TREE_KEY_STRING) || defined(TREE_KEY_ENDSTRING)
207 #ifdef TREE_KEY_STRING
208 # define TREE_KEY(x) x TREE_KEY_STRING
209 # ifndef TREE_GIVE_INIT_KEY
210 # define TREE_GIVE_INIT_KEY
211 static inline void P(init_key) (P(node) *n, char *k)
212 { TREE_KEY(n->) = k; }
215 # define TREE_KEY(x) x TREE_KEY_ENDSTRING
216 # define TREE_GIVE_EXTRA_SIZE
217 static inline int P(extra_size) (char *k)
218 { return strlen(k); }
219 # ifndef TREE_GIVE_INIT_KEY
220 # define TREE_GIVE_INIT_KEY
221 static inline void P(init_key) (P(node) *n, char *k)
222 { strcpy(TREE_KEY(n->), k); }
225 #define TREE_KEY_DECL char *TREE_KEY()
227 #ifndef TREE_GIVE_CMP
228 # define TREE_GIVE_CMP
229 static inline int P(cmp) (char *x, char *y)
232 return strcasecmp(x,y);
239 #elif defined(TREE_KEY_COMPLEX)
241 #define TREE_KEY(x) TREE_KEY_COMPLEX(x)
244 #error You forgot to set the tree key type.
247 #ifndef TREE_CONSERVE_SPACE
248 static inline uns P(red_flag) (P(bucket) *node)
249 { return node->red_flag; }
250 static inline void P(set_red_flag) (P(bucket) *node, uns flag)
251 { node->red_flag = flag; }
252 static inline P(bucket) * P(tree_son) (P(bucket) *node, uns id)
253 { return node->son[id]; }
254 static inline void P(set_tree_son) (P(bucket) *node, uns id, P(bucket) *son)
255 { node->son[id] = son; }
257 /* Pointers are aligned, hence we can use lower bits. */
258 static inline uns P(red_flag) (P(bucket) *node)
259 { return ((long) node->son[0]) & 1L; }
260 static inline void P(set_red_flag) (P(bucket) *node, uns flag)
261 { (long) node->son[0] = (((long) node->son[0]) & ~1L) | (flag & 1L); }
262 static inline P(bucket) * P(tree_son) (P(bucket) *node, uns id)
263 { return (void *) (((long) node->son[id]) & ~1L); }
264 static inline void P(set_tree_son) (P(bucket) *node, uns id, P(bucket) *son)
265 { node->son[id] = (void *) ((long) son | (((long) node->son[id]) & 1L) ); }
268 /* Defaults for missing parameters. */
270 #ifndef TREE_GIVE_CMP
271 #error Unable to determine how to compare two keys.
274 #ifdef TREE_GIVE_EXTRA_SIZE
275 /* This trickery is needed to avoid `unused parameter' warnings */
276 # define TREE_EXTRA_SIZE P(extra_size)
279 * Beware, C macros are expanded iteratively, not recursively,
280 * hence we get only a _single_ argument, although the expansion
281 * of TREE_KEY contains commas.
283 # define TREE_EXTRA_SIZE(x) 0
286 #ifndef TREE_GIVE_INIT_KEY
287 # error Unable to determine how to initialize keys.
290 #ifndef TREE_GIVE_INIT_DATA
291 static inline void P(init_data) (P(node) *n UNUSED)
298 #ifndef TREE_GIVE_ALLOC
299 # ifdef TREE_USE_POOL
300 static inline void * P(alloc) (unsigned int size)
301 { return mp_alloc_fast(TREE_USE_POOL, size); }
302 # define TREE_SAFE_FREE(x)
304 static inline void * P(alloc) (unsigned int size)
305 { return xmalloc(size); }
307 static inline void P(free) (void *x)
312 #ifndef TREE_SAFE_FREE
313 # define TREE_SAFE_FREE(x) P(free) (x)
319 # define STATIC static
322 #ifndef TREE_MAX_DEPTH
323 # define TREE_MAX_DEPTH 64
326 /* Now the operations */
328 STATIC void P(init) (T *t)
330 t->count = t->height = 0;
334 #ifdef TREE_WANT_CLEANUP
335 static void P(cleanup_subtree) (T *t, P(bucket) *node)
339 P(cleanup_subtree) (t, P(tree_son) (node, 0));
340 P(cleanup_subtree) (t, P(tree_son) (node, 1));
345 STATIC void P(cleanup) (T *t)
347 P(cleanup_subtree) (t, t->root);
353 static uns P(fill_stack) (P(stack_entry) *stack, uns max_depth, P(bucket) *node, TREE_KEY_DECL, uns son_id UNUSED)
356 stack[0].buck = node;
357 for (i=0; stack[i].buck; i++)
360 cmp = P(cmp) (TREE_KEY(), TREE_KEY(stack[i].buck->n.));
367 ASSERT(i+1 < max_depth);
368 stack[i+1].buck = P(tree_son) (stack[i].buck, stack[i].son);
370 #ifdef TREE_WANT_FIND_NEXT
374 /* Find first/last of equal keys according to son_id. */
375 idx = P(fill_stack) (stack+i+1, max_depth-i-1,
376 P(tree_son) (stack[i].buck, son_id), TREE_KEY(), son_id);
377 if (stack[i+1+idx].buck)
379 stack[i].son = son_id;
388 #if defined(TREE_WANT_FIND) || defined(TREE_WANT_LOOKUP)
389 STATIC P(node) * P(find) (T *t, TREE_KEY_DECL)
391 P(stack_entry) stack[TREE_MAX_DEPTH];
393 depth = P(fill_stack) (stack, TREE_MAX_DEPTH, t->root, TREE_KEY(), 0);
394 return stack[depth].buck ? &stack[depth].buck->n : NULL;
398 #ifdef TREE_STORE_PARENT
399 STATIC P(node) * P(adjacent) (P(node) *start, uns direction)
401 P(bucket) *node = SKIP_BACK(P(bucket), n, start);
402 P(bucket) *next = P(tree_son) (node, direction);
407 node = P(tree_son) (next, 1 - direction);
416 while (next && node == P(tree_son) (next, direction))
423 ASSERT(node == P(tree_son) (next, 1 - direction));
429 #if defined(TREE_WANT_FIND_NEXT) || defined(TREE_WANT_DELETE) || defined(TREE_WANT_REMOVE)
430 static int P(find_next_node) (P(stack_entry) *stack, uns max_depth, uns direction)
435 ASSERT(depth+1 < max_depth);
436 stack[depth].son = direction;
437 stack[depth+1].buck = P(tree_son) (stack[depth].buck, direction);
439 while (stack[depth].buck)
441 ASSERT(depth+1 < max_depth);
442 stack[depth].son = 1 - direction;
443 stack[depth+1].buck = P(tree_son) (stack[depth].buck, 1 - direction);
451 #ifdef TREE_WANT_FIND_NEXT
452 STATIC P(node) * P(find_next) (P(node) *start)
454 P(node) *next = P(adjacent) (start, 1);
455 if (next && P(cmp) (TREE_KEY(start->), TREE_KEY(next->)) == 0)
463 #ifdef TREE_WANT_SEARCH
464 STATIC P(node) * P(search) (T *t, TREE_KEY_DECL)
466 P(stack_entry) stack[TREE_MAX_DEPTH];
468 depth = P(fill_stack) (stack, TREE_MAX_DEPTH, t->root, TREE_KEY(), 0);
469 if (!stack[depth].buck)
476 return &stack[depth].buck->n;
481 #define TREE_TRACE(txt...) do { printf(txt); fflush(stdout); } while (0)
483 #define TREE_TRACE(txt...)
486 static inline P(bucket) * P(rotation) (P(bucket) *node, uns son_id)
488 /* Destroys red_flag's in node, son. Returns new root. */
489 P(bucket) *son = P(tree_son) (node, son_id);
490 TREE_TRACE("Rotation (node %d, son %d), direction %d\n", node->n.key, son->n.key, son_id);
491 node->son[son_id] = P(tree_son) (son, 1-son_id);
492 son->son[1-son_id] = node;
493 #ifdef TREE_STORE_PARENT
494 if (node->son[son_id])
495 node->son[son_id]->parent = node;
496 son->parent = node->parent;
502 static void P(rotate_after_insert) (T *t, P(stack_entry) *stack, uns depth)
505 P(bucket) *parent, *grand, *uncle;
508 node = stack[depth].buck;
509 ASSERT(P(red_flag) (node));
510 /* At this moment, node became red. The paths sum have
511 * been preserved, but we have to check the parental
515 ASSERT(t->root == node);
518 parent = stack[depth-1].buck;
519 if (!P(red_flag) (parent))
523 ASSERT(t->root == parent);
524 P(set_red_flag) (parent, 0);
528 grand = stack[depth-2].buck;
529 ASSERT(!P(red_flag) (grand));
530 /* The parent is also red, the grandparent exists and it
532 s1 = stack[depth-1].son;
533 s2 = stack[depth-2].son;
534 uncle = P(tree_son) (grand, 1-s2);
535 if (uncle && P(red_flag) (uncle))
537 /* Red parent and uncle, black grandparent.
538 * Exchange and try another iteration. */
539 P(set_red_flag) (parent, 0);
540 P(set_red_flag) (uncle, 0);
541 P(set_red_flag) (grand, 1);
543 TREE_TRACE("Swapping colours (parent %d, uncle %d, grand %d), passing thru\n", parent->n.key, uncle->n.key, grand->n.key);
546 /* Black uncle and grandparent, we need to rotate. Test
550 node = P(rotation) (grand, s2);
551 P(set_red_flag) (parent, 0);
552 P(set_red_flag) (grand, 1);
556 grand->son[s2] = P(rotation) (parent, s1);
557 node = P(rotation) (grand, s2);
558 P(set_red_flag) (grand, 1);
559 P(set_red_flag) (parent, 1);
560 P(set_red_flag) (node, 0);
563 P(set_tree_son) (stack[depth-3].buck, stack[depth-3].son, node);
568 #if defined(TREE_WANT_NEW) || defined(TREE_WANT_LOOKUP)
569 STATIC P(node) * P(new) (T *t, TREE_KEY_DECL)
571 P(stack_entry) stack[TREE_MAX_DEPTH];
574 depth = P(fill_stack) (stack, TREE_MAX_DEPTH, t->root, TREE_KEY(), 1);
575 #ifdef TREE_WANT_FIND_NEXT
576 /* It is the last found value, hence everything in the right subtree is
577 * strongly _bigger_. */
578 depth += P(find_next_node) (stack+depth, TREE_MAX_DEPTH-depth, 1);
580 ASSERT(!stack[depth].buck);
581 /* We are in a leaf, hence we can easily append a new leaf to it. */
582 added = P(alloc) (sizeof(struct P(bucket)) + TREE_EXTRA_SIZE(TREE_KEY()) );
583 added->son[0] = added->son[1] = NULL;
584 stack[depth].buck = added;
587 #ifdef TREE_STORE_PARENT
588 added->parent = stack[depth-1].buck;
590 P(set_tree_son) (stack[depth-1].buck, stack[depth-1].son, added);
594 #ifdef TREE_STORE_PARENT
595 added->parent = NULL;
599 P(set_red_flag) (added, 1); /* Set it red to not disturb the path sum. */
600 P(init_key) (&added->n, TREE_KEY());
601 P(init_data) (&added->n);
603 /* Let us reorganize the red_flag's and the structure of the tree. */
604 P(rotate_after_insert) (t, stack, depth);
609 #ifdef TREE_WANT_LOOKUP
610 STATIC P(node) * P(lookup) (T *t, TREE_KEY_DECL)
613 node = P(find) (t, TREE_KEY());
616 return P(new) (t, TREE_KEY());
620 #if defined(TREE_WANT_REMOVE) || defined(TREE_WANT_DELETE)
621 static void P(rotate_after_delete) (T *t, P(stack_entry) *stack, int depth)
624 P(bucket) *parent, *sibling, *instead;
625 uns parent_red, del_son, sibl_red;
632 parent = stack[depth].buck;
633 parent_red = P(red_flag) (parent);
634 del_son = stack[depth].son;
635 /* For the 1st iteration: we have deleted parent->son[del_son], which
636 * was a black node with no son. Hence there is one mising black
637 * vertex in that path, which we are going to fix now.
639 * For other iterations: in that path, there is also missing a black
642 ASSERT(!P(tree_son) (parent, del_son));
643 sibling = P(tree_son) (parent, 1-del_son);
645 sibl_red = P(red_flag) (sibling);
651 son[0] = P(tree_son) (sibling, 0);
652 son[1] = P(tree_son) (sibling, 1);
653 red[0] = son[0] ? P(red_flag) (son[0]) : 0;
654 red[1] = son[1] ? P(red_flag) (son[1]) : 0;
655 if (!red[0] && !red[1])
657 P(set_red_flag) (sibling, 1);
658 P(set_red_flag) (parent, 0);
665 TREE_TRACE("Swapping colours (parent %d, sibling %d), passing thru\n", parent->n.key, sibling->n.key);
668 } else if (!red[del_son])
670 instead = P(rotation) (parent, 1-del_son);
671 P(set_red_flag) (instead, parent_red);
672 P(set_red_flag) (parent, 0);
673 P(set_red_flag) (son[1-del_son], 0);
674 } else /* red[del_son] */
676 parent->son[1-del_son] = P(rotation) (sibling, del_son);
677 instead = P(rotation) (parent, 1-del_son);
678 P(set_red_flag) (instead, parent_red);
679 P(set_red_flag) (parent, 0);
680 P(set_red_flag) (sibling, 0);
682 } else /* sibl_red */
684 P(bucket) *grand[2], *son;
687 son = P(tree_son) (sibling, del_son);
688 ASSERT(son && !P(red_flag) (son));
689 grand[0] = P(tree_son) (son, 0);
690 grand[1] = P(tree_son) (son, 1);
691 red[0] = grand[0] ? P(red_flag) (grand[0]) : 0;
692 red[1] = grand[1] ? P(red_flag) (grand[1]) : 0;
693 if (!red[0] && !red[1])
695 instead = P(rotation) (parent, 1-del_son);
696 P(set_red_flag) (instead, 0);
697 P(set_red_flag) (parent, 0);
698 P(set_red_flag) (son, 1);
700 else if (!red[del_son])
702 parent->son[1-del_son] = P(rotation) (sibling, del_son);
703 instead = P(rotation) (parent, 1-del_son);
704 P(set_red_flag) (instead, 0);
705 P(set_red_flag) (parent, 0);
706 P(set_red_flag) (sibling, 1);
707 P(set_red_flag) (grand[1-del_son], 0);
708 } else /* red[del_son] */
710 sibling->son[del_son] = P(rotation) (son, del_son);
711 parent->son[1-del_son] = P(rotation) (sibling, del_son);
712 instead = P(rotation) (parent, 1-del_son);
713 P(set_red_flag) (instead, 0);
714 P(set_red_flag) (parent, 0);
715 P(set_red_flag) (sibling, 1);
716 P(set_red_flag) (son, 0);
719 /* We have performed all desired rotations and need to store the new
720 * pointer to the subtree. */
723 P(set_tree_son) (stack[depth-1].buck, stack[depth-1].son, instead);
728 static void P(remove_by_stack) (T *t, P(stack_entry) *stack, uns depth)
730 P(bucket) *node = stack[depth].buck;
733 for (i=0; i<depth; i++)
734 ASSERT(P(tree_son) (stack[i].buck, stack[i].son) == stack[i+1].buck);
735 if (P(tree_son) (node, 0) && P(tree_son) (node, 1))
738 uns flag_node, flag_xchg;
739 uns d = P(find_next_node) (stack+depth, TREE_MAX_DEPTH-depth, 1);
743 xchg = stack[depth+d].buck;
744 flag_node = P(red_flag) (node);
745 flag_xchg = P(red_flag) (xchg);
746 ASSERT(!P(tree_son) (xchg, 0));
747 son = P(tree_son) (xchg, 1);
748 stack[depth].buck = xchg; /* Magic iff d == 1. */
749 stack[depth+d].buck = node;
750 xchg->son[0] = P(tree_son) (node, 0);
751 xchg->son[1] = P(tree_son) (node, 1);
753 P(set_tree_son) (stack[depth-1].buck, stack[depth-1].son, xchg);
758 P(set_tree_son) (stack[depth+d-1].buck, stack[depth+d-1].son, node);
759 #ifdef TREE_STORE_PARENT
760 xchg->parent = depth > 0 ? stack[depth-1].buck : NULL;
761 xchg->son[0]->parent = xchg;
762 xchg->son[1]->parent = xchg;
763 node->parent = stack[depth+d-1].buck;
767 P(set_red_flag) (xchg, flag_node);
768 P(set_red_flag) (node, flag_xchg);
771 else if (P(tree_son) (node, 0))
772 son = P(tree_son) (node, 0);
774 son = P(tree_son) (node, 1);
775 /* At this moment, stack[depth].buck == node and it has at most one son
776 * and it is stored in the variable son. */
780 P(set_tree_son) (stack[depth-1].buck, stack[depth-1].son, son);
781 #ifdef TREE_STORE_PARENT
783 son->parent = stack[depth-1].buck;
789 #ifdef TREE_STORE_PARENT
794 if (P(red_flag) (node))
799 TREE_SAFE_FREE(node);
800 /* We have deleted a black node. */
803 ASSERT(P(red_flag) (son));
804 P(set_red_flag) (son, 0);
807 P(rotate_after_delete) (t, stack, (int) depth - 1);
811 #ifdef TREE_WANT_REMOVE
812 STATIC void P(remove) (T *t, P(node) *Node)
814 P(stack_entry) stack[TREE_MAX_DEPTH];
815 P(bucket) *node = SKIP_BACK(P(bucket), n, Node);
817 stack[0].buck = node;
822 ASSERT(depth < TREE_MAX_DEPTH);
823 stack[depth].buck = node->parent;
824 stack[depth].son = P(tree_son) (node->parent, 0) == node ? 0 : 1;
827 for (i=0; i<(depth+1)/2; i++)
829 P(stack_entry) tmp = stack[i];
830 stack[i] = stack[depth-i];
831 stack[depth-i] = tmp;
833 P(remove_by_stack) (t, stack, depth);
837 #ifdef TREE_WANT_DELETE
838 STATIC int P(delete) (T *t, TREE_KEY_DECL)
840 P(stack_entry) stack[TREE_MAX_DEPTH];
842 depth = P(fill_stack) (stack, TREE_MAX_DEPTH, t->root, TREE_KEY(), 1);
843 if (stack[depth].buck)
845 P(remove_by_stack) (t, stack, depth);
853 #ifdef TREE_WANT_DUMP
854 static void P(dump_subtree) (struct fastbuf *fb, T *t, P(bucket) *node, P(bucket) *parent, int cmp_res, int level, uns black)
860 ASSERT(black == t->height);
863 flag = P(red_flag) (node);
864 #ifdef TREE_STORE_PARENT
865 ASSERT(node->parent == parent);
869 ASSERT(!flag || !P(red_flag) (parent));
870 cmp_res *= P(cmp) (TREE_KEY(node->n.), TREE_KEY(parent->n.));
871 #ifdef TREE_WANT_FIND_NEXT
872 ASSERT(cmp_res >= 0);
877 P(dump_subtree) (fb, t, P(tree_son) (node, 0), node, -1, level+1, black + (1-flag));
881 for (i=0; i<level; i++)
883 sprintf(tmp, "L%d %c\t", level, flag ? 'R' : 'B');
885 P(dump_key) (fb, &node->n);
886 P(dump_data) (fb, &node->n);
889 P(dump_subtree) (fb, t, P(tree_son) (node, 1), node, +1, level+1, black + (1-flag));
892 STATIC void P(dump) (struct fastbuf *fb, T *t)
897 sprintf(tmp, "Tree of %d nodes and height %d\n", t->count, t->height);
900 P(dump_subtree) (fb, t, t->root, NULL, 0, 0, 0);
909 /* And the iterator */
911 #ifdef TREE_WANT_ITERATOR
912 static P(node) * P(first_node) (T *t, uns direction)
914 P(bucket) *node = t->root, *prev = NULL;
918 node = P(tree_son) (node, direction);
920 return prev ? &prev->n : NULL;
925 #define TREE_FOR_ALL(t_px, t_ptr, t_var) \
928 TREE_GLUE(t_px,node) *t_var = TREE_GLUE(t_px,first_node)(t_ptr, 0); \
929 for (; t_var; t_var = TREE_GLUE(t_px,adjacent)(t_var, 1)) \
931 #define TREE_END_FOR } } while(0)
932 #define TREE_BREAK break
933 #define TREE_CONTINUE continue
934 #define TREE_GLUE(x,y) x##_##y
939 /* Finally, undefine all the parameters */
946 #undef TREE_KEY_ATOMIC
947 #undef TREE_KEY_STRING
948 #undef TREE_KEY_ENDSTRING
949 #undef TREE_KEY_COMPLEX
951 #undef TREE_WANT_CLEANUP
952 #undef TREE_WANT_FIND
953 #undef TREE_WANT_FIND_NEXT
954 #undef TREE_WANT_SEARCH
955 #undef TREE_WANT_ADJACENT
957 #undef TREE_WANT_LOOKUP
958 #undef TREE_WANT_DELETE
959 #undef TREE_WANT_REMOVE
960 #undef TREE_WANT_DUMP
961 #undef TREE_WANT_ITERATOR
963 #undef TREE_GIVE_EXTRA_SIZE
964 #undef TREE_GIVE_INIT_KEY
965 #undef TREE_GIVE_INIT_DATA
966 #undef TREE_GIVE_ALLOC
968 #undef TREE_ATOMIC_TYPE
971 #undef TREE_CONSERVE_SPACE
972 #undef TREE_MAX_DEPTH
973 #undef TREE_STORE_PARENT
975 #undef TREE_EXTRA_SIZE
976 #undef TREE_SAFE_FREE