2 *******************************************************************************
4 * Copyright (C) 2008-2010 Jason Evans <jasone@FreeBSD.org>.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice(s), this list of conditions and the following disclaimer
12 * unmodified other than the allowable addition of one or more
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice(s), this list of conditions and the following disclaimer in
16 * the documentation and/or other materials provided with the
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
20 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
26 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
28 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
29 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 ******************************************************************************
33 * cpp macro implementation of left-leaning 2-3 red-black trees. Parent
34 * pointers are not used, and color bits are stored in the least significant
35 * bit of right-child pointers (if RB_COMPACT is defined), thus making node
36 * linkage as compact as is possible for red-black trees.
41 * #include <stdbool.h>
42 * #define NDEBUG // (Optional, see assert(3).)
44 * #define RB_COMPACT // (Optional, embed color bits in right-child pointers.)
48 *******************************************************************************
54 #include <sys/cdefs.h>
55 __FBSDID("$FreeBSD$");
59 #define rb_node(a_type) \
62 a_type *rbn_right_red; \
65 #define rb_node(a_type) \
74 #define rb_tree(a_type) \
81 #define rbtn_left_get(a_type, a_field, a_node) \
82 ((a_node)->a_field.rbn_left)
83 #define rbtn_left_set(a_type, a_field, a_node, a_left) do { \
84 (a_node)->a_field.rbn_left = a_left; \
88 /* Right accessors. */
89 #define rbtn_right_get(a_type, a_field, a_node) \
90 ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red) \
92 #define rbtn_right_set(a_type, a_field, a_node, a_right) do { \
93 (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right) \
94 | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1))); \
97 /* Color accessors. */
98 #define rbtn_red_get(a_type, a_field, a_node) \
99 ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red) \
101 #define rbtn_color_set(a_type, a_field, a_node, a_red) do { \
102 (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t) \
103 (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)) \
104 | ((ssize_t)a_red)); \
106 #define rbtn_red_set(a_type, a_field, a_node) do { \
107 (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) \
108 (a_node)->a_field.rbn_right_red) | ((size_t)1)); \
110 #define rbtn_black_set(a_type, a_field, a_node) do { \
111 (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t) \
112 (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)); \
115 /* Right accessors. */
116 #define rbtn_right_get(a_type, a_field, a_node) \
117 ((a_node)->a_field.rbn_right)
118 #define rbtn_right_set(a_type, a_field, a_node, a_right) do { \
119 (a_node)->a_field.rbn_right = a_right; \
122 /* Color accessors. */
123 #define rbtn_red_get(a_type, a_field, a_node) \
124 ((a_node)->a_field.rbn_red)
125 #define rbtn_color_set(a_type, a_field, a_node, a_red) do { \
126 (a_node)->a_field.rbn_red = (a_red); \
128 #define rbtn_red_set(a_type, a_field, a_node) do { \
129 (a_node)->a_field.rbn_red = true; \
131 #define rbtn_black_set(a_type, a_field, a_node) do { \
132 (a_node)->a_field.rbn_red = false; \
136 /* Node initializer. */
137 #define rbt_node_new(a_type, a_field, a_rbt, a_node) do { \
138 rbtn_left_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \
139 rbtn_right_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \
140 rbtn_red_set(a_type, a_field, (a_node)); \
143 /* Tree initializer. */
144 #define rb_new(a_type, a_field, a_rbt) do { \
145 (a_rbt)->rbt_root = &(a_rbt)->rbt_nil; \
146 rbt_node_new(a_type, a_field, a_rbt, &(a_rbt)->rbt_nil); \
147 rbtn_black_set(a_type, a_field, &(a_rbt)->rbt_nil); \
150 /* Internal utility macros. */
151 #define rbtn_first(a_type, a_field, a_rbt, a_root, r_node) do { \
152 (r_node) = (a_root); \
153 if ((r_node) != &(a_rbt)->rbt_nil) { \
155 rbtn_left_get(a_type, a_field, (r_node)) != &(a_rbt)->rbt_nil;\
156 (r_node) = rbtn_left_get(a_type, a_field, (r_node))) { \
161 #define rbtn_last(a_type, a_field, a_rbt, a_root, r_node) do { \
162 (r_node) = (a_root); \
163 if ((r_node) != &(a_rbt)->rbt_nil) { \
164 for (; rbtn_right_get(a_type, a_field, (r_node)) != \
165 &(a_rbt)->rbt_nil; (r_node) = rbtn_right_get(a_type, a_field, \
171 #define rbtn_rotate_left(a_type, a_field, a_node, r_node) do { \
172 (r_node) = rbtn_right_get(a_type, a_field, (a_node)); \
173 rbtn_right_set(a_type, a_field, (a_node), \
174 rbtn_left_get(a_type, a_field, (r_node))); \
175 rbtn_left_set(a_type, a_field, (r_node), (a_node)); \
178 #define rbtn_rotate_right(a_type, a_field, a_node, r_node) do { \
179 (r_node) = rbtn_left_get(a_type, a_field, (a_node)); \
180 rbtn_left_set(a_type, a_field, (a_node), \
181 rbtn_right_get(a_type, a_field, (r_node))); \
182 rbtn_right_set(a_type, a_field, (r_node), (a_node)); \
186 * The rb_proto() macro generates function prototypes that correspond to the
187 * functions generated by an equivalently parameterized call to rb_gen().
190 #define rb_proto(a_attr, a_prefix, a_rbt_type, a_type) \
192 a_prefix##new(a_rbt_type *rbtree); \
194 a_prefix##first(a_rbt_type *rbtree); \
196 a_prefix##last(a_rbt_type *rbtree); \
198 a_prefix##next(a_rbt_type *rbtree, a_type *node); \
200 a_prefix##prev(a_rbt_type *rbtree, a_type *node); \
202 a_prefix##search(a_rbt_type *rbtree, a_type *key); \
204 a_prefix##nsearch(a_rbt_type *rbtree, a_type *key); \
206 a_prefix##psearch(a_rbt_type *rbtree, a_type *key); \
208 a_prefix##insert(a_rbt_type *rbtree, a_type *node); \
210 a_prefix##remove(a_rbt_type *rbtree, a_type *node); \
212 a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \
213 a_rbt_type *, a_type *, void *), void *arg); \
215 a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \
216 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg);
219 * The rb_gen() macro generates a type-specific red-black tree implementation,
220 * based on the above cpp macros.
224 * a_attr : Function attribute for generated functions (ex: static).
225 * a_prefix : Prefix for generated functions (ex: extree_).
226 * a_rb_type : Type for red-black tree data structure (ex: extree_t).
227 * a_type : Type for red-black tree node data structure (ex:
229 * a_field : Name of red-black tree node linkage (ex: extree_link).
230 * a_cmp : Node comparison function name, with the following prototype:
231 * int (a_cmp *)(a_type *a_node, a_type *a_other);
234 * Interpretation of comparision function return values:
235 * -1 : a_node < a_other
236 * 0 : a_node == a_other
237 * 1 : a_node > a_other
238 * In all cases, the a_node or a_key macro argument is the first
239 * argument to the comparison function, which makes it possible
240 * to write comparison functions that treat the first argument
243 * Assuming the following setup:
245 * typedef struct ex_node_s ex_node_t;
247 * rb_node(ex_node_t) ex_link;
249 * typedef rb(ex_node_t) ex_t;
250 * rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp, 1297, 1301)
252 * The following API is generated:
255 * ex_new(ex_t *extree);
256 * Description: Initialize a red-black tree structure.
258 * extree: Pointer to an uninitialized red-black tree object.
261 * ex_first(ex_t *extree);
263 * ex_last(ex_t *extree);
264 * Description: Get the first/last node in extree.
266 * extree: Pointer to an initialized red-black tree object.
267 * Ret: First/last node in extree, or NULL if extree is empty.
270 * ex_next(ex_t *extree, ex_node_t *node);
272 * ex_prev(ex_t *extree, ex_node_t *node);
273 * Description: Get node's successor/predecessor.
275 * extree: Pointer to an initialized red-black tree object.
276 * node : A node in extree.
277 * Ret: node's successor/predecessor in extree, or NULL if node is
281 * ex_search(ex_t *extree, ex_node_t *key);
282 * Description: Search for node that matches key.
284 * extree: Pointer to an initialized red-black tree object.
286 * Ret: Node in extree that matches key, or NULL if no match.
289 * ex_nsearch(ex_t *extree, ex_node_t *key);
291 * ex_psearch(ex_t *extree, ex_node_t *key);
292 * Description: Search for node that matches key. If no match is found,
293 * return what would be key's successor/predecessor, were
296 * extree: Pointer to an initialized red-black tree object.
298 * Ret: Node in extree that matches key, or if no match, hypothetical
299 * node's successor/predecessor (NULL if no successor/predecessor).
302 * ex_insert(ex_t *extree, ex_node_t *node);
303 * Description: Insert node into extree.
305 * extree: Pointer to an initialized red-black tree object.
306 * node : Node to be inserted into extree.
309 * ex_remove(ex_t *extree, ex_node_t *node);
310 * Description: Remove node from extree.
312 * extree: Pointer to an initialized red-black tree object.
313 * node : Node in extree to be removed.
316 * ex_iter(ex_t *extree, ex_node_t *start, ex_node_t *(*cb)(ex_t *,
317 * ex_node_t *, void *), void *arg);
319 * ex_reverse_iter(ex_t *extree, ex_node_t *start, ex_node *(*cb)(ex_t *,
320 * ex_node_t *, void *), void *arg);
321 * Description: Iterate forward/backward over extree, starting at node.
322 * If extree is modified, iteration must be immediately
323 * terminated by the callback function that causes the
326 * extree: Pointer to an initialized red-black tree object.
327 * start : Node at which to start iteration, or NULL to start at
329 * cb : Callback function, which is called for each node during
330 * iteration. Under normal circumstances the callback function
331 * should return NULL, which causes iteration to continue. If a
332 * callback function returns non-NULL, iteration is immediately
333 * terminated and the non-NULL return value is returned by the
334 * iterator. This is useful for re-starting iteration after
336 * arg : Opaque pointer passed to cb().
337 * Ret: NULL if iteration completed, or the non-NULL callback return value
338 * that caused termination of the iteration.
340 #define rb_gen(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp) \
342 a_prefix##new(a_rbt_type *rbtree) { \
343 rb_new(a_type, a_field, rbtree); \
346 a_prefix##first(a_rbt_type *rbtree) { \
348 rbtn_first(a_type, a_field, rbtree, rbtree->rbt_root, ret); \
349 if (ret == &rbtree->rbt_nil) { \
355 a_prefix##last(a_rbt_type *rbtree) { \
357 rbtn_last(a_type, a_field, rbtree, rbtree->rbt_root, ret); \
358 if (ret == &rbtree->rbt_nil) { \
364 a_prefix##next(a_rbt_type *rbtree, a_type *node) { \
366 if (rbtn_right_get(a_type, a_field, node) != &rbtree->rbt_nil) { \
367 rbtn_first(a_type, a_field, rbtree, rbtn_right_get(a_type, \
368 a_field, node), ret); \
370 a_type *tnode = rbtree->rbt_root; \
371 assert(tnode != &rbtree->rbt_nil); \
372 ret = &rbtree->rbt_nil; \
374 int cmp = (a_cmp)(node, tnode); \
377 tnode = rbtn_left_get(a_type, a_field, tnode); \
378 } else if (cmp > 0) { \
379 tnode = rbtn_right_get(a_type, a_field, tnode); \
383 assert(tnode != &rbtree->rbt_nil); \
386 if (ret == &rbtree->rbt_nil) { \
392 a_prefix##prev(a_rbt_type *rbtree, a_type *node) { \
394 if (rbtn_left_get(a_type, a_field, node) != &rbtree->rbt_nil) { \
395 rbtn_last(a_type, a_field, rbtree, rbtn_left_get(a_type, \
396 a_field, node), ret); \
398 a_type *tnode = rbtree->rbt_root; \
399 assert(tnode != &rbtree->rbt_nil); \
400 ret = &rbtree->rbt_nil; \
402 int cmp = (a_cmp)(node, tnode); \
404 tnode = rbtn_left_get(a_type, a_field, tnode); \
405 } else if (cmp > 0) { \
407 tnode = rbtn_right_get(a_type, a_field, tnode); \
411 assert(tnode != &rbtree->rbt_nil); \
414 if (ret == &rbtree->rbt_nil) { \
420 a_prefix##search(a_rbt_type *rbtree, a_type *key) { \
423 ret = rbtree->rbt_root; \
424 while (ret != &rbtree->rbt_nil \
425 && (cmp = (a_cmp)(key, ret)) != 0) { \
427 ret = rbtn_left_get(a_type, a_field, ret); \
429 ret = rbtn_right_get(a_type, a_field, ret); \
432 if (ret == &rbtree->rbt_nil) { \
438 a_prefix##nsearch(a_rbt_type *rbtree, a_type *key) { \
440 a_type *tnode = rbtree->rbt_root; \
441 ret = &rbtree->rbt_nil; \
442 while (tnode != &rbtree->rbt_nil) { \
443 int cmp = (a_cmp)(key, tnode); \
446 tnode = rbtn_left_get(a_type, a_field, tnode); \
447 } else if (cmp > 0) { \
448 tnode = rbtn_right_get(a_type, a_field, tnode); \
454 if (ret == &rbtree->rbt_nil) { \
460 a_prefix##psearch(a_rbt_type *rbtree, a_type *key) { \
462 a_type *tnode = rbtree->rbt_root; \
463 ret = &rbtree->rbt_nil; \
464 while (tnode != &rbtree->rbt_nil) { \
465 int cmp = (a_cmp)(key, tnode); \
467 tnode = rbtn_left_get(a_type, a_field, tnode); \
468 } else if (cmp > 0) { \
470 tnode = rbtn_right_get(a_type, a_field, tnode); \
476 if (ret == &rbtree->rbt_nil) { \
482 a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \
486 } path[sizeof(void *) << 4], *pathp; \
487 rbt_node_new(a_type, a_field, rbtree, node); \
489 path->node = rbtree->rbt_root; \
490 for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \
491 int cmp = pathp->cmp = a_cmp(node, pathp->node); \
494 pathp[1].node = rbtn_left_get(a_type, a_field, \
497 pathp[1].node = rbtn_right_get(a_type, a_field, \
501 pathp->node = node; \
503 for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \
504 a_type *cnode = pathp->node; \
505 if (pathp->cmp < 0) { \
506 a_type *left = pathp[1].node; \
507 rbtn_left_set(a_type, a_field, cnode, left); \
508 if (rbtn_red_get(a_type, a_field, left)) { \
509 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
510 if (rbtn_red_get(a_type, a_field, leftleft)) { \
511 /* Fix up 4-node. */ \
513 rbtn_black_set(a_type, a_field, leftleft); \
514 rbtn_rotate_right(a_type, a_field, cnode, tnode); \
521 a_type *right = pathp[1].node; \
522 rbtn_right_set(a_type, a_field, cnode, right); \
523 if (rbtn_red_get(a_type, a_field, right)) { \
524 a_type *left = rbtn_left_get(a_type, a_field, cnode); \
525 if (rbtn_red_get(a_type, a_field, left)) { \
526 /* Split 4-node. */ \
527 rbtn_black_set(a_type, a_field, left); \
528 rbtn_black_set(a_type, a_field, right); \
529 rbtn_red_set(a_type, a_field, cnode); \
533 bool tred = rbtn_red_get(a_type, a_field, cnode); \
534 rbtn_rotate_left(a_type, a_field, cnode, tnode); \
535 rbtn_color_set(a_type, a_field, tnode, tred); \
536 rbtn_red_set(a_type, a_field, cnode); \
543 pathp->node = cnode; \
545 /* Set root, and make it black. */ \
546 rbtree->rbt_root = path->node; \
547 rbtn_black_set(a_type, a_field, rbtree->rbt_root); \
550 a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \
554 } *pathp, *nodep, path[sizeof(void *) << 4]; \
556 nodep = NULL; /* Silence compiler warning. */ \
557 path->node = rbtree->rbt_root; \
558 for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \
559 int cmp = pathp->cmp = a_cmp(node, pathp->node); \
561 pathp[1].node = rbtn_left_get(a_type, a_field, \
564 pathp[1].node = rbtn_right_get(a_type, a_field, \
567 /* Find node's successor, in preparation for swap. */ \
570 for (pathp++; pathp->node != &rbtree->rbt_nil; \
573 pathp[1].node = rbtn_left_get(a_type, a_field, \
580 assert(nodep->node == node); \
582 if (pathp->node != node) { \
583 /* Swap node with its successor. */ \
584 bool tred = rbtn_red_get(a_type, a_field, pathp->node); \
585 rbtn_color_set(a_type, a_field, pathp->node, \
586 rbtn_red_get(a_type, a_field, node)); \
587 rbtn_left_set(a_type, a_field, pathp->node, \
588 rbtn_left_get(a_type, a_field, node)); \
589 /* If node's successor is its right child, the following code */\
590 /* will do the wrong thing for the right child pointer. */\
591 /* However, it doesn't matter, because the pointer will be */\
592 /* properly set when the successor is pruned. */\
593 rbtn_right_set(a_type, a_field, pathp->node, \
594 rbtn_right_get(a_type, a_field, node)); \
595 rbtn_color_set(a_type, a_field, node, tred); \
596 /* The pruned leaf node's child pointers are never accessed */\
597 /* again, so don't bother setting them to nil. */\
598 nodep->node = pathp->node; \
599 pathp->node = node; \
600 if (nodep == path) { \
601 rbtree->rbt_root = nodep->node; \
603 if (nodep[-1].cmp < 0) { \
604 rbtn_left_set(a_type, a_field, nodep[-1].node, \
607 rbtn_right_set(a_type, a_field, nodep[-1].node, \
612 a_type *left = rbtn_left_get(a_type, a_field, node); \
613 if (left != &rbtree->rbt_nil) { \
614 /* node has no successor, but it has a left child. */\
615 /* Splice node out, without losing the left child. */\
616 assert(rbtn_red_get(a_type, a_field, node) == false); \
617 assert(rbtn_red_get(a_type, a_field, left)); \
618 rbtn_black_set(a_type, a_field, left); \
619 if (pathp == path) { \
620 rbtree->rbt_root = left; \
622 if (pathp[-1].cmp < 0) { \
623 rbtn_left_set(a_type, a_field, pathp[-1].node, \
626 rbtn_right_set(a_type, a_field, pathp[-1].node, \
631 } else if (pathp == path) { \
632 /* The tree only contained one node. */ \
633 rbtree->rbt_root = &rbtree->rbt_nil; \
637 if (rbtn_red_get(a_type, a_field, pathp->node)) { \
638 /* Prune red node, which requires no fixup. */ \
639 assert(pathp[-1].cmp < 0); \
640 rbtn_left_set(a_type, a_field, pathp[-1].node, \
644 /* The node to be pruned is black, so unwind until balance is */\
646 pathp->node = &rbtree->rbt_nil; \
647 for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \
648 assert(pathp->cmp != 0); \
649 if (pathp->cmp < 0) { \
650 rbtn_left_set(a_type, a_field, pathp->node, \
652 assert(rbtn_red_get(a_type, a_field, pathp[1].node) \
654 if (rbtn_red_get(a_type, a_field, pathp->node)) { \
655 a_type *right = rbtn_right_get(a_type, a_field, \
657 a_type *rightleft = rbtn_left_get(a_type, a_field, \
660 if (rbtn_red_get(a_type, a_field, rightleft)) { \
661 /* In the following diagrams, ||, //, and \\ */\
662 /* indicate the path to the removed node. */\
671 rbtn_black_set(a_type, a_field, pathp->node); \
672 rbtn_rotate_right(a_type, a_field, right, tnode); \
673 rbtn_right_set(a_type, a_field, pathp->node, tnode);\
674 rbtn_rotate_left(a_type, a_field, pathp->node, \
684 rbtn_rotate_left(a_type, a_field, pathp->node, \
687 /* Balance restored, but rotation modified subtree */\
689 assert((uintptr_t)pathp > (uintptr_t)path); \
690 if (pathp[-1].cmp < 0) { \
691 rbtn_left_set(a_type, a_field, pathp[-1].node, \
694 rbtn_right_set(a_type, a_field, pathp[-1].node, \
699 a_type *right = rbtn_right_get(a_type, a_field, \
701 a_type *rightleft = rbtn_left_get(a_type, a_field, \
703 if (rbtn_red_get(a_type, a_field, rightleft)) { \
711 rbtn_black_set(a_type, a_field, rightleft); \
712 rbtn_rotate_right(a_type, a_field, right, tnode); \
713 rbtn_right_set(a_type, a_field, pathp->node, tnode);\
714 rbtn_rotate_left(a_type, a_field, pathp->node, \
716 /* Balance restored, but rotation modified */\
717 /* subree root, which may actually be the tree */\
719 if (pathp == path) { \
721 rbtree->rbt_root = tnode; \
723 if (pathp[-1].cmp < 0) { \
724 rbtn_left_set(a_type, a_field, \
725 pathp[-1].node, tnode); \
727 rbtn_right_set(a_type, a_field, \
728 pathp[-1].node, tnode); \
740 rbtn_red_set(a_type, a_field, pathp->node); \
741 rbtn_rotate_left(a_type, a_field, pathp->node, \
743 pathp->node = tnode; \
748 rbtn_right_set(a_type, a_field, pathp->node, \
750 left = rbtn_left_get(a_type, a_field, pathp->node); \
751 if (rbtn_red_get(a_type, a_field, left)) { \
753 a_type *leftright = rbtn_right_get(a_type, a_field, \
755 a_type *leftrightleft = rbtn_left_get(a_type, a_field, \
757 if (rbtn_red_get(a_type, a_field, leftrightleft)) { \
767 rbtn_black_set(a_type, a_field, leftrightleft); \
768 rbtn_rotate_right(a_type, a_field, pathp->node, \
770 rbtn_rotate_right(a_type, a_field, pathp->node, \
772 rbtn_right_set(a_type, a_field, unode, tnode); \
773 rbtn_rotate_left(a_type, a_field, unode, tnode); \
783 assert(leftright != &rbtree->rbt_nil); \
784 rbtn_red_set(a_type, a_field, leftright); \
785 rbtn_rotate_right(a_type, a_field, pathp->node, \
787 rbtn_black_set(a_type, a_field, tnode); \
789 /* Balance restored, but rotation modified subtree */\
790 /* root, which may actually be the tree root. */\
791 if (pathp == path) { \
793 rbtree->rbt_root = tnode; \
795 if (pathp[-1].cmp < 0) { \
796 rbtn_left_set(a_type, a_field, pathp[-1].node, \
799 rbtn_right_set(a_type, a_field, pathp[-1].node, \
804 } else if (rbtn_red_get(a_type, a_field, pathp->node)) { \
805 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
806 if (rbtn_red_get(a_type, a_field, leftleft)) { \
814 rbtn_black_set(a_type, a_field, pathp->node); \
815 rbtn_red_set(a_type, a_field, left); \
816 rbtn_black_set(a_type, a_field, leftleft); \
817 rbtn_rotate_right(a_type, a_field, pathp->node, \
819 /* Balance restored, but rotation modified */\
821 assert((uintptr_t)pathp > (uintptr_t)path); \
822 if (pathp[-1].cmp < 0) { \
823 rbtn_left_set(a_type, a_field, pathp[-1].node, \
826 rbtn_right_set(a_type, a_field, pathp[-1].node, \
837 rbtn_red_set(a_type, a_field, left); \
838 rbtn_black_set(a_type, a_field, pathp->node); \
839 /* Balance restored. */ \
843 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
844 if (rbtn_red_get(a_type, a_field, leftleft)) { \
852 rbtn_black_set(a_type, a_field, leftleft); \
853 rbtn_rotate_right(a_type, a_field, pathp->node, \
855 /* Balance restored, but rotation modified */\
856 /* subtree root, which may actually be the tree */\
858 if (pathp == path) { \
860 rbtree->rbt_root = tnode; \
862 if (pathp[-1].cmp < 0) { \
863 rbtn_left_set(a_type, a_field, \
864 pathp[-1].node, tnode); \
866 rbtn_right_set(a_type, a_field, \
867 pathp[-1].node, tnode); \
878 rbtn_red_set(a_type, a_field, left); \
884 rbtree->rbt_root = path->node; \
885 assert(rbtn_red_get(a_type, a_field, rbtree->rbt_root) == false); \
888 a_prefix##iter_recurse(a_rbt_type *rbtree, a_type *node, \
889 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
890 if (node == &rbtree->rbt_nil) { \
891 return (&rbtree->rbt_nil); \
894 if ((ret = a_prefix##iter_recurse(rbtree, rbtn_left_get(a_type, \
895 a_field, node), cb, arg)) != &rbtree->rbt_nil \
896 || (ret = cb(rbtree, node, arg)) != NULL) { \
899 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
900 a_field, node), cb, arg)); \
904 a_prefix##iter_start(a_rbt_type *rbtree, a_type *start, a_type *node, \
905 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
906 int cmp = a_cmp(start, node); \
909 if ((ret = a_prefix##iter_start(rbtree, start, \
910 rbtn_left_get(a_type, a_field, node), cb, arg)) != \
911 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \
914 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
915 a_field, node), cb, arg)); \
916 } else if (cmp > 0) { \
917 return (a_prefix##iter_start(rbtree, start, \
918 rbtn_right_get(a_type, a_field, node), cb, arg)); \
921 if ((ret = cb(rbtree, node, arg)) != NULL) { \
924 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \
925 a_field, node), cb, arg)); \
929 a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \
930 a_rbt_type *, a_type *, void *), void *arg) { \
932 if (start != NULL) { \
933 ret = a_prefix##iter_start(rbtree, start, rbtree->rbt_root, \
936 ret = a_prefix##iter_recurse(rbtree, rbtree->rbt_root, cb, arg);\
938 if (ret == &rbtree->rbt_nil) { \
944 a_prefix##reverse_iter_recurse(a_rbt_type *rbtree, a_type *node, \
945 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
946 if (node == &rbtree->rbt_nil) { \
947 return (&rbtree->rbt_nil); \
950 if ((ret = a_prefix##reverse_iter_recurse(rbtree, \
951 rbtn_right_get(a_type, a_field, node), cb, arg)) != \
952 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \
955 return (a_prefix##reverse_iter_recurse(rbtree, \
956 rbtn_left_get(a_type, a_field, node), cb, arg)); \
960 a_prefix##reverse_iter_start(a_rbt_type *rbtree, a_type *start, \
961 a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \
963 int cmp = a_cmp(start, node); \
966 if ((ret = a_prefix##reverse_iter_start(rbtree, start, \
967 rbtn_right_get(a_type, a_field, node), cb, arg)) != \
968 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \
971 return (a_prefix##reverse_iter_recurse(rbtree, \
972 rbtn_left_get(a_type, a_field, node), cb, arg)); \
973 } else if (cmp < 0) { \
974 return (a_prefix##reverse_iter_start(rbtree, start, \
975 rbtn_left_get(a_type, a_field, node), cb, arg)); \
978 if ((ret = cb(rbtree, node, arg)) != NULL) { \
981 return (a_prefix##reverse_iter_recurse(rbtree, \
982 rbtn_left_get(a_type, a_field, node), cb, arg)); \
986 a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \
987 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \
989 if (start != NULL) { \
990 ret = a_prefix##reverse_iter_start(rbtree, start, \
991 rbtree->rbt_root, cb, arg); \
993 ret = a_prefix##reverse_iter_recurse(rbtree, rbtree->rbt_root, \
996 if (ret == &rbtree->rbt_nil) { \