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