|
Gnash
0.8.10
|
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_ */
1.7.5