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