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