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