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