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