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