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