62#define rbtree_node_entry(ptr, type, member) container_of(ptr, type, member)
74#error "Must define NAME."
77#define RBTREE_NAME NAME
88#error "Must define KEY_TYPE."
105#ifndef KEY_IS_STRICTLY_LESS
106#error "Must define KEY_IS_STRICTLY_LESS."
107#define KEY_IS_STRICTLY_LESS(a, b) ((a) < (b))
122#ifdef ALLOW_DUPLICATES
129#ifdef KEY_MEMBER_IS_FIRST
133#define RBTREE_NODE_TYPE struct JOIN(RBTREE_NAME, node)
134#define RBTREE_CONTAINS_KEY JOIN(RBTREE_NAME, contains_key)
135#define RBTREE_NODE_IS_RED JOIN(RBTREE_NAME, node_is_red)
136#define RBTREE_NODE_IS_BLACK JOIN(RBTREE_NAME, node_is_black)
137#define RBTREE_NODE_GET_PARENT_PTR JOIN(RBTREE_NAME, node_get_parent_ptr)
138#define RBTREE_INSERT_FIXUP JOIN(internal, JOIN(RBTREE_NAME, insert_fixup))
139#define RBTREE_DELETE_FIXUP JOIN(internal, JOIN(RBTREE_NAME, delete_fixup))
141#define RBTREE_NODE_TRANSPLANT JOIN(internal, JOIN(RBTREE_NAME, node_transplant))
142#define RBTREE_NODE_SET_COLOR_TO_RED JOIN(internal, JOIN(RBTREE_NAME, node_set_color_to_red))
143#define RBTREE_NODE_SET_COLOR_TO_BLACK JOIN(internal, JOIN(RBTREE_NAME, node_set_color_to_black))
144#define RBTREE_NODE_SET_PARENT_PTR JOIN(internal, JOIN(RBTREE_NAME, node_set_parent_ptr))
145#define RBTREE_NODE_SET_COLOR_TO_COLOR_OF_OTHER JOIN(internal, JOIN(RBTREE_NAME, node_set_color_to_color_of_other))
146#define RBTREE_ROTATE_DIR JOIN(internal, JOIN(RBTREE_NAME, rotate_dir))
148#define RBTREE_CHILD_DIR(node_ptr) ((node_ptr) == RBTREE_NODE_GET_PARENT_PTR(node_ptr)->left_ptr ? 0 : 1)
158struct JOIN(RBTREE_NAME, node) {
159#ifdef KEY_MEMBER_IS_FIRST
169 RBTREE_NODE_TYPE *child_ptrs[2];
171#ifndef KEY_MEMBER_IS_FIRST
182static inline void JOIN(internal,
JOIN(RBTREE_NAME, node_set_color_to_red))(RBTREE_NODE_TYPE *node_ptr)
184 assert(node_ptr != NULL);
186 node_ptr->__parent_ptr_with_color_bit &= ~(uintptr_t)1;
189static inline void JOIN(internal,
JOIN(RBTREE_NAME, node_set_color_to_black))(RBTREE_NODE_TYPE *node_ptr)
191 assert(node_ptr != NULL);
193 node_ptr->__parent_ptr_with_color_bit |= 1;
196static inline void JOIN(internal,
197 JOIN(RBTREE_NAME, node_set_color_to_color_of_other))(RBTREE_NODE_TYPE *node_ptr,
198 const RBTREE_NODE_TYPE *other_ptr)
200 assert(other_ptr != NULL);
201 assert(node_ptr != NULL);
203 const bool is_black = other_ptr->__parent_ptr_with_color_bit & 1;
205 node_ptr->__parent_ptr_with_color_bit &= ~(uintptr_t)1;
206 node_ptr->__parent_ptr_with_color_bit += is_black;
209static inline void JOIN(internal,
JOIN(RBTREE_NAME, node_set_parent_ptr))(RBTREE_NODE_TYPE *node_ptr,
210 RBTREE_NODE_TYPE *parent_ptr)
212 assert(node_ptr != NULL);
214 const bool is_black = node_ptr->__parent_ptr_with_color_bit & 1;
216 node_ptr->__parent_ptr_with_color_bit = (uintptr_t)parent_ptr;
217 node_ptr->__parent_ptr_with_color_bit += is_black;
222static inline RBTREE_NODE_TYPE *
JOIN(internal,
JOIN(RBTREE_NAME, rotate_dir))(RBTREE_NODE_TYPE **rootptr_ptr,
223 RBTREE_NODE_TYPE *P,
const int dir);
226static inline void JOIN(internal,
JOIN(RBTREE_NAME, insert_fixup))(RBTREE_NODE_TYPE **rootptr_ptr, RBTREE_NODE_TYPE *N);
229static inline void JOIN(internal,
JOIN(RBTREE_NAME, node_transplant))(RBTREE_NODE_TYPE **rootptr_ptr,
230 RBTREE_NODE_TYPE *src_node,
231 RBTREE_NODE_TYPE *dest_node);
235static inline void JOIN(internal,
JOIN(RBTREE_NAME, delete_fixup))(RBTREE_NODE_TYPE **rootptr_ptr, RBTREE_NODE_TYPE *P,
247static inline void JOIN(RBTREE_NAME, init)(RBTREE_NODE_TYPE **rootptr_ptr)
249 assert(rootptr_ptr != NULL);
260static inline void JOIN(RBTREE_NAME, node_init)(RBTREE_NODE_TYPE *node_ptr,
KEY_TYPE key)
262 assert(node_ptr != NULL);
265 node_ptr->left_ptr = node_ptr->right_ptr = NULL;
266 RBTREE_NODE_SET_PARENT_PTR(node_ptr, NULL);
274static inline RBTREE_NODE_TYPE *
JOIN(RBTREE_NAME, node_get_parent_ptr)(RBTREE_NODE_TYPE *node_ptr)
276 assert(node_ptr != NULL);
278 return (RBTREE_NODE_TYPE *)(node_ptr->__parent_ptr_with_color_bit & ~(uintptr_t)1);
286static inline bool JOIN(RBTREE_NAME, node_is_black)(
const RBTREE_NODE_TYPE *node_ptr)
288 assert(node_ptr != NULL);
290 return (node_ptr->__parent_ptr_with_color_bit & 1);
298static inline bool JOIN(RBTREE_NAME, node_is_red)(
const RBTREE_NODE_TYPE *node_ptr)
300 assert(node_ptr != NULL);
302 return !RBTREE_NODE_IS_BLACK(node_ptr);
312static inline bool JOIN(RBTREE_NAME, is_empty)(RBTREE_NODE_TYPE **rootptr_ptr)
314 assert(rootptr_ptr != NULL);
316 return *rootptr_ptr == NULL;
327static inline bool JOIN(RBTREE_NAME, contains_key)(RBTREE_NODE_TYPE **rootptr_ptr,
const KEY_TYPE key)
329 assert(rootptr_ptr != NULL);
331 RBTREE_NODE_TYPE *node_ptr = *rootptr_ptr;
333 while (node_ptr != NULL) {
336 const bool is_equal = !is_strictly_less && !is_strictly_greater;
341 else if (is_strictly_less) {
342 node_ptr = node_ptr->left_ptr;
345 node_ptr = node_ptr->right_ptr;
360static inline RBTREE_NODE_TYPE *
JOIN(RBTREE_NAME, search_node)(RBTREE_NODE_TYPE **rootptr_ptr,
const KEY_TYPE key)
362 assert(rootptr_ptr != NULL);
364 RBTREE_NODE_TYPE *node_ptr = *rootptr_ptr;
365 while (node_ptr != NULL) {
368 const bool is_equal = !is_strictly_less && !is_strictly_greater;
373 else if (is_strictly_less) {
374 node_ptr = node_ptr->left_ptr;
377 node_ptr = node_ptr->right_ptr;
389static inline void JOIN(RBTREE_NAME, insert_node)(RBTREE_NODE_TYPE **rootptr_ptr, RBTREE_NODE_TYPE *node_ptr)
391 assert(rootptr_ptr != NULL);
392 assert(node_ptr != NULL);
393#ifndef ALLOW_DUPLICATES
394 assert(RBTREE_CONTAINS_KEY(rootptr_ptr, node_ptr->key) ==
false);
397 RBTREE_NODE_TYPE *parent_ptr = NULL;
398 RBTREE_NODE_TYPE *current_ptr = *rootptr_ptr;
400 while (current_ptr != NULL) {
403 parent_ptr = current_ptr;
405 if (is_strictly_greater) {
406 current_ptr = current_ptr->right_ptr;
409 current_ptr = current_ptr->left_ptr;
413 node_ptr->left_ptr = node_ptr->right_ptr = NULL;
414 RBTREE_NODE_SET_PARENT_PTR(node_ptr, parent_ptr);
415 RBTREE_NODE_SET_COLOR_TO_RED(node_ptr);
417 if (parent_ptr == NULL) {
418 *rootptr_ptr = node_ptr;
423 parent_ptr->child_ptrs[dir] = node_ptr;
425 RBTREE_INSERT_FIXUP(rootptr_ptr, node_ptr);
437static inline RBTREE_NODE_TYPE *
JOIN(RBTREE_NAME, delete_node)(RBTREE_NODE_TYPE **rootptr_ptr,
438 RBTREE_NODE_TYPE *node_ptr)
440 assert(rootptr_ptr != NULL);
441 assert(node_ptr != NULL);
443 if (node_ptr->left_ptr == NULL && node_ptr->right_ptr == NULL) {
444 if (node_ptr == *rootptr_ptr || RBTREE_NODE_IS_RED(node_ptr)) {
445 RBTREE_NODE_TRANSPLANT(rootptr_ptr, node_ptr, NULL);
448 RBTREE_NODE_TYPE *
const parent_ptr = RBTREE_NODE_GET_PARENT_PTR(node_ptr);
450 const int dir = RBTREE_CHILD_DIR(node_ptr) ? 1 : 0;
452 RBTREE_NODE_TRANSPLANT(rootptr_ptr, node_ptr, NULL);
454 RBTREE_DELETE_FIXUP(rootptr_ptr, parent_ptr, dir);
457 else if (node_ptr->left_ptr == NULL || node_ptr->right_ptr == NULL) {
458 const int dir = node_ptr->left_ptr == NULL;
460 assert(RBTREE_NODE_IS_BLACK(node_ptr));
461 assert(RBTREE_NODE_IS_RED(node_ptr->child_ptrs[dir]));
463 RBTREE_NODE_SET_COLOR_TO_BLACK(node_ptr->child_ptrs[dir]);
465 RBTREE_NODE_TRANSPLANT(rootptr_ptr, node_ptr, node_ptr->child_ptrs[dir]);
468 RBTREE_NODE_TYPE *successor_ptr = node_ptr->right_ptr;
470 while (successor_ptr->left_ptr != NULL) {
471 successor_ptr = successor_ptr->left_ptr;
474 const bool prev_successor_black = RBTREE_NODE_IS_BLACK(successor_ptr);
476 const int prev_successor_dir = RBTREE_CHILD_DIR(successor_ptr);
478 RBTREE_NODE_TYPE *
const prev_successor_parent_ptr = RBTREE_NODE_GET_PARENT_PTR(successor_ptr);
480 RBTREE_NODE_TYPE *
const prev_successor_child_ptr = successor_ptr->right_ptr;
483 if (RBTREE_NODE_GET_PARENT_PTR(successor_ptr) != node_ptr) {
484 RBTREE_NODE_TRANSPLANT(rootptr_ptr, successor_ptr, successor_ptr->right_ptr);
486 successor_ptr->right_ptr = node_ptr->right_ptr;
487 RBTREE_NODE_SET_PARENT_PTR(node_ptr->right_ptr, successor_ptr);
489 RBTREE_NODE_TRANSPLANT(rootptr_ptr, node_ptr, successor_ptr);
491 successor_ptr->left_ptr = node_ptr->left_ptr;
492 RBTREE_NODE_SET_PARENT_PTR(node_ptr->left_ptr, successor_ptr);
494 RBTREE_NODE_SET_COLOR_TO_COLOR_OF_OTHER(successor_ptr, node_ptr);
497 if (prev_successor_child_ptr != NULL) {
498 assert(prev_successor_black);
499 assert(RBTREE_NODE_IS_RED(prev_successor_child_ptr));
501 RBTREE_NODE_SET_COLOR_TO_BLACK(prev_successor_child_ptr);
503 else if (prev_successor_child_ptr == NULL && prev_successor_black) {
504 RBTREE_NODE_TYPE *actual_successor_ptr =
505 (prev_successor_parent_ptr == node_ptr) ? successor_ptr : prev_successor_parent_ptr;
507 RBTREE_DELETE_FIXUP(rootptr_ptr, actual_successor_ptr, prev_successor_dir);
511 node_ptr->left_ptr = node_ptr->right_ptr = NULL;
512 RBTREE_NODE_SET_PARENT_PTR(node_ptr, NULL);
519static inline RBTREE_NODE_TYPE *
JOIN(internal,
JOIN(RBTREE_NAME, rotate_dir))(RBTREE_NODE_TYPE **rootptr_ptr,
520 RBTREE_NODE_TYPE *P,
const int dir)
522 assert(rootptr_ptr != NULL);
524 assert(dir == 0 || dir == 1);
545 RBTREE_NODE_TYPE *G = RBTREE_NODE_GET_PARENT_PTR(P);
546 RBTREE_NODE_TYPE *S = P->child_ptrs[1 - dir];
548 RBTREE_NODE_TYPE *C = S->child_ptrs[dir];
550 P->child_ptrs[1 - dir] = C;
552 RBTREE_NODE_SET_PARENT_PTR(C, P);
555 S->child_ptrs[dir] = P;
556 RBTREE_NODE_SET_PARENT_PTR(P, S);
558 RBTREE_NODE_SET_PARENT_PTR(S, G);
560 G->child_ptrs[P == G->left_ptr ? 0 : 1] = S;
568static inline void JOIN(internal,
JOIN(RBTREE_NAME, insert_fixup))(RBTREE_NODE_TYPE **rootptr_ptr, RBTREE_NODE_TYPE *N)
570 assert(rootptr_ptr != NULL);
572 assert(RBTREE_NODE_IS_RED(N));
573 assert(N != *rootptr_ptr);
575 RBTREE_NODE_TYPE *P = RBTREE_NODE_GET_PARENT_PTR(N);
576 RBTREE_NODE_TYPE *G = NULL;
577 RBTREE_NODE_TYPE *U = NULL;
580 if (RBTREE_NODE_IS_BLACK(P)) {
583 if ((G = RBTREE_NODE_GET_PARENT_PTR(P)) == NULL) {
584 RBTREE_NODE_SET_COLOR_TO_BLACK(P);
587 const int dir = RBTREE_CHILD_DIR(P);
588 U = G->child_ptrs[1 - dir];
590 if (U == NULL || RBTREE_NODE_IS_BLACK(U)) {
591 if (N == P->child_ptrs[1 - dir]) {
592 RBTREE_ROTATE_DIR(rootptr_ptr, P, dir);
594 P = G->child_ptrs[dir];
596 RBTREE_NODE_SET_COLOR_TO_BLACK(P);
597 RBTREE_NODE_SET_COLOR_TO_RED(G);
598 RBTREE_ROTATE_DIR(rootptr_ptr, G, 1 - dir);
602 RBTREE_NODE_SET_COLOR_TO_BLACK(P);
603 RBTREE_NODE_SET_COLOR_TO_BLACK(U);
604 RBTREE_NODE_SET_COLOR_TO_RED(G);
607 P = RBTREE_NODE_GET_PARENT_PTR(N);
611static inline void JOIN(internal,
JOIN(RBTREE_NAME, node_transplant))(RBTREE_NODE_TYPE **rootptr_ptr,
612 RBTREE_NODE_TYPE *src_node,
613 RBTREE_NODE_TYPE *dest_node)
615 assert(rootptr_ptr != NULL);
616 assert(src_node != NULL);
618 RBTREE_NODE_TYPE *src_node_parent_ptr = RBTREE_NODE_GET_PARENT_PTR(src_node);
620 if (src_node_parent_ptr == NULL) {
621 *rootptr_ptr = dest_node;
624 src_node_parent_ptr->child_ptrs[RBTREE_CHILD_DIR(src_node)] = dest_node;
627 if (dest_node != NULL) {
628 RBTREE_NODE_SET_PARENT_PTR(dest_node, src_node_parent_ptr);
632static inline void JOIN(internal,
JOIN(RBTREE_NAME, delete_fixup))(RBTREE_NODE_TYPE **rootptr_ptr, RBTREE_NODE_TYPE *P,
635 assert(rootptr_ptr != NULL);
637 assert(dir == 0 || dir == 1);
639 RBTREE_NODE_TYPE *N = NULL;
640 RBTREE_NODE_TYPE *S = NULL;
641 RBTREE_NODE_TYPE *C = NULL;
642 RBTREE_NODE_TYPE *D = NULL;
645 S = P->child_ptrs[1 - dir];
646 D = S->child_ptrs[1 - dir];
647 C = S->child_ptrs[dir];
649 if (RBTREE_NODE_IS_RED(S)) {
652 if (D != NULL && RBTREE_NODE_IS_RED(D)) {
655 if (C != NULL && RBTREE_NODE_IS_RED(C)) {
658 if (RBTREE_NODE_IS_RED(P)) {
661 RBTREE_NODE_SET_COLOR_TO_RED(S);
664 P = RBTREE_NODE_GET_PARENT_PTR(N);
665 }
while (P != NULL && (dir = RBTREE_CHILD_DIR(N),
true));
669 RBTREE_ROTATE_DIR(rootptr_ptr, P, dir);
670 RBTREE_NODE_SET_COLOR_TO_RED(P);
671 RBTREE_NODE_SET_COLOR_TO_BLACK(S);
673 D = S->child_ptrs[1 - dir];
674 if (D != NULL && RBTREE_NODE_IS_RED(D)) {
677 C = S->child_ptrs[dir];
678 if (C != NULL && RBTREE_NODE_IS_RED(C)) {
682 RBTREE_NODE_SET_COLOR_TO_RED(S);
683 RBTREE_NODE_SET_COLOR_TO_BLACK(P);
686 RBTREE_ROTATE_DIR(rootptr_ptr, S, 1 - dir);
687 RBTREE_NODE_SET_COLOR_TO_RED(S);
688 RBTREE_NODE_SET_COLOR_TO_BLACK(C);
692 RBTREE_ROTATE_DIR(rootptr_ptr, P, dir);
693 RBTREE_NODE_SET_COLOR_TO_COLOR_OF_OTHER(S, P);
694 RBTREE_NODE_SET_COLOR_TO_BLACK(P);
695 RBTREE_NODE_SET_COLOR_TO_BLACK(D);
707#undef KEY_IS_STRICTLY_LESS
708#undef ALLOW_DUPLICATES
709#undef KEY_MEMBER_IS_FIRST
713#undef RBTREE_NODE_TYPE
715#undef RBTREE_NODE_IS_RED
716#undef RBTREE_NODE_IS_BLACK
717#undef RBTREE_NODE_GET_PARENT_PTR
718#undef RBTREE_NODE_TRANSPLANT
719#undef RBTREE_NODE_SET_COLOR_TO_COLOR_OF_OTHER
720#undef RBTREE_NODE_SET_COLOR_TO_RED
721#undef RBTREE_NODE_SET_COLOR_TO_BLACK
722#undef RBTREE_NODE_SET_PARENT_PTR
724#undef RBTREE_CONTAINS_KEY
725#undef RBTREE_INSERT_FIXUP
726#undef RBTREE_DELETE_FIXUP
727#undef RBTREE_CHILD_DIR
#define KEY_TYPE
The key type. This must be manually defined before including this header file.
Definition fhashtable.h:132
C preprocessor macros for pasting tokens together.
#define JOIN(a, b)
First expand tokens, then paste them together with a _ in between.
Definition paste.h:35
#define KEY_TYPE
The key type. This must be manually defined before including this header file.
Definition rbtree.h:89
#define KEY_IS_STRICTLY_LESS(a, b)
Used to compare two keys. This must be manually defined before including this header file.
Definition rbtree.h:107
uintptr_t __parent_ptr_with_color_bit
Definition rbtree.h:162
rbtree_node_type * left_ptr
pointer to left node
Definition rbtree.h:166
KEY_TYPE key
node key
Definition rbtree.h:172
rbtree_node_type * right_ptr
pointer to right node
Definition rbtree.h:167