64#define RBTREE_LEFT_ROTATE(prefix, Type, left, right, parent) \
66void 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; \
83extern int const prefix##_dummy
92#define RBTREE_RIGHT_ROTATE(prefix, Type, left, right, parent) \
94void 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; \
111extern int const prefix##_dummy
113#define RBTREE_BALANCE_INSERT1(prefix, Type, left, right, parent, IS_RED, SET_RED, IS_BLACK, SET_BLACK) \
115void prefix ## _balance_insert(Type **top, Type *node) \
117 Type *dad, *uncle, *granddad; \
119extern int const prefix##_dummy
129#define RBTREE_BALANCE_INSERT(prefix, Type, left, right, parent, IS_RED, SET_RED, IS_BLACK, SET_BLACK) \
131void 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); \
177extern int const prefix##_dummy
179#define RBTREE_BALANCE_DELETE(prefix, Type, left, right, parent, \
180 IS_RED, SET_RED, IS_BLACK, SET_BLACK, \
183void 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); \
255extern 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) \
277int 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); \
334extern 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) \
353int 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); \
382extern 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, \
397void 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); \
456extern int const prefix##_dummy
458#if DOCUMENTATION_ONLY
469#define RBTREE_SUCC(SCOPE, prefix, Type, left, right, parent) \
470SCOPE 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; \
485extern 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; \
514extern int const prefix##_dummy
516#if DOCUMENTATION_ONLY
527#define RBTREE_FIRST(SCOPE, prefix, Type, left, right, parent) \
528SCOPE Type *prefix##_first(Type const *node) \
530 while (node && left(node)) \
533 return (Type *)node; \
535extern int const prefix##_dummy
537#if DOCUMENTATION_ONLY
548#define RBTREE_LAST(SCOPE, prefix, Type, left, right, parent) \
549SCOPE Type *prefix##_last(Type const *node) \
551 while (node && right(node)) \
552 node = right(node); \
554 return (Type *)node; \
556extern int const prefix##_dummy
558#if DOCUMENTATION_ONLY
569#define RBTREE_HEIGHT(SCOPE, prefix, Type, getleft, getright, getparent) \
570SCOPE int prefix##_height(Type const *node) \
577 left = getleft(node) ? prefix##_height(getleft(node)) : 0; \
578 right = getright(node) ? prefix##_height(getright(node)) : 0; \
585extern 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)
int rbtree_insert(Type **tree, Type *node, Type **return_old)
Insert a node into the tree.
Type * rbtree_succ(Type const *node)
Return inorder successor of node node.
Type * rbtree_last(Type const *node)
Return last node in the tree to which node belongs to.
Type * rbtree_prec(Type const *node)
Return inorder precedessor of node node.
Type * rbtree_first(Type const *node)
Return first node in the tree to which node belongs to.
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.
struct node Type
Type used for rbtree nodes.
Definition rbtree.h:54