52 #if DOCUMENTATION_ONLY 64 #define RBTREE_LEFT_ROTATE(prefix, Type, left, right, parent) \ 66 void prefix ## _left_rotate(Type **top, Type *x) \ 68 Type *c = right(x), *dad = parent(x); assert(c); \ 70 if ((right(x) = left(c))) \ 71 parent(right(x)) = x; \ 73 if (!(parent(c) = dad)) \ 75 else if (left(dad) == x) \ 78 assert(right(dad) == x), right(dad) = c; \ 83 extern int const prefix##_dummy 92 #define RBTREE_RIGHT_ROTATE(prefix, Type, left, right, parent) \ 94 void prefix ## _right_rotate(Type **top, Type *x) \ 96 Type *c = left(x), *dad = parent(x); assert(c); \ 98 if ((left(x) = right(c))) \ 99 parent(left(x)) = x; \ 101 if (!(parent(c) = dad)) \ 103 else if (right(dad) == x) \ 106 assert(left(dad) == x), left(dad) = c; \ 111 extern int const prefix##_dummy 113 #define RBTREE_BALANCE_INSERT1(prefix, Type, left, right, parent, IS_RED, SET_RED, IS_BLACK, SET_BLACK) \ 115 void prefix ## _balance_insert(Type **top, Type *node) \ 117 Type *dad, *uncle, *granddad; \ 119 extern int const prefix##_dummy 129 #define RBTREE_BALANCE_INSERT(prefix, Type, left, right, parent, IS_RED, SET_RED, IS_BLACK, SET_BLACK) \ 131 void prefix ## _balance_insert(Type **top, Type *node) \ 133 Type *dad, *uncle, *granddad; \ 137 for (dad = parent(node); node != *top && IS_RED(dad); dad = parent(node)) { \ 139 granddad = parent(dad); assert(granddad); \ 140 if (dad == left(granddad)) { \ 141 uncle = right(granddad); \ 142 if (IS_RED(uncle)) { \ 143 SET_BLACK(dad); SET_BLACK(uncle); SET_RED(granddad); \ 146 if (node == right(dad)) { \ 147 prefix##_left_rotate(top, node = dad); \ 148 dad = parent(node); assert(dad); \ 149 granddad = parent(dad); assert(granddad); \ 153 prefix##_right_rotate(top, granddad); \ 155 } else { assert(dad == right(granddad)); \ 156 uncle = left(granddad); \ 157 if (IS_RED(uncle)) { \ 158 SET_BLACK(dad); SET_BLACK(uncle); SET_RED(granddad); \ 161 if (node == left(dad)) { \ 162 prefix##_right_rotate(top, node = dad); \ 163 dad = parent(node); assert(dad); \ 164 granddad = parent(dad); assert(granddad); \ 168 prefix##_left_rotate(top, granddad); \ 177 extern int const prefix##_dummy 179 #define RBTREE_BALANCE_DELETE(prefix, Type, left, right, parent, \ 180 IS_RED, SET_RED, IS_BLACK, SET_BLACK, \ 183 void prefix##_balance_delete(Type **top, Type *node) \ 185 Type *dad, *brother; \ 187 for (dad = parent(node); node != *top && IS_RED(dad); dad = parent(node)) { \ 188 if (node == left(dad)) { \ 189 brother = right(dad); \ 196 assert(IS_BLACK(brother)); \ 198 if (IS_BLACK(left(brother)) && IS_BLACK(right(brother))) { \ 204 if (IS_BLACK(right(brother))) { \ 206 SET_BLACK(left(brother)); \ 207 prefix##_right_rotate(top, brother); \ 208 brother = right(dad); \ 211 COPY_COLOR(brother, dad); \ 213 if (right(brother)) \ 214 SET_BLACK(right(brother)); \ 215 prefix##_left_rotate(top, dad); \ 219 assert(node == right(dad)); \ 221 brother = left(dad); \ 228 assert(IS_BLACK(brother)); \ 230 if (IS_BLACK(left(brother)) && IS_BLACK(right(brother))) { \ 236 if (IS_BLACK(left(brother))) { \ 237 SET_BLACK(right(brother)); \ 239 prefix##_left_rotate(top, brother); \ 240 brother = left(dad); \ 243 COPY_COLOR(brother, parent(node)); \ 244 SET_BLACK(parent(node)); \ 246 SET_BLACK(left(brother)); \ 247 prefix##_right_rotate(top, dad); \ 255 extern int const prefix##_dummy 257 #if DOCUMENTATION_ONLY 273 #define RBTREE_INSERT(SCOPE, prefix, Type, left, right, parent, \ 274 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \ 275 CMP, REMOVE, INSERT) \ 277 int prefix ## _insert(Type **const tree, \ 281 Type *old, *dad, **slot; \ 283 if (tree == NULL || node == NULL) return -1; \ 285 for (slot = tree, old = *slot, dad = NULL; old; old = *slot) { \ 286 int result = CMP(node, old); \ 288 dad = old, slot = &(left(old)); \ 289 else if (result > 0) \ 290 dad = old, slot = &(right(old)); \ 298 if (!return_old) return -1; \ 300 if ((left(node) = left(old))) \ 301 parent(left(node)) = node; \ 302 if ((right(node) = right(old))) \ 303 parent(right(node)) = node; \ 305 if (!(parent(node) = parent(old))) \ 307 else if (left(parent(node)) == old) \ 308 left(parent(node)) = node; \ 309 else assert(right(parent(node)) == old), \ 310 right(parent(node)) = node; \ 312 COPY_COLOR(node, old); \ 318 parent(node) = dad; \ 320 if (tree != slot) { \ 321 prefix##_balance_insert(tree, node); \ 334 extern int const prefix##_dummy 336 #if DOCUMENTATION_ONLY 349 #define RBTREE_APPEND(SCOPE, prefix, Type, left, right, parent, \ 350 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \ 351 CMP, REMOVE, INSERT) \ 353 int prefix ## _append(Type **const tree, \ 356 Type *old, *dad, **slot; \ 358 if (tree == NULL || node == NULL) return -1; \ 360 for (slot = tree, old = *slot, dad = NULL; old; old = *slot) { \ 363 if (CMP(node, old) < 0) \ 364 dad = old, slot = &(left(old)); \ 366 dad = old, slot = &(right(old)); \ 370 parent(node) = dad; \ 372 if (tree != slot) { \ 373 prefix##_balance_insert(tree, node); \ 382 extern int const prefix##_dummy 384 #if DOCUMENTATION_ONLY 393 #define RBTREE_REMOVE(SCOPE, prefix, Type, left, right, parent, \ 394 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \ 397 void prefix##_remove(Type **top, Type *node) \ 400 int need_to_balance; \ 402 if (top == NULL || node == NULL) \ 406 for (dad = node; dad; dad = parent(dad)) \ 413 if (!left(node) || !right(node)) \ 415 else for (dad = right(node); left(dad); dad = left(dad)) \ 418 kid = left(dad) ? left(dad) : right(dad); \ 421 if (!(parent(dad))) \ 423 else if (left(parent(dad)) == dad) \ 424 left(parent(dad)) = kid; \ 425 else assert(right(parent(dad)) == dad), \ 426 right(parent(dad)) = kid; \ 428 parent(kid) = parent(dad); \ 430 need_to_balance = kid && IS_BLACK(dad); \ 434 if (!(parent(dad) = parent(node))) \ 436 else if (left(parent(dad)) == node) \ 437 left(parent(dad)) = dad; \ 438 else assert(right(parent(dad)) == node), \ 439 right(parent(dad)) = dad; \ 441 COPY_COLOR(dad, node); \ 443 if ((left(dad) = left(node))) \ 444 parent(left(dad)) = dad; \ 446 if ((right(dad) = right(node))) \ 447 parent(right(dad)) = dad; \ 453 if (need_to_balance) \ 454 prefix##_balance_delete(top, kid); \ 456 extern int const prefix##_dummy 458 #if DOCUMENTATION_ONLY 469 #define RBTREE_SUCC(SCOPE, prefix, Type, left, right, parent) \ 470 SCOPE Type *prefix##_succ(Type const *node) \ 475 for (node = right(node); left(node); node = left(node)) \ 477 return (Type *)node; \ 480 for (dad = parent(node); dad && node == right(dad); dad = parent(node)) \ 483 return (Type *)dad; \ 485 extern int const prefix##_dummy 487 #if DOCUMENTATION_ONLY 498 #define RBTREE_PREC(SCOPE, prefix, Type, left, right, parent) \ 499 SCOPE Type *prefix##_prec(Type const *node) \ 504 for (node = left(node); right(node); node = right(node)) \ 506 return (Type *)node; \ 509 for (dad = parent(node); dad && node == left(dad); dad = parent(node)) \ 512 return (Type *)dad; \ 514 extern int const prefix##_dummy 516 #if DOCUMENTATION_ONLY 527 #define RBTREE_FIRST(SCOPE, prefix, Type, left, right, parent) \ 528 SCOPE Type *prefix##_first(Type const *node) \ 530 while (node && left(node)) \ 533 return (Type *)node; \ 535 extern int const prefix##_dummy 537 #if DOCUMENTATION_ONLY 548 #define RBTREE_LAST(SCOPE, prefix, Type, left, right, parent) \ 549 SCOPE Type *prefix##_last(Type const *node) \ 551 while (node && right(node)) \ 552 node = right(node); \ 554 return (Type *)node; \ 556 extern int const prefix##_dummy 558 #if DOCUMENTATION_ONLY 569 #define RBTREE_HEIGHT(SCOPE, prefix, Type, getleft, getright, getparent) \ 570 SCOPE int prefix##_height(Type const *node) \ 577 left = getleft(node) ? prefix##_height(getleft(node)) : 0; \ 578 right = getright(node) ? prefix##_height(getright(node)) : 0; \ 585 extern int const prefix##_dummy 598 #define RBTREE_PROTOS(SCOPE, prefix, Type) \ 599 SCOPE int prefix ## _insert(Type **, Type *, Type **return_old); \ 600 SCOPE int prefix ## _append(Type **, Type *); \ 601 SCOPE void prefix ## _remove(Type **, Type *); \ 602 SCOPE Type *prefix ## _succ(Type const *); \ 603 SCOPE Type *prefix ## _prec(Type const *); \ 604 SCOPE Type *prefix ## _first(Type const *); \ 605 SCOPE Type *prefix ## _last(Type const *); \ 606 SCOPE int prefix ## _height(Type const *) 647 #define RBTREE_BODIES(SCOPE, prefix, Type, \ 648 left, right, parent, \ 649 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \ 650 CMP, INSERT, REMOVE) \ 651 RBTREE_LEFT_ROTATE(prefix, Type, left, right, parent); \ 652 RBTREE_RIGHT_ROTATE(prefix, Type, left, right, parent); \ 653 RBTREE_BALANCE_INSERT(prefix, Type, left, right, parent, \ 654 IS_RED, SET_RED, IS_BLACK, SET_BLACK); \ 655 RBTREE_BALANCE_DELETE(prefix, Type, left, right, parent, \ 656 IS_RED, SET_RED, IS_BLACK, SET_BLACK, \ 658 RBTREE_INSERT(SCOPE, prefix, Type, left, right, parent, \ 659 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \ 660 CMP, REMOVE, INSERT); \ 661 RBTREE_APPEND(SCOPE, prefix, Type, left, right, parent, \ 662 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \ 663 CMP, REMOVE, INSERT); \ 664 RBTREE_REMOVE(SCOPE, prefix, Type, left, right, parent, \ 665 IS_RED, SET_RED, IS_BLACK, SET_BLACK, COPY_COLOR, \ 667 RBTREE_SUCC(SCOPE, prefix, Type, left, right, parent); \ 668 RBTREE_PREC(SCOPE, prefix, Type, left, right, parent); \ 669 RBTREE_FIRST(SCOPE, prefix, Type, left, right, parent); \ 670 RBTREE_LAST(SCOPE, prefix, Type, left, right, parent); \ 671 RBTREE_HEIGHT(SCOPE, prefix, Type, left, right, parent) Type * rbtree_first(Type const *node)
Return first node in the tree to which node belongs to.
Type * rbtree_succ(Type const *node)
Return inorder successor of node node.
int rbtree_height(Type const *node)
Return height of the tree below node.
void rbtree_remove(Type **tree, Type *node)
Remove a node from the tree.
int rbtree_append(Type **tree, Type *node)
Append a node into the tree.
Type * rbtree_last(Type const *node)
Return last node in the tree to which node belongs to.
int rbtree_insert(Type **tree, Type *node, Type **return_old)
Insert a node into the tree.
struct node Type
Type used for rbtree nodes.
Definition: rbtree.h:54
Type * rbtree_prec(Type const *node)
Return inorder precedessor of node node.