lib/libc/stdlib/rb.h

   1 /*-
   2  *******************************************************************************
   3  *
   4  * Copyright (C) 2008-2010 Jason Evans <jasone@FreeBSD.org>.
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  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
  13  *    copyright notices.
  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
  17  *    distribution.
  18  *
  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.
  30  *
  31  ******************************************************************************
  32  *
  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.
  37  *
  38  * Usage:
  39  *
  40  *   #include <stdint.h>
  41  *   #include <stdbool.h>
  42  *   #define NDEBUG // (Optional, see assert(3).)
  43  *   #include <assert.h>
  44  *   #define RB_COMPACT // (Optional, embed color bits in right-child pointers.)
  45  *   #include <rb.h>
  46  *   ...
  47  *
  48  *******************************************************************************
  49  */
  50
  51 #ifndef RB_H_
  52 #define RB_H_
  53
  54 #include <sys/cdefs.h>
  55 __FBSDID("$FreeBSD$");
  56
  57 #ifdef RB_COMPACT
  58 /* Node structure. */
  59 #define rb_node(a_type)                                                 \
  60 struct {                                                                \
  61     a_type *rbn_left;                                                   \
  62     a_type *rbn_right_red;                                              \
  63 }
  64 #else
  65 #define rb_node(a_type)                                                 \
  66 struct {                                                                \
  67     a_type *rbn_left;                                                   \
  68     a_type *rbn_right;                                                  \
  69     bool rbn_red;                                                       \
  70 }
  71 #endif
  72
  73 /* Root structure. */
  74 #define rb_tree(a_type)                                                 \
  75 struct {                                                                \
  76     a_type *rbt_root;                                                   \
  77     a_type rbt_nil;                                                     \
  78 }
  79
  80 /* Left accessors. */
  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;                                \
  85 } while (0)
  86
  87 #ifdef RB_COMPACT
  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)           \
  91       & ((ssize_t)-2)))
  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))); \
  95 } while (0)
  96
  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)              \
 100       & ((size_t)1)))
 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));                                              \
 105 } while (0)
 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));                  \
 109 } while (0)
 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));                \
 113 } while (0)
 114 #else
 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;                              \
 120 } while (0)
 121
 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);                                \
 127 } while (0)
 128 #define rbtn_red_set(a_type, a_field, a_node) do {                      \
 129     (a_node)->a_field.rbn_red = true;                                   \
 130 } while (0)
 131 #define rbtn_black_set(a_type, a_field, a_node) do {                    \
 132     (a_node)->a_field.rbn_red = false;                                  \
 133 } while (0)
 134 #endif
 135
 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));                            \
 141 } while (0)
 142
 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);                 \
 148 } while (0)
 149
 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) {                                \
 154         for (;                                                          \
 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))) {        \
 157         }                                                               \
 158     }                                                                   \
 159 } while (0)
 160
 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, \
 166           (r_node))) {                                                  \
 167         }                                                               \
 168     }                                                                   \
 169 } while (0)
 170
 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));                 \
 176 } while (0)
 177
 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));                \
 183 } while (0)
 184
 185 /*
 186  * The rb_proto() macro generates function prototypes that correspond to the
 187  * functions generated by an equivalently parameterized call to rb_gen().
 188  */
 189
 190 #define rb_proto(a_attr, a_prefix, a_rbt_type, a_type)                  \
 191 a_attr void                                                             \
 192 a_prefix##new(a_rbt_type *rbtree);                                      \
 193 a_attr a_type *                                                         \
 194 a_prefix##first(a_rbt_type *rbtree);                                    \
 195 a_attr a_type *                                                         \
 196 a_prefix##last(a_rbt_type *rbtree);                                     \
 197 a_attr a_type *                                                         \
 198 a_prefix##next(a_rbt_type *rbtree, a_type *node);                       \
 199 a_attr a_type *                                                         \
 200 a_prefix##prev(a_rbt_type *rbtree, a_type *node);                       \
 201 a_attr a_type *                                                         \
 202 a_prefix##search(a_rbt_type *rbtree, a_type *key);                      \
 203 a_attr a_type *                                                         \
 204 a_prefix##nsearch(a_rbt_type *rbtree, a_type *key);                     \
 205 a_attr a_type *                                                         \
 206 a_prefix##psearch(a_rbt_type *rbtree, a_type *key);                     \
 207 a_attr void                                                             \
 208 a_prefix##insert(a_rbt_type *rbtree, a_type *node);                     \
 209 a_attr void                                                             \
 210 a_prefix##remove(a_rbt_type *rbtree, a_type *node);                     \
 211 a_attr a_type *                                                         \
 212 a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)(        \
 213   a_rbt_type *, a_type *, void *), void *arg);                          \
 214 a_attr a_type *                                                         \
 215 a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start,               \
 216   a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg);
 217
 218 /*
 219  * The rb_gen() macro generates a type-specific red-black tree implementation,
 220  * based on the above cpp macros.
 221  *
 222  * Arguments:
 223  *
 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:
 228  *               extree_node_t).
 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);
 232  *                                       ^^^^^^
 233  *                                    or a_key
 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
 241  *               specially.
 242  *
 243  * Assuming the following setup:
 244  *
 245  *   typedef struct ex_node_s ex_node_t;
 246  *   struct ex_node_s {
 247  *       rb_node(ex_node_t) ex_link;
 248  *   };
 249  *   typedef rb(ex_node_t) ex_t;
 250  *   rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp, 1297, 1301)
 251  *
 252  * The following API is generated:
 253  *
 254  *   static void
 255  *   ex_new(ex_t *extree);
 256  *       Description: Initialize a red-black tree structure.
 257  *       Args:
 258  *         extree: Pointer to an uninitialized red-black tree object.
 259  *
 260  *   static ex_node_t *
 261  *   ex_first(ex_t *extree);
 262  *   static ex_node_t *
 263  *   ex_last(ex_t *extree);
 264  *       Description: Get the first/last node in extree.
 265  *       Args:
 266  *         extree: Pointer to an initialized red-black tree object.
 267  *       Ret: First/last node in extree, or NULL if extree is empty.
 268  *
 269  *   static ex_node_t *
 270  *   ex_next(ex_t *extree, ex_node_t *node);
 271  *   static ex_node_t *
 272  *   ex_prev(ex_t *extree, ex_node_t *node);
 273  *       Description: Get node's successor/predecessor.
 274  *       Args:
 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
 278  *            last/first.
 279  *
 280  *   static ex_node_t *
 281  *   ex_search(ex_t *extree, ex_node_t *key);
 282  *       Description: Search for node that matches key.
 283  *       Args:
 284  *         extree: Pointer to an initialized red-black tree object.
 285  *         key  : Search key.
 286  *       Ret: Node in extree that matches key, or NULL if no match.
 287  *
 288  *   static ex_node_t *
 289  *   ex_nsearch(ex_t *extree, ex_node_t *key);
 290  *   static ex_node_t *
 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
 294  *                    key in extree.
 295  *       Args:
 296  *         extree: Pointer to an initialized red-black tree object.
 297  *         key   : Search key.
 298  *       Ret: Node in extree that matches key, or if no match, hypothetical
 299  *            node's successor/predecessor (NULL if no successor/predecessor).
 300  *
 301  *   static void
 302  *   ex_insert(ex_t *extree, ex_node_t *node);
 303  *       Description: Insert node into extree.
 304  *       Args:
 305  *         extree: Pointer to an initialized red-black tree object.
 306  *         node  : Node to be inserted into extree.
 307  *
 308  *   static void
 309  *   ex_remove(ex_t *extree, ex_node_t *node);
 310  *       Description: Remove node from extree.
 311  *       Args:
 312  *         extree: Pointer to an initialized red-black tree object.
 313  *         node  : Node in extree to be removed.
 314  *
 315  *   static ex_node_t *
 316  *   ex_iter(ex_t *extree, ex_node_t *start, ex_node_t *(*cb)(ex_t *,
 317  *     ex_node_t *, void *), void *arg);
 318  *   static ex_node_t *
 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
 324  *                    modification.
 325  *       Args:
 326  *         extree: Pointer to an initialized red-black tree object.
 327  *         start : Node at which to start iteration, or NULL to start at
 328  *                 first/last node.
 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
 335  *                 modifying extree.
 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.
 339  */
 340 #define rb_gen(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp)    \
 341 a_attr void                                                             \
 342 a_prefix##new(a_rbt_type *rbtree) {                                     \
 343     rb_new(a_type, a_field, rbtree);                                    \
 344 }                                                                       \
 345 a_attr a_type *                                                         \
 346 a_prefix##first(a_rbt_type *rbtree) {                                   \
 347     a_type *ret;                                                        \
 348     rbtn_first(a_type, a_field, rbtree, rbtree->rbt_root, ret);         \
 349     if (ret == &rbtree->rbt_nil) {                                      \
 350         ret = NULL;                                                     \
 351     }                                                                   \
 352     return (ret);                                                       \
 353 }                                                                       \
 354 a_attr a_type *                                                         \
 355 a_prefix##last(a_rbt_type *rbtree) {                                    \
 356     a_type *ret;                                                        \
 357     rbtn_last(a_type, a_field, rbtree, rbtree->rbt_root, ret);          \
 358     if (ret == &rbtree->rbt_nil) {                                      \
 359         ret = NULL;                                                     \
 360     }                                                                   \
 361     return (ret);                                                       \
 362 }                                                                       \
 363 a_attr a_type *                                                         \
 364 a_prefix##next(a_rbt_type *rbtree, a_type *node) {                      \
 365     a_type *ret;                                                        \
 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);                                         \
 369     } else {                                                            \
 370         a_type *tnode = rbtree->rbt_root;                               \
 371         assert(tnode != &rbtree->rbt_nil);                              \
 372         ret = &rbtree->rbt_nil;                                         \
 373         while (true) {                                                  \
 374             int cmp = (a_cmp)(node, tnode);                             \
 375             if (cmp < 0) {                                              \
 376                 ret = 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);         \
 380             } else {                                                    \
 381                 break;                                                  \
 382             }                                                           \
 383             assert(tnode != &rbtree->rbt_nil);                          \
 384         }                                                               \
 385     }                                                                   \
 386     if (ret == &rbtree->rbt_nil) {                                      \
 387         ret = (NULL);                                                   \
 388     }                                                                   \
 389     return (ret);                                                       \
 390 }                                                                       \
 391 a_attr a_type *                                                         \
 392 a_prefix##prev(a_rbt_type *rbtree, a_type *node) {                      \
 393     a_type *ret;                                                        \
 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);                                         \
 397     } else {                                                            \
 398         a_type *tnode = rbtree->rbt_root;                               \
 399         assert(tnode != &rbtree->rbt_nil);                              \
 400         ret = &rbtree->rbt_nil;                                         \
 401         while (true) {                                                  \
 402             int cmp = (a_cmp)(node, tnode);                             \
 403             if (cmp < 0) {                                              \
 404                 tnode = rbtn_left_get(a_type, a_field, tnode);          \
 405             } else if (cmp > 0) {                                       \
 406                 ret = tnode;                                            \
 407                 tnode = rbtn_right_get(a_type, a_field, tnode);         \
 408             } else {                                                    \
 409                 break;                                                  \
 410             }                                                           \
 411             assert(tnode != &rbtree->rbt_nil);                          \
 412         }                                                               \
 413     }                                                                   \
 414     if (ret == &rbtree->rbt_nil) {                                      \
 415         ret = (NULL);                                                   \
 416     }                                                                   \
 417     return (ret);                                                       \
 418 }                                                                       \
 419 a_attr a_type *                                                         \
 420 a_prefix##search(a_rbt_type *rbtree, a_type *key) {                     \
 421     a_type *ret;                                                        \
 422     int cmp;                                                            \
 423     ret = rbtree->rbt_root;                                             \
 424     while (ret != &rbtree->rbt_nil                                      \
 425       && (cmp = (a_cmp)(key, ret)) != 0) {                              \
 426         if (cmp < 0) {                                                  \
 427             ret = rbtn_left_get(a_type, a_field, ret);                  \
 428         } else {                                                        \
 429             ret = rbtn_right_get(a_type, a_field, ret);                 \
 430         }                                                               \
 431     }                                                                   \
 432     if (ret == &rbtree->rbt_nil) {                                      \
 433         ret = (NULL);                                                   \
 434     }                                                                   \
 435     return (ret);                                                       \
 436 }                                                                       \
 437 a_attr a_type *                                                         \
 438 a_prefix##nsearch(a_rbt_type *rbtree, a_type *key) {                    \
 439     a_type *ret;                                                        \
 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);                                  \
 444         if (cmp < 0) {                                                  \
 445             ret = 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);             \
 449         } else {                                                        \
 450             ret = tnode;                                                \
 451             break;                                                      \
 452         }                                                               \
 453     }                                                                   \
 454     if (ret == &rbtree->rbt_nil) {                                      \
 455         ret = (NULL);                                                   \
 456     }                                                                   \
 457     return (ret);                                                       \
 458 }                                                                       \
 459 a_attr a_type *                                                         \
 460 a_prefix##psearch(a_rbt_type *rbtree, a_type *key) {                    \
 461     a_type *ret;                                                        \
 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);                                  \
 466         if (cmp < 0) {                                                  \
 467             tnode = rbtn_left_get(a_type, a_field, tnode);              \
 468         } else if (cmp > 0) {                                           \
 469             ret = tnode;                                                \
 470             tnode = rbtn_right_get(a_type, a_field, tnode);             \
 471         } else {                                                        \
 472             ret = tnode;                                                \
 473             break;                                                      \
 474         }                                                               \
 475     }                                                                   \
 476     if (ret == &rbtree->rbt_nil) {                                      \
 477         ret = (NULL);                                                   \
 478     }                                                                   \
 479     return (ret);                                                       \
 480 }                                                                       \
 481 a_attr void                                                             \
 482 a_prefix##insert(a_rbt_type *rbtree, a_type *node) {                    \
 483     struct {                                                            \
 484         a_type *node;                                                   \
 485         int cmp;                                                        \
 486     } path[sizeof(void *) << 4], *pathp;                                \
 487     rbt_node_new(a_type, a_field, rbtree, node);                        \
 488     /* Wind. */                                                         \
 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);                \
 492         assert(cmp != 0);                                               \
 493         if (cmp < 0) {                                                  \
 494             pathp[1].node = rbtn_left_get(a_type, a_field,              \
 495               pathp->node);                                             \
 496         } else {                                                        \
 497             pathp[1].node = rbtn_right_get(a_type, a_field,             \
 498               pathp->node);                                             \
 499         }                                                               \
 500     }                                                                   \
 501     pathp->node = node;                                                 \
 502     /* Unwind. */                                                       \
 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. */                                \
 512                     a_type *tnode;                                      \
 513                     rbtn_black_set(a_type, a_field, leftleft);          \
 514                     rbtn_rotate_right(a_type, a_field, cnode, tnode);   \
 515                     cnode = tnode;                                      \
 516                 }                                                       \
 517             } else {                                                    \
 518                 return;                                                 \
 519             }                                                           \
 520         } else {                                                        \
 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);               \
 530                 } else {                                                \
 531                     /* Lean left. */                                    \
 532                     a_type *tnode;                                      \
 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);               \
 537                     cnode = tnode;                                      \
 538                 }                                                       \
 539             } else {                                                    \
 540                 return;                                                 \
 541             }                                                           \
 542         }                                                               \
 543         pathp->node = cnode;                                            \
 544     }                                                                   \
 545     /* Set root, and make it black. */                                  \
 546     rbtree->rbt_root = path->node;                                      \
 547     rbtn_black_set(a_type, a_field, rbtree->rbt_root);                  \
 548 }                                                                       \
 549 a_attr void                                                             \
 550 a_prefix##remove(a_rbt_type *rbtree, a_type *node) {                    \
 551     struct {                                                            \
 552         a_type *node;                                                   \
 553         int cmp;                                                        \
 554     } *pathp, *nodep, path[sizeof(void *) << 4];                        \
 555     /* Wind. */                                                         \
 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);                \
 560         if (cmp < 0) {                                                  \
 561             pathp[1].node = rbtn_left_get(a_type, a_field,              \
 562               pathp->node);                                             \
 563         } else {                                                        \
 564             pathp[1].node = rbtn_right_get(a_type, a_field,             \
 565               pathp->node);                                             \
 566             if (cmp == 0) {                                             \
 567                 /* Find node's successor, in preparation for swap. */   \
 568                 pathp->cmp = 1;                                         \
 569                 nodep = pathp;                                          \
 570                 for (pathp++; pathp->node != &rbtree->rbt_nil;          \
 571                   pathp++) {                                            \
 572                     pathp->cmp = -1;                                    \
 573                     pathp[1].node = rbtn_left_get(a_type, a_field,      \
 574                       pathp->node);                                     \
 575                 }                                                       \
 576                 break;                                                  \
 577             }                                                           \
 578         }                                                               \
 579     }                                                                   \
 580     assert(nodep->node == node);                                        \
 581     pathp--;                                                            \
 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;                             \
 602         } else {                                                        \
 603             if (nodep[-1].cmp < 0) {                                    \
 604                 rbtn_left_set(a_type, a_field, nodep[-1].node,          \
 605                   nodep->node);                                         \
 606             } else {                                                    \
 607                 rbtn_right_set(a_type, a_field, nodep[-1].node,         \
 608                   nodep->node);                                         \
 609             }                                                           \
 610         }                                                               \
 611     } else {                                                            \
 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;                                \
 621             } else {                                                    \
 622                 if (pathp[-1].cmp < 0) {                                \
 623                     rbtn_left_set(a_type, a_field, pathp[-1].node,      \
 624                       left);                                            \
 625                 } else {                                                \
 626                     rbtn_right_set(a_type, a_field, pathp[-1].node,     \
 627                       left);                                            \
 628                 }                                                       \
 629             }                                                           \
 630             return;                                                     \
 631         } else if (pathp == path) {                                     \
 632             /* The tree only contained one node. */                     \
 633             rbtree->rbt_root = &rbtree->rbt_nil;                        \
 634             return;                                                     \
 635         }                                                               \
 636     }                                                                   \
 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,                  \
 641           &rbtree->rbt_nil);                                            \
 642         return;                                                         \
 643     }                                                                   \
 644     /* The node to be pruned is black, so unwind until balance is     */\
 645     /* restored.                                                      */\
 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,                 \
 651               pathp[1].node);                                           \
 652             assert(rbtn_red_get(a_type, a_field, pathp[1].node)         \
 653               == false);                                                \
 654             if (rbtn_red_get(a_type, a_field, pathp->node)) {           \
 655                 a_type *right = rbtn_right_get(a_type, a_field,         \
 656                   pathp->node);                                         \
 657                 a_type *rightleft = rbtn_left_get(a_type, a_field,      \
 658                   right);                                               \
 659                 a_type *tnode;                                          \
 660                 if (rbtn_red_get(a_type, a_field, rightleft)) {         \
 661                     /* In the following diagrams, ||, //, and \\      */\
 662                     /* indicate the path to the removed node.         */\
 663                     /*                                                */\
 664                     /*      ||                                        */\
 665                     /*    pathp(r)                                    */\
 666                     /*  //        \                                   */\
 667                     /* (b)        (b)                                 */\
 668                     /*           /                                    */\
 669                     /*          (r)                                   */\
 670                     /*                                                */\
 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,      \
 675                       tnode);                                           \
 676                 } else {                                                \
 677                     /*      ||                                        */\
 678                     /*    pathp(r)                                    */\
 679                     /*  //        \                                   */\
 680                     /* (b)        (b)                                 */\
 681                     /*           /                                    */\
 682                     /*          (b)                                   */\
 683                     /*                                                */\
 684                     rbtn_rotate_left(a_type, a_field, pathp->node,      \
 685                       tnode);                                           \
 686                 }                                                       \
 687                 /* Balance restored, but rotation modified subtree    */\
 688                 /* root.                                              */\
 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,      \
 692                       tnode);                                           \
 693                 } else {                                                \
 694                     rbtn_right_set(a_type, a_field, pathp[-1].node,     \
 695                       tnode);                                           \
 696                 }                                                       \
 697                 return;                                                 \
 698             } else {                                                    \
 699                 a_type *right = rbtn_right_get(a_type, a_field,         \
 700                   pathp->node);                                         \
 701                 a_type *rightleft = rbtn_left_get(a_type, a_field,      \
 702                   right);                                               \
 703                 if (rbtn_red_get(a_type, a_field, rightleft)) {         \
 704                     /*      ||                                        */\
 705                     /*    pathp(b)                                    */\
 706                     /*  //        \                                   */\
 707                     /* (b)        (b)                                 */\
 708                     /*           /                                    */\
 709                     /*          (r)                                   */\
 710                     a_type *tnode;                                      \
 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,      \
 715                       tnode);                                           \
 716                     /* Balance restored, but rotation modified        */\
 717                     /* subree root, which may actually be the tree    */\
 718                     /* root.                                          */\
 719                     if (pathp == path) {                                \
 720                         /* Set root. */                                 \
 721                         rbtree->rbt_root = tnode;                       \
 722                     } else {                                            \
 723                         if (pathp[-1].cmp < 0) {                        \
 724                             rbtn_left_set(a_type, a_field,              \
 725                               pathp[-1].node, tnode);                   \
 726                         } else {                                        \
 727                             rbtn_right_set(a_type, a_field,             \
 728                               pathp[-1].node, tnode);                   \
 729                         }                                               \
 730                     }                                                   \
 731                     return;                                             \
 732                 } else {                                                \
 733                     /*      ||                                        */\
 734                     /*    pathp(b)                                    */\
 735                     /*  //        \                                   */\
 736                     /* (b)        (b)                                 */\
 737                     /*           /                                    */\
 738                     /*          (b)                                   */\
 739                     a_type *tnode;                                      \
 740                     rbtn_red_set(a_type, a_field, pathp->node);         \
 741                     rbtn_rotate_left(a_type, a_field, pathp->node,      \
 742                       tnode);                                           \
 743                     pathp->node = tnode;                                \
 744                 }                                                       \
 745             }                                                           \
 746         } else {                                                        \
 747             a_type *left;                                               \
 748             rbtn_right_set(a_type, a_field, pathp->node,                \
 749               pathp[1].node);                                           \
 750             left = rbtn_left_get(a_type, a_field, pathp->node);         \
 751             if (rbtn_red_get(a_type, a_field, left)) {                  \
 752                 a_type *tnode;                                          \
 753                 a_type *leftright = rbtn_right_get(a_type, a_field,     \
 754                   left);                                                \
 755                 a_type *leftrightleft = rbtn_left_get(a_type, a_field,  \
 756                   leftright);                                           \
 757                 if (rbtn_red_get(a_type, a_field, leftrightleft)) {     \
 758                     /*      ||                                        */\
 759                     /*    pathp(b)                                    */\
 760                     /*   /        \\                                  */\
 761                     /* (r)        (b)                                 */\
 762                     /*   \                                            */\
 763                     /*   (b)                                          */\
 764                     /*   /                                            */\
 765                     /* (r)                                            */\
 766                     a_type *unode;                                      \
 767                     rbtn_black_set(a_type, a_field, leftrightleft);     \
 768                     rbtn_rotate_right(a_type, a_field, pathp->node,     \
 769                       unode);                                           \
 770                     rbtn_rotate_right(a_type, a_field, pathp->node,     \
 771                       tnode);                                           \
 772                     rbtn_right_set(a_type, a_field, unode, tnode);      \
 773                     rbtn_rotate_left(a_type, a_field, unode, tnode);    \
 774                 } else {                                                \
 775                     /*      ||                                        */\
 776                     /*    pathp(b)                                    */\
 777                     /*   /        \\                                  */\
 778                     /* (r)        (b)                                 */\
 779                     /*   \                                            */\
 780                     /*   (b)                                          */\
 781                     /*   /                                            */\
 782                     /* (b)                                            */\
 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,     \
 786                       tnode);                                           \
 787                     rbtn_black_set(a_type, a_field, tnode);             \
 788                 }                                                       \
 789                 /* Balance restored, but rotation modified subtree    */\
 790                 /* root, which may actually be the tree root.         */\
 791                 if (pathp == path) {                                    \
 792                     /* Set root. */                                     \
 793                     rbtree->rbt_root = tnode;                           \
 794                 } else {                                                \
 795                     if (pathp[-1].cmp < 0) {                            \
 796                         rbtn_left_set(a_type, a_field, pathp[-1].node,  \
 797                           tnode);                                       \
 798                     } else {                                            \
 799                         rbtn_right_set(a_type, a_field, pathp[-1].node, \
 800                           tnode);                                       \
 801                     }                                                   \
 802                 }                                                       \
 803                 return;                                                 \
 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)) {          \
 807                     /*        ||                                      */\
 808                     /*      pathp(r)                                  */\
 809                     /*     /        \\                                */\
 810                     /*   (b)        (b)                               */\
 811                     /*   /                                            */\
 812                     /* (r)                                            */\
 813                     a_type *tnode;                                      \
 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,     \
 818                       tnode);                                           \
 819                     /* Balance restored, but rotation modified        */\
 820                     /* subtree root.                                  */\
 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,  \
 824                           tnode);                                       \
 825                     } else {                                            \
 826                         rbtn_right_set(a_type, a_field, pathp[-1].node, \
 827                           tnode);                                       \
 828                     }                                                   \
 829                     return;                                             \
 830                 } else {                                                \
 831                     /*        ||                                      */\
 832                     /*      pathp(r)                                  */\
 833                     /*     /        \\                                */\
 834                     /*   (b)        (b)                               */\
 835                     /*   /                                            */\
 836                     /* (b)                                            */\
 837                     rbtn_red_set(a_type, a_field, left);                \
 838                     rbtn_black_set(a_type, a_field, pathp->node);       \
 839                     /* Balance restored. */                             \
 840                     return;                                             \
 841                 }                                                       \
 842             } else {                                                    \
 843                 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
 844                 if (rbtn_red_get(a_type, a_field, leftleft)) {          \
 845                     /*               ||                               */\
 846                     /*             pathp(b)                           */\
 847                     /*            /        \\                         */\
 848                     /*          (b)        (b)                        */\
 849                     /*          /                                     */\
 850                     /*        (r)                                     */\
 851                     a_type *tnode;                                      \
 852                     rbtn_black_set(a_type, a_field, leftleft);          \
 853                     rbtn_rotate_right(a_type, a_field, pathp->node,     \
 854                       tnode);                                           \
 855                     /* Balance restored, but rotation modified        */\
 856                     /* subtree root, which may actually be the tree   */\
 857                     /* root.                                          */\
 858                     if (pathp == path) {                                \
 859                         /* Set root. */                                 \
 860                         rbtree->rbt_root = tnode;                       \
 861                     } else {                                            \
 862                         if (pathp[-1].cmp < 0) {                        \
 863                             rbtn_left_set(a_type, a_field,              \
 864                               pathp[-1].node, tnode);                   \
 865                         } else {                                        \
 866                             rbtn_right_set(a_type, a_field,             \
 867                               pathp[-1].node, tnode);                   \
 868                         }                                               \
 869                     }                                                   \
 870                     return;                                             \
 871                 } else {                                                \
 872                     /*               ||                               */\
 873                     /*             pathp(b)                           */\
 874                     /*            /        \\                         */\
 875                     /*          (b)        (b)                        */\
 876                     /*          /                                     */\
 877                     /*        (b)                                     */\
 878                     rbtn_red_set(a_type, a_field, left);                \
 879                 }                                                       \
 880             }                                                           \
 881         }                                                               \
 882     }                                                                   \
 883     /* Set root. */                                                     \
 884     rbtree->rbt_root = path->node;                                      \
 885     assert(rbtn_red_get(a_type, a_field, rbtree->rbt_root) == false);   \
 886 }                                                                       \
 887 a_attr a_type *                                                         \
 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);                                      \
 892     } else {                                                            \
 893         a_type *ret;                                                    \
 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) {                   \
 897             return (ret);                                               \
 898         }                                                               \
 899         return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type,   \
 900           a_field, node), cb, arg));                                    \
 901     }                                                                   \
 902 }                                                                       \
 903 a_attr a_type *                                                         \
 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);                                       \
 907     if (cmp < 0) {                                                      \
 908         a_type *ret;                                                    \
 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) {  \
 912             return (ret);                                               \
 913         }                                                               \
 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));             \
 919     } else {                                                            \
 920         a_type *ret;                                                    \
 921         if ((ret = cb(rbtree, node, arg)) != NULL) {                    \
 922             return (ret);                                               \
 923         }                                                               \
 924         return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type,   \
 925           a_field, node), cb, arg));                                    \
 926     }                                                                   \
 927 }                                                                       \
 928 a_attr a_type *                                                         \
 929 a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)(        \
 930   a_rbt_type *, a_type *, void *), void *arg) {                         \
 931     a_type *ret;                                                        \
 932     if (start != NULL) {                                                \
 933         ret = a_prefix##iter_start(rbtree, start, rbtree->rbt_root,     \
 934           cb, arg);                                                     \
 935     } else {                                                            \
 936         ret = a_prefix##iter_recurse(rbtree, rbtree->rbt_root, cb, arg);\
 937     }                                                                   \
 938     if (ret == &rbtree->rbt_nil) {                                      \
 939         ret = NULL;                                                     \
 940     }                                                                   \
 941     return (ret);                                                       \
 942 }                                                                       \
 943 a_attr a_type *                                                         \
 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);                                      \
 948     } else {                                                            \
 949         a_type *ret;                                                    \
 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) {  \
 953             return (ret);                                               \
 954         }                                                               \
 955         return (a_prefix##reverse_iter_recurse(rbtree,                  \
 956           rbtn_left_get(a_type, a_field, node), cb, arg));              \
 957     }                                                                   \
 958 }                                                                       \
 959 a_attr a_type *                                                         \
 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 *),          \
 962   void *arg) {                                                          \
 963     int cmp = a_cmp(start, node);                                       \
 964     if (cmp > 0) {                                                      \
 965         a_type *ret;                                                    \
 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) {  \
 969             return (ret);                                               \
 970         }                                                               \
 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));              \
 976     } else {                                                            \
 977         a_type *ret;                                                    \
 978         if ((ret = cb(rbtree, node, arg)) != NULL) {                    \
 979             return (ret);                                               \
 980         }                                                               \
 981         return (a_prefix##reverse_iter_recurse(rbtree,                  \
 982           rbtn_left_get(a_type, a_field, node), cb, arg));              \
 983     }                                                                   \
 984 }                                                                       \
 985 a_attr a_type *                                                         \
 986 a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start,               \
 987   a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) {           \
 988     a_type *ret;                                                        \
 989     if (start != NULL) {                                                \
 990         ret = a_prefix##reverse_iter_start(rbtree, start,               \
 991           rbtree->rbt_root, cb, arg);                                   \
 992     } else {                                                            \
 993         ret = a_prefix##reverse_iter_recurse(rbtree, rbtree->rbt_root,  \
 994           cb, arg);                                                     \
 995     }                                                                   \
 996     if (ret == &rbtree->rbt_nil) {                                      \
 997         ret = NULL;                                                     \
 998     }                                                                   \
 999     return (ret);                                                       \
1000 }
1001
1002 #endif /* RB_H_ */