lib/libc/stdlib/rb.h

   1 /******************************************************************************
   2  *
   3  * Copyright (C) 2008 Jason Evans <jasone@FreeBSD.org>.
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice(s), this list of conditions and the following disclaimer
  11  *    unmodified other than the allowable addition of one or more
  12  *    copyright notices.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice(s), this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
  19  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  21  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
  22  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  25  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  26  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
  27  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  28  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  *
  30  ******************************************************************************
  31  *
  32  * cpp macro implementation of left-leaning red-black trees.
  33  *
  34  * Usage:
  35  *
  36  *   (Optional, see assert(3).)
  37  *   #define NDEBUG
  38  *
  39  *   (Required.)
  40  *   #include <assert.h>
  41  *   #include <rb.h>
  42  *   ...
  43  *
  44  * All operations are done non-recursively.  Parent pointers are not used, and
  45  * color bits are stored in the least significant bit of right-child pointers,
  46  * thus making node linkage as compact as is possible for red-black trees.
  47  *
  48  * Some macros use a comparison function pointer, which is expected to have the
  49  * following prototype:
  50  *
  51  *   int (a_cmp *)(a_type *a_node, a_type *a_other);
  52  *                         ^^^^^^
  53  *                      or a_key
  54  *
  55  * Interpretation of comparision function return values:
  56  *
  57  *   -1 : a_node <  a_other
  58  *    0 : a_node == a_other
  59  *    1 : a_node >  a_other
  60  *
  61  * In all cases, the a_node or a_key macro argument is the first argument to the
  62  * comparison function, which makes it possible to write comparison functions
  63  * that treat the first argument specially.
  64  *
  65  ******************************************************************************/
  66
  67 #ifndef RB_H_
  68 #define RB_H_
  69
  70 #include <sys/cdefs.h>
  71 __FBSDID("$FreeBSD$");
  72
  73 /* Node structure. */
  74 #define rb_node(a_type)                                                 \
  75 struct {                                                                \
  76     a_type *rbn_left;                                                   \
  77     a_type *rbn_right_red;                                              \
  78 }
  79
  80 /* Root structure. */
  81 #define rb_tree(a_type)                                                 \
  82 struct {                                                                \
  83     a_type *rbt_root;                                                   \
  84     a_type rbt_nil;                                                     \
  85 }
  86
  87 /* Left accessors. */
  88 #define rbp_left_get(a_type, a_field, a_node)                           \
  89     ((a_node)->a_field.rbn_left)
  90 #define rbp_left_set(a_type, a_field, a_node, a_left) do {              \
  91     (a_node)->a_field.rbn_left = a_left;                                \
  92 } while (0)
  93
  94 /* Right accessors. */
  95 #define rbp_right_get(a_type, a_field, a_node)                          \
  96     ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red)           \
  97       & ((ssize_t)-2)))
  98 #define rbp_right_set(a_type, a_field, a_node, a_right) do {            \
  99     (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right) \
 100       | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1))); \
 101 } while (0)
 102
 103 /* Color accessors. */
 104 #define rbp_red_get(a_type, a_field, a_node)                            \
 105     ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red)              \
 106       & ((size_t)1)))
 107 #define rbp_color_set(a_type, a_field, a_node, a_red) do {              \
 108     (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t)          \
 109       (a_node)->a_field.rbn_right_red) & ((ssize_t)-2))                 \
 110       | ((ssize_t)a_red));                                              \
 111 } while (0)
 112 #define rbp_red_set(a_type, a_field, a_node) do {                       \
 113     (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t)          \
 114       (a_node)->a_field.rbn_right_red) | ((size_t)1));                  \
 115 } while (0)
 116 #define rbp_black_set(a_type, a_field, a_node) do {                     \
 117     (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t)           \
 118       (a_node)->a_field.rbn_right_red) & ((ssize_t)-2));                \
 119 } while (0)
 120
 121 /* Node initializer. */
 122 #define rbp_node_new(a_type, a_field, a_tree, a_node) do {              \
 123     rbp_left_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil);        \
 124     rbp_right_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil);       \
 125     rbp_red_set(a_type, a_field, (a_node));                             \
 126 } while (0)
 127
 128 /* Tree initializer. */
 129 #define rb_new(a_type, a_field, a_tree) do {                            \
 130     (a_tree)->rbt_root = &(a_tree)->rbt_nil;                            \
 131     rbp_node_new(a_type, a_field, a_tree, &(a_tree)->rbt_nil);          \
 132     rbp_black_set(a_type, a_field, &(a_tree)->rbt_nil);                 \
 133 } while (0)
 134
 135 /* Tree operations. */
 136 #define rbp_black_height(a_type, a_field, a_tree, r_height) do {        \
 137     a_type *rbp_bh_t;                                                   \
 138     for (rbp_bh_t = (a_tree)->rbt_root, (r_height) = 0;                 \
 139       rbp_bh_t != &(a_tree)->rbt_nil;                                   \
 140       rbp_bh_t = rbp_left_get(a_type, a_field, rbp_bh_t)) {             \
 141         if (rbp_red_get(a_type, a_field, rbp_bh_t) == false) {          \
 142             (r_height)++;                                               \
 143         }                                                               \
 144     }                                                                   \
 145 } while (0)
 146
 147 #define rbp_first(a_type, a_field, a_tree, a_root, r_node) do {         \
 148     for ((r_node) = (a_root);                                           \
 149       rbp_left_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil;    \
 150       (r_node) = rbp_left_get(a_type, a_field, (r_node))) {             \
 151     }                                                                   \
 152 } while (0)
 153
 154 #define rbp_last(a_type, a_field, a_tree, a_root, r_node) do {          \
 155     for ((r_node) = (a_root);                                           \
 156       rbp_right_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil;   \
 157       (r_node) = rbp_right_get(a_type, a_field, (r_node))) {            \
 158     }                                                                   \
 159 } while (0)
 160
 161 #define rbp_next(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {   \
 162     if (rbp_right_get(a_type, a_field, (a_node))                        \
 163       != &(a_tree)->rbt_nil) {                                          \
 164         rbp_first(a_type, a_field, a_tree, rbp_right_get(a_type,        \
 165           a_field, (a_node)), (r_node));                                \
 166     } else {                                                            \
 167         a_type *rbp_n_t = (a_tree)->rbt_root;                           \
 168         assert(rbp_n_t != &(a_tree)->rbt_nil);                          \
 169         (r_node) = &(a_tree)->rbt_nil;                                  \
 170         while (true) {                                                  \
 171             int rbp_n_cmp = (a_cmp)((a_node), rbp_n_t);                 \
 172             if (rbp_n_cmp < 0) {                                        \
 173                 (r_node) = rbp_n_t;                                     \
 174                 rbp_n_t = rbp_left_get(a_type, a_field, rbp_n_t);       \
 175             } else if (rbp_n_cmp > 0) {                                 \
 176                 rbp_n_t = rbp_right_get(a_type, a_field, rbp_n_t);      \
 177             } else {                                                    \
 178                 break;                                                  \
 179             }                                                           \
 180             assert(rbp_n_t != &(a_tree)->rbt_nil);                      \
 181         }                                                               \
 182     }                                                                   \
 183 } while (0)
 184
 185 #define rbp_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {   \
 186     if (rbp_left_get(a_type, a_field, (a_node)) != &(a_tree)->rbt_nil) {\
 187         rbp_last(a_type, a_field, a_tree, rbp_left_get(a_type,          \
 188           a_field, (a_node)), (r_node));                                \
 189     } else {                                                            \
 190         a_type *rbp_p_t = (a_tree)->rbt_root;                           \
 191         assert(rbp_p_t != &(a_tree)->rbt_nil);                          \
 192         (r_node) = &(a_tree)->rbt_nil;                                  \
 193         while (true) {                                                  \
 194             int rbp_p_cmp = (a_cmp)((a_node), rbp_p_t);                 \
 195             if (rbp_p_cmp < 0) {                                        \
 196                 rbp_p_t = rbp_left_get(a_type, a_field, rbp_p_t);       \
 197             } else if (rbp_p_cmp > 0) {                                 \
 198                 (r_node) = rbp_p_t;                                     \
 199                 rbp_p_t = rbp_right_get(a_type, a_field, rbp_p_t);      \
 200             } else {                                                    \
 201                 break;                                                  \
 202             }                                                           \
 203             assert(rbp_p_t != &(a_tree)->rbt_nil);                      \
 204         }                                                               \
 205     }                                                                   \
 206 } while (0)
 207
 208 #define rb_first(a_type, a_field, a_tree, r_node) do {                  \
 209     rbp_first(a_type, a_field, a_tree, (a_tree)->rbt_root, (r_node));   \
 210     if ((r_node) == &(a_tree)->rbt_nil) {                               \
 211         (r_node) = NULL;                                                \
 212     }                                                                   \
 213 } while (0)
 214
 215 #define rb_last(a_type, a_field, a_tree, r_node) do {                   \
 216     rbp_last(a_type, a_field, a_tree, (a_tree)->rbt_root, r_node);      \
 217     if ((r_node) == &(a_tree)->rbt_nil) {                               \
 218         (r_node) = NULL;                                                \
 219     }                                                                   \
 220 } while (0)
 221
 222 #define rb_next(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {    \
 223     rbp_next(a_type, a_field, a_cmp, a_tree, (a_node), (r_node));       \
 224     if ((r_node) == &(a_tree)->rbt_nil) {                               \
 225         (r_node) = NULL;                                                \
 226     }                                                                   \
 227 } while (0)
 228
 229 #define rb_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {    \
 230     rbp_prev(a_type, a_field, a_cmp, a_tree, (a_node), (r_node));       \
 231     if ((r_node) == &(a_tree)->rbt_nil) {                               \
 232         (r_node) = NULL;                                                \
 233     }                                                                   \
 234 } while (0)
 235
 236 #define rb_search(a_type, a_field, a_cmp, a_tree, a_key, r_node) do {   \
 237     int rbp_se_cmp;                                                     \
 238     (r_node) = (a_tree)->rbt_root;                                      \
 239     while ((r_node) != &(a_tree)->rbt_nil                               \
 240       && (rbp_se_cmp = (a_cmp)((a_key), (r_node))) != 0) {              \
 241         if (rbp_se_cmp < 0) {                                           \
 242             (r_node) = rbp_left_get(a_type, a_field, (r_node));         \
 243         } else {                                                        \
 244             (r_node) = rbp_right_get(a_type, a_field, (r_node));        \
 245         }                                                               \
 246     }                                                                   \
 247     if ((r_node) == &(a_tree)->rbt_nil) {                               \
 248         (r_node) = NULL;                                                \
 249     }                                                                   \
 250 } while (0)
 251
 252 /*
 253  * Find a match if it exists.  Otherwise, find the next greater node, if one
 254  * exists.
 255  */
 256 #define rb_nsearch(a_type, a_field, a_cmp, a_tree, a_key, r_node) do {  \
 257     a_type *rbp_ns_t = (a_tree)->rbt_root;                              \
 258     (r_node) = NULL;                                                    \
 259     while (rbp_ns_t != &(a_tree)->rbt_nil) {                            \
 260         int rbp_ns_cmp = (a_cmp)((a_key), rbp_ns_t);                    \
 261         if (rbp_ns_cmp < 0) {                                           \
 262             (r_node) = rbp_ns_t;                                        \
 263             rbp_ns_t = rbp_left_get(a_type, a_field, rbp_ns_t);         \
 264         } else if (rbp_ns_cmp > 0) {                                    \
 265             rbp_ns_t = rbp_right_get(a_type, a_field, rbp_ns_t);        \
 266         } else {                                                        \
 267             (r_node) = rbp_ns_t;                                        \
 268             break;                                                      \
 269         }                                                               \
 270     }                                                                   \
 271 } while (0)
 272
 273 /*
 274  * Find a match if it exists.  Otherwise, find the previous lesser node, if one
 275  * exists.
 276  */
 277 #define rb_psearch(a_type, a_field, a_cmp, a_tree, a_key, r_node) do {  \
 278     a_type *rbp_ps_t = (a_tree)->rbt_root;                              \
 279     (r_node) = NULL;                                                    \
 280     while (rbp_ps_t != &(a_tree)->rbt_nil) {                            \
 281         int rbp_ps_cmp = (a_cmp)((a_key), rbp_ps_t);                    \
 282         if (rbp_ps_cmp < 0) {                                           \
 283             rbp_ps_t = rbp_left_get(a_type, a_field, rbp_ps_t);         \
 284         } else if (rbp_ps_cmp > 0) {                                    \
 285             (r_node) = rbp_ps_t;                                        \
 286             rbp_ps_t = rbp_right_get(a_type, a_field, rbp_ps_t);        \
 287         } else {                                                        \
 288             (r_node) = rbp_ps_t;                                        \
 289             break;                                                      \
 290         }                                                               \
 291     }                                                                   \
 292 } while (0)
 293
 294 #define rbp_rotate_left(a_type, a_field, a_node, r_node) do {           \
 295     (r_node) = rbp_right_get(a_type, a_field, (a_node));                \
 296     rbp_right_set(a_type, a_field, (a_node),                            \
 297       rbp_left_get(a_type, a_field, (r_node)));                         \
 298     rbp_left_set(a_type, a_field, (r_node), (a_node));                  \
 299 } while (0)
 300
 301 #define rbp_rotate_right(a_type, a_field, a_node, r_node) do {          \
 302     (r_node) = rbp_left_get(a_type, a_field, (a_node));                 \
 303     rbp_left_set(a_type, a_field, (a_node),                             \
 304       rbp_right_get(a_type, a_field, (r_node)));                        \
 305     rbp_right_set(a_type, a_field, (r_node), (a_node));                 \
 306 } while (0)
 307
 308 #define rbp_lean_left(a_type, a_field, a_node, r_node) do {             \
 309     bool rbp_ll_red;                                                    \
 310     rbp_rotate_left(a_type, a_field, (a_node), (r_node));               \
 311     rbp_ll_red = rbp_red_get(a_type, a_field, (a_node));                \
 312     rbp_color_set(a_type, a_field, (r_node), rbp_ll_red);               \
 313     rbp_red_set(a_type, a_field, (a_node));                             \
 314 } while (0)
 315
 316 #define rbp_lean_right(a_type, a_field, a_node, r_node) do {            \
 317     bool rbp_lr_red;                                                    \
 318     rbp_rotate_right(a_type, a_field, (a_node), (r_node));              \
 319     rbp_lr_red = rbp_red_get(a_type, a_field, (a_node));                \
 320     rbp_color_set(a_type, a_field, (r_node), rbp_lr_red);               \
 321     rbp_red_set(a_type, a_field, (a_node));                             \
 322 } while (0)
 323
 324 #define rbp_move_red_left(a_type, a_field, a_node, r_node) do {         \
 325     a_type *rbp_mrl_t, *rbp_mrl_u;                                      \
 326     rbp_mrl_t = rbp_left_get(a_type, a_field, (a_node));                \
 327     rbp_red_set(a_type, a_field, rbp_mrl_t);                            \
 328     rbp_mrl_t = rbp_right_get(a_type, a_field, (a_node));               \
 329     rbp_mrl_u = rbp_left_get(a_type, a_field, rbp_mrl_t);               \
 330     if (rbp_red_get(a_type, a_field, rbp_mrl_u)) {                      \
 331         rbp_rotate_right(a_type, a_field, rbp_mrl_t, rbp_mrl_u);        \
 332         rbp_right_set(a_type, a_field, (a_node), rbp_mrl_u);            \
 333         rbp_rotate_left(a_type, a_field, (a_node), (r_node));           \
 334         rbp_mrl_t = rbp_right_get(a_type, a_field, (a_node));           \
 335         if (rbp_red_get(a_type, a_field, rbp_mrl_t)) {                  \
 336             rbp_black_set(a_type, a_field, rbp_mrl_t);                  \
 337             rbp_red_set(a_type, a_field, (a_node));                     \
 338             rbp_rotate_left(a_type, a_field, (a_node), rbp_mrl_t);      \
 339             rbp_left_set(a_type, a_field, (r_node), rbp_mrl_t);         \
 340         } else {                                                        \
 341             rbp_black_set(a_type, a_field, (a_node));                   \
 342         }                                                               \
 343     } else {                                                            \
 344         rbp_red_set(a_type, a_field, (a_node));                         \
 345         rbp_rotate_left(a_type, a_field, (a_node), (r_node));           \
 346     }                                                                   \
 347 } while (0)
 348
 349 #define rbp_move_red_right(a_type, a_field, a_node, r_node) do {        \
 350     a_type *rbp_mrr_t;                                                  \
 351     rbp_mrr_t = rbp_left_get(a_type, a_field, (a_node));                \
 352     if (rbp_red_get(a_type, a_field, rbp_mrr_t)) {                      \
 353         a_type *rbp_mrr_u, *rbp_mrr_v;                                  \
 354         rbp_mrr_u = rbp_right_get(a_type, a_field, rbp_mrr_t);          \
 355         rbp_mrr_v = rbp_left_get(a_type, a_field, rbp_mrr_u);           \
 356         if (rbp_red_get(a_type, a_field, rbp_mrr_v)) {                  \
 357             rbp_color_set(a_type, a_field, rbp_mrr_u,                   \
 358               rbp_red_get(a_type, a_field, (a_node)));                  \
 359             rbp_black_set(a_type, a_field, rbp_mrr_v);                  \
 360             rbp_rotate_left(a_type, a_field, rbp_mrr_t, rbp_mrr_u);     \
 361             rbp_left_set(a_type, a_field, (a_node), rbp_mrr_u);         \
 362             rbp_rotate_right(a_type, a_field, (a_node), (r_node));      \
 363             rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t);      \
 364             rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t);        \
 365         } else {                                                        \
 366             rbp_color_set(a_type, a_field, rbp_mrr_t,                   \
 367               rbp_red_get(a_type, a_field, (a_node)));                  \
 368             rbp_red_set(a_type, a_field, rbp_mrr_u);                    \
 369             rbp_rotate_right(a_type, a_field, (a_node), (r_node));      \
 370             rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t);      \
 371             rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t);        \
 372         }                                                               \
 373         rbp_red_set(a_type, a_field, (a_node));                         \
 374     } else {                                                            \
 375         rbp_red_set(a_type, a_field, rbp_mrr_t);                        \
 376         rbp_mrr_t = rbp_left_get(a_type, a_field, rbp_mrr_t);           \
 377         if (rbp_red_get(a_type, a_field, rbp_mrr_t)) {                  \
 378             rbp_black_set(a_type, a_field, rbp_mrr_t);                  \
 379             rbp_rotate_right(a_type, a_field, (a_node), (r_node));      \
 380             rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t);      \
 381             rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t);        \
 382         } else {                                                        \
 383             rbp_rotate_left(a_type, a_field, (a_node), (r_node));       \
 384         }                                                               \
 385     }                                                                   \
 386 } while (0)
 387
 388 #define rb_insert(a_type, a_field, a_cmp, a_tree, a_node) do {          \
 389     a_type rbp_i_s;                                                     \
 390     a_type *rbp_i_g, *rbp_i_p, *rbp_i_c, *rbp_i_t, *rbp_i_u;            \
 391     int rbp_i_cmp = 0;                                                  \
 392     rbp_i_g = &(a_tree)->rbt_nil;                                       \
 393     rbp_left_set(a_type, a_field, &rbp_i_s, (a_tree)->rbt_root);        \
 394     rbp_right_set(a_type, a_field, &rbp_i_s, &(a_tree)->rbt_nil);       \
 395     rbp_black_set(a_type, a_field, &rbp_i_s);                           \
 396     rbp_i_p = &rbp_i_s;                                                 \
 397     rbp_i_c = (a_tree)->rbt_root;                                       \
 398     /* Iteratively search down the tree for the insertion point,      */\
 399     /* splitting 4-nodes as they are encountered.  At the end of each */\
 400     /* iteration, rbp_i_g->rbp_i_p->rbp_i_c is a 3-level path down    */\
 401     /* the tree, assuming a sufficiently deep tree.                   */\
 402     while (rbp_i_c != &(a_tree)->rbt_nil) {                             \
 403         rbp_i_t = rbp_left_get(a_type, a_field, rbp_i_c);               \
 404         rbp_i_u = rbp_left_get(a_type, a_field, rbp_i_t);               \
 405         if (rbp_red_get(a_type, a_field, rbp_i_t)                       \
 406           && rbp_red_get(a_type, a_field, rbp_i_u)) {                   \
 407             /* rbp_i_c is the top of a logical 4-node, so split it.   */\
 408             /* This iteration does not move down the tree, due to the */\
 409             /* disruptiveness of node splitting.                      */\
 410             /*                                                        */\
 411             /* Rotate right.                                          */\
 412             rbp_rotate_right(a_type, a_field, rbp_i_c, rbp_i_t);        \
 413             /* Pass red links up one level.                           */\
 414             rbp_i_u = rbp_left_get(a_type, a_field, rbp_i_t);           \
 415             rbp_black_set(a_type, a_field, rbp_i_u);                    \
 416             if (rbp_left_get(a_type, a_field, rbp_i_p) == rbp_i_c) {    \
 417                 rbp_left_set(a_type, a_field, rbp_i_p, rbp_i_t);        \
 418                 rbp_i_c = rbp_i_t;                                      \
 419             } else {                                                    \
 420                 /* rbp_i_c was the right child of rbp_i_p, so rotate  */\
 421                 /* left in order to maintain the left-leaning         */\
 422                 /* invariant.                                         */\
 423                 assert(rbp_right_get(a_type, a_field, rbp_i_p)          \
 424                   == rbp_i_c);                                          \
 425                 rbp_right_set(a_type, a_field, rbp_i_p, rbp_i_t);       \
 426                 rbp_lean_left(a_type, a_field, rbp_i_p, rbp_i_u);       \
 427                 if (rbp_left_get(a_type, a_field, rbp_i_g) == rbp_i_p) {\
 428                     rbp_left_set(a_type, a_field, rbp_i_g, rbp_i_u);    \
 429                 } else {                                                \
 430                     assert(rbp_right_get(a_type, a_field, rbp_i_g)      \
 431                       == rbp_i_p);                                      \
 432                     rbp_right_set(a_type, a_field, rbp_i_g, rbp_i_u);   \
 433                 }                                                       \
 434                 rbp_i_p = rbp_i_u;                                      \
 435                 rbp_i_cmp = (a_cmp)((a_node), rbp_i_p);                 \
 436                 if (rbp_i_cmp < 0) {                                    \
 437                     rbp_i_c = rbp_left_get(a_type, a_field, rbp_i_p);   \
 438                 } else {                                                \
 439                     assert(rbp_i_cmp > 0);                              \
 440                     rbp_i_c = rbp_right_get(a_type, a_field, rbp_i_p);  \
 441                 }                                                       \
 442                 continue;                                               \
 443             }                                                           \
 444         }                                                               \
 445         rbp_i_g = rbp_i_p;                                              \
 446         rbp_i_p = rbp_i_c;                                              \
 447         rbp_i_cmp = (a_cmp)((a_node), rbp_i_c);                         \
 448         if (rbp_i_cmp < 0) {                                            \
 449             rbp_i_c = rbp_left_get(a_type, a_field, rbp_i_c);           \
 450         } else {                                                        \
 451             assert(rbp_i_cmp > 0);                                      \
 452             rbp_i_c = rbp_right_get(a_type, a_field, rbp_i_c);          \
 453         }                                                               \
 454     }                                                                   \
 455     /* rbp_i_p now refers to the node under which to insert.          */\
 456     rbp_node_new(a_type, a_field, a_tree, (a_node));                    \
 457     if (rbp_i_cmp > 0) {                                                \
 458         rbp_right_set(a_type, a_field, rbp_i_p, (a_node));              \
 459         rbp_lean_left(a_type, a_field, rbp_i_p, rbp_i_t);               \
 460         if (rbp_left_get(a_type, a_field, rbp_i_g) == rbp_i_p) {        \
 461             rbp_left_set(a_type, a_field, rbp_i_g, rbp_i_t);            \
 462         } else if (rbp_right_get(a_type, a_field, rbp_i_g) == rbp_i_p) {\
 463             rbp_right_set(a_type, a_field, rbp_i_g, rbp_i_t);           \
 464         }                                                               \
 465     } else {                                                            \
 466         rbp_left_set(a_type, a_field, rbp_i_p, (a_node));               \
 467     }                                                                   \
 468     /* Update the root and make sure that it is black.                */\
 469     (a_tree)->rbt_root = rbp_left_get(a_type, a_field, &rbp_i_s);       \
 470     rbp_black_set(a_type, a_field, (a_tree)->rbt_root);                 \
 471 } while (0)
 472
 473 #define rb_remove(a_type, a_field, a_cmp, a_tree, a_node) do {          \
 474     a_type rbp_r_s;                                                     \
 475     a_type *rbp_r_p, *rbp_r_c, *rbp_r_xp, *rbp_r_t, *rbp_r_u;           \
 476     int rbp_r_cmp;                                                      \
 477     rbp_left_set(a_type, a_field, &rbp_r_s, (a_tree)->rbt_root);        \
 478     rbp_right_set(a_type, a_field, &rbp_r_s, &(a_tree)->rbt_nil);       \
 479     rbp_black_set(a_type, a_field, &rbp_r_s);                           \
 480     rbp_r_p = &rbp_r_s;                                                 \
 481     rbp_r_c = (a_tree)->rbt_root;                                       \
 482     rbp_r_xp = &(a_tree)->rbt_nil;                                      \
 483     /* Iterate down the tree, but always transform 2-nodes to 3- or   */\
 484     /* 4-nodes in order to maintain the invariant that the current    */\
 485     /* node is not a 2-node.  This allows simple deletion once a leaf */\
 486     /* is reached.  Handle the root specially though, since there may */\
 487     /* be no way to convert it from a 2-node to a 3-node.             */\
 488     rbp_r_cmp = (a_cmp)((a_node), rbp_r_c);                             \
 489     if (rbp_r_cmp < 0) {                                                \
 490         rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c);               \
 491         rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);               \
 492         if (rbp_red_get(a_type, a_field, rbp_r_t) == false              \
 493           && rbp_red_get(a_type, a_field, rbp_r_u) == false) {          \
 494             /* Apply standard transform to prepare for left move.     */\
 495             rbp_move_red_left(a_type, a_field, rbp_r_c, rbp_r_t);       \
 496             rbp_black_set(a_type, a_field, rbp_r_t);                    \
 497             rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);            \
 498             rbp_r_c = rbp_r_t;                                          \
 499         } else {                                                        \
 500             /* Move left.                                             */\
 501             rbp_r_p = rbp_r_c;                                          \
 502             rbp_r_c = rbp_left_get(a_type, a_field, rbp_r_c);           \
 503         }                                                               \
 504     } else {                                                            \
 505         if (rbp_r_cmp == 0) {                                           \
 506             assert((a_node) == rbp_r_c);                                \
 507             if (rbp_right_get(a_type, a_field, rbp_r_c)                 \
 508               == &(a_tree)->rbt_nil) {                                  \
 509                 /* Delete root node (which is also a leaf node).      */\
 510                 if (rbp_left_get(a_type, a_field, rbp_r_c)              \
 511                   != &(a_tree)->rbt_nil) {                              \
 512                     rbp_lean_right(a_type, a_field, rbp_r_c, rbp_r_t);  \
 513                     rbp_right_set(a_type, a_field, rbp_r_t,             \
 514                       &(a_tree)->rbt_nil);                              \
 515                 } else {                                                \
 516                     rbp_r_t = &(a_tree)->rbt_nil;                       \
 517                 }                                                       \
 518                 rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);        \
 519             } else {                                                    \
 520                 /* This is the node we want to delete, but we will    */\
 521                 /* instead swap it with its successor and delete the  */\
 522                 /* successor.  Record enough information to do the    */\
 523                 /* swap later.  rbp_r_xp is the a_node's parent.      */\
 524                 rbp_r_xp = rbp_r_p;                                     \
 525                 rbp_r_cmp = 1; /* Note that deletion is incomplete.   */\
 526             }                                                           \
 527         }                                                               \
 528         if (rbp_r_cmp == 1) {                                           \
 529             if (rbp_red_get(a_type, a_field, rbp_left_get(a_type,       \
 530               a_field, rbp_right_get(a_type, a_field, rbp_r_c)))        \
 531               == false) {                                               \
 532                 rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c);       \
 533                 if (rbp_red_get(a_type, a_field, rbp_r_t)) {            \
 534                     /* Standard transform.                            */\
 535                     rbp_move_red_right(a_type, a_field, rbp_r_c,        \
 536                       rbp_r_t);                                         \
 537                 } else {                                                \
 538                     /* Root-specific transform.                       */\
 539                     rbp_red_set(a_type, a_field, rbp_r_c);              \
 540                     rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);   \
 541                     if (rbp_red_get(a_type, a_field, rbp_r_u)) {        \
 542                         rbp_black_set(a_type, a_field, rbp_r_u);        \
 543                         rbp_rotate_right(a_type, a_field, rbp_r_c,      \
 544                           rbp_r_t);                                     \
 545                         rbp_rotate_left(a_type, a_field, rbp_r_c,       \
 546                           rbp_r_u);                                     \
 547                         rbp_right_set(a_type, a_field, rbp_r_t,         \
 548                           rbp_r_u);                                     \
 549                     } else {                                            \
 550                         rbp_red_set(a_type, a_field, rbp_r_t);          \
 551                         rbp_rotate_left(a_type, a_field, rbp_r_c,       \
 552                           rbp_r_t);                                     \
 553                     }                                                   \
 554                 }                                                       \
 555                 rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);        \
 556                 rbp_r_c = rbp_r_t;                                      \
 557             } else {                                                    \
 558                 /* Move right.                                        */\
 559                 rbp_r_p = rbp_r_c;                                      \
 560                 rbp_r_c = rbp_right_get(a_type, a_field, rbp_r_c);      \
 561             }                                                           \
 562         }                                                               \
 563     }                                                                   \
 564     if (rbp_r_cmp != 0) {                                               \
 565         while (true) {                                                  \
 566             assert(rbp_r_p != &(a_tree)->rbt_nil);                      \
 567             rbp_r_cmp = (a_cmp)((a_node), rbp_r_c);                     \
 568             if (rbp_r_cmp < 0) {                                        \
 569                 rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c);       \
 570                 if (rbp_r_t == &(a_tree)->rbt_nil) {                    \
 571                     /* rbp_r_c now refers to the successor node to    */\
 572                     /* relocate, and rbp_r_xp/a_node refer to the     */\
 573                     /* context for the relocation.                    */\
 574                     if (rbp_left_get(a_type, a_field, rbp_r_xp)         \
 575                       == (a_node)) {                                    \
 576                         rbp_left_set(a_type, a_field, rbp_r_xp,         \
 577                           rbp_r_c);                                     \
 578                     } else {                                            \
 579                         assert(rbp_right_get(a_type, a_field,           \
 580                           rbp_r_xp) == (a_node));                       \
 581                         rbp_right_set(a_type, a_field, rbp_r_xp,        \
 582                           rbp_r_c);                                     \
 583                     }                                                   \
 584                     rbp_left_set(a_type, a_field, rbp_r_c,              \
 585                       rbp_left_get(a_type, a_field, (a_node)));         \
 586                     rbp_right_set(a_type, a_field, rbp_r_c,             \
 587                       rbp_right_get(a_type, a_field, (a_node)));        \
 588                     rbp_color_set(a_type, a_field, rbp_r_c,             \
 589                       rbp_red_get(a_type, a_field, (a_node)));          \
 590                     if (rbp_left_get(a_type, a_field, rbp_r_p)          \
 591                       == rbp_r_c) {                                     \
 592                         rbp_left_set(a_type, a_field, rbp_r_p,          \
 593                           &(a_tree)->rbt_nil);                          \
 594                     } else {                                            \
 595                         assert(rbp_right_get(a_type, a_field, rbp_r_p)  \
 596                           == rbp_r_c);                                  \
 597                         rbp_right_set(a_type, a_field, rbp_r_p,         \
 598                           &(a_tree)->rbt_nil);                          \
 599                     }                                                   \
 600                     break;                                              \
 601                 }                                                       \
 602                 rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);       \
 603                 if (rbp_red_get(a_type, a_field, rbp_r_t) == false      \
 604                   && rbp_red_get(a_type, a_field, rbp_r_u) == false) {  \
 605                     rbp_move_red_left(a_type, a_field, rbp_r_c,         \
 606                       rbp_r_t);                                         \
 607                     if (rbp_left_get(a_type, a_field, rbp_r_p)          \
 608                       == rbp_r_c) {                                     \
 609                         rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);\
 610                     } else {                                            \
 611                         rbp_right_set(a_type, a_field, rbp_r_p,         \
 612                           rbp_r_t);                                     \
 613                     }                                                   \
 614                     rbp_r_c = rbp_r_t;                                  \
 615                 } else {                                                \
 616                     rbp_r_p = rbp_r_c;                                  \
 617                     rbp_r_c = rbp_left_get(a_type, a_field, rbp_r_c);   \
 618                 }                                                       \
 619             } else {                                                    \
 620                 /* Check whether to delete this node (it has to be    */\
 621                 /* the correct node and a leaf node).                 */\
 622                 if (rbp_r_cmp == 0) {                                   \
 623                     assert((a_node) == rbp_r_c);                        \
 624                     if (rbp_right_get(a_type, a_field, rbp_r_c)         \
 625                       == &(a_tree)->rbt_nil) {                          \
 626                         /* Delete leaf node.                          */\
 627                         if (rbp_left_get(a_type, a_field, rbp_r_c)      \
 628                           != &(a_tree)->rbt_nil) {                      \
 629                             rbp_lean_right(a_type, a_field, rbp_r_c,    \
 630                               rbp_r_t);                                 \
 631                             rbp_right_set(a_type, a_field, rbp_r_t,     \
 632                               &(a_tree)->rbt_nil);                      \
 633                         } else {                                        \
 634                             rbp_r_t = &(a_tree)->rbt_nil;               \
 635                         }                                               \
 636                         if (rbp_left_get(a_type, a_field, rbp_r_p)      \
 637                           == rbp_r_c) {                                 \
 638                             rbp_left_set(a_type, a_field, rbp_r_p,      \
 639                               rbp_r_t);                                 \
 640                         } else {                                        \
 641                             rbp_right_set(a_type, a_field, rbp_r_p,     \
 642                               rbp_r_t);                                 \
 643                         }                                               \
 644                         break;                                          \
 645                     } else {                                            \
 646                         /* This is the node we want to delete, but we */\
 647                         /* will instead swap it with its successor    */\
 648                         /* and delete the successor.  Record enough   */\
 649                         /* information to do the swap later.          */\
 650                         /* rbp_r_xp is a_node's parent.               */\
 651                         rbp_r_xp = rbp_r_p;                             \
 652                     }                                                   \
 653                 }                                                       \
 654                 rbp_r_t = rbp_right_get(a_type, a_field, rbp_r_c);      \
 655                 rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);       \
 656                 if (rbp_red_get(a_type, a_field, rbp_r_u) == false) {   \
 657                     rbp_move_red_right(a_type, a_field, rbp_r_c,        \
 658                       rbp_r_t);                                         \
 659                     if (rbp_left_get(a_type, a_field, rbp_r_p)          \
 660                       == rbp_r_c) {                                     \
 661                         rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);\
 662                     } else {                                            \
 663                         rbp_right_set(a_type, a_field, rbp_r_p,         \
 664                           rbp_r_t);                                     \
 665                     }                                                   \
 666                     rbp_r_c = rbp_r_t;                                  \
 667                 } else {                                                \
 668                     rbp_r_p = rbp_r_c;                                  \
 669                     rbp_r_c = rbp_right_get(a_type, a_field, rbp_r_c);  \
 670                 }                                                       \
 671             }                                                           \
 672         }                                                               \
 673     }                                                                   \
 674     /* Update root.                                                   */\
 675     (a_tree)->rbt_root = rbp_left_get(a_type, a_field, &rbp_r_s);       \
 676 } while (0)
 677
 678 /*
 679  * The rb_wrap() macro provides a convenient way to wrap functions around the
 680  * cpp macros.  The main benefits of wrapping are that 1) repeated macro
 681  * expansion can cause code bloat, especially for rb_{insert,remove)(), and
 682  * 2) type, linkage, comparison functions, etc. need not be specified at every
 683  * call point.
 684  */
 685
 686 #define rb_wrap(a_attr, a_prefix, a_tree_type, a_type, a_field, a_cmp)  \
 687 a_attr void                                                             \
 688 a_prefix##new(a_tree_type *tree) {                                      \
 689     rb_new(a_type, a_field, tree);                                      \
 690 }                                                                       \
 691 a_attr a_type *                                                         \
 692 a_prefix##first(a_tree_type *tree) {                                    \
 693     a_type *ret;                                                        \
 694     rb_first(a_type, a_field, tree, ret);                               \
 695     return (ret);                                                       \
 696 }                                                                       \
 697 a_attr a_type *                                                         \
 698 a_prefix##last(a_tree_type *tree) {                                     \
 699     a_type *ret;                                                        \
 700     rb_last(a_type, a_field, tree, ret);                                \
 701     return (ret);                                                       \
 702 }                                                                       \
 703 a_attr a_type *                                                         \
 704 a_prefix##next(a_tree_type *tree, a_type *node) {                       \
 705     a_type *ret;                                                        \
 706     rb_next(a_type, a_field, a_cmp, tree, node, ret);                   \
 707     return (ret);                                                       \
 708 }                                                                       \
 709 a_attr a_type *                                                         \
 710 a_prefix##prev(a_tree_type *tree, a_type *node) {                       \
 711     a_type *ret;                                                        \
 712     rb_prev(a_type, a_field, a_cmp, tree, node, ret);                   \
 713     return (ret);                                                       \
 714 }                                                                       \
 715 a_attr a_type *                                                         \
 716 a_prefix##search(a_tree_type *tree, a_type *key) {                      \
 717     a_type *ret;                                                        \
 718     rb_search(a_type, a_field, a_cmp, tree, key, ret);                  \
 719     return (ret);                                                       \
 720 }                                                                       \
 721 a_attr a_type *                                                         \
 722 a_prefix##nsearch(a_tree_type *tree, a_type *key) {                     \
 723     a_type *ret;                                                        \
 724     rb_nsearch(a_type, a_field, a_cmp, tree, key, ret);                 \
 725     return (ret);                                                       \
 726 }                                                                       \
 727 a_attr a_type *                                                         \
 728 a_prefix##psearch(a_tree_type *tree, a_type *key) {                     \
 729     a_type *ret;                                                        \
 730     rb_psearch(a_type, a_field, a_cmp, tree, key, ret);                 \
 731     return (ret);                                                       \
 732 }                                                                       \
 733 a_attr void                                                             \
 734 a_prefix##insert(a_tree_type *tree, a_type *node) {                     \
 735     rb_insert(a_type, a_field, a_cmp, tree, node);                      \
 736 }                                                                       \
 737 a_attr void                                                             \
 738 a_prefix##remove(a_tree_type *tree, a_type *node) {                     \
 739     rb_remove(a_type, a_field, a_cmp, tree, node);                      \
 740 }
 741
 742 /*
 743  * The iterators simulate recursion via an array of pointers that store the
 744  * current path.  This is critical to performance, since a series of calls to
 745  * rb_{next,prev}() would require time proportional to (n lg n), whereas this
 746  * implementation only requires time proportional to (n).
 747  *
 748  * Since the iterators cache a path down the tree, any tree modification may
 749  * cause the cached path to become invalid.  In order to continue iteration,
 750  * use something like the following sequence:
 751  *
 752  *   {
 753  *       a_type *node, *tnode;
 754  *
 755  *       rb_foreach_begin(a_type, a_field, a_tree, node) {
 756  *           ...
 757  *           rb_next(a_type, a_field, a_cmp, a_tree, node, tnode);
 758  *           rb_remove(a_type, a_field, a_cmp, a_tree, node);
 759  *           rb_foreach_next(a_type, a_field, a_cmp, a_tree, tnode);
 760  *           ...
 761  *       } rb_foreach_end(a_type, a_field, a_tree, node)
 762  *   }
 763  *
 764  * Note that this idiom is not advised if every iteration modifies the tree,
 765  * since in that case there is no algorithmic complexity improvement over a
 766  * series of rb_{next,prev}() calls, thus making the setup overhead wasted
 767  * effort.
 768  */
 769
 770 #define rb_foreach_begin(a_type, a_field, a_tree, a_var) {              \
 771     /* Compute the maximum possible tree depth (3X the black height). */\
 772     unsigned rbp_f_height;                                              \
 773     rbp_black_height(a_type, a_field, a_tree, rbp_f_height);            \
 774     rbp_f_height *= 3;                                                  \
 775     {                                                                   \
 776         /* Initialize the path to contain the left spine.             */\
 777         a_type *rbp_f_path[rbp_f_height];                               \
 778         a_type *rbp_f_node;                                             \
 779         bool rbp_f_synced = false;                                      \
 780         unsigned rbp_f_depth = 0;                                       \
 781         if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {                 \
 782             rbp_f_path[rbp_f_depth] = (a_tree)->rbt_root;               \
 783             rbp_f_depth++;                                              \
 784             while ((rbp_f_node = rbp_left_get(a_type, a_field,          \
 785               rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) {      \
 786                 rbp_f_path[rbp_f_depth] = rbp_f_node;                   \
 787                 rbp_f_depth++;                                          \
 788             }                                                           \
 789         }                                                               \
 790         /* While the path is non-empty, iterate.                      */\
 791         while (rbp_f_depth > 0) {                                       \
 792             (a_var) = rbp_f_path[rbp_f_depth-1];
 793
 794 /* Only use if modifying the tree during iteration. */
 795 #define rb_foreach_next(a_type, a_field, a_cmp, a_tree, a_node)         \
 796             /* Re-initialize the path to contain the path to a_node.  */\
 797             rbp_f_depth = 0;                                            \
 798             if (a_node != NULL) {                                       \
 799                 if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {         \
 800                     rbp_f_path[rbp_f_depth] = (a_tree)->rbt_root;       \
 801                     rbp_f_depth++;                                      \
 802                     rbp_f_node = rbp_f_path[0];                         \
 803                     while (true) {                                      \
 804                         int rbp_f_cmp = (a_cmp)((a_node),               \
 805                           rbp_f_path[rbp_f_depth-1]);                   \
 806                         if (rbp_f_cmp < 0) {                            \
 807                             rbp_f_node = rbp_left_get(a_type, a_field,  \
 808                               rbp_f_path[rbp_f_depth-1]);               \
 809                         } else if (rbp_f_cmp > 0) {                     \
 810                             rbp_f_node = rbp_right_get(a_type, a_field, \
 811                               rbp_f_path[rbp_f_depth-1]);               \
 812                         } else {                                        \
 813                             break;                                      \
 814                         }                                               \
 815                         assert(rbp_f_node != &(a_tree)->rbt_nil);       \
 816                         rbp_f_path[rbp_f_depth] = rbp_f_node;           \
 817                         rbp_f_depth++;                                  \
 818                     }                                                   \
 819                 }                                                       \
 820             }                                                           \
 821             rbp_f_synced = true;
 822
 823 #define rb_foreach_end(a_type, a_field, a_tree, a_var)                  \
 824             if (rbp_f_synced) {                                         \
 825                 rbp_f_synced = false;                                   \
 826                 continue;                                               \
 827             }                                                           \
 828             /* Find the successor.                                    */\
 829             if ((rbp_f_node = rbp_right_get(a_type, a_field,            \
 830               rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) {      \
 831                 /* The successor is the left-most node in the right   */\
 832                 /* subtree.                                           */\
 833                 rbp_f_path[rbp_f_depth] = rbp_f_node;                   \
 834                 rbp_f_depth++;                                          \
 835                 while ((rbp_f_node = rbp_left_get(a_type, a_field,      \
 836                   rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) {  \
 837                     rbp_f_path[rbp_f_depth] = rbp_f_node;               \
 838                     rbp_f_depth++;                                      \
 839                 }                                                       \
 840             } else {                                                    \
 841                 /* The successor is above the current node.  Unwind   */\
 842                 /* until a left-leaning edge is removed from the      */\
 843                 /* path, or the path is empty.                        */\
 844                 for (rbp_f_depth--; rbp_f_depth > 0; rbp_f_depth--) {   \
 845                     if (rbp_left_get(a_type, a_field,                   \
 846                       rbp_f_path[rbp_f_depth-1])                        \
 847                       == rbp_f_path[rbp_f_depth]) {                     \
 848                         break;                                          \
 849                     }                                                   \
 850                 }                                                       \
 851             }                                                           \
 852         }                                                               \
 853     }                                                                   \
 854 }
 855
 856 #define rb_foreach_reverse_begin(a_type, a_field, a_tree, a_var) {      \
 857     /* Compute the maximum possible tree depth (3X the black height). */\
 858     unsigned rbp_fr_height;                                             \
 859     rbp_black_height(a_type, a_field, a_tree, rbp_fr_height);           \
 860     rbp_fr_height *= 3;                                                 \
 861     {                                                                   \
 862         /* Initialize the path to contain the right spine.            */\
 863         a_type *rbp_fr_path[rbp_fr_height];                             \
 864         a_type *rbp_fr_node;                                            \
 865         bool rbp_fr_synced = false;                                     \
 866         unsigned rbp_fr_depth = 0;                                      \
 867         if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {                 \
 868             rbp_fr_path[rbp_fr_depth] = (a_tree)->rbt_root;             \
 869             rbp_fr_depth++;                                             \
 870             while ((rbp_fr_node = rbp_right_get(a_type, a_field,        \
 871               rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) {    \
 872                 rbp_fr_path[rbp_fr_depth] = rbp_fr_node;                \
 873                 rbp_fr_depth++;                                         \
 874             }                                                           \
 875         }                                                               \
 876         /* While the path is non-empty, iterate.                      */\
 877         while (rbp_fr_depth > 0) {                                      \
 878             (a_var) = rbp_fr_path[rbp_fr_depth-1];
 879
 880 /* Only use if modifying the tree during iteration. */
 881 #define rb_foreach_reverse_prev(a_type, a_field, a_cmp, a_tree, a_node) \
 882             /* Re-initialize the path to contain the path to a_node.  */\
 883             rbp_fr_depth = 0;                                           \
 884             if (a_node != NULL) {                                       \
 885                 if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {         \
 886                     rbp_fr_path[rbp_fr_depth] = (a_tree)->rbt_root;     \
 887                     rbp_fr_depth++;                                     \
 888                     rbp_fr_node = rbp_fr_path[0];                       \
 889                     while (true) {                                      \
 890                         int rbp_fr_cmp = (a_cmp)((a_node),              \
 891                           rbp_fr_path[rbp_fr_depth-1]);                 \
 892                         if (rbp_fr_cmp < 0) {                           \
 893                             rbp_fr_node = rbp_left_get(a_type, a_field, \
 894                               rbp_fr_path[rbp_fr_depth-1]);             \
 895                         } else if (rbp_fr_cmp > 0) {                    \
 896                             rbp_fr_node = rbp_right_get(a_type, a_field,\
 897                               rbp_fr_path[rbp_fr_depth-1]);             \
 898                         } else {                                        \
 899                             break;                                      \
 900                         }                                               \
 901                         assert(rbp_fr_node != &(a_tree)->rbt_nil);      \
 902                         rbp_fr_path[rbp_fr_depth] = rbp_fr_node;        \
 903                         rbp_fr_depth++;                                 \
 904                     }                                                   \
 905                 }                                                       \
 906             }                                                           \
 907             rbp_fr_synced = true;
 908
 909 #define rb_foreach_reverse_end(a_type, a_field, a_tree, a_var)          \
 910             if (rbp_fr_synced) {                                        \
 911                 rbp_fr_synced = false;                                  \
 912                 continue;                                               \
 913             }                                                           \
 914             if (rbp_fr_depth == 0) {                                    \
 915                 /* rb_foreach_reverse_sync() was called with a NULL   */\
 916                 /* a_node.                                            */\
 917                 break;                                                  \
 918             }                                                           \
 919             /* Find the predecessor.                                  */\
 920             if ((rbp_fr_node = rbp_left_get(a_type, a_field,            \
 921               rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) {    \
 922                 /* The predecessor is the right-most node in the left */\
 923                 /* subtree.                                           */\
 924                 rbp_fr_path[rbp_fr_depth] = rbp_fr_node;                \
 925                 rbp_fr_depth++;                                         \
 926                 while ((rbp_fr_node = rbp_right_get(a_type, a_field,    \
 927                   rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) {\
 928                     rbp_fr_path[rbp_fr_depth] = rbp_fr_node;            \
 929                     rbp_fr_depth++;                                     \
 930                 }                                                       \
 931             } else {                                                    \
 932                 /* The predecessor is above the current node.  Unwind */\
 933                 /* until a right-leaning edge is removed from the     */\
 934                 /* path, or the path is empty.                        */\
 935                 for (rbp_fr_depth--; rbp_fr_depth > 0; rbp_fr_depth--) {\
 936                     if (rbp_right_get(a_type, a_field,                  \
 937                       rbp_fr_path[rbp_fr_depth-1])                      \
 938                       == rbp_fr_path[rbp_fr_depth]) {                   \
 939                         break;                                          \
 940                     }                                                   \
 941                 }                                                       \
 942             }                                                           \
 943         }                                                               \
 944     }                                                                   \
 945 }
 946
 947 #endif /* RB_H_ */