contrib/jemalloc/include/jemalloc/internal/rb.h

   1 /*-
   2  *******************************************************************************
   3  *
   4  * cpp macro implementation of left-leaning 2-3 red-black trees.  Parent
   5  * pointers are not used, and color bits are stored in the least significant
   6  * bit of right-child pointers (if RB_COMPACT is defined), thus making node
   7  * linkage as compact as is possible for red-black trees.
   8  *
   9  * Usage:
  10  *
  11  *   #include <stdint.h>
  12  *   #include <stdbool.h>
  13  *   #define NDEBUG // (Optional, see assert(3).)
  14  *   #include <assert.h>
  15  *   #define RB_COMPACT // (Optional, embed color bits in right-child pointers.)
  16  *   #include <rb.h>
  17  *   ...
  18  *
  19  *******************************************************************************
  20  */
  21
  22 #ifndef RB_H_
  23 #define RB_H_
  24
  25 #if 0
  26 __FBSDID("$FreeBSD$");
  27 #endif
  28
  29 #ifdef RB_COMPACT
  30 /* Node structure. */
  31 #define rb_node(a_type)                                                 \
  32 struct {                                                                \
  33     a_type *rbn_left;                                                   \
  34     a_type *rbn_right_red;                                              \
  35 }
  36 #else
  37 #define rb_node(a_type)                                                 \
  38 struct {                                                                \
  39     a_type *rbn_left;                                                   \
  40     a_type *rbn_right;                                                  \
  41     bool rbn_red;                                                       \
  42 }
  43 #endif
  44
  45 /* Root structure. */
  46 #define rb_tree(a_type)                                                 \
  47 struct {                                                                \
  48     a_type *rbt_root;                                                   \
  49     a_type rbt_nil;                                                     \
  50 }
  51
  52 /* Left accessors. */
  53 #define rbtn_left_get(a_type, a_field, a_node)                          \
  54     ((a_node)->a_field.rbn_left)
  55 #define rbtn_left_set(a_type, a_field, a_node, a_left) do {             \
  56     (a_node)->a_field.rbn_left = a_left;                                \
  57 } while (0)
  58
  59 #ifdef RB_COMPACT
  60 /* Right accessors. */
  61 #define rbtn_right_get(a_type, a_field, a_node)                         \
  62     ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red)           \
  63       & ((ssize_t)-2)))
  64 #define rbtn_right_set(a_type, a_field, a_node, a_right) do {           \
  65     (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right) \
  66       | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1))); \
  67 } while (0)
  68
  69 /* Color accessors. */
  70 #define rbtn_red_get(a_type, a_field, a_node)                           \
  71     ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red)              \
  72       & ((size_t)1)))
  73 #define rbtn_color_set(a_type, a_field, a_node, a_red) do {             \
  74     (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t)          \
  75       (a_node)->a_field.rbn_right_red) & ((ssize_t)-2))                 \
  76       | ((ssize_t)a_red));                                              \
  77 } while (0)
  78 #define rbtn_red_set(a_type, a_field, a_node) do {                      \
  79     (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t)          \
  80       (a_node)->a_field.rbn_right_red) | ((size_t)1));                  \
  81 } while (0)
  82 #define rbtn_black_set(a_type, a_field, a_node) do {                    \
  83     (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t)           \
  84       (a_node)->a_field.rbn_right_red) & ((ssize_t)-2));                \
  85 } while (0)
  86 #else
  87 /* Right accessors. */
  88 #define rbtn_right_get(a_type, a_field, a_node)                         \
  89     ((a_node)->a_field.rbn_right)
  90 #define rbtn_right_set(a_type, a_field, a_node, a_right) do {           \
  91     (a_node)->a_field.rbn_right = a_right;                              \
  92 } while (0)
  93
  94 /* Color accessors. */
  95 #define rbtn_red_get(a_type, a_field, a_node)                           \
  96     ((a_node)->a_field.rbn_red)
  97 #define rbtn_color_set(a_type, a_field, a_node, a_red) do {             \
  98     (a_node)->a_field.rbn_red = (a_red);                                \
  99 } while (0)
 100 #define rbtn_red_set(a_type, a_field, a_node) do {                      \
 101     (a_node)->a_field.rbn_red = true;                                   \
 102 } while (0)
 103 #define rbtn_black_set(a_type, a_field, a_node) do {                    \
 104     (a_node)->a_field.rbn_red = false;                                  \
 105 } while (0)
 106 #endif
 107
 108 /* Node initializer. */
 109 #define rbt_node_new(a_type, a_field, a_rbt, a_node) do {               \
 110     rbtn_left_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil);        \
 111     rbtn_right_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil);       \
 112     rbtn_red_set(a_type, a_field, (a_node));                            \
 113 } while (0)
 114
 115 /* Tree initializer. */
 116 #define rb_new(a_type, a_field, a_rbt) do {                             \
 117     (a_rbt)->rbt_root = &(a_rbt)->rbt_nil;                              \
 118     rbt_node_new(a_type, a_field, a_rbt, &(a_rbt)->rbt_nil);            \
 119     rbtn_black_set(a_type, a_field, &(a_rbt)->rbt_nil);                 \
 120 } while (0)
 121
 122 /* Internal utility macros. */
 123 #define rbtn_first(a_type, a_field, a_rbt, a_root, r_node) do {         \
 124     (r_node) = (a_root);                                                \
 125     if ((r_node) != &(a_rbt)->rbt_nil) {                                \
 126         for (;                                                          \
 127           rbtn_left_get(a_type, a_field, (r_node)) != &(a_rbt)->rbt_nil;\
 128           (r_node) = rbtn_left_get(a_type, a_field, (r_node))) {        \
 129         }                                                               \
 130     }                                                                   \
 131 } while (0)
 132
 133 #define rbtn_last(a_type, a_field, a_rbt, a_root, r_node) do {          \
 134     (r_node) = (a_root);                                                \
 135     if ((r_node) != &(a_rbt)->rbt_nil) {                                \
 136         for (; rbtn_right_get(a_type, a_field, (r_node)) !=             \
 137           &(a_rbt)->rbt_nil; (r_node) = rbtn_right_get(a_type, a_field, \
 138           (r_node))) {                                                  \
 139         }                                                               \
 140     }                                                                   \
 141 } while (0)
 142
 143 #define rbtn_rotate_left(a_type, a_field, a_node, r_node) do {          \
 144     (r_node) = rbtn_right_get(a_type, a_field, (a_node));               \
 145     rbtn_right_set(a_type, a_field, (a_node),                           \
 146       rbtn_left_get(a_type, a_field, (r_node)));                        \
 147     rbtn_left_set(a_type, a_field, (r_node), (a_node));                 \
 148 } while (0)
 149
 150 #define rbtn_rotate_right(a_type, a_field, a_node, r_node) do {         \
 151     (r_node) = rbtn_left_get(a_type, a_field, (a_node));                \
 152     rbtn_left_set(a_type, a_field, (a_node),                            \
 153       rbtn_right_get(a_type, a_field, (r_node)));                       \
 154     rbtn_right_set(a_type, a_field, (r_node), (a_node));                \
 155 } while (0)
 156
 157 /*
 158  * The rb_proto() macro generates function prototypes that correspond to the
 159  * functions generated by an equivalently parameterized call to rb_gen().
 160  */
 161
 162 #define rb_proto(a_attr, a_prefix, a_rbt_type, a_type)                  \
 163 a_attr void                                                             \
 164 a_prefix##new(a_rbt_type *rbtree);                                      \
 165 a_attr a_type *                                                         \
 166 a_prefix##first(a_rbt_type *rbtree);                                    \
 167 a_attr a_type *                                                         \
 168 a_prefix##last(a_rbt_type *rbtree);                                     \
 169 a_attr a_type *                                                         \
 170 a_prefix##next(a_rbt_type *rbtree, a_type *node);                       \
 171 a_attr a_type *                                                         \
 172 a_prefix##prev(a_rbt_type *rbtree, a_type *node);                       \
 173 a_attr a_type *                                                         \
 174 a_prefix##search(a_rbt_type *rbtree, a_type *key);                      \
 175 a_attr a_type *                                                         \
 176 a_prefix##nsearch(a_rbt_type *rbtree, a_type *key);                     \
 177 a_attr a_type *                                                         \
 178 a_prefix##psearch(a_rbt_type *rbtree, a_type *key);                     \
 179 a_attr void                                                             \
 180 a_prefix##insert(a_rbt_type *rbtree, a_type *node);                     \
 181 a_attr void                                                             \
 182 a_prefix##remove(a_rbt_type *rbtree, a_type *node);                     \
 183 a_attr a_type *                                                         \
 184 a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)(        \
 185   a_rbt_type *, a_type *, void *), void *arg);                          \
 186 a_attr a_type *                                                         \
 187 a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start,               \
 188   a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg);
 189
 190 /*
 191  * The rb_gen() macro generates a type-specific red-black tree implementation,
 192  * based on the above cpp macros.
 193  *
 194  * Arguments:
 195  *
 196  *   a_attr    : Function attribute for generated functions (ex: static).
 197  *   a_prefix  : Prefix for generated functions (ex: ex_).
 198  *   a_rb_type : Type for red-black tree data structure (ex: ex_t).
 199  *   a_type    : Type for red-black tree node data structure (ex: ex_node_t).
 200  *   a_field   : Name of red-black tree node linkage (ex: ex_link).
 201  *   a_cmp     : Node comparison function name, with the following prototype:
 202  *                 int (a_cmp *)(a_type *a_node, a_type *a_other);
 203  *                                       ^^^^^^
 204  *                                    or a_key
 205  *               Interpretation of comparision function return values:
 206  *                 -1 : a_node <  a_other
 207  *                  0 : a_node == a_other
 208  *                  1 : a_node >  a_other
 209  *               In all cases, the a_node or a_key macro argument is the first
 210  *               argument to the comparison function, which makes it possible
 211  *               to write comparison functions that treat the first argument
 212  *               specially.
 213  *
 214  * Assuming the following setup:
 215  *
 216  *   typedef struct ex_node_s ex_node_t;
 217  *   struct ex_node_s {
 218  *       rb_node(ex_node_t) ex_link;
 219  *   };
 220  *   typedef rb_tree(ex_node_t) ex_t;
 221  *   rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp)
 222  *
 223  * The following API is generated:
 224  *
 225  *   static void
 226  *   ex_new(ex_t *tree);
 227  *       Description: Initialize a red-black tree structure.
 228  *       Args:
 229  *         tree: Pointer to an uninitialized red-black tree object.
 230  *
 231  *   static ex_node_t *
 232  *   ex_first(ex_t *tree);
 233  *   static ex_node_t *
 234  *   ex_last(ex_t *tree);
 235  *       Description: Get the first/last node in tree.
 236  *       Args:
 237  *         tree: Pointer to an initialized red-black tree object.
 238  *       Ret: First/last node in tree, or NULL if tree is empty.
 239  *
 240  *   static ex_node_t *
 241  *   ex_next(ex_t *tree, ex_node_t *node);
 242  *   static ex_node_t *
 243  *   ex_prev(ex_t *tree, ex_node_t *node);
 244  *       Description: Get node's successor/predecessor.
 245  *       Args:
 246  *         tree: Pointer to an initialized red-black tree object.
 247  *         node: A node in tree.
 248  *       Ret: node's successor/predecessor in tree, or NULL if node is
 249  *            last/first.
 250  *
 251  *   static ex_node_t *
 252  *   ex_search(ex_t *tree, ex_node_t *key);
 253  *       Description: Search for node that matches key.
 254  *       Args:
 255  *         tree: Pointer to an initialized red-black tree object.
 256  *         key : Search key.
 257  *       Ret: Node in tree that matches key, or NULL if no match.
 258  *
 259  *   static ex_node_t *
 260  *   ex_nsearch(ex_t *tree, ex_node_t *key);
 261  *   static ex_node_t *
 262  *   ex_psearch(ex_t *tree, ex_node_t *key);
 263  *       Description: Search for node that matches key.  If no match is found,
 264  *                    return what would be key's successor/predecessor, were
 265  *                    key in tree.
 266  *       Args:
 267  *         tree: Pointer to an initialized red-black tree object.
 268  *         key : Search key.
 269  *       Ret: Node in tree that matches key, or if no match, hypothetical node's
 270  *            successor/predecessor (NULL if no successor/predecessor).
 271  *
 272  *   static void
 273  *   ex_insert(ex_t *tree, ex_node_t *node);
 274  *       Description: Insert node into tree.
 275  *       Args:
 276  *         tree: Pointer to an initialized red-black tree object.
 277  *         node: Node to be inserted into tree.
 278  *
 279  *   static void
 280  *   ex_remove(ex_t *tree, ex_node_t *node);
 281  *       Description: Remove node from tree.
 282  *       Args:
 283  *         tree: Pointer to an initialized red-black tree object.
 284  *         node: Node in tree to be removed.
 285  *
 286  *   static ex_node_t *
 287  *   ex_iter(ex_t *tree, ex_node_t *start, ex_node_t *(*cb)(ex_t *,
 288  *     ex_node_t *, void *), void *arg);
 289  *   static ex_node_t *
 290  *   ex_reverse_iter(ex_t *tree, ex_node_t *start, ex_node *(*cb)(ex_t *,
 291  *     ex_node_t *, void *), void *arg);
 292  *       Description: Iterate forward/backward over tree, starting at node.  If
 293  *                    tree is modified, iteration must be immediately
 294  *                    terminated by the callback function that causes the
 295  *                    modification.
 296  *       Args:
 297  *         tree : Pointer to an initialized red-black tree object.
 298  *         start: Node at which to start iteration, or NULL to start at
 299  *                first/last node.
 300  *         cb   : Callback function, which is called for each node during
 301  *                iteration.  Under normal circumstances the callback function
 302  *                should return NULL, which causes iteration to continue.  If a
 303  *                callback function returns non-NULL, iteration is immediately
 304  *                terminated and the non-NULL return value is returned by the
 305  *                iterator.  This is useful for re-starting iteration after
 306  *                modifying tree.
 307  *         arg  : Opaque pointer passed to cb().
 308  *       Ret: NULL if iteration completed, or the non-NULL callback return value
 309  *            that caused termination of the iteration.
 310  */
 311 #define rb_gen(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp)    \
 312 a_attr void                                                             \
 313 a_prefix##new(a_rbt_type *rbtree) {                                     \
 314     rb_new(a_type, a_field, rbtree);                                    \
 315 }                                                                       \
 316 a_attr a_type *                                                         \
 317 a_prefix##first(a_rbt_type *rbtree) {                                   \
 318     a_type *ret;                                                        \
 319     rbtn_first(a_type, a_field, rbtree, rbtree->rbt_root, ret);         \
 320     if (ret == &rbtree->rbt_nil) {                                      \
 321         ret = NULL;                                                     \
 322     }                                                                   \
 323     return (ret);                                                       \
 324 }                                                                       \
 325 a_attr a_type *                                                         \
 326 a_prefix##last(a_rbt_type *rbtree) {                                    \
 327     a_type *ret;                                                        \
 328     rbtn_last(a_type, a_field, rbtree, rbtree->rbt_root, ret);          \
 329     if (ret == &rbtree->rbt_nil) {                                      \
 330         ret = NULL;                                                     \
 331     }                                                                   \
 332     return (ret);                                                       \
 333 }                                                                       \
 334 a_attr a_type *                                                         \
 335 a_prefix##next(a_rbt_type *rbtree, a_type *node) {                      \
 336     a_type *ret;                                                        \
 337     if (rbtn_right_get(a_type, a_field, node) != &rbtree->rbt_nil) {    \
 338         rbtn_first(a_type, a_field, rbtree, rbtn_right_get(a_type,      \
 339           a_field, node), ret);                                         \
 340     } else {                                                            \
 341         a_type *tnode = rbtree->rbt_root;                               \
 342         assert(tnode != &rbtree->rbt_nil);                              \
 343         ret = &rbtree->rbt_nil;                                         \
 344         while (true) {                                                  \
 345             int cmp = (a_cmp)(node, tnode);                             \
 346             if (cmp < 0) {                                              \
 347                 ret = tnode;                                            \
 348                 tnode = rbtn_left_get(a_type, a_field, tnode);          \
 349             } else if (cmp > 0) {                                       \
 350                 tnode = rbtn_right_get(a_type, a_field, tnode);         \
 351             } else {                                                    \
 352                 break;                                                  \
 353             }                                                           \
 354             assert(tnode != &rbtree->rbt_nil);                          \
 355         }                                                               \
 356     }                                                                   \
 357     if (ret == &rbtree->rbt_nil) {                                      \
 358         ret = (NULL);                                                   \
 359     }                                                                   \
 360     return (ret);                                                       \
 361 }                                                                       \
 362 a_attr a_type *                                                         \
 363 a_prefix##prev(a_rbt_type *rbtree, a_type *node) {                      \
 364     a_type *ret;                                                        \
 365     if (rbtn_left_get(a_type, a_field, node) != &rbtree->rbt_nil) {     \
 366         rbtn_last(a_type, a_field, rbtree, rbtn_left_get(a_type,        \
 367           a_field, node), ret);                                         \
 368     } else {                                                            \
 369         a_type *tnode = rbtree->rbt_root;                               \
 370         assert(tnode != &rbtree->rbt_nil);                              \
 371         ret = &rbtree->rbt_nil;                                         \
 372         while (true) {                                                  \
 373             int cmp = (a_cmp)(node, tnode);                             \
 374             if (cmp < 0) {                                              \
 375                 tnode = rbtn_left_get(a_type, a_field, tnode);          \
 376             } else if (cmp > 0) {                                       \
 377                 ret = tnode;                                            \
 378                 tnode = rbtn_right_get(a_type, a_field, tnode);         \
 379             } else {                                                    \
 380                 break;                                                  \
 381             }                                                           \
 382             assert(tnode != &rbtree->rbt_nil);                          \
 383         }                                                               \
 384     }                                                                   \
 385     if (ret == &rbtree->rbt_nil) {                                      \
 386         ret = (NULL);                                                   \
 387     }                                                                   \
 388     return (ret);                                                       \
 389 }                                                                       \
 390 a_attr a_type *                                                         \
 391 a_prefix##search(a_rbt_type *rbtree, a_type *key) {                     \
 392     a_type *ret;                                                        \
 393     int cmp;                                                            \
 394     ret = rbtree->rbt_root;                                             \
 395     while (ret != &rbtree->rbt_nil                                      \
 396       && (cmp = (a_cmp)(key, ret)) != 0) {                              \
 397         if (cmp < 0) {                                                  \
 398             ret = rbtn_left_get(a_type, a_field, ret);                  \
 399         } else {                                                        \
 400             ret = rbtn_right_get(a_type, a_field, ret);                 \
 401         }                                                               \
 402     }                                                                   \
 403     if (ret == &rbtree->rbt_nil) {                                      \
 404         ret = (NULL);                                                   \
 405     }                                                                   \
 406     return (ret);                                                       \
 407 }                                                                       \
 408 a_attr a_type *                                                         \
 409 a_prefix##nsearch(a_rbt_type *rbtree, a_type *key) {                    \
 410     a_type *ret;                                                        \
 411     a_type *tnode = rbtree->rbt_root;                                   \
 412     ret = &rbtree->rbt_nil;                                             \
 413     while (tnode != &rbtree->rbt_nil) {                                 \
 414         int cmp = (a_cmp)(key, tnode);                                  \
 415         if (cmp < 0) {                                                  \
 416             ret = tnode;                                                \
 417             tnode = rbtn_left_get(a_type, a_field, tnode);              \
 418         } else if (cmp > 0) {                                           \
 419             tnode = rbtn_right_get(a_type, a_field, tnode);             \
 420         } else {                                                        \
 421             ret = tnode;                                                \
 422             break;                                                      \
 423         }                                                               \
 424     }                                                                   \
 425     if (ret == &rbtree->rbt_nil) {                                      \
 426         ret = (NULL);                                                   \
 427     }                                                                   \
 428     return (ret);                                                       \
 429 }                                                                       \
 430 a_attr a_type *                                                         \
 431 a_prefix##psearch(a_rbt_type *rbtree, a_type *key) {                    \
 432     a_type *ret;                                                        \
 433     a_type *tnode = rbtree->rbt_root;                                   \
 434     ret = &rbtree->rbt_nil;                                             \
 435     while (tnode != &rbtree->rbt_nil) {                                 \
 436         int cmp = (a_cmp)(key, tnode);                                  \
 437         if (cmp < 0) {                                                  \
 438             tnode = rbtn_left_get(a_type, a_field, tnode);              \
 439         } else if (cmp > 0) {                                           \
 440             ret = tnode;                                                \
 441             tnode = rbtn_right_get(a_type, a_field, tnode);             \
 442         } else {                                                        \
 443             ret = tnode;                                                \
 444             break;                                                      \
 445         }                                                               \
 446     }                                                                   \
 447     if (ret == &rbtree->rbt_nil) {                                      \
 448         ret = (NULL);                                                   \
 449     }                                                                   \
 450     return (ret);                                                       \
 451 }                                                                       \
 452 a_attr void                                                             \
 453 a_prefix##insert(a_rbt_type *rbtree, a_type *node) {                    \
 454     struct {                                                            \
 455         a_type *node;                                                   \
 456         int cmp;                                                        \
 457     } path[sizeof(void *) << 4], *pathp;                                \
 458     rbt_node_new(a_type, a_field, rbtree, node);                        \
 459     /* Wind. */                                                         \
 460     path->node = rbtree->rbt_root;                                      \
 461     for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) {      \
 462         int cmp = pathp->cmp = a_cmp(node, pathp->node);                \
 463         assert(cmp != 0);                                               \
 464         if (cmp < 0) {                                                  \
 465             pathp[1].node = rbtn_left_get(a_type, a_field,              \
 466               pathp->node);                                             \
 467         } else {                                                        \
 468             pathp[1].node = rbtn_right_get(a_type, a_field,             \
 469               pathp->node);                                             \
 470         }                                                               \
 471     }                                                                   \
 472     pathp->node = node;                                                 \
 473     /* Unwind. */                                                       \
 474     for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) {       \
 475         a_type *cnode = pathp->node;                                    \
 476         if (pathp->cmp < 0) {                                           \
 477             a_type *left = pathp[1].node;                               \
 478             rbtn_left_set(a_type, a_field, cnode, left);                \
 479             if (rbtn_red_get(a_type, a_field, left)) {                  \
 480                 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
 481                 if (rbtn_red_get(a_type, a_field, leftleft)) {          \
 482                     /* Fix up 4-node. */                                \
 483                     a_type *tnode;                                      \
 484                     rbtn_black_set(a_type, a_field, leftleft);          \
 485                     rbtn_rotate_right(a_type, a_field, cnode, tnode);   \
 486                     cnode = tnode;                                      \
 487                 }                                                       \
 488             } else {                                                    \
 489                 return;                                                 \
 490             }                                                           \
 491         } else {                                                        \
 492             a_type *right = pathp[1].node;                              \
 493             rbtn_right_set(a_type, a_field, cnode, right);              \
 494             if (rbtn_red_get(a_type, a_field, right)) {                 \
 495                 a_type *left = rbtn_left_get(a_type, a_field, cnode);   \
 496                 if (rbtn_red_get(a_type, a_field, left)) {              \
 497                     /* Split 4-node. */                                 \
 498                     rbtn_black_set(a_type, a_field, left);              \
 499                     rbtn_black_set(a_type, a_field, right);             \
 500                     rbtn_red_set(a_type, a_field, cnode);               \
 501                 } else {                                                \
 502                     /* Lean left. */                                    \
 503                     a_type *tnode;                                      \
 504                     bool tred = rbtn_red_get(a_type, a_field, cnode);   \
 505                     rbtn_rotate_left(a_type, a_field, cnode, tnode);    \
 506                     rbtn_color_set(a_type, a_field, tnode, tred);       \
 507                     rbtn_red_set(a_type, a_field, cnode);               \
 508                     cnode = tnode;                                      \
 509                 }                                                       \
 510             } else {                                                    \
 511                 return;                                                 \
 512             }                                                           \
 513         }                                                               \
 514         pathp->node = cnode;                                            \
 515     }                                                                   \
 516     /* Set root, and make it black. */                                  \
 517     rbtree->rbt_root = path->node;                                      \
 518     rbtn_black_set(a_type, a_field, rbtree->rbt_root);                  \
 519 }                                                                       \
 520 a_attr void                                                             \
 521 a_prefix##remove(a_rbt_type *rbtree, a_type *node) {                    \
 522     struct {                                                            \
 523         a_type *node;                                                   \
 524         int cmp;                                                        \
 525     } *pathp, *nodep, path[sizeof(void *) << 4];                        \
 526     /* Wind. */                                                         \
 527     nodep = NULL; /* Silence compiler warning. */                       \
 528     path->node = rbtree->rbt_root;                                      \
 529     for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) {      \
 530         int cmp = pathp->cmp = a_cmp(node, pathp->node);                \
 531         if (cmp < 0) {                                                  \
 532             pathp[1].node = rbtn_left_get(a_type, a_field,              \
 533               pathp->node);                                             \
 534         } else {                                                        \
 535             pathp[1].node = rbtn_right_get(a_type, a_field,             \
 536               pathp->node);                                             \
 537             if (cmp == 0) {                                             \
 538                 /* Find node's successor, in preparation for swap. */   \
 539                 pathp->cmp = 1;                                         \
 540                 nodep = pathp;                                          \
 541                 for (pathp++; pathp->node != &rbtree->rbt_nil;          \
 542                   pathp++) {                                            \
 543                     pathp->cmp = -1;                                    \
 544                     pathp[1].node = rbtn_left_get(a_type, a_field,      \
 545                       pathp->node);                                     \
 546                 }                                                       \
 547                 break;                                                  \
 548             }                                                           \
 549         }                                                               \
 550     }                                                                   \
 551     assert(nodep->node == node);                                        \
 552     pathp--;                                                            \
 553     if (pathp->node != node) {                                          \
 554         /* Swap node with its successor. */                             \
 555         bool tred = rbtn_red_get(a_type, a_field, pathp->node);         \
 556         rbtn_color_set(a_type, a_field, pathp->node,                    \
 557           rbtn_red_get(a_type, a_field, node));                         \
 558         rbtn_left_set(a_type, a_field, pathp->node,                     \
 559           rbtn_left_get(a_type, a_field, node));                        \
 560         /* If node's successor is its right child, the following code */\
 561         /* will do the wrong thing for the right child pointer.       */\
 562         /* However, it doesn't matter, because the pointer will be    */\
 563         /* properly set when the successor is pruned.                 */\
 564         rbtn_right_set(a_type, a_field, pathp->node,                    \
 565           rbtn_right_get(a_type, a_field, node));                       \
 566         rbtn_color_set(a_type, a_field, node, tred);                    \
 567         /* The pruned leaf node's child pointers are never accessed   */\
 568         /* again, so don't bother setting them to nil.                */\
 569         nodep->node = pathp->node;                                      \
 570         pathp->node = node;                                             \
 571         if (nodep == path) {                                            \
 572             rbtree->rbt_root = nodep->node;                             \
 573         } else {                                                        \
 574             if (nodep[-1].cmp < 0) {                                    \
 575                 rbtn_left_set(a_type, a_field, nodep[-1].node,          \
 576                   nodep->node);                                         \
 577             } else {                                                    \
 578                 rbtn_right_set(a_type, a_field, nodep[-1].node,         \
 579                   nodep->node);                                         \
 580             }                                                           \
 581         }                                                               \
 582     } else {                                                            \
 583         a_type *left = rbtn_left_get(a_type, a_field, node);            \
 584         if (left != &rbtree->rbt_nil) {                                 \
 585             /* node has no successor, but it has a left child.        */\
 586             /* Splice node out, without losing the left child.        */\
 587             assert(rbtn_red_get(a_type, a_field, node) == false);       \
 588             assert(rbtn_red_get(a_type, a_field, left));                \
 589             rbtn_black_set(a_type, a_field, left);                      \
 590             if (pathp == path) {                                        \
 591                 rbtree->rbt_root = left;                                \
 592             } else {                                                    \
 593                 if (pathp[-1].cmp < 0) {                                \
 594                     rbtn_left_set(a_type, a_field, pathp[-1].node,      \
 595                       left);                                            \
 596                 } else {                                                \
 597                     rbtn_right_set(a_type, a_field, pathp[-1].node,     \
 598                       left);                                            \
 599                 }                                                       \
 600             }                                                           \
 601             return;                                                     \
 602         } else if (pathp == path) {                                     \
 603             /* The tree only contained one node. */                     \
 604             rbtree->rbt_root = &rbtree->rbt_nil;                        \
 605             return;                                                     \
 606         }                                                               \
 607     }                                                                   \
 608     if (rbtn_red_get(a_type, a_field, pathp->node)) {                   \
 609         /* Prune red node, which requires no fixup. */                  \
 610         assert(pathp[-1].cmp < 0);                                      \
 611         rbtn_left_set(a_type, a_field, pathp[-1].node,                  \
 612           &rbtree->rbt_nil);                                            \
 613         return;                                                         \
 614     }                                                                   \
 615     /* The node to be pruned is black, so unwind until balance is     */\
 616     /* restored.                                                      */\
 617     pathp->node = &rbtree->rbt_nil;                                     \
 618     for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) {       \
 619         assert(pathp->cmp != 0);                                        \
 620         if (pathp->cmp < 0) {                                           \
 621             rbtn_left_set(a_type, a_field, pathp->node,                 \
 622               pathp[1].node);                                           \
 623             assert(rbtn_red_get(a_type, a_field, pathp[1].node)         \
 624               == false);                                                \
 625             if (rbtn_red_get(a_type, a_field, pathp->node)) {           \
 626                 a_type *right = rbtn_right_get(a_type, a_field,         \
 627                   pathp->node);                                         \
 628                 a_type *rightleft = rbtn_left_get(a_type, a_field,      \
 629                   right);                                               \
 630                 a_type *tnode;                                          \
 631                 if (rbtn_red_get(a_type, a_field, rightleft)) {         \
 632                     /* In the following diagrams, ||, //, and \\      */\
 633                     /* indicate the path to the removed node.         */\
 634                     /*                                                */\
 635                     /*      ||                                        */\
 636                     /*    pathp(r)                                    */\
 637                     /*  //        \                                   */\
 638                     /* (b)        (b)                                 */\
 639                     /*           /                                    */\
 640                     /*          (r)                                   */\
 641                     /*                                                */\
 642                     rbtn_black_set(a_type, a_field, pathp->node);       \
 643                     rbtn_rotate_right(a_type, a_field, right, tnode);   \
 644                     rbtn_right_set(a_type, a_field, pathp->node, tnode);\
 645                     rbtn_rotate_left(a_type, a_field, pathp->node,      \
 646                       tnode);                                           \
 647                 } else {                                                \
 648                     /*      ||                                        */\
 649                     /*    pathp(r)                                    */\
 650                     /*  //        \                                   */\
 651                     /* (b)        (b)                                 */\
 652                     /*           /                                    */\
 653                     /*          (b)                                   */\
 654                     /*                                                */\
 655                     rbtn_rotate_left(a_type, a_field, pathp->node,      \
 656                       tnode);                                           \
 657                 }                                                       \
 658                 /* Balance restored, but rotation modified subtree    */\
 659                 /* root.                                              */\
 660                 assert((uintptr_t)pathp > (uintptr_t)path);             \
 661                 if (pathp[-1].cmp < 0) {                                \
 662                     rbtn_left_set(a_type, a_field, pathp[-1].node,      \
 663                       tnode);                                           \
 664                 } else {                                                \
 665                     rbtn_right_set(a_type, a_field, pathp[-1].node,     \
 666                       tnode);                                           \
 667                 }                                                       \
 668                 return;                                                 \
 669             } else {                                                    \
 670                 a_type *right = rbtn_right_get(a_type, a_field,         \
 671                   pathp->node);                                         \
 672                 a_type *rightleft = rbtn_left_get(a_type, a_field,      \
 673                   right);                                               \
 674                 if (rbtn_red_get(a_type, a_field, rightleft)) {         \
 675                     /*      ||                                        */\
 676                     /*    pathp(b)                                    */\
 677                     /*  //        \                                   */\
 678                     /* (b)        (b)                                 */\
 679                     /*           /                                    */\
 680                     /*          (r)                                   */\
 681                     a_type *tnode;                                      \
 682                     rbtn_black_set(a_type, a_field, rightleft);         \
 683                     rbtn_rotate_right(a_type, a_field, right, tnode);   \
 684                     rbtn_right_set(a_type, a_field, pathp->node, tnode);\
 685                     rbtn_rotate_left(a_type, a_field, pathp->node,      \
 686                       tnode);                                           \
 687                     /* Balance restored, but rotation modified        */\
 688                     /* subree root, which may actually be the tree    */\
 689                     /* root.                                          */\
 690                     if (pathp == path) {                                \
 691                         /* Set root. */                                 \
 692                         rbtree->rbt_root = tnode;                       \
 693                     } else {                                            \
 694                         if (pathp[-1].cmp < 0) {                        \
 695                             rbtn_left_set(a_type, a_field,              \
 696                               pathp[-1].node, tnode);                   \
 697                         } else {                                        \
 698                             rbtn_right_set(a_type, a_field,             \
 699                               pathp[-1].node, tnode);                   \
 700                         }                                               \
 701                     }                                                   \
 702                     return;                                             \
 703                 } else {                                                \
 704                     /*      ||                                        */\
 705                     /*    pathp(b)                                    */\
 706                     /*  //        \                                   */\
 707                     /* (b)        (b)                                 */\
 708                     /*           /                                    */\
 709                     /*          (b)                                   */\
 710                     a_type *tnode;                                      \
 711                     rbtn_red_set(a_type, a_field, pathp->node);         \
 712                     rbtn_rotate_left(a_type, a_field, pathp->node,      \
 713                       tnode);                                           \
 714                     pathp->node = tnode;                                \
 715                 }                                                       \
 716             }                                                           \
 717         } else {                                                        \
 718             a_type *left;                                               \
 719             rbtn_right_set(a_type, a_field, pathp->node,                \
 720               pathp[1].node);                                           \
 721             left = rbtn_left_get(a_type, a_field, pathp->node);         \
 722             if (rbtn_red_get(a_type, a_field, left)) {                  \
 723                 a_type *tnode;                                          \
 724                 a_type *leftright = rbtn_right_get(a_type, a_field,     \
 725                   left);                                                \
 726                 a_type *leftrightleft = rbtn_left_get(a_type, a_field,  \
 727                   leftright);                                           \
 728                 if (rbtn_red_get(a_type, a_field, leftrightleft)) {     \
 729                     /*      ||                                        */\
 730                     /*    pathp(b)                                    */\
 731                     /*   /        \\                                  */\
 732                     /* (r)        (b)                                 */\
 733                     /*   \                                            */\
 734                     /*   (b)                                          */\
 735                     /*   /                                            */\
 736                     /* (r)                                            */\
 737                     a_type *unode;                                      \
 738                     rbtn_black_set(a_type, a_field, leftrightleft);     \
 739                     rbtn_rotate_right(a_type, a_field, pathp->node,     \
 740                       unode);                                           \
 741                     rbtn_rotate_right(a_type, a_field, pathp->node,     \
 742                       tnode);                                           \
 743                     rbtn_right_set(a_type, a_field, unode, tnode);      \
 744                     rbtn_rotate_left(a_type, a_field, unode, tnode);    \
 745                 } else {                                                \
 746                     /*      ||                                        */\
 747                     /*    pathp(b)                                    */\
 748                     /*   /        \\                                  */\
 749                     /* (r)        (b)                                 */\
 750                     /*   \                                            */\
 751                     /*   (b)                                          */\
 752                     /*   /                                            */\
 753                     /* (b)                                            */\
 754                     assert(leftright != &rbtree->rbt_nil);              \
 755                     rbtn_red_set(a_type, a_field, leftright);           \
 756                     rbtn_rotate_right(a_type, a_field, pathp->node,     \
 757                       tnode);                                           \
 758                     rbtn_black_set(a_type, a_field, tnode);             \
 759                 }                                                       \
 760                 /* Balance restored, but rotation modified subtree    */\
 761                 /* root, which may actually be the tree root.         */\
 762                 if (pathp == path) {                                    \
 763                     /* Set root. */                                     \
 764                     rbtree->rbt_root = tnode;                           \
 765                 } else {                                                \
 766                     if (pathp[-1].cmp < 0) {                            \
 767                         rbtn_left_set(a_type, a_field, pathp[-1].node,  \
 768                           tnode);                                       \
 769                     } else {                                            \
 770                         rbtn_right_set(a_type, a_field, pathp[-1].node, \
 771                           tnode);                                       \
 772                     }                                                   \
 773                 }                                                       \
 774                 return;                                                 \
 775             } else if (rbtn_red_get(a_type, a_field, pathp->node)) {    \
 776                 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
 777                 if (rbtn_red_get(a_type, a_field, leftleft)) {          \
 778                     /*        ||                                      */\
 779                     /*      pathp(r)                                  */\
 780                     /*     /        \\                                */\
 781                     /*   (b)        (b)                               */\
 782                     /*   /                                            */\
 783                     /* (r)                                            */\
 784                     a_type *tnode;                                      \
 785                     rbtn_black_set(a_type, a_field, pathp->node);       \
 786                     rbtn_red_set(a_type, a_field, left);                \
 787                     rbtn_black_set(a_type, a_field, leftleft);          \
 788                     rbtn_rotate_right(a_type, a_field, pathp->node,     \
 789                       tnode);                                           \
 790                     /* Balance restored, but rotation modified        */\
 791                     /* subtree root.                                  */\
 792                     assert((uintptr_t)pathp > (uintptr_t)path);         \
 793                     if (pathp[-1].cmp < 0) {                            \
 794                         rbtn_left_set(a_type, a_field, pathp[-1].node,  \
 795                           tnode);                                       \
 796                     } else {                                            \
 797                         rbtn_right_set(a_type, a_field, pathp[-1].node, \
 798                           tnode);                                       \
 799                     }                                                   \
 800                     return;                                             \
 801                 } else {                                                \
 802                     /*        ||                                      */\
 803                     /*      pathp(r)                                  */\
 804                     /*     /        \\                                */\
 805                     /*   (b)        (b)                               */\
 806                     /*   /                                            */\
 807                     /* (b)                                            */\
 808                     rbtn_red_set(a_type, a_field, left);                \
 809                     rbtn_black_set(a_type, a_field, pathp->node);       \
 810                     /* Balance restored. */                             \
 811                     return;                                             \
 812                 }                                                       \
 813             } else {                                                    \
 814                 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\
 815                 if (rbtn_red_get(a_type, a_field, leftleft)) {          \
 816                     /*               ||                               */\
 817                     /*             pathp(b)                           */\
 818                     /*            /        \\                         */\
 819                     /*          (b)        (b)                        */\
 820                     /*          /                                     */\
 821                     /*        (r)                                     */\
 822                     a_type *tnode;                                      \
 823                     rbtn_black_set(a_type, a_field, leftleft);          \
 824                     rbtn_rotate_right(a_type, a_field, pathp->node,     \
 825                       tnode);                                           \
 826                     /* Balance restored, but rotation modified        */\
 827                     /* subtree root, which may actually be the tree   */\
 828                     /* root.                                          */\
 829                     if (pathp == path) {                                \
 830                         /* Set root. */                                 \
 831                         rbtree->rbt_root = tnode;                       \
 832                     } else {                                            \
 833                         if (pathp[-1].cmp < 0) {                        \
 834                             rbtn_left_set(a_type, a_field,              \
 835                               pathp[-1].node, tnode);                   \
 836                         } else {                                        \
 837                             rbtn_right_set(a_type, a_field,             \
 838                               pathp[-1].node, tnode);                   \
 839                         }                                               \
 840                     }                                                   \
 841                     return;                                             \
 842                 } else {                                                \
 843                     /*               ||                               */\
 844                     /*             pathp(b)                           */\
 845                     /*            /        \\                         */\
 846                     /*          (b)        (b)                        */\
 847                     /*          /                                     */\
 848                     /*        (b)                                     */\
 849                     rbtn_red_set(a_type, a_field, left);                \
 850                 }                                                       \
 851             }                                                           \
 852         }                                                               \
 853     }                                                                   \
 854     /* Set root. */                                                     \
 855     rbtree->rbt_root = path->node;                                      \
 856     assert(rbtn_red_get(a_type, a_field, rbtree->rbt_root) == false);   \
 857 }                                                                       \
 858 a_attr a_type *                                                         \
 859 a_prefix##iter_recurse(a_rbt_type *rbtree, a_type *node,                \
 860   a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) {           \
 861     if (node == &rbtree->rbt_nil) {                                     \
 862         return (&rbtree->rbt_nil);                                      \
 863     } else {                                                            \
 864         a_type *ret;                                                    \
 865         if ((ret = a_prefix##iter_recurse(rbtree, rbtn_left_get(a_type, \
 866           a_field, node), cb, arg)) != &rbtree->rbt_nil                 \
 867           || (ret = cb(rbtree, node, arg)) != NULL) {                   \
 868             return (ret);                                               \
 869         }                                                               \
 870         return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type,   \
 871           a_field, node), cb, arg));                                    \
 872     }                                                                   \
 873 }                                                                       \
 874 a_attr a_type *                                                         \
 875 a_prefix##iter_start(a_rbt_type *rbtree, a_type *start, a_type *node,   \
 876   a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) {           \
 877     int cmp = a_cmp(start, node);                                       \
 878     if (cmp < 0) {                                                      \
 879         a_type *ret;                                                    \
 880         if ((ret = a_prefix##iter_start(rbtree, start,                  \
 881           rbtn_left_get(a_type, a_field, node), cb, arg)) !=            \
 882           &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) {  \
 883             return (ret);                                               \
 884         }                                                               \
 885         return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type,   \
 886           a_field, node), cb, arg));                                    \
 887     } else if (cmp > 0) {                                               \
 888         return (a_prefix##iter_start(rbtree, start,                     \
 889           rbtn_right_get(a_type, a_field, node), cb, arg));             \
 890     } else {                                                            \
 891         a_type *ret;                                                    \
 892         if ((ret = cb(rbtree, node, arg)) != NULL) {                    \
 893             return (ret);                                               \
 894         }                                                               \
 895         return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type,   \
 896           a_field, node), cb, arg));                                    \
 897     }                                                                   \
 898 }                                                                       \
 899 a_attr a_type *                                                         \
 900 a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)(        \
 901   a_rbt_type *, a_type *, void *), void *arg) {                         \
 902     a_type *ret;                                                        \
 903     if (start != NULL) {                                                \
 904         ret = a_prefix##iter_start(rbtree, start, rbtree->rbt_root,     \
 905           cb, arg);                                                     \
 906     } else {                                                            \
 907         ret = a_prefix##iter_recurse(rbtree, rbtree->rbt_root, cb, arg);\
 908     }                                                                   \
 909     if (ret == &rbtree->rbt_nil) {                                      \
 910         ret = NULL;                                                     \
 911     }                                                                   \
 912     return (ret);                                                       \
 913 }                                                                       \
 914 a_attr a_type *                                                         \
 915 a_prefix##reverse_iter_recurse(a_rbt_type *rbtree, a_type *node,        \
 916   a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) {           \
 917     if (node == &rbtree->rbt_nil) {                                     \
 918         return (&rbtree->rbt_nil);                                      \
 919     } else {                                                            \
 920         a_type *ret;                                                    \
 921         if ((ret = a_prefix##reverse_iter_recurse(rbtree,               \
 922           rbtn_right_get(a_type, a_field, node), cb, arg)) !=           \
 923           &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) {  \
 924             return (ret);                                               \
 925         }                                                               \
 926         return (a_prefix##reverse_iter_recurse(rbtree,                  \
 927           rbtn_left_get(a_type, a_field, node), cb, arg));              \
 928     }                                                                   \
 929 }                                                                       \
 930 a_attr a_type *                                                         \
 931 a_prefix##reverse_iter_start(a_rbt_type *rbtree, a_type *start,         \
 932   a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *),          \
 933   void *arg) {                                                          \
 934     int cmp = a_cmp(start, node);                                       \
 935     if (cmp > 0) {                                                      \
 936         a_type *ret;                                                    \
 937         if ((ret = a_prefix##reverse_iter_start(rbtree, start,          \
 938           rbtn_right_get(a_type, a_field, node), cb, arg)) !=           \
 939           &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) {  \
 940             return (ret);                                               \
 941         }                                                               \
 942         return (a_prefix##reverse_iter_recurse(rbtree,                  \
 943           rbtn_left_get(a_type, a_field, node), cb, arg));              \
 944     } else if (cmp < 0) {                                               \
 945         return (a_prefix##reverse_iter_start(rbtree, start,             \
 946           rbtn_left_get(a_type, a_field, node), cb, arg));              \
 947     } else {                                                            \
 948         a_type *ret;                                                    \
 949         if ((ret = cb(rbtree, node, arg)) != NULL) {                    \
 950             return (ret);                                               \
 951         }                                                               \
 952         return (a_prefix##reverse_iter_recurse(rbtree,                  \
 953           rbtn_left_get(a_type, a_field, node), cb, arg));              \
 954     }                                                                   \
 955 }                                                                       \
 956 a_attr a_type *                                                         \
 957 a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start,               \
 958   a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) {           \
 959     a_type *ret;                                                        \
 960     if (start != NULL) {                                                \
 961         ret = a_prefix##reverse_iter_start(rbtree, start,               \
 962           rbtree->rbt_root, cb, arg);                                   \
 963     } else {                                                            \
 964         ret = a_prefix##reverse_iter_recurse(rbtree, rbtree->rbt_root,  \
 965           cb, arg);                                                     \
 966     }                                                                   \
 967     if (ret == &rbtree->rbt_nil) {                                      \
 968         ret = NULL;                                                     \
 969     }                                                                   \
 970     return (ret);                                                       \
 971 }
 972
 973 #endif /* RB_H_ */