1/*- 2 ******************************************************************************* 3 * 4 * Copyright (C) 2008-2010 Jason Evans <jasone@FreeBSD.org>. 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice(s), this list of conditions and the following disclaimer 12 * unmodified other than the allowable addition of one or more 13 * copyright notices. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice(s), this list of conditions and the following disclaimer in 16 * the documentation and/or other materials provided with the 17 * distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY 20 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE 23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 26 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 28 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 29 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 * 31 ****************************************************************************** 32 * 33 * cpp macro implementation of left-leaning 2-3 red-black trees. Parent 34 * pointers are not used, and color bits are stored in the least significant 35 * bit of right-child pointers (if RB_COMPACT is defined), thus making node 36 * linkage as compact as is possible for red-black trees. 37 * 38 * Usage: 39 * 40 * #include <stdint.h> 41 * #include <stdbool.h> 42 * #define NDEBUG // (Optional, see assert(3).) 43 * #include <assert.h> 44 * #define RB_COMPACT // (Optional, embed color bits in right-child pointers.) 45 * #include <rb.h> 46 * ... 47 * 48 ******************************************************************************* 49 */ 50 51#ifndef RB_H_ 52#define RB_H_ 53 54#include <sys/cdefs.h> 55__FBSDID("$FreeBSD$"); 56 57#ifdef RB_COMPACT 58/* Node structure. */ 59#define rb_node(a_type) \ 60struct { \ 61 a_type *rbn_left; \ 62 a_type *rbn_right_red; \ 63} 64#else 65#define rb_node(a_type) \ 66struct { \ 67 a_type *rbn_left; \ 68 a_type *rbn_right; \ 69 bool rbn_red; \ 70} 71#endif 72 73/* Root structure. */ 74#define rb_tree(a_type) \ 75struct { \ 76 a_type *rbt_root; \ 77 a_type rbt_nil; \ 78} 79 80/* Left accessors. */ 81#define rbtn_left_get(a_type, a_field, a_node) \ 82 ((a_node)->a_field.rbn_left) 83#define rbtn_left_set(a_type, a_field, a_node, a_left) do { \ 84 (a_node)->a_field.rbn_left = a_left; \ 85} while (0) 86 87#ifdef RB_COMPACT 88/* Right accessors. */ 89#define rbtn_right_get(a_type, a_field, a_node) \ 90 ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red) \ 91 & ((ssize_t)-2))) 92#define rbtn_right_set(a_type, a_field, a_node, a_right) do { \ 93 (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right) \ 94 | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1))); \ 95} while (0) 96 97/* Color accessors. */ 98#define rbtn_red_get(a_type, a_field, a_node) \ 99 ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red) \ 100 & ((size_t)1))) 101#define rbtn_color_set(a_type, a_field, a_node, a_red) do { \ 102 (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t) \ 103 (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)) \ 104 | ((ssize_t)a_red)); \ 105} while (0) 106#define rbtn_red_set(a_type, a_field, a_node) do { \ 107 (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) \ 108 (a_node)->a_field.rbn_right_red) | ((size_t)1)); \ 109} while (0) 110#define rbtn_black_set(a_type, a_field, a_node) do { \ 111 (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t) \ 112 (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)); \ 113} while (0) 114#else 115/* Right accessors. */ 116#define rbtn_right_get(a_type, a_field, a_node) \ 117 ((a_node)->a_field.rbn_right) 118#define rbtn_right_set(a_type, a_field, a_node, a_right) do { \ 119 (a_node)->a_field.rbn_right = a_right; \ 120} while (0) 121 122/* Color accessors. */ 123#define rbtn_red_get(a_type, a_field, a_node) \ 124 ((a_node)->a_field.rbn_red) 125#define rbtn_color_set(a_type, a_field, a_node, a_red) do { \ 126 (a_node)->a_field.rbn_red = (a_red); \ 127} while (0) 128#define rbtn_red_set(a_type, a_field, a_node) do { \ 129 (a_node)->a_field.rbn_red = true; \ 130} while (0) 131#define rbtn_black_set(a_type, a_field, a_node) do { \ 132 (a_node)->a_field.rbn_red = false; \ 133} while (0) 134#endif 135 136/* Node initializer. */ 137#define rbt_node_new(a_type, a_field, a_rbt, a_node) do { \ 138 rbtn_left_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \ 139 rbtn_right_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \ 140 rbtn_red_set(a_type, a_field, (a_node)); \ 141} while (0) 142 143/* Tree initializer. */ 144#define rb_new(a_type, a_field, a_rbt) do { \ 145 (a_rbt)->rbt_root = &(a_rbt)->rbt_nil; \ 146 rbt_node_new(a_type, a_field, a_rbt, &(a_rbt)->rbt_nil); \ 147 rbtn_black_set(a_type, a_field, &(a_rbt)->rbt_nil); \ 148} while (0) 149 150/* Internal utility macros. */ 151#define rbtn_first(a_type, a_field, a_rbt, a_root, r_node) do { \ 152 (r_node) = (a_root); \ 153 if ((r_node) != &(a_rbt)->rbt_nil) { \ 154 for (; \ 155 rbtn_left_get(a_type, a_field, (r_node)) != &(a_rbt)->rbt_nil;\ 156 (r_node) = rbtn_left_get(a_type, a_field, (r_node))) { \ 157 } \ 158 } \ 159} while (0) 160 161#define rbtn_last(a_type, a_field, a_rbt, a_root, r_node) do { \ 162 (r_node) = (a_root); \ 163 if ((r_node) != &(a_rbt)->rbt_nil) { \ 164 for (; rbtn_right_get(a_type, a_field, (r_node)) != \ 165 &(a_rbt)->rbt_nil; (r_node) = rbtn_right_get(a_type, a_field, \ 166 (r_node))) { \ 167 } \ 168 } \ 169} while (0) 170 171#define rbtn_rotate_left(a_type, a_field, a_node, r_node) do { \ 172 (r_node) = rbtn_right_get(a_type, a_field, (a_node)); \ 173 rbtn_right_set(a_type, a_field, (a_node), \ 174 rbtn_left_get(a_type, a_field, (r_node))); \ 175 rbtn_left_set(a_type, a_field, (r_node), (a_node)); \ 176} while (0) 177 178#define rbtn_rotate_right(a_type, a_field, a_node, r_node) do { \ 179 (r_node) = rbtn_left_get(a_type, a_field, (a_node)); \ 180 rbtn_left_set(a_type, a_field, (a_node), \ 181 rbtn_right_get(a_type, a_field, (r_node))); \ 182 rbtn_right_set(a_type, a_field, (r_node), (a_node)); \ 183} while (0) 184 185/* 186 * The rb_proto() macro generates function prototypes that correspond to the 187 * functions generated by an equivalently parameterized call to rb_gen(). 188 */ 189 190#define rb_proto(a_attr, a_prefix, a_rbt_type, a_type) \ 191a_attr void \ 192a_prefix##new(a_rbt_type *rbtree); \ 193a_attr a_type * \ 194a_prefix##first(a_rbt_type *rbtree); \ 195a_attr a_type * \ 196a_prefix##last(a_rbt_type *rbtree); \ 197a_attr a_type * \ 198a_prefix##next(a_rbt_type *rbtree, a_type *node); \ 199a_attr a_type * \ 200a_prefix##prev(a_rbt_type *rbtree, a_type *node); \ 201a_attr a_type * \ 202a_prefix##search(a_rbt_type *rbtree, a_type *key); \ 203a_attr a_type * \ 204a_prefix##nsearch(a_rbt_type *rbtree, a_type *key); \ 205a_attr a_type * \ 206a_prefix##psearch(a_rbt_type *rbtree, a_type *key); \ 207a_attr void \ 208a_prefix##insert(a_rbt_type *rbtree, a_type *node); \ 209a_attr void \ 210a_prefix##remove(a_rbt_type *rbtree, a_type *node); \ 211a_attr a_type * \ 212a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \ 213 a_rbt_type *, a_type *, void *), void *arg); \ 214a_attr a_type * \ 215a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \ 216 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg); 217 218/* 219 * The rb_gen() macro generates a type-specific red-black tree implementation, 220 * based on the above cpp macros. 221 * 222 * Arguments: 223 * 224 * a_attr : Function attribute for generated functions (ex: static). 225 * a_prefix : Prefix for generated functions (ex: extree_). 226 * a_rb_type : Type for red-black tree data structure (ex: extree_t). 227 * a_type : Type for red-black tree node data structure (ex: 228 * extree_node_t). 229 * a_field : Name of red-black tree node linkage (ex: extree_link). 230 * a_cmp : Node comparison function name, with the following prototype: 231 * int (a_cmp *)(a_type *a_node, a_type *a_other); 232 * ^^^^^^ 233 * or a_key 234 * Interpretation of comparision function return values: 235 * -1 : a_node < a_other 236 * 0 : a_node == a_other 237 * 1 : a_node > a_other 238 * In all cases, the a_node or a_key macro argument is the first 239 * argument to the comparison function, which makes it possible 240 * to write comparison functions that treat the first argument 241 * specially. 242 * 243 * Assuming the following setup: 244 * 245 * typedef struct ex_node_s ex_node_t; 246 * struct ex_node_s { 247 * rb_node(ex_node_t) ex_link; 248 * }; 249 * typedef rb(ex_node_t) ex_t; 250 * rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp, 1297, 1301) 251 * 252 * The following API is generated: 253 * 254 * static void 255 * ex_new(ex_t *extree); 256 * Description: Initialize a red-black tree structure. 257 * Args: 258 * extree: Pointer to an uninitialized red-black tree object. 259 * 260 * static ex_node_t * 261 * ex_first(ex_t *extree); 262 * static ex_node_t * 263 * ex_last(ex_t *extree); 264 * Description: Get the first/last node in extree. 265 * Args: 266 * extree: Pointer to an initialized red-black tree object. 267 * Ret: First/last node in extree, or NULL if extree is empty. 268 * 269 * static ex_node_t * 270 * ex_next(ex_t *extree, ex_node_t *node); 271 * static ex_node_t * 272 * ex_prev(ex_t *extree, ex_node_t *node); 273 * Description: Get node's successor/predecessor. 274 * Args: 275 * extree: Pointer to an initialized red-black tree object. 276 * node : A node in extree. 277 * Ret: node's successor/predecessor in extree, or NULL if node is 278 * last/first. 279 * 280 * static ex_node_t * 281 * ex_search(ex_t *extree, ex_node_t *key); 282 * Description: Search for node that matches key. 283 * Args: 284 * extree: Pointer to an initialized red-black tree object. 285 * key : Search key. 286 * Ret: Node in extree that matches key, or NULL if no match. 287 * 288 * static ex_node_t * 289 * ex_nsearch(ex_t *extree, ex_node_t *key); 290 * static ex_node_t * 291 * ex_psearch(ex_t *extree, ex_node_t *key); 292 * Description: Search for node that matches key. If no match is found, 293 * return what would be key's successor/predecessor, were 294 * key in extree. 295 * Args: 296 * extree: Pointer to an initialized red-black tree object. 297 * key : Search key. 298 * Ret: Node in extree that matches key, or if no match, hypothetical 299 * node's successor/predecessor (NULL if no successor/predecessor). 300 * 301 * static void 302 * ex_insert(ex_t *extree, ex_node_t *node); 303 * Description: Insert node into extree. 304 * Args: 305 * extree: Pointer to an initialized red-black tree object. 306 * node : Node to be inserted into extree. 307 * 308 * static void 309 * ex_remove(ex_t *extree, ex_node_t *node); 310 * Description: Remove node from extree. 311 * Args: 312 * extree: Pointer to an initialized red-black tree object. 313 * node : Node in extree to be removed. 314 * 315 * static ex_node_t * 316 * ex_iter(ex_t *extree, ex_node_t *start, ex_node_t *(*cb)(ex_t *, 317 * ex_node_t *, void *), void *arg); 318 * static ex_node_t * 319 * ex_reverse_iter(ex_t *extree, ex_node_t *start, ex_node *(*cb)(ex_t *, 320 * ex_node_t *, void *), void *arg); 321 * Description: Iterate forward/backward over extree, starting at node. 322 * If extree is modified, iteration must be immediately 323 * terminated by the callback function that causes the 324 * modification. 325 * Args: 326 * extree: Pointer to an initialized red-black tree object. 327 * start : Node at which to start iteration, or NULL to start at 328 * first/last node. 329 * cb : Callback function, which is called for each node during 330 * iteration. Under normal circumstances the callback function 331 * should return NULL, which causes iteration to continue. If a 332 * callback function returns non-NULL, iteration is immediately 333 * terminated and the non-NULL return value is returned by the 334 * iterator. This is useful for re-starting iteration after 335 * modifying extree. 336 * arg : Opaque pointer passed to cb(). 337 * Ret: NULL if iteration completed, or the non-NULL callback return value 338 * that caused termination of the iteration. 339 */ 340#define rb_gen(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp) \ 341a_attr void \ 342a_prefix##new(a_rbt_type *rbtree) { \ 343 rb_new(a_type, a_field, rbtree); \ 344} \ 345a_attr a_type * \ 346a_prefix##first(a_rbt_type *rbtree) { \ 347 a_type *ret; \ 348 rbtn_first(a_type, a_field, rbtree, rbtree->rbt_root, ret); \ 349 if (ret == &rbtree->rbt_nil) { \ 350 ret = NULL; \ 351 } \ 352 return (ret); \ 353} \ 354a_attr a_type * \ 355a_prefix##last(a_rbt_type *rbtree) { \ 356 a_type *ret; \ 357 rbtn_last(a_type, a_field, rbtree, rbtree->rbt_root, ret); \ 358 if (ret == &rbtree->rbt_nil) { \ 359 ret = NULL; \ 360 } \ 361 return (ret); \ 362} \ 363a_attr a_type * \ 364a_prefix##next(a_rbt_type *rbtree, a_type *node) { \ 365 a_type *ret; \ 366 if (rbtn_right_get(a_type, a_field, node) != &rbtree->rbt_nil) { \ 367 rbtn_first(a_type, a_field, rbtree, rbtn_right_get(a_type, \ 368 a_field, node), ret); \ 369 } else { \ 370 a_type *tnode = rbtree->rbt_root; \ 371 assert(tnode != &rbtree->rbt_nil); \ 372 ret = &rbtree->rbt_nil; \ 373 while (true) { \ 374 int cmp = (a_cmp)(node, tnode); \ 375 if (cmp < 0) { \ 376 ret = tnode; \ 377 tnode = rbtn_left_get(a_type, a_field, tnode); \ 378 } else if (cmp > 0) { \ 379 tnode = rbtn_right_get(a_type, a_field, tnode); \ 380 } else { \ 381 break; \ 382 } \ 383 assert(tnode != &rbtree->rbt_nil); \ 384 } \ 385 } \ 386 if (ret == &rbtree->rbt_nil) { \ 387 ret = (NULL); \ 388 } \ 389 return (ret); \ 390} \ 391a_attr a_type * \ 392a_prefix##prev(a_rbt_type *rbtree, a_type *node) { \ 393 a_type *ret; \ 394 if (rbtn_left_get(a_type, a_field, node) != &rbtree->rbt_nil) { \ 395 rbtn_last(a_type, a_field, rbtree, rbtn_left_get(a_type, \ 396 a_field, node), ret); \ 397 } else { \ 398 a_type *tnode = rbtree->rbt_root; \ 399 assert(tnode != &rbtree->rbt_nil); \ 400 ret = &rbtree->rbt_nil; \ 401 while (true) { \ 402 int cmp = (a_cmp)(node, tnode); \ 403 if (cmp < 0) { \ 404 tnode = rbtn_left_get(a_type, a_field, tnode); \ 405 } else if (cmp > 0) { \ 406 ret = tnode; \ 407 tnode = rbtn_right_get(a_type, a_field, tnode); \ 408 } else { \ 409 break; \ 410 } \ 411 assert(tnode != &rbtree->rbt_nil); \ 412 } \ 413 } \ 414 if (ret == &rbtree->rbt_nil) { \ 415 ret = (NULL); \ 416 } \ 417 return (ret); \ 418} \ 419a_attr a_type * \ 420a_prefix##search(a_rbt_type *rbtree, a_type *key) { \ 421 a_type *ret; \ 422 int cmp; \ 423 ret = rbtree->rbt_root; \ 424 while (ret != &rbtree->rbt_nil \ 425 && (cmp = (a_cmp)(key, ret)) != 0) { \ 426 if (cmp < 0) { \ 427 ret = rbtn_left_get(a_type, a_field, ret); \ 428 } else { \ 429 ret = rbtn_right_get(a_type, a_field, ret); \ 430 } \ 431 } \ 432 if (ret == &rbtree->rbt_nil) { \ 433 ret = (NULL); \ 434 } \ 435 return (ret); \ 436} \ 437a_attr a_type * \ 438a_prefix##nsearch(a_rbt_type *rbtree, a_type *key) { \ 439 a_type *ret; \ 440 a_type *tnode = rbtree->rbt_root; \ 441 ret = &rbtree->rbt_nil; \ 442 while (tnode != &rbtree->rbt_nil) { \ 443 int cmp = (a_cmp)(key, tnode); \ 444 if (cmp < 0) { \ 445 ret = tnode; \ 446 tnode = rbtn_left_get(a_type, a_field, tnode); \ 447 } else if (cmp > 0) { \ 448 tnode = rbtn_right_get(a_type, a_field, tnode); \ 449 } else { \ 450 ret = tnode; \ 451 break; \ 452 } \ 453 } \ 454 if (ret == &rbtree->rbt_nil) { \ 455 ret = (NULL); \ 456 } \ 457 return (ret); \ 458} \ 459a_attr a_type * \ 460a_prefix##psearch(a_rbt_type *rbtree, a_type *key) { \ 461 a_type *ret; \ 462 a_type *tnode = rbtree->rbt_root; \ 463 ret = &rbtree->rbt_nil; \ 464 while (tnode != &rbtree->rbt_nil) { \ 465 int cmp = (a_cmp)(key, tnode); \ 466 if (cmp < 0) { \ 467 tnode = rbtn_left_get(a_type, a_field, tnode); \ 468 } else if (cmp > 0) { \ 469 ret = tnode; \ 470 tnode = rbtn_right_get(a_type, a_field, tnode); \ 471 } else { \ 472 ret = tnode; \ 473 break; \ 474 } \ 475 } \ 476 if (ret == &rbtree->rbt_nil) { \ 477 ret = (NULL); \ 478 } \ 479 return (ret); \ 480} \ 481a_attr void \ 482a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \ 483 struct { \ 484 a_type *node; \ 485 int cmp; \ 486 } path[sizeof(void *) << 4], *pathp; \ 487 rbt_node_new(a_type, a_field, rbtree, node); \ 488 /* Wind. */ \ 489 path->node = rbtree->rbt_root; \ 490 for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \ 491 int cmp = pathp->cmp = a_cmp(node, pathp->node); \ 492 assert(cmp != 0); \ 493 if (cmp < 0) { \ 494 pathp[1].node = rbtn_left_get(a_type, a_field, \ 495 pathp->node); \ 496 } else { \ 497 pathp[1].node = rbtn_right_get(a_type, a_field, \ 498 pathp->node); \ 499 } \ 500 } \ 501 pathp->node = node; \ 502 /* Unwind. */ \ 503 for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \ 504 a_type *cnode = pathp->node; \ 505 if (pathp->cmp < 0) { \ 506 a_type *left = pathp[1].node; \ 507 rbtn_left_set(a_type, a_field, cnode, left); \ 508 if (rbtn_red_get(a_type, a_field, left)) { \ 509 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ 510 if (rbtn_red_get(a_type, a_field, leftleft)) { \ 511 /* Fix up 4-node. */ \ 512 a_type *tnode; \ 513 rbtn_black_set(a_type, a_field, leftleft); \ 514 rbtn_rotate_right(a_type, a_field, cnode, tnode); \ 515 cnode = tnode; \ 516 } \ 517 } else { \ 518 return; \ 519 } \ 520 } else { \ 521 a_type *right = pathp[1].node; \ 522 rbtn_right_set(a_type, a_field, cnode, right); \ 523 if (rbtn_red_get(a_type, a_field, right)) { \ 524 a_type *left = rbtn_left_get(a_type, a_field, cnode); \ 525 if (rbtn_red_get(a_type, a_field, left)) { \ 526 /* Split 4-node. */ \ 527 rbtn_black_set(a_type, a_field, left); \ 528 rbtn_black_set(a_type, a_field, right); \ 529 rbtn_red_set(a_type, a_field, cnode); \ 530 } else { \ 531 /* Lean left. */ \ 532 a_type *tnode; \ 533 bool tred = rbtn_red_get(a_type, a_field, cnode); \ 534 rbtn_rotate_left(a_type, a_field, cnode, tnode); \ 535 rbtn_color_set(a_type, a_field, tnode, tred); \ 536 rbtn_red_set(a_type, a_field, cnode); \ 537 cnode = tnode; \ 538 } \ 539 } else { \ 540 return; \ 541 } \ 542 } \ 543 pathp->node = cnode; \ 544 } \ 545 /* Set root, and make it black. */ \ 546 rbtree->rbt_root = path->node; \ 547 rbtn_black_set(a_type, a_field, rbtree->rbt_root); \ 548} \ 549a_attr void \ 550a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ 551 struct { \ 552 a_type *node; \ 553 int cmp; \ 554 } *pathp, *nodep, path[sizeof(void *) << 4]; \ 555 /* Wind. */ \ 556 nodep = NULL; /* Silence compiler warning. */ \ 557 path->node = rbtree->rbt_root; \ 558 for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \ 559 int cmp = pathp->cmp = a_cmp(node, pathp->node); \ 560 if (cmp < 0) { \ 561 pathp[1].node = rbtn_left_get(a_type, a_field, \ 562 pathp->node); \ 563 } else { \ 564 pathp[1].node = rbtn_right_get(a_type, a_field, \ 565 pathp->node); \ 566 if (cmp == 0) { \ 567 /* Find node's successor, in preparation for swap. */ \ 568 pathp->cmp = 1; \ 569 nodep = pathp; \ 570 for (pathp++; pathp->node != &rbtree->rbt_nil; \ 571 pathp++) { \ 572 pathp->cmp = -1; \ 573 pathp[1].node = rbtn_left_get(a_type, a_field, \ 574 pathp->node); \ 575 } \ 576 break; \ 577 } \ 578 } \ 579 } \ 580 assert(nodep->node == node); \ 581 pathp--; \ 582 if (pathp->node != node) { \ 583 /* Swap node with its successor. */ \ 584 bool tred = rbtn_red_get(a_type, a_field, pathp->node); \ 585 rbtn_color_set(a_type, a_field, pathp->node, \ 586 rbtn_red_get(a_type, a_field, node)); \ 587 rbtn_left_set(a_type, a_field, pathp->node, \ 588 rbtn_left_get(a_type, a_field, node)); \ 589 /* If node's successor is its right child, the following code */\ 590 /* will do the wrong thing for the right child pointer. */\ 591 /* However, it doesn't matter, because the pointer will be */\ 592 /* properly set when the successor is pruned. */\ 593 rbtn_right_set(a_type, a_field, pathp->node, \ 594 rbtn_right_get(a_type, a_field, node)); \ 595 rbtn_color_set(a_type, a_field, node, tred); \ 596 /* The pruned leaf node's child pointers are never accessed */\ 597 /* again, so don't bother setting them to nil. */\ 598 nodep->node = pathp->node; \ 599 pathp->node = node; \ 600 if (nodep == path) { \ 601 rbtree->rbt_root = nodep->node; \ 602 } else { \ 603 if (nodep[-1].cmp < 0) { \ 604 rbtn_left_set(a_type, a_field, nodep[-1].node, \ 605 nodep->node); \ 606 } else { \ 607 rbtn_right_set(a_type, a_field, nodep[-1].node, \ 608 nodep->node); \ 609 } \ 610 } \ 611 } else { \ 612 a_type *left = rbtn_left_get(a_type, a_field, node); \ 613 if (left != &rbtree->rbt_nil) { \ 614 /* node has no successor, but it has a left child. */\ 615 /* Splice node out, without losing the left child. */\ 616 assert(rbtn_red_get(a_type, a_field, node) == false); \ 617 assert(rbtn_red_get(a_type, a_field, left)); \ 618 rbtn_black_set(a_type, a_field, left); \ 619 if (pathp == path) { \ 620 rbtree->rbt_root = left; \ 621 } else { \ 622 if (pathp[-1].cmp < 0) { \ 623 rbtn_left_set(a_type, a_field, pathp[-1].node, \ 624 left); \ 625 } else { \ 626 rbtn_right_set(a_type, a_field, pathp[-1].node, \ 627 left); \ 628 } \ 629 } \ 630 return; \ 631 } else if (pathp == path) { \ 632 /* The tree only contained one node. */ \ 633 rbtree->rbt_root = &rbtree->rbt_nil; \ 634 return; \ 635 } \ 636 } \ 637 if (rbtn_red_get(a_type, a_field, pathp->node)) { \ 638 /* Prune red node, which requires no fixup. */ \ 639 assert(pathp[-1].cmp < 0); \ 640 rbtn_left_set(a_type, a_field, pathp[-1].node, \ 641 &rbtree->rbt_nil); \ 642 return; \ 643 } \ 644 /* The node to be pruned is black, so unwind until balance is */\ 645 /* restored. */\ 646 pathp->node = &rbtree->rbt_nil; \ 647 for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \ 648 assert(pathp->cmp != 0); \ 649 if (pathp->cmp < 0) { \ 650 rbtn_left_set(a_type, a_field, pathp->node, \ 651 pathp[1].node); \ 652 assert(rbtn_red_get(a_type, a_field, pathp[1].node) \ 653 == false); \ 654 if (rbtn_red_get(a_type, a_field, pathp->node)) { \ 655 a_type *right = rbtn_right_get(a_type, a_field, \ 656 pathp->node); \ 657 a_type *rightleft = rbtn_left_get(a_type, a_field, \ 658 right); \ 659 a_type *tnode; \ 660 if (rbtn_red_get(a_type, a_field, rightleft)) { \ 661 /* In the following diagrams, ||, //, and \\ */\ 662 /* indicate the path to the removed node. */\ 663 /* */\ 664 /* || */\ 665 /* pathp(r) */\ 666 /* // \ */\ 667 /* (b) (b) */\ 668 /* / */\ 669 /* (r) */\ 670 /* */\ 671 rbtn_black_set(a_type, a_field, pathp->node); \ 672 rbtn_rotate_right(a_type, a_field, right, tnode); \ 673 rbtn_right_set(a_type, a_field, pathp->node, tnode);\ 674 rbtn_rotate_left(a_type, a_field, pathp->node, \ 675 tnode); \ 676 } else { \ 677 /* || */\ 678 /* pathp(r) */\ 679 /* // \ */\ 680 /* (b) (b) */\ 681 /* / */\ 682 /* (b) */\ 683 /* */\ 684 rbtn_rotate_left(a_type, a_field, pathp->node, \ 685 tnode); \ 686 } \ 687 /* Balance restored, but rotation modified subtree */\ 688 /* root. */\ 689 assert((uintptr_t)pathp > (uintptr_t)path); \ 690 if (pathp[-1].cmp < 0) { \ 691 rbtn_left_set(a_type, a_field, pathp[-1].node, \ 692 tnode); \ 693 } else { \ 694 rbtn_right_set(a_type, a_field, pathp[-1].node, \ 695 tnode); \ 696 } \ 697 return; \ 698 } else { \ 699 a_type *right = rbtn_right_get(a_type, a_field, \ 700 pathp->node); \ 701 a_type *rightleft = rbtn_left_get(a_type, a_field, \ 702 right); \ 703 if (rbtn_red_get(a_type, a_field, rightleft)) { \ 704 /* || */\ 705 /* pathp(b) */\ 706 /* // \ */\ 707 /* (b) (b) */\ 708 /* / */\ 709 /* (r) */\ 710 a_type *tnode; \ 711 rbtn_black_set(a_type, a_field, rightleft); \ 712 rbtn_rotate_right(a_type, a_field, right, tnode); \ 713 rbtn_right_set(a_type, a_field, pathp->node, tnode);\ 714 rbtn_rotate_left(a_type, a_field, pathp->node, \ 715 tnode); \ 716 /* Balance restored, but rotation modified */\ 717 /* subree root, which may actually be the tree */\ 718 /* root. */\ 719 if (pathp == path) { \ 720 /* Set root. */ \ 721 rbtree->rbt_root = tnode; \ 722 } else { \ 723 if (pathp[-1].cmp < 0) { \ 724 rbtn_left_set(a_type, a_field, \ 725 pathp[-1].node, tnode); \ 726 } else { \ 727 rbtn_right_set(a_type, a_field, \ 728 pathp[-1].node, tnode); \ 729 } \ 730 } \ 731 return; \ 732 } else { \ 733 /* || */\ 734 /* pathp(b) */\ 735 /* // \ */\ 736 /* (b) (b) */\ 737 /* / */\ 738 /* (b) */\ 739 a_type *tnode; \ 740 rbtn_red_set(a_type, a_field, pathp->node); \ 741 rbtn_rotate_left(a_type, a_field, pathp->node, \ 742 tnode); \ 743 pathp->node = tnode; \ 744 } \ 745 } \ 746 } else { \ 747 a_type *left; \ 748 rbtn_right_set(a_type, a_field, pathp->node, \ 749 pathp[1].node); \ 750 left = rbtn_left_get(a_type, a_field, pathp->node); \ 751 if (rbtn_red_get(a_type, a_field, left)) { \ 752 a_type *tnode; \ 753 a_type *leftright = rbtn_right_get(a_type, a_field, \ 754 left); \ 755 a_type *leftrightleft = rbtn_left_get(a_type, a_field, \ 756 leftright); \ 757 if (rbtn_red_get(a_type, a_field, leftrightleft)) { \ 758 /* || */\ 759 /* pathp(b) */\ 760 /* / \\ */\ 761 /* (r) (b) */\ 762 /* \ */\ 763 /* (b) */\ 764 /* / */\ 765 /* (r) */\ 766 a_type *unode; \ 767 rbtn_black_set(a_type, a_field, leftrightleft); \ 768 rbtn_rotate_right(a_type, a_field, pathp->node, \ 769 unode); \ 770 rbtn_rotate_right(a_type, a_field, pathp->node, \ 771 tnode); \ 772 rbtn_right_set(a_type, a_field, unode, tnode); \ 773 rbtn_rotate_left(a_type, a_field, unode, tnode); \ 774 } else { \ 775 /* || */\ 776 /* pathp(b) */\ 777 /* / \\ */\ 778 /* (r) (b) */\ 779 /* \ */\ 780 /* (b) */\ 781 /* / */\ 782 /* (b) */\ 783 assert(leftright != &rbtree->rbt_nil); \ 784 rbtn_red_set(a_type, a_field, leftright); \ 785 rbtn_rotate_right(a_type, a_field, pathp->node, \ 786 tnode); \ 787 rbtn_black_set(a_type, a_field, tnode); \ 788 } \ 789 /* Balance restored, but rotation modified subtree */\ 790 /* root, which may actually be the tree root. */\ 791 if (pathp == path) { \ 792 /* Set root. */ \ 793 rbtree->rbt_root = tnode; \ 794 } else { \ 795 if (pathp[-1].cmp < 0) { \ 796 rbtn_left_set(a_type, a_field, pathp[-1].node, \ 797 tnode); \ 798 } else { \ 799 rbtn_right_set(a_type, a_field, pathp[-1].node, \ 800 tnode); \ 801 } \ 802 } \ 803 return; \ 804 } else if (rbtn_red_get(a_type, a_field, pathp->node)) { \ 805 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ 806 if (rbtn_red_get(a_type, a_field, leftleft)) { \ 807 /* || */\ 808 /* pathp(r) */\ 809 /* / \\ */\ 810 /* (b) (b) */\ 811 /* / */\ 812 /* (r) */\ 813 a_type *tnode; \ 814 rbtn_black_set(a_type, a_field, pathp->node); \ 815 rbtn_red_set(a_type, a_field, left); \ 816 rbtn_black_set(a_type, a_field, leftleft); \ 817 rbtn_rotate_right(a_type, a_field, pathp->node, \ 818 tnode); \ 819 /* Balance restored, but rotation modified */\ 820 /* subtree root. */\ 821 assert((uintptr_t)pathp > (uintptr_t)path); \ 822 if (pathp[-1].cmp < 0) { \ 823 rbtn_left_set(a_type, a_field, pathp[-1].node, \ 824 tnode); \ 825 } else { \ 826 rbtn_right_set(a_type, a_field, pathp[-1].node, \ 827 tnode); \ 828 } \ 829 return; \ 830 } else { \ 831 /* || */\ 832 /* pathp(r) */\ 833 /* / \\ */\ 834 /* (b) (b) */\ 835 /* / */\ 836 /* (b) */\ 837 rbtn_red_set(a_type, a_field, left); \ 838 rbtn_black_set(a_type, a_field, pathp->node); \ 839 /* Balance restored. */ \ 840 return; \ 841 } \ 842 } else { \ 843 a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ 844 if (rbtn_red_get(a_type, a_field, leftleft)) { \ 845 /* || */\ 846 /* pathp(b) */\ 847 /* / \\ */\ 848 /* (b) (b) */\ 849 /* / */\ 850 /* (r) */\ 851 a_type *tnode; \ 852 rbtn_black_set(a_type, a_field, leftleft); \ 853 rbtn_rotate_right(a_type, a_field, pathp->node, \ 854 tnode); \ 855 /* Balance restored, but rotation modified */\ 856 /* subtree root, which may actually be the tree */\ 857 /* root. */\ 858 if (pathp == path) { \ 859 /* Set root. */ \ 860 rbtree->rbt_root = tnode; \ 861 } else { \ 862 if (pathp[-1].cmp < 0) { \ 863 rbtn_left_set(a_type, a_field, \ 864 pathp[-1].node, tnode); \ 865 } else { \ 866 rbtn_right_set(a_type, a_field, \ 867 pathp[-1].node, tnode); \ 868 } \ 869 } \ 870 return; \ 871 } else { \ 872 /* || */\ 873 /* pathp(b) */\ 874 /* / \\ */\ 875 /* (b) (b) */\ 876 /* / */\ 877 /* (b) */\ 878 rbtn_red_set(a_type, a_field, left); \ 879 } \ 880 } \ 881 } \ 882 } \ 883 /* Set root. */ \ 884 rbtree->rbt_root = path->node; \ 885 assert(rbtn_red_get(a_type, a_field, rbtree->rbt_root) == false); \ 886} \ 887a_attr a_type * \ 888a_prefix##iter_recurse(a_rbt_type *rbtree, a_type *node, \ 889 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ 890 if (node == &rbtree->rbt_nil) { \ 891 return (&rbtree->rbt_nil); \ 892 } else { \ 893 a_type *ret; \ 894 if ((ret = a_prefix##iter_recurse(rbtree, rbtn_left_get(a_type, \ 895 a_field, node), cb, arg)) != &rbtree->rbt_nil \ 896 || (ret = cb(rbtree, node, arg)) != NULL) { \ 897 return (ret); \ 898 } \ 899 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \ 900 a_field, node), cb, arg)); \ 901 } \ 902} \ 903a_attr a_type * \ 904a_prefix##iter_start(a_rbt_type *rbtree, a_type *start, a_type *node, \ 905 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ 906 int cmp = a_cmp(start, node); \ 907 if (cmp < 0) { \ 908 a_type *ret; \ 909 if ((ret = a_prefix##iter_start(rbtree, start, \ 910 rbtn_left_get(a_type, a_field, node), cb, arg)) != \ 911 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \ 912 return (ret); \ 913 } \ 914 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \ 915 a_field, node), cb, arg)); \ 916 } else if (cmp > 0) { \ 917 return (a_prefix##iter_start(rbtree, start, \ 918 rbtn_right_get(a_type, a_field, node), cb, arg)); \ 919 } else { \ 920 a_type *ret; \ 921 if ((ret = cb(rbtree, node, arg)) != NULL) { \ 922 return (ret); \ 923 } \ 924 return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \ 925 a_field, node), cb, arg)); \ 926 } \ 927} \ 928a_attr a_type * \ 929a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \ 930 a_rbt_type *, a_type *, void *), void *arg) { \ 931 a_type *ret; \ 932 if (start != NULL) { \ 933 ret = a_prefix##iter_start(rbtree, start, rbtree->rbt_root, \ 934 cb, arg); \ 935 } else { \ 936 ret = a_prefix##iter_recurse(rbtree, rbtree->rbt_root, cb, arg);\ 937 } \ 938 if (ret == &rbtree->rbt_nil) { \ 939 ret = NULL; \ 940 } \ 941 return (ret); \ 942} \ 943a_attr a_type * \ 944a_prefix##reverse_iter_recurse(a_rbt_type *rbtree, a_type *node, \ 945 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ 946 if (node == &rbtree->rbt_nil) { \ 947 return (&rbtree->rbt_nil); \ 948 } else { \ 949 a_type *ret; \ 950 if ((ret = a_prefix##reverse_iter_recurse(rbtree, \ 951 rbtn_right_get(a_type, a_field, node), cb, arg)) != \ 952 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \ 953 return (ret); \ 954 } \ 955 return (a_prefix##reverse_iter_recurse(rbtree, \ 956 rbtn_left_get(a_type, a_field, node), cb, arg)); \ 957 } \ 958} \ 959a_attr a_type * \ 960a_prefix##reverse_iter_start(a_rbt_type *rbtree, a_type *start, \ 961 a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \ 962 void *arg) { \ 963 int cmp = a_cmp(start, node); \ 964 if (cmp > 0) { \ 965 a_type *ret; \ 966 if ((ret = a_prefix##reverse_iter_start(rbtree, start, \ 967 rbtn_right_get(a_type, a_field, node), cb, arg)) != \ 968 &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \ 969 return (ret); \ 970 } \ 971 return (a_prefix##reverse_iter_recurse(rbtree, \ 972 rbtn_left_get(a_type, a_field, node), cb, arg)); \ 973 } else if (cmp < 0) { \ 974 return (a_prefix##reverse_iter_start(rbtree, start, \ 975 rbtn_left_get(a_type, a_field, node), cb, arg)); \ 976 } else { \ 977 a_type *ret; \ 978 if ((ret = cb(rbtree, node, arg)) != NULL) { \ 979 return (ret); \ 980 } \ 981 return (a_prefix##reverse_iter_recurse(rbtree, \ 982 rbtn_left_get(a_type, a_field, node), cb, arg)); \ 983 } \ 984} \ 985a_attr a_type * \ 986a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \ 987 a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ 988 a_type *ret; \ 989 if (start != NULL) { \ 990 ret = a_prefix##reverse_iter_start(rbtree, start, \ 991 rbtree->rbt_root, cb, arg); \ 992 } else { \ 993 ret = a_prefix##reverse_iter_recurse(rbtree, rbtree->rbt_root, \ 994 cb, arg); \ 995 } \ 996 if (ret == &rbtree->rbt_nil) { \ 997 ret = NULL; \ 998 } \ 999 return (ret); \ 1000} 1001 1002#endif /* RB_H_ */ 1003