Gnash  0.8.10
jemalloc_rb.h
Go to the documentation of this file.
00001 /******************************************************************************
00002  *
00003  * Copyright (C) 2008 Jason Evans <jasone@FreeBSD.org>.
00004  * All rights reserved.
00005  *
00006  * Redistribution and use in source and binary forms, with or without
00007  * modification, are permitted provided that the following conditions
00008  * are met:
00009  * 1. Redistributions of source code must retain the above copyright
00010  *    notice(s), this list of conditions and the following disclaimer
00011  *    unmodified other than the allowable addition of one or more
00012  *    copyright notices.
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice(s), this list of conditions and the following disclaimer in
00015  *    the documentation and/or other materials provided with the
00016  *    distribution.
00017  *
00018  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
00019  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00020  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00021  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
00022  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
00023  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
00024  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
00025  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
00026  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
00027  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
00028  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  *
00030  ******************************************************************************
00031  *
00032  * cpp macro implementation of left-leaning red-black trees.
00033  *
00034  * Usage:
00035  *
00036  *   (Optional.)
00037  *   #define SIZEOF_PTR ...
00038  *   #define SIZEOF_PTR_2POW ...
00039  *   #define RB_NO_C99_VARARRAYS
00040  *
00041  *   (Optional, see assert(3).)
00042  *   #define NDEBUG
00043  *
00044  *   (Required.)
00045  *   #include <assert.h>
00046  *   #include <rb.h>
00047  *   ...
00048  *
00049  * All operations are done non-recursively.  Parent pointers are not used, and
00050  * color bits are stored in the least significant bit of right-child pointers,
00051  * thus making node linkage as compact as is possible for red-black trees.
00052  *
00053  * Some macros use a comparison function pointer, which is expected to have the
00054  * following prototype:
00055  *
00056  *   int (a_cmp *)(a_type *a_node, a_type *a_other);
00057  *                         ^^^^^^
00058  *                      or a_key
00059  *
00060  * Interpretation of comparision function return values:
00061  *
00062  *   -1 : a_node <  a_other
00063  *    0 : a_node == a_other
00064  *    1 : a_node >  a_other
00065  *
00066  * In all cases, the a_node or a_key macro argument is the first argument to the
00067  * comparison function, which makes it possible to write comparison functions
00068  * that treat the first argument specially.
00069  *
00070  ******************************************************************************/
00071 
00072 #ifndef RB_H_
00073 #define RB_H_
00074 
00075 #if 0
00076 #include <sys/cdefs.h>
00077 __FBSDID("$FreeBSD: head/lib/libc/stdlib/rb.h 178995 2008-05-14 18:33:13Z jasone $");
00078 #endif
00079 
00080 /* Node structure. */
00081 #define rb_node(a_type)                                                 \
00082 struct {                                                                \
00083     a_type *rbn_left;                                                   \
00084     a_type *rbn_right_red;                                              \
00085 }
00086 
00087 /* Root structure. */
00088 #define rb_tree(a_type)                                                 \
00089 struct {                                                                \
00090     a_type *rbt_root;                                                   \
00091     a_type rbt_nil;                                                     \
00092 }
00093 
00094 /* Left accessors. */
00095 #define rbp_left_get(a_type, a_field, a_node)                           \
00096     ((a_node)->a_field.rbn_left)
00097 #define rbp_left_set(a_type, a_field, a_node, a_left) do {              \
00098     (a_node)->a_field.rbn_left = a_left;                                \
00099 } while (0)
00100 
00101 /* Right accessors. */
00102 #define rbp_right_get(a_type, a_field, a_node)                          \
00103     ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red)           \
00104       & ((ssize_t)-2)))
00105 #define rbp_right_set(a_type, a_field, a_node, a_right) do {            \
00106     (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right) \
00107       | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1))); \
00108 } while (0)
00109 
00110 /* Color accessors. */
00111 #define rbp_red_get(a_type, a_field, a_node)                            \
00112     ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red)              \
00113       & ((size_t)1)))
00114 #define rbp_color_set(a_type, a_field, a_node, a_red) do {              \
00115     (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t)          \
00116       (a_node)->a_field.rbn_right_red) & ((ssize_t)-2))                 \
00117       | ((ssize_t)a_red));                                              \
00118 } while (0)
00119 #define rbp_red_set(a_type, a_field, a_node) do {                       \
00120     (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t)          \
00121       (a_node)->a_field.rbn_right_red) | ((size_t)1));                  \
00122 } while (0)
00123 #define rbp_black_set(a_type, a_field, a_node) do {                     \
00124     (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t)           \
00125       (a_node)->a_field.rbn_right_red) & ((ssize_t)-2));                \
00126 } while (0)
00127 
00128 /* Node initializer. */
00129 #define rbp_node_new(a_type, a_field, a_tree, a_node) do {              \
00130     rbp_left_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil);        \
00131     rbp_right_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil);       \
00132     rbp_red_set(a_type, a_field, (a_node));                             \
00133 } while (0)
00134 
00135 /* Tree initializer. */
00136 #define rb_new(a_type, a_field, a_tree) do {                            \
00137     (a_tree)->rbt_root = &(a_tree)->rbt_nil;                            \
00138     rbp_node_new(a_type, a_field, a_tree, &(a_tree)->rbt_nil);          \
00139     rbp_black_set(a_type, a_field, &(a_tree)->rbt_nil);                 \
00140 } while (0)
00141 
00142 /* Tree operations. */
00143 #define rbp_black_height(a_type, a_field, a_tree, r_height) do {        \
00144     a_type *rbp_bh_t;                                                   \
00145     for (rbp_bh_t = (a_tree)->rbt_root, (r_height) = 0;                 \
00146       rbp_bh_t != &(a_tree)->rbt_nil;                                   \
00147       rbp_bh_t = rbp_left_get(a_type, a_field, rbp_bh_t)) {             \
00148         if (rbp_red_get(a_type, a_field, rbp_bh_t) == false) {          \
00149             (r_height)++;                                               \
00150         }                                                               \
00151     }                                                                   \
00152 } while (0)
00153 
00154 #define rbp_first(a_type, a_field, a_tree, a_root, r_node) do {         \
00155     for ((r_node) = (a_root);                                           \
00156       rbp_left_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil;    \
00157       (r_node) = rbp_left_get(a_type, a_field, (r_node))) {             \
00158     }                                                                   \
00159 } while (0)
00160 
00161 #define rbp_last(a_type, a_field, a_tree, a_root, r_node) do {          \
00162     for ((r_node) = (a_root);                                           \
00163       rbp_right_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil;   \
00164       (r_node) = rbp_right_get(a_type, a_field, (r_node))) {            \
00165     }                                                                   \
00166 } while (0)
00167 
00168 #define rbp_next(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {   \
00169     if (rbp_right_get(a_type, a_field, (a_node))                        \
00170       != &(a_tree)->rbt_nil) {                                          \
00171         rbp_first(a_type, a_field, a_tree, rbp_right_get(a_type,        \
00172           a_field, (a_node)), (r_node));                                \
00173     } else {                                                            \
00174         a_type *rbp_n_t = (a_tree)->rbt_root;                           \
00175         assert(rbp_n_t != &(a_tree)->rbt_nil);                          \
00176         (r_node) = &(a_tree)->rbt_nil;                                  \
00177         while (true) {                                                  \
00178             int rbp_n_cmp = (a_cmp)((a_node), rbp_n_t);                 \
00179             if (rbp_n_cmp < 0) {                                        \
00180                 (r_node) = rbp_n_t;                                     \
00181                 rbp_n_t = rbp_left_get(a_type, a_field, rbp_n_t);       \
00182             } else if (rbp_n_cmp > 0) {                                 \
00183                 rbp_n_t = rbp_right_get(a_type, a_field, rbp_n_t);      \
00184             } else {                                                    \
00185                 break;                                                  \
00186             }                                                           \
00187             assert(rbp_n_t != &(a_tree)->rbt_nil);                      \
00188         }                                                               \
00189     }                                                                   \
00190 } while (0)
00191 
00192 #define rbp_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {   \
00193     if (rbp_left_get(a_type, a_field, (a_node)) != &(a_tree)->rbt_nil) {\
00194         rbp_last(a_type, a_field, a_tree, rbp_left_get(a_type,          \
00195           a_field, (a_node)), (r_node));                                \
00196     } else {                                                            \
00197         a_type *rbp_p_t = (a_tree)->rbt_root;                           \
00198         assert(rbp_p_t != &(a_tree)->rbt_nil);                          \
00199         (r_node) = &(a_tree)->rbt_nil;                                  \
00200         while (true) {                                                  \
00201             int rbp_p_cmp = (a_cmp)((a_node), rbp_p_t);                 \
00202             if (rbp_p_cmp < 0) {                                        \
00203                 rbp_p_t = rbp_left_get(a_type, a_field, rbp_p_t);       \
00204             } else if (rbp_p_cmp > 0) {                                 \
00205                 (r_node) = rbp_p_t;                                     \
00206                 rbp_p_t = rbp_right_get(a_type, a_field, rbp_p_t);      \
00207             } else {                                                    \
00208                 break;                                                  \
00209             }                                                           \
00210             assert(rbp_p_t != &(a_tree)->rbt_nil);                      \
00211         }                                                               \
00212     }                                                                   \
00213 } while (0)
00214 
00215 #define rb_first(a_type, a_field, a_tree, r_node) do {                  \
00216     rbp_first(a_type, a_field, a_tree, (a_tree)->rbt_root, (r_node));   \
00217     if ((r_node) == &(a_tree)->rbt_nil) {                               \
00218         (r_node) = NULL;                                                \
00219     }                                                                   \
00220 } while (0)
00221 
00222 #define rb_last(a_type, a_field, a_tree, r_node) do {                   \
00223     rbp_last(a_type, a_field, a_tree, (a_tree)->rbt_root, r_node);      \
00224     if ((r_node) == &(a_tree)->rbt_nil) {                               \
00225         (r_node) = NULL;                                                \
00226     }                                                                   \
00227 } while (0)
00228 
00229 #define rb_next(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {    \
00230     rbp_next(a_type, a_field, a_cmp, a_tree, (a_node), (r_node));       \
00231     if ((r_node) == &(a_tree)->rbt_nil) {                               \
00232         (r_node) = NULL;                                                \
00233     }                                                                   \
00234 } while (0)
00235 
00236 #define rb_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {    \
00237     rbp_prev(a_type, a_field, a_cmp, a_tree, (a_node), (r_node));       \
00238     if ((r_node) == &(a_tree)->rbt_nil) {                               \
00239         (r_node) = NULL;                                                \
00240     }                                                                   \
00241 } while (0)
00242 
00243 #define rb_search(a_type, a_field, a_cmp, a_tree, a_key, r_node) do {   \
00244     int rbp_se_cmp;                                                     \
00245     (r_node) = (a_tree)->rbt_root;                                      \
00246     while ((r_node) != &(a_tree)->rbt_nil                               \
00247       && (rbp_se_cmp = (a_cmp)((a_key), (r_node))) != 0) {              \
00248         if (rbp_se_cmp < 0) {                                           \
00249             (r_node) = rbp_left_get(a_type, a_field, (r_node));         \
00250         } else {                                                        \
00251             (r_node) = rbp_right_get(a_type, a_field, (r_node));        \
00252         }                                                               \
00253     }                                                                   \
00254     if ((r_node) == &(a_tree)->rbt_nil) {                               \
00255         (r_node) = NULL;                                                \
00256     }                                                                   \
00257 } while (0)
00258 
00259 /*
00260  * Find a match if it exists.  Otherwise, find the next greater node, if one
00261  * exists.
00262  */
00263 #define rb_nsearch(a_type, a_field, a_cmp, a_tree, a_key, r_node) do {  \
00264     a_type *rbp_ns_t = (a_tree)->rbt_root;                              \
00265     (r_node) = NULL;                                                    \
00266     while (rbp_ns_t != &(a_tree)->rbt_nil) {                            \
00267         int rbp_ns_cmp = (a_cmp)((a_key), rbp_ns_t);                    \
00268         if (rbp_ns_cmp < 0) {                                           \
00269             (r_node) = rbp_ns_t;                                        \
00270             rbp_ns_t = rbp_left_get(a_type, a_field, rbp_ns_t);         \
00271         } else if (rbp_ns_cmp > 0) {                                    \
00272             rbp_ns_t = rbp_right_get(a_type, a_field, rbp_ns_t);        \
00273         } else {                                                        \
00274             (r_node) = rbp_ns_t;                                        \
00275             break;                                                      \
00276         }                                                               \
00277     }                                                                   \
00278 } while (0)
00279 
00280 /*
00281  * Find a match if it exists.  Otherwise, find the previous lesser node, if one
00282  * exists.
00283  */
00284 #define rb_psearch(a_type, a_field, a_cmp, a_tree, a_key, r_node) do {  \
00285     a_type *rbp_ps_t = (a_tree)->rbt_root;                              \
00286     (r_node) = NULL;                                                    \
00287     while (rbp_ps_t != &(a_tree)->rbt_nil) {                            \
00288         int rbp_ps_cmp = (a_cmp)((a_key), rbp_ps_t);                    \
00289         if (rbp_ps_cmp < 0) {                                           \
00290             rbp_ps_t = rbp_left_get(a_type, a_field, rbp_ps_t);         \
00291         } else if (rbp_ps_cmp > 0) {                                    \
00292             (r_node) = rbp_ps_t;                                        \
00293             rbp_ps_t = rbp_right_get(a_type, a_field, rbp_ps_t);        \
00294         } else {                                                        \
00295             (r_node) = rbp_ps_t;                                        \
00296             break;                                                      \
00297         }                                                               \
00298     }                                                                   \
00299 } while (0)
00300 
00301 #define rbp_rotate_left(a_type, a_field, a_node, r_node) do {           \
00302     (r_node) = rbp_right_get(a_type, a_field, (a_node));                \
00303     rbp_right_set(a_type, a_field, (a_node),                            \
00304       rbp_left_get(a_type, a_field, (r_node)));                         \
00305     rbp_left_set(a_type, a_field, (r_node), (a_node));                  \
00306 } while (0)
00307 
00308 #define rbp_rotate_right(a_type, a_field, a_node, r_node) do {          \
00309     (r_node) = rbp_left_get(a_type, a_field, (a_node));                 \
00310     rbp_left_set(a_type, a_field, (a_node),                             \
00311       rbp_right_get(a_type, a_field, (r_node)));                        \
00312     rbp_right_set(a_type, a_field, (r_node), (a_node));                 \
00313 } while (0)
00314 
00315 #define rbp_lean_left(a_type, a_field, a_node, r_node) do {             \
00316     bool rbp_ll_red;                                                    \
00317     rbp_rotate_left(a_type, a_field, (a_node), (r_node));               \
00318     rbp_ll_red = rbp_red_get(a_type, a_field, (a_node));                \
00319     rbp_color_set(a_type, a_field, (r_node), rbp_ll_red);               \
00320     rbp_red_set(a_type, a_field, (a_node));                             \
00321 } while (0)
00322 
00323 #define rbp_lean_right(a_type, a_field, a_node, r_node) do {            \
00324     bool rbp_lr_red;                                                    \
00325     rbp_rotate_right(a_type, a_field, (a_node), (r_node));              \
00326     rbp_lr_red = rbp_red_get(a_type, a_field, (a_node));                \
00327     rbp_color_set(a_type, a_field, (r_node), rbp_lr_red);               \
00328     rbp_red_set(a_type, a_field, (a_node));                             \
00329 } while (0)
00330 
00331 #define rbp_move_red_left(a_type, a_field, a_node, r_node) do {         \
00332     a_type *rbp_mrl_t, *rbp_mrl_u;                                      \
00333     rbp_mrl_t = rbp_left_get(a_type, a_field, (a_node));                \
00334     rbp_red_set(a_type, a_field, rbp_mrl_t);                            \
00335     rbp_mrl_t = rbp_right_get(a_type, a_field, (a_node));               \
00336     rbp_mrl_u = rbp_left_get(a_type, a_field, rbp_mrl_t);               \
00337     if (rbp_red_get(a_type, a_field, rbp_mrl_u)) {                      \
00338         rbp_rotate_right(a_type, a_field, rbp_mrl_t, rbp_mrl_u);        \
00339         rbp_right_set(a_type, a_field, (a_node), rbp_mrl_u);            \
00340         rbp_rotate_left(a_type, a_field, (a_node), (r_node));           \
00341         rbp_mrl_t = rbp_right_get(a_type, a_field, (a_node));           \
00342         if (rbp_red_get(a_type, a_field, rbp_mrl_t)) {                  \
00343             rbp_black_set(a_type, a_field, rbp_mrl_t);                  \
00344             rbp_red_set(a_type, a_field, (a_node));                     \
00345             rbp_rotate_left(a_type, a_field, (a_node), rbp_mrl_t);      \
00346             rbp_left_set(a_type, a_field, (r_node), rbp_mrl_t);         \
00347         } else {                                                        \
00348             rbp_black_set(a_type, a_field, (a_node));                   \
00349         }                                                               \
00350     } else {                                                            \
00351         rbp_red_set(a_type, a_field, (a_node));                         \
00352         rbp_rotate_left(a_type, a_field, (a_node), (r_node));           \
00353     }                                                                   \
00354 } while (0)
00355 
00356 #define rbp_move_red_right(a_type, a_field, a_node, r_node) do {        \
00357     a_type *rbp_mrr_t;                                                  \
00358     rbp_mrr_t = rbp_left_get(a_type, a_field, (a_node));                \
00359     if (rbp_red_get(a_type, a_field, rbp_mrr_t)) {                      \
00360         a_type *rbp_mrr_u, *rbp_mrr_v;                                  \
00361         rbp_mrr_u = rbp_right_get(a_type, a_field, rbp_mrr_t);          \
00362         rbp_mrr_v = rbp_left_get(a_type, a_field, rbp_mrr_u);           \
00363         if (rbp_red_get(a_type, a_field, rbp_mrr_v)) {                  \
00364             rbp_color_set(a_type, a_field, rbp_mrr_u,                   \
00365               rbp_red_get(a_type, a_field, (a_node)));                  \
00366             rbp_black_set(a_type, a_field, rbp_mrr_v);                  \
00367             rbp_rotate_left(a_type, a_field, rbp_mrr_t, rbp_mrr_u);     \
00368             rbp_left_set(a_type, a_field, (a_node), rbp_mrr_u);         \
00369             rbp_rotate_right(a_type, a_field, (a_node), (r_node));      \
00370             rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t);      \
00371             rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t);        \
00372         } else {                                                        \
00373             rbp_color_set(a_type, a_field, rbp_mrr_t,                   \
00374               rbp_red_get(a_type, a_field, (a_node)));                  \
00375             rbp_red_set(a_type, a_field, rbp_mrr_u);                    \
00376             rbp_rotate_right(a_type, a_field, (a_node), (r_node));      \
00377             rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t);      \
00378             rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t);        \
00379         }                                                               \
00380         rbp_red_set(a_type, a_field, (a_node));                         \
00381     } else {                                                            \
00382         rbp_red_set(a_type, a_field, rbp_mrr_t);                        \
00383         rbp_mrr_t = rbp_left_get(a_type, a_field, rbp_mrr_t);           \
00384         if (rbp_red_get(a_type, a_field, rbp_mrr_t)) {                  \
00385             rbp_black_set(a_type, a_field, rbp_mrr_t);                  \
00386             rbp_rotate_right(a_type, a_field, (a_node), (r_node));      \
00387             rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t);      \
00388             rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t);        \
00389         } else {                                                        \
00390             rbp_rotate_left(a_type, a_field, (a_node), (r_node));       \
00391         }                                                               \
00392     }                                                                   \
00393 } while (0)
00394 
00395 #define rb_insert(a_type, a_field, a_cmp, a_tree, a_node) do {          \
00396     a_type rbp_i_s;                                                     \
00397     a_type *rbp_i_g, *rbp_i_p, *rbp_i_c, *rbp_i_t, *rbp_i_u;            \
00398     int rbp_i_cmp = 0;                                                  \
00399     rbp_i_g = &(a_tree)->rbt_nil;                                       \
00400     rbp_left_set(a_type, a_field, &rbp_i_s, (a_tree)->rbt_root);        \
00401     rbp_right_set(a_type, a_field, &rbp_i_s, &(a_tree)->rbt_nil);       \
00402     rbp_black_set(a_type, a_field, &rbp_i_s);                           \
00403     rbp_i_p = &rbp_i_s;                                                 \
00404     rbp_i_c = (a_tree)->rbt_root;                                       \
00405     /* Iteratively search down the tree for the insertion point,      */\
00406     /* splitting 4-nodes as they are encountered.  At the end of each */\
00407     /* iteration, rbp_i_g->rbp_i_p->rbp_i_c is a 3-level path down    */\
00408     /* the tree, assuming a sufficiently deep tree.                   */\
00409     while (rbp_i_c != &(a_tree)->rbt_nil) {                             \
00410         rbp_i_t = rbp_left_get(a_type, a_field, rbp_i_c);               \
00411         rbp_i_u = rbp_left_get(a_type, a_field, rbp_i_t);               \
00412         if (rbp_red_get(a_type, a_field, rbp_i_t)                       \
00413           && rbp_red_get(a_type, a_field, rbp_i_u)) {                   \
00414             /* rbp_i_c is the top of a logical 4-node, so split it.   */\
00415             /* This iteration does not move down the tree, due to the */\
00416             /* disruptiveness of node splitting.                      */\
00417             /*                                                        */\
00418             /* Rotate right.                                          */\
00419             rbp_rotate_right(a_type, a_field, rbp_i_c, rbp_i_t);        \
00420             /* Pass red links up one level.                           */\
00421             rbp_i_u = rbp_left_get(a_type, a_field, rbp_i_t);           \
00422             rbp_black_set(a_type, a_field, rbp_i_u);                    \
00423             if (rbp_left_get(a_type, a_field, rbp_i_p) == rbp_i_c) {    \
00424                 rbp_left_set(a_type, a_field, rbp_i_p, rbp_i_t);        \
00425                 rbp_i_c = rbp_i_t;                                      \
00426             } else {                                                    \
00427                 /* rbp_i_c was the right child of rbp_i_p, so rotate  */\
00428                 /* left in order to maintain the left-leaning         */\
00429                 /* invariant.                                         */\
00430                 assert(rbp_right_get(a_type, a_field, rbp_i_p)          \
00431                   == rbp_i_c);                                          \
00432                 rbp_right_set(a_type, a_field, rbp_i_p, rbp_i_t);       \
00433                 rbp_lean_left(a_type, a_field, rbp_i_p, rbp_i_u);       \
00434                 if (rbp_left_get(a_type, a_field, rbp_i_g) == rbp_i_p) {\
00435                     rbp_left_set(a_type, a_field, rbp_i_g, rbp_i_u);    \
00436                 } else {                                                \
00437                     assert(rbp_right_get(a_type, a_field, rbp_i_g)      \
00438                       == rbp_i_p);                                      \
00439                     rbp_right_set(a_type, a_field, rbp_i_g, rbp_i_u);   \
00440                 }                                                       \
00441                 rbp_i_p = rbp_i_u;                                      \
00442                 rbp_i_cmp = (a_cmp)((a_node), rbp_i_p);                 \
00443                 if (rbp_i_cmp < 0) {                                    \
00444                     rbp_i_c = rbp_left_get(a_type, a_field, rbp_i_p);   \
00445                 } else {                                                \
00446                     assert(rbp_i_cmp > 0);                              \
00447                     rbp_i_c = rbp_right_get(a_type, a_field, rbp_i_p);  \
00448                 }                                                       \
00449                 continue;                                               \
00450             }                                                           \
00451         }                                                               \
00452         rbp_i_g = rbp_i_p;                                              \
00453         rbp_i_p = rbp_i_c;                                              \
00454         rbp_i_cmp = (a_cmp)((a_node), rbp_i_c);                         \
00455         if (rbp_i_cmp < 0) {                                            \
00456             rbp_i_c = rbp_left_get(a_type, a_field, rbp_i_c);           \
00457         } else {                                                        \
00458             assert(rbp_i_cmp > 0);                                      \
00459             rbp_i_c = rbp_right_get(a_type, a_field, rbp_i_c);          \
00460         }                                                               \
00461     }                                                                   \
00462     /* rbp_i_p now refers to the node under which to insert.          */\
00463     rbp_node_new(a_type, a_field, a_tree, (a_node));                    \
00464     if (rbp_i_cmp > 0) {                                                \
00465         rbp_right_set(a_type, a_field, rbp_i_p, (a_node));              \
00466         rbp_lean_left(a_type, a_field, rbp_i_p, rbp_i_t);               \
00467         if (rbp_left_get(a_type, a_field, rbp_i_g) == rbp_i_p) {        \
00468             rbp_left_set(a_type, a_field, rbp_i_g, rbp_i_t);            \
00469         } else if (rbp_right_get(a_type, a_field, rbp_i_g) == rbp_i_p) {\
00470             rbp_right_set(a_type, a_field, rbp_i_g, rbp_i_t);           \
00471         }                                                               \
00472     } else {                                                            \
00473         rbp_left_set(a_type, a_field, rbp_i_p, (a_node));               \
00474     }                                                                   \
00475     /* Update the root and make sure that it is black.                */\
00476     (a_tree)->rbt_root = rbp_left_get(a_type, a_field, &rbp_i_s);       \
00477     rbp_black_set(a_type, a_field, (a_tree)->rbt_root);                 \
00478 } while (0)
00479 
00480 #define rb_remove(a_type, a_field, a_cmp, a_tree, a_node) do {          \
00481     a_type rbp_r_s;                                                     \
00482     a_type *rbp_r_p, *rbp_r_c, *rbp_r_xp, *rbp_r_t, *rbp_r_u;           \
00483     int rbp_r_cmp;                                                      \
00484     rbp_left_set(a_type, a_field, &rbp_r_s, (a_tree)->rbt_root);        \
00485     rbp_right_set(a_type, a_field, &rbp_r_s, &(a_tree)->rbt_nil);       \
00486     rbp_black_set(a_type, a_field, &rbp_r_s);                           \
00487     rbp_r_p = &rbp_r_s;                                                 \
00488     rbp_r_c = (a_tree)->rbt_root;                                       \
00489     rbp_r_xp = &(a_tree)->rbt_nil;                                      \
00490     /* Iterate down the tree, but always transform 2-nodes to 3- or   */\
00491     /* 4-nodes in order to maintain the invariant that the current    */\
00492     /* node is not a 2-node.  This allows simple deletion once a leaf */\
00493     /* is reached.  Handle the root specially though, since there may */\
00494     /* be no way to convert it from a 2-node to a 3-node.             */\
00495     rbp_r_cmp = (a_cmp)((a_node), rbp_r_c);                             \
00496     if (rbp_r_cmp < 0) {                                                \
00497         rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c);               \
00498         rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);               \
00499         if (rbp_red_get(a_type, a_field, rbp_r_t) == false              \
00500           && rbp_red_get(a_type, a_field, rbp_r_u) == false) {          \
00501             /* Apply standard transform to prepare for left move.     */\
00502             rbp_move_red_left(a_type, a_field, rbp_r_c, rbp_r_t);       \
00503             rbp_black_set(a_type, a_field, rbp_r_t);                    \
00504             rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);            \
00505             rbp_r_c = rbp_r_t;                                          \
00506         } else {                                                        \
00507             /* Move left.                                             */\
00508             rbp_r_p = rbp_r_c;                                          \
00509             rbp_r_c = rbp_left_get(a_type, a_field, rbp_r_c);           \
00510         }                                                               \
00511     } else {                                                            \
00512         if (rbp_r_cmp == 0) {                                           \
00513             assert((a_node) == rbp_r_c);                                \
00514             if (rbp_right_get(a_type, a_field, rbp_r_c)                 \
00515               == &(a_tree)->rbt_nil) {                                  \
00516                 /* Delete root node (which is also a leaf node).      */\
00517                 if (rbp_left_get(a_type, a_field, rbp_r_c)              \
00518                   != &(a_tree)->rbt_nil) {                              \
00519                     rbp_lean_right(a_type, a_field, rbp_r_c, rbp_r_t);  \
00520                     rbp_right_set(a_type, a_field, rbp_r_t,             \
00521                       &(a_tree)->rbt_nil);                              \
00522                 } else {                                                \
00523                     rbp_r_t = &(a_tree)->rbt_nil;                       \
00524                 }                                                       \
00525                 rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);        \
00526             } else {                                                    \
00527                 /* This is the node we want to delete, but we will    */\
00528                 /* instead swap it with its successor and delete the  */\
00529                 /* successor.  Record enough information to do the    */\
00530                 /* swap later.  rbp_r_xp is the a_node's parent.      */\
00531                 rbp_r_xp = rbp_r_p;                                     \
00532                 rbp_r_cmp = 1; /* Note that deletion is incomplete.   */\
00533             }                                                           \
00534         }                                                               \
00535         if (rbp_r_cmp == 1) {                                           \
00536             if (rbp_red_get(a_type, a_field, rbp_left_get(a_type,       \
00537               a_field, rbp_right_get(a_type, a_field, rbp_r_c)))        \
00538               == false) {                                               \
00539                 rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c);       \
00540                 if (rbp_red_get(a_type, a_field, rbp_r_t)) {            \
00541                     /* Standard transform.                            */\
00542                     rbp_move_red_right(a_type, a_field, rbp_r_c,        \
00543                       rbp_r_t);                                         \
00544                 } else {                                                \
00545                     /* Root-specific transform.                       */\
00546                     rbp_red_set(a_type, a_field, rbp_r_c);              \
00547                     rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);   \
00548                     if (rbp_red_get(a_type, a_field, rbp_r_u)) {        \
00549                         rbp_black_set(a_type, a_field, rbp_r_u);        \
00550                         rbp_rotate_right(a_type, a_field, rbp_r_c,      \
00551                           rbp_r_t);                                     \
00552                         rbp_rotate_left(a_type, a_field, rbp_r_c,       \
00553                           rbp_r_u);                                     \
00554                         rbp_right_set(a_type, a_field, rbp_r_t,         \
00555                           rbp_r_u);                                     \
00556                     } else {                                            \
00557                         rbp_red_set(a_type, a_field, rbp_r_t);          \
00558                         rbp_rotate_left(a_type, a_field, rbp_r_c,       \
00559                           rbp_r_t);                                     \
00560                     }                                                   \
00561                 }                                                       \
00562                 rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);        \
00563                 rbp_r_c = rbp_r_t;                                      \
00564             } else {                                                    \
00565                 /* Move right.                                        */\
00566                 rbp_r_p = rbp_r_c;                                      \
00567                 rbp_r_c = rbp_right_get(a_type, a_field, rbp_r_c);      \
00568             }                                                           \
00569         }                                                               \
00570     }                                                                   \
00571     if (rbp_r_cmp != 0) {                                               \
00572         while (true) {                                                  \
00573             assert(rbp_r_p != &(a_tree)->rbt_nil);                      \
00574             rbp_r_cmp = (a_cmp)((a_node), rbp_r_c);                     \
00575             if (rbp_r_cmp < 0) {                                        \
00576                 rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c);       \
00577                 if (rbp_r_t == &(a_tree)->rbt_nil) {                    \
00578                     /* rbp_r_c now refers to the successor node to    */\
00579                     /* relocate, and rbp_r_xp/a_node refer to the     */\
00580                     /* context for the relocation.                    */\
00581                     if (rbp_left_get(a_type, a_field, rbp_r_xp)         \
00582                       == (a_node)) {                                    \
00583                         rbp_left_set(a_type, a_field, rbp_r_xp,         \
00584                           rbp_r_c);                                     \
00585                     } else {                                            \
00586                         assert(rbp_right_get(a_type, a_field,           \
00587                           rbp_r_xp) == (a_node));                       \
00588                         rbp_right_set(a_type, a_field, rbp_r_xp,        \
00589                           rbp_r_c);                                     \
00590                     }                                                   \
00591                     rbp_left_set(a_type, a_field, rbp_r_c,              \
00592                       rbp_left_get(a_type, a_field, (a_node)));         \
00593                     rbp_right_set(a_type, a_field, rbp_r_c,             \
00594                       rbp_right_get(a_type, a_field, (a_node)));        \
00595                     rbp_color_set(a_type, a_field, rbp_r_c,             \
00596                       rbp_red_get(a_type, a_field, (a_node)));          \
00597                     if (rbp_left_get(a_type, a_field, rbp_r_p)          \
00598                       == rbp_r_c) {                                     \
00599                         rbp_left_set(a_type, a_field, rbp_r_p,          \
00600                           &(a_tree)->rbt_nil);                          \
00601                     } else {                                            \
00602                         assert(rbp_right_get(a_type, a_field, rbp_r_p)  \
00603                           == rbp_r_c);                                  \
00604                         rbp_right_set(a_type, a_field, rbp_r_p,         \
00605                           &(a_tree)->rbt_nil);                          \
00606                     }                                                   \
00607                     break;                                              \
00608                 }                                                       \
00609                 rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);       \
00610                 if (rbp_red_get(a_type, a_field, rbp_r_t) == false      \
00611                   && rbp_red_get(a_type, a_field, rbp_r_u) == false) {  \
00612                     rbp_move_red_left(a_type, a_field, rbp_r_c,         \
00613                       rbp_r_t);                                         \
00614                     if (rbp_left_get(a_type, a_field, rbp_r_p)          \
00615                       == rbp_r_c) {                                     \
00616                         rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);\
00617                     } else {                                            \
00618                         rbp_right_set(a_type, a_field, rbp_r_p,         \
00619                           rbp_r_t);                                     \
00620                     }                                                   \
00621                     rbp_r_c = rbp_r_t;                                  \
00622                 } else {                                                \
00623                     rbp_r_p = rbp_r_c;                                  \
00624                     rbp_r_c = rbp_left_get(a_type, a_field, rbp_r_c);   \
00625                 }                                                       \
00626             } else {                                                    \
00627                 /* Check whether to delete this node (it has to be    */\
00628                 /* the correct node and a leaf node).                 */\
00629                 if (rbp_r_cmp == 0) {                                   \
00630                     assert((a_node) == rbp_r_c);                        \
00631                     if (rbp_right_get(a_type, a_field, rbp_r_c)         \
00632                       == &(a_tree)->rbt_nil) {                          \
00633                         /* Delete leaf node.                          */\
00634                         if (rbp_left_get(a_type, a_field, rbp_r_c)      \
00635                           != &(a_tree)->rbt_nil) {                      \
00636                             rbp_lean_right(a_type, a_field, rbp_r_c,    \
00637                               rbp_r_t);                                 \
00638                             rbp_right_set(a_type, a_field, rbp_r_t,     \
00639                               &(a_tree)->rbt_nil);                      \
00640                         } else {                                        \
00641                             rbp_r_t = &(a_tree)->rbt_nil;               \
00642                         }                                               \
00643                         if (rbp_left_get(a_type, a_field, rbp_r_p)      \
00644                           == rbp_r_c) {                                 \
00645                             rbp_left_set(a_type, a_field, rbp_r_p,      \
00646                               rbp_r_t);                                 \
00647                         } else {                                        \
00648                             rbp_right_set(a_type, a_field, rbp_r_p,     \
00649                               rbp_r_t);                                 \
00650                         }                                               \
00651                         break;                                          \
00652                     } else {                                            \
00653                         /* This is the node we want to delete, but we */\
00654                         /* will instead swap it with its successor    */\
00655                         /* and delete the successor.  Record enough   */\
00656                         /* information to do the swap later.          */\
00657                         /* rbp_r_xp is a_node's parent.               */\
00658                         rbp_r_xp = rbp_r_p;                             \
00659                     }                                                   \
00660                 }                                                       \
00661                 rbp_r_t = rbp_right_get(a_type, a_field, rbp_r_c);      \
00662                 rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);       \
00663                 if (rbp_red_get(a_type, a_field, rbp_r_u) == false) {   \
00664                     rbp_move_red_right(a_type, a_field, rbp_r_c,        \
00665                       rbp_r_t);                                         \
00666                     if (rbp_left_get(a_type, a_field, rbp_r_p)          \
00667                       == rbp_r_c) {                                     \
00668                         rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);\
00669                     } else {                                            \
00670                         rbp_right_set(a_type, a_field, rbp_r_p,         \
00671                           rbp_r_t);                                     \
00672                     }                                                   \
00673                     rbp_r_c = rbp_r_t;                                  \
00674                 } else {                                                \
00675                     rbp_r_p = rbp_r_c;                                  \
00676                     rbp_r_c = rbp_right_get(a_type, a_field, rbp_r_c);  \
00677                 }                                                       \
00678             }                                                           \
00679         }                                                               \
00680     }                                                                   \
00681     /* Update root.                                                   */\
00682     (a_tree)->rbt_root = rbp_left_get(a_type, a_field, &rbp_r_s);       \
00683 } while (0)
00684 
00685 /*
00686  * The rb_wrap() macro provides a convenient way to wrap functions around the
00687  * cpp macros.  The main benefits of wrapping are that 1) repeated macro
00688  * expansion can cause code bloat, especially for rb_{insert,remove)(), and
00689  * 2) type, linkage, comparison functions, etc. need not be specified at every
00690  * call point.
00691  */
00692 
00693 #define rb_wrap(a_attr, a_prefix, a_tree_type, a_type, a_field, a_cmp)  \
00694 a_attr void                                                             \
00695 a_prefix##new(a_tree_type *tree) {                                      \
00696     rb_new(a_type, a_field, tree);                                      \
00697 }                                                                       \
00698 a_attr a_type *                                                         \
00699 a_prefix##first(a_tree_type *tree) {                                    \
00700     a_type *ret;                                                        \
00701     rb_first(a_type, a_field, tree, ret);                               \
00702     return (ret);                                                       \
00703 }                                                                       \
00704 a_attr a_type *                                                         \
00705 a_prefix##last(a_tree_type *tree) {                                     \
00706     a_type *ret;                                                        \
00707     rb_last(a_type, a_field, tree, ret);                                \
00708     return (ret);                                                       \
00709 }                                                                       \
00710 a_attr a_type *                                                         \
00711 a_prefix##next(a_tree_type *tree, a_type *node) {                       \
00712     a_type *ret;                                                        \
00713     rb_next(a_type, a_field, a_cmp, tree, node, ret);                   \
00714     return (ret);                                                       \
00715 }                                                                       \
00716 a_attr a_type *                                                         \
00717 a_prefix##prev(a_tree_type *tree, a_type *node) {                       \
00718     a_type *ret;                                                        \
00719     rb_prev(a_type, a_field, a_cmp, tree, node, ret);                   \
00720     return (ret);                                                       \
00721 }                                                                       \
00722 a_attr a_type *                                                         \
00723 a_prefix##search(a_tree_type *tree, a_type *key) {                      \
00724     a_type *ret;                                                        \
00725     rb_search(a_type, a_field, a_cmp, tree, key, ret);                  \
00726     return (ret);                                                       \
00727 }                                                                       \
00728 a_attr a_type *                                                         \
00729 a_prefix##nsearch(a_tree_type *tree, a_type *key) {                     \
00730     a_type *ret;                                                        \
00731     rb_nsearch(a_type, a_field, a_cmp, tree, key, ret);                 \
00732     return (ret);                                                       \
00733 }                                                                       \
00734 a_attr a_type *                                                         \
00735 a_prefix##psearch(a_tree_type *tree, a_type *key) {                     \
00736     a_type *ret;                                                        \
00737     rb_psearch(a_type, a_field, a_cmp, tree, key, ret);                 \
00738     return (ret);                                                       \
00739 }                                                                       \
00740 a_attr void                                                             \
00741 a_prefix##insert(a_tree_type *tree, a_type *node) {                     \
00742     rb_insert(a_type, a_field, a_cmp, tree, node);                      \
00743 }                                                                       \
00744 a_attr void                                                             \
00745 a_prefix##remove(a_tree_type *tree, a_type *node) {                     \
00746     rb_remove(a_type, a_field, a_cmp, tree, node);                      \
00747 }
00748 
00749 /*
00750  * The iterators simulate recursion via an array of pointers that store the
00751  * current path.  This is critical to performance, since a series of calls to
00752  * rb_{next,prev}() would require time proportional to (n lg n), whereas this
00753  * implementation only requires time proportional to (n).
00754  *
00755  * Since the iterators cache a path down the tree, any tree modification may
00756  * cause the cached path to become invalid.  In order to continue iteration,
00757  * use something like the following sequence:
00758  *
00759  *   {
00760  *       a_type *node, *tnode;
00761  *
00762  *       rb_foreach_begin(a_type, a_field, a_tree, node) {
00763  *           ...
00764  *           rb_next(a_type, a_field, a_cmp, a_tree, node, tnode);
00765  *           rb_remove(a_type, a_field, a_cmp, a_tree, node);
00766  *           rb_foreach_next(a_type, a_field, a_cmp, a_tree, tnode);
00767  *           ...
00768  *       } rb_foreach_end(a_type, a_field, a_tree, node)
00769  *   }
00770  *
00771  * Note that this idiom is not advised if every iteration modifies the tree,
00772  * since in that case there is no algorithmic complexity improvement over a
00773  * series of rb_{next,prev}() calls, thus making the setup overhead wasted
00774  * effort.
00775  */
00776 
00777 #ifdef RB_NO_C99_VARARRAYS
00778    /*
00779     * Avoid using variable-length arrays, at the cost of using more stack space.
00780     * Size the path arrays such that they are always large enough, even if a
00781     * tree consumes all of memory.  Since each node must contain a minimum of
00782     * two pointers, there can never be more nodes than:
00783     *
00784     *   1 << ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1))
00785     *
00786     * Since the depth of a tree is limited to 3*lg(#nodes), the maximum depth
00787     * is:
00788     *
00789     *   (3 * ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1)))
00790     *
00791     * This works out to a maximum depth of 87 and 180 for 32- and 64-bit
00792     * systems, respectively (approximatly 348 and 1440 bytes, respectively).
00793     */
00794 #  define rbp_compute_f_height(a_type, a_field, a_tree)
00795 #  define rbp_f_height  (3 * ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1)))
00796 #  define rbp_compute_fr_height(a_type, a_field, a_tree)
00797 #  define rbp_fr_height (3 * ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1)))
00798 #else
00799 #  define rbp_compute_f_height(a_type, a_field, a_tree)                 \
00800     /* Compute the maximum possible tree depth (3X the black height). */\
00801     unsigned rbp_f_height;                                              \
00802     rbp_black_height(a_type, a_field, a_tree, rbp_f_height);            \
00803     rbp_f_height *= 3;
00804 #  define rbp_compute_fr_height(a_type, a_field, a_tree)                \
00805     /* Compute the maximum possible tree depth (3X the black height). */\
00806     unsigned rbp_fr_height;                                             \
00807     rbp_black_height(a_type, a_field, a_tree, rbp_fr_height);           \
00808     rbp_fr_height *= 3;
00809 #endif
00810 
00811 #define rb_foreach_begin(a_type, a_field, a_tree, a_var) {              \
00812     rbp_compute_f_height(a_type, a_field, a_tree)                       \
00813     {                                                                   \
00814         /* Initialize the path to contain the left spine.             */\
00815         a_type *rbp_f_path[rbp_f_height];                               \
00816         a_type *rbp_f_node;                                             \
00817         bool rbp_f_synced = false;                                      \
00818         unsigned rbp_f_depth = 0;                                       \
00819         if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {                 \
00820             rbp_f_path[rbp_f_depth] = (a_tree)->rbt_root;               \
00821             rbp_f_depth++;                                              \
00822             while ((rbp_f_node = rbp_left_get(a_type, a_field,          \
00823               rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) {      \
00824                 rbp_f_path[rbp_f_depth] = rbp_f_node;                   \
00825                 rbp_f_depth++;                                          \
00826             }                                                           \
00827         }                                                               \
00828         /* While the path is non-empty, iterate.                      */\
00829         while (rbp_f_depth > 0) {                                       \
00830             (a_var) = rbp_f_path[rbp_f_depth-1];
00831 
00832 /* Only use if modifying the tree during iteration. */
00833 #define rb_foreach_next(a_type, a_field, a_cmp, a_tree, a_node)         \
00834             /* Re-initialize the path to contain the path to a_node.  */\
00835             rbp_f_depth = 0;                                            \
00836             if (a_node != NULL) {                                       \
00837                 if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {         \
00838                     rbp_f_path[rbp_f_depth] = (a_tree)->rbt_root;       \
00839                     rbp_f_depth++;                                      \
00840                     rbp_f_node = rbp_f_path[0];                         \
00841                     while (true) {                                      \
00842                         int rbp_f_cmp = (a_cmp)((a_node),               \
00843                           rbp_f_path[rbp_f_depth-1]);                   \
00844                         if (rbp_f_cmp < 0) {                            \
00845                             rbp_f_node = rbp_left_get(a_type, a_field,  \
00846                               rbp_f_path[rbp_f_depth-1]);               \
00847                         } else if (rbp_f_cmp > 0) {                     \
00848                             rbp_f_node = rbp_right_get(a_type, a_field, \
00849                               rbp_f_path[rbp_f_depth-1]);               \
00850                         } else {                                        \
00851                             break;                                      \
00852                         }                                               \
00853                         assert(rbp_f_node != &(a_tree)->rbt_nil);       \
00854                         rbp_f_path[rbp_f_depth] = rbp_f_node;           \
00855                         rbp_f_depth++;                                  \
00856                     }                                                   \
00857                 }                                                       \
00858             }                                                           \
00859             rbp_f_synced = true;
00860 
00861 #define rb_foreach_end(a_type, a_field, a_tree, a_var)                  \
00862             if (rbp_f_synced) {                                         \
00863                 rbp_f_synced = false;                                   \
00864                 continue;                                               \
00865             }                                                           \
00866             /* Find the successor.                                    */\
00867             if ((rbp_f_node = rbp_right_get(a_type, a_field,            \
00868               rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) {      \
00869                 /* The successor is the left-most node in the right   */\
00870                 /* subtree.                                           */\
00871                 rbp_f_path[rbp_f_depth] = rbp_f_node;                   \
00872                 rbp_f_depth++;                                          \
00873                 while ((rbp_f_node = rbp_left_get(a_type, a_field,      \
00874                   rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) {  \
00875                     rbp_f_path[rbp_f_depth] = rbp_f_node;               \
00876                     rbp_f_depth++;                                      \
00877                 }                                                       \
00878             } else {                                                    \
00879                 /* The successor is above the current node.  Unwind   */\
00880                 /* until a left-leaning edge is removed from the      */\
00881                 /* path, or the path is empty.                        */\
00882                 for (rbp_f_depth--; rbp_f_depth > 0; rbp_f_depth--) {   \
00883                     if (rbp_left_get(a_type, a_field,                   \
00884                       rbp_f_path[rbp_f_depth-1])                        \
00885                       == rbp_f_path[rbp_f_depth]) {                     \
00886                         break;                                          \
00887                     }                                                   \
00888                 }                                                       \
00889             }                                                           \
00890         }                                                               \
00891     }                                                                   \
00892 }
00893 
00894 #define rb_foreach_reverse_begin(a_type, a_field, a_tree, a_var) {      \
00895     rbp_compute_fr_height(a_type, a_field, a_tree)                      \
00896     {                                                                   \
00897         /* Initialize the path to contain the right spine.            */\
00898         a_type *rbp_fr_path[rbp_fr_height];                             \
00899         a_type *rbp_fr_node;                                            \
00900         bool rbp_fr_synced = false;                                     \
00901         unsigned rbp_fr_depth = 0;                                      \
00902         if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {                 \
00903             rbp_fr_path[rbp_fr_depth] = (a_tree)->rbt_root;             \
00904             rbp_fr_depth++;                                             \
00905             while ((rbp_fr_node = rbp_right_get(a_type, a_field,        \
00906               rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) {    \
00907                 rbp_fr_path[rbp_fr_depth] = rbp_fr_node;                \
00908                 rbp_fr_depth++;                                         \
00909             }                                                           \
00910         }                                                               \
00911         /* While the path is non-empty, iterate.                      */\
00912         while (rbp_fr_depth > 0) {                                      \
00913             (a_var) = rbp_fr_path[rbp_fr_depth-1];
00914 
00915 /* Only use if modifying the tree during iteration. */
00916 #define rb_foreach_reverse_prev(a_type, a_field, a_cmp, a_tree, a_node) \
00917             /* Re-initialize the path to contain the path to a_node.  */\
00918             rbp_fr_depth = 0;                                           \
00919             if (a_node != NULL) {                                       \
00920                 if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {         \
00921                     rbp_fr_path[rbp_fr_depth] = (a_tree)->rbt_root;     \
00922                     rbp_fr_depth++;                                     \
00923                     rbp_fr_node = rbp_fr_path[0];                       \
00924                     while (true) {                                      \
00925                         int rbp_fr_cmp = (a_cmp)((a_node),              \
00926                           rbp_fr_path[rbp_fr_depth-1]);                 \
00927                         if (rbp_fr_cmp < 0) {                           \
00928                             rbp_fr_node = rbp_left_get(a_type, a_field, \
00929                               rbp_fr_path[rbp_fr_depth-1]);             \
00930                         } else if (rbp_fr_cmp > 0) {                    \
00931                             rbp_fr_node = rbp_right_get(a_type, a_field,\
00932                               rbp_fr_path[rbp_fr_depth-1]);             \
00933                         } else {                                        \
00934                             break;                                      \
00935                         }                                               \
00936                         assert(rbp_fr_node != &(a_tree)->rbt_nil);      \
00937                         rbp_fr_path[rbp_fr_depth] = rbp_fr_node;        \
00938                         rbp_fr_depth++;                                 \
00939                     }                                                   \
00940                 }                                                       \
00941             }                                                           \
00942             rbp_fr_synced = true;
00943 
00944 #define rb_foreach_reverse_end(a_type, a_field, a_tree, a_var)          \
00945             if (rbp_fr_synced) {                                        \
00946                 rbp_fr_synced = false;                                  \
00947                 continue;                                               \
00948             }                                                           \
00949             if (rbp_fr_depth == 0) {                                    \
00950                 /* rb_foreach_reverse_sync() was called with a NULL   */\
00951                 /* a_node.                                            */\
00952                 break;                                                  \
00953             }                                                           \
00954             /* Find the predecessor.                                  */\
00955             if ((rbp_fr_node = rbp_left_get(a_type, a_field,            \
00956               rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) {    \
00957                 /* The predecessor is the right-most node in the left */\
00958                 /* subtree.                                           */\
00959                 rbp_fr_path[rbp_fr_depth] = rbp_fr_node;                \
00960                 rbp_fr_depth++;                                         \
00961                 while ((rbp_fr_node = rbp_right_get(a_type, a_field,    \
00962                   rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) {\
00963                     rbp_fr_path[rbp_fr_depth] = rbp_fr_node;            \
00964                     rbp_fr_depth++;                                     \
00965                 }                                                       \
00966             } else {                                                    \
00967                 /* The predecessor is above the current node.  Unwind */\
00968                 /* until a right-leaning edge is removed from the     */\
00969                 /* path, or the path is empty.                        */\
00970                 for (rbp_fr_depth--; rbp_fr_depth > 0; rbp_fr_depth--) {\
00971                     if (rbp_right_get(a_type, a_field,                  \
00972                       rbp_fr_path[rbp_fr_depth-1])                      \
00973                       == rbp_fr_path[rbp_fr_depth]) {                   \
00974                         break;                                          \
00975                     }                                                   \
00976                 }                                                       \
00977             }                                                           \
00978         }                                                               \
00979     }                                                                   \
00980 }
00981 
00982 #endif /* RB_H_ */