dsa-c
 
Loading...
Searching...
No Matches
rbtree_template.h
Go to the documentation of this file.
1
26
31
32#ifdef __cplusplus
33extern "C" {
34#endif
35
36#include <assert.h>
37#include <stdbool.h>
38#include <stddef.h>
39#include <stdint.h>
40
41// macro definitions: {{{
42
47#ifndef PASTE
48#define PASTE(a, b) a##b
49#endif
50
55#ifndef XPASTE
56#define XPASTE(a, b) PASTE(a, b)
57#endif
58
63#ifndef JOIN
64#define JOIN(a, b) XPASTE(a, XPASTE(_, b))
65#endif
66
74#ifndef NAME
75#error "Must define NAME."
76#else
77#define RBTREE_NAME NAME
78#endif
79
87#ifndef KEY_TYPE
88#define FUNCTION_DEFINITIONS
89#define TYPE_DEFINITIONS
90#define KEY_TYPE int
91#error "Must define KEY_TYPE."
92#endif
93
107#ifndef KEY_IS_STRICTLY_LESS
108#error "Must define KEY_IS_STRICTLY_LESS."
109#define KEY_IS_STRICTLY_LESS(a, b) ((a) < (b))
110#endif
111
124#ifdef ALLOW_DUPLICATES
125#endif
126
131#ifdef KEY_MEMBER_IS_FIRST
132#endif
133
138#ifndef FUNCTION_LINKAGE
139#define FUNCTION_LINKAGE
140#endif
141
143#define RBTREE_NODE_TYPE struct JOIN(RBTREE_NAME, node)
144#define RBTREE_CONTAINS_KEY JOIN(RBTREE_NAME, contains_key)
145#define RBTREE_NODE_IS_RED JOIN(RBTREE_NAME, node_is_red)
146#define RBTREE_NODE_IS_BLACK JOIN(RBTREE_NAME, node_is_black)
147#define RBTREE_NODE_GET_PARENT_PTR JOIN(RBTREE_NAME, node_get_parent_ptr)
148#define RBTREE_INSERT_FIXUP JOIN(internal, JOIN(RBTREE_NAME, insert_fixup))
149#define RBTREE_DELETE_FIXUP JOIN(internal, JOIN(RBTREE_NAME, delete_fixup))
150
151#define RBTREE_NODE_TRANSPLANT JOIN(internal, JOIN(RBTREE_NAME, node_transplant))
152#define RBTREE_NODE_SET_COLOR_TO_RED JOIN(internal, JOIN(RBTREE_NAME, node_set_color_to_red))
153#define RBTREE_NODE_SET_COLOR_TO_BLACK JOIN(internal, JOIN(RBTREE_NAME, node_set_color_to_black))
154#define RBTREE_NODE_SET_PARENT_PTR JOIN(internal, JOIN(RBTREE_NAME, node_set_parent_ptr))
155#define RBTREE_NODE_SET_COLOR_TO_COLOR_OF_OTHER JOIN(internal, JOIN(RBTREE_NAME, node_set_color_to_color_of_other))
156#define RBTREE_ROTATE_DIR JOIN(internal, JOIN(RBTREE_NAME, rotate_dir))
157
158#define RBTREE_CHILD_DIR(node_ptr) ((node_ptr) == RBTREE_NODE_GET_PARENT_PTR(node_ptr)->left_ptr ? 0 : 1)
160
161// }}}
162
163// type definitions: {{{
164
169
170#ifdef TYPE_DEFINITIONS
171
175struct JOIN(RBTREE_NAME, node) {
176#ifdef KEY_MEMBER_IS_FIRST
177 KEY_TYPE key;
178#endif
179 uintptr_t __parent_ptr_with_color_bit;
181 union {
182 struct {
183 RBTREE_NODE_TYPE *left_ptr;
184 RBTREE_NODE_TYPE *right_ptr;
185 };
186 RBTREE_NODE_TYPE *child_ptrs[2];
187 };
188#ifndef KEY_MEMBER_IS_FIRST
189 KEY_TYPE key;
190#endif
191};
192
193#endif
194
195// }}}
196
197// function declarations: {{{
198
206FUNCTION_LINKAGE void JOIN(RBTREE_NAME, init)(RBTREE_NODE_TYPE **rootptr_ptr);
207
214FUNCTION_LINKAGE void JOIN(RBTREE_NAME, node_init)(RBTREE_NODE_TYPE *node_ptr, KEY_TYPE key);
215
221FUNCTION_LINKAGE RBTREE_NODE_TYPE *JOIN(RBTREE_NAME, node_get_parent_ptr)(RBTREE_NODE_TYPE *node_ptr);
222
228FUNCTION_LINKAGE bool JOIN(RBTREE_NAME, node_is_black)(const RBTREE_NODE_TYPE *node_ptr);
229
235FUNCTION_LINKAGE bool JOIN(RBTREE_NAME, node_is_red)(const RBTREE_NODE_TYPE *node_ptr);
236
244FUNCTION_LINKAGE bool JOIN(RBTREE_NAME, is_empty)(RBTREE_NODE_TYPE **rootptr_ptr);
245
254FUNCTION_LINKAGE bool JOIN(RBTREE_NAME, contains_key)(RBTREE_NODE_TYPE **rootptr_ptr, const KEY_TYPE key);
255
265FUNCTION_LINKAGE RBTREE_NODE_TYPE *JOIN(RBTREE_NAME, search_node)(RBTREE_NODE_TYPE **rootptr_ptr, const KEY_TYPE key);
266
273FUNCTION_LINKAGE void JOIN(RBTREE_NAME, insert_node)(RBTREE_NODE_TYPE **rootptr_ptr, RBTREE_NODE_TYPE *node_ptr);
274
283FUNCTION_LINKAGE RBTREE_NODE_TYPE *JOIN(RBTREE_NAME, delete_node)(RBTREE_NODE_TYPE **rootptr_ptr,
284 RBTREE_NODE_TYPE *node_ptr);
285
286// @}}}
287
288// function definitions: {{{
289
294#ifdef FUNCTION_DEFINITIONS
295
297
298static inline void JOIN(internal, JOIN(RBTREE_NAME, node_set_color_to_red))(RBTREE_NODE_TYPE *node_ptr)
299{
300 node_ptr->__parent_ptr_with_color_bit &= ~(uintptr_t)1;
301}
302
303static inline void JOIN(internal, JOIN(RBTREE_NAME, node_set_color_to_black))(RBTREE_NODE_TYPE *node_ptr)
304{
305 node_ptr->__parent_ptr_with_color_bit |= 1;
306}
307
308static inline void JOIN(internal,
309 JOIN(RBTREE_NAME, node_set_color_to_color_of_other))(RBTREE_NODE_TYPE *node_ptr,
310 const RBTREE_NODE_TYPE *other_ptr)
311{
312 const bool is_black = other_ptr->__parent_ptr_with_color_bit & 1;
313
314 node_ptr->__parent_ptr_with_color_bit &= ~(uintptr_t)1;
315 node_ptr->__parent_ptr_with_color_bit += is_black;
316}
317
318static inline void JOIN(internal, JOIN(RBTREE_NAME, node_set_parent_ptr))(RBTREE_NODE_TYPE *node_ptr,
319 RBTREE_NODE_TYPE *parent_ptr)
320{
321 const bool is_black = node_ptr->__parent_ptr_with_color_bit & 1;
322
323 node_ptr->__parent_ptr_with_color_bit = (uintptr_t)parent_ptr;
324 node_ptr->__parent_ptr_with_color_bit += is_black;
325}
326
327// rotate a subtree around a given subtree root node and direction (0: left or
328// 1: right). returns the new subtree root
329static inline RBTREE_NODE_TYPE *JOIN(internal, JOIN(RBTREE_NAME, rotate_dir))(RBTREE_NODE_TYPE **rootptr_ptr,
330 RBTREE_NODE_TYPE *P, const int dir);
331
332// rebalance tree after insert. see explanation in the sources linked above.
333static inline void JOIN(internal, JOIN(RBTREE_NAME, insert_fixup))(RBTREE_NODE_TYPE **rootptr_ptr, RBTREE_NODE_TYPE *N);
334
335// move the parent of a node (src) to another node (dest).
336static inline void JOIN(internal, JOIN(RBTREE_NAME, node_transplant))(RBTREE_NODE_TYPE **rootptr_ptr,
337 RBTREE_NODE_TYPE *src_node,
338 RBTREE_NODE_TYPE *dest_node);
339
340// rebalance tree after delete. see explanation in the sources linked above.
341// for the special case where: (P's child) was not root and was black and had no children.
342static inline void JOIN(internal, JOIN(RBTREE_NAME, delete_fixup))(RBTREE_NODE_TYPE **rootptr_ptr, RBTREE_NODE_TYPE *P,
343 int dir);
344
346
347FUNCTION_LINKAGE void JOIN(RBTREE_NAME, init)(RBTREE_NODE_TYPE **rootptr_ptr)
348{
349 assert(rootptr_ptr != NULL);
350
351 *rootptr_ptr = NULL;
352}
353
354FUNCTION_LINKAGE void JOIN(RBTREE_NAME, node_init)(RBTREE_NODE_TYPE *node_ptr, KEY_TYPE key)
355{
356 assert(node_ptr != NULL);
357
358 node_ptr->key = key;
359 node_ptr->left_ptr = node_ptr->right_ptr = NULL;
360 RBTREE_NODE_SET_PARENT_PTR(node_ptr, NULL);
361}
362
363FUNCTION_LINKAGE RBTREE_NODE_TYPE *JOIN(RBTREE_NAME, node_get_parent_ptr)(RBTREE_NODE_TYPE *node_ptr)
364{
365 assert(node_ptr != NULL);
366
367 return (RBTREE_NODE_TYPE *)(node_ptr->__parent_ptr_with_color_bit & ~(uintptr_t)1);
368}
369
370FUNCTION_LINKAGE bool JOIN(RBTREE_NAME, node_is_black)(const RBTREE_NODE_TYPE *node_ptr)
371{
372 assert(node_ptr != NULL);
373
374 return (node_ptr->__parent_ptr_with_color_bit & 1);
375}
376
377FUNCTION_LINKAGE bool JOIN(RBTREE_NAME, node_is_red)(const RBTREE_NODE_TYPE *node_ptr)
378{
379 assert(node_ptr != NULL);
380
381 return !RBTREE_NODE_IS_BLACK(node_ptr);
382}
383
384FUNCTION_LINKAGE bool JOIN(RBTREE_NAME, is_empty)(RBTREE_NODE_TYPE **rootptr_ptr)
385{
386 assert(rootptr_ptr != NULL);
387
388 return *rootptr_ptr == NULL;
389}
390
391FUNCTION_LINKAGE bool JOIN(RBTREE_NAME, contains_key)(RBTREE_NODE_TYPE **rootptr_ptr, const KEY_TYPE key)
392{
393 assert(rootptr_ptr != NULL);
394
395 RBTREE_NODE_TYPE *node_ptr = *rootptr_ptr;
396
397 while (node_ptr != NULL) {
398 const bool is_strictly_less = KEY_IS_STRICTLY_LESS(key, node_ptr->key);
399 const bool is_strictly_greater = KEY_IS_STRICTLY_LESS(node_ptr->key, key);
400 const bool is_equal = !is_strictly_less && !is_strictly_greater;
401
402 if (is_equal) {
403 return true;
404 }
405 else if (is_strictly_less) {
406 node_ptr = node_ptr->left_ptr;
407 }
408 else {
409 node_ptr = node_ptr->right_ptr;
410 }
411 }
412 return false;
413}
414
415FUNCTION_LINKAGE RBTREE_NODE_TYPE *JOIN(RBTREE_NAME, search_node)(RBTREE_NODE_TYPE **rootptr_ptr, const KEY_TYPE key)
416{
417 assert(rootptr_ptr != NULL);
418
419 RBTREE_NODE_TYPE *node_ptr = *rootptr_ptr;
420 while (node_ptr != NULL) {
421 const bool is_strictly_less = KEY_IS_STRICTLY_LESS(key, node_ptr->key);
422 const bool is_strictly_greater = KEY_IS_STRICTLY_LESS(node_ptr->key, key);
423 const bool is_equal = !is_strictly_less && !is_strictly_greater;
424
425 if (is_equal) {
426 return node_ptr;
427 }
428 else if (is_strictly_less) {
429 node_ptr = node_ptr->left_ptr;
430 }
431 else {
432 node_ptr = node_ptr->right_ptr;
433 }
434 }
435 return NULL;
436}
437
438FUNCTION_LINKAGE void JOIN(RBTREE_NAME, insert_node)(RBTREE_NODE_TYPE **rootptr_ptr, RBTREE_NODE_TYPE *node_ptr)
439{
440 assert(rootptr_ptr != NULL);
441 assert(node_ptr != NULL);
442#ifndef ALLOW_DUPLICATES
443 assert(RBTREE_CONTAINS_KEY(rootptr_ptr, node_ptr->key) == false);
444#endif
445
446 RBTREE_NODE_TYPE *parent_ptr = NULL;
447 RBTREE_NODE_TYPE *current_ptr = *rootptr_ptr;
448
449 while (current_ptr != NULL) {
450 const bool is_strictly_greater = KEY_IS_STRICTLY_LESS(current_ptr->key, node_ptr->key);
451
452 parent_ptr = current_ptr;
453
454 if (is_strictly_greater) {
455 current_ptr = current_ptr->right_ptr;
456 }
457 else {
458 current_ptr = current_ptr->left_ptr;
459 }
460 }
461
462 node_ptr->left_ptr = node_ptr->right_ptr = NULL;
463 RBTREE_NODE_SET_PARENT_PTR(node_ptr, parent_ptr);
464 RBTREE_NODE_SET_COLOR_TO_RED(node_ptr);
465
466 if (parent_ptr == NULL) {
467 *rootptr_ptr = node_ptr;
468 }
469 else {
470 const int dir = KEY_IS_STRICTLY_LESS(parent_ptr->key, node_ptr->key) ? 1 : 0;
471
472 parent_ptr->child_ptrs[dir] = node_ptr;
473
474 RBTREE_INSERT_FIXUP(rootptr_ptr, node_ptr);
475 }
476}
477
478FUNCTION_LINKAGE RBTREE_NODE_TYPE *JOIN(RBTREE_NAME, delete_node)(RBTREE_NODE_TYPE **rootptr_ptr,
479 RBTREE_NODE_TYPE *node_ptr)
480{
481 assert(rootptr_ptr != NULL);
482 assert(node_ptr != NULL);
483
484 if (node_ptr->left_ptr == NULL && node_ptr->right_ptr == NULL) {
485 if (node_ptr == *rootptr_ptr || RBTREE_NODE_IS_RED(node_ptr)) {
486 RBTREE_NODE_TRANSPLANT(rootptr_ptr, node_ptr, NULL);
487 }
488 else {
489 RBTREE_NODE_TYPE *const parent_ptr = RBTREE_NODE_GET_PARENT_PTR(node_ptr);
490
491 const int dir = RBTREE_CHILD_DIR(node_ptr) ? 1 : 0;
492
493 RBTREE_NODE_TRANSPLANT(rootptr_ptr, node_ptr, NULL);
494
495 RBTREE_DELETE_FIXUP(rootptr_ptr, parent_ptr, dir);
496 }
497 }
498 else if (node_ptr->left_ptr == NULL || node_ptr->right_ptr == NULL) {
499 const int dir = node_ptr->left_ptr == NULL;
500
501 assert(RBTREE_NODE_IS_BLACK(node_ptr));
502 assert(RBTREE_NODE_IS_RED(node_ptr->child_ptrs[dir]));
503
504 RBTREE_NODE_SET_COLOR_TO_BLACK(node_ptr->child_ptrs[dir]);
505
506 RBTREE_NODE_TRANSPLANT(rootptr_ptr, node_ptr, node_ptr->child_ptrs[dir]);
507 }
508 else {
509 RBTREE_NODE_TYPE *successor_ptr = node_ptr->right_ptr;
510
511 while (successor_ptr->left_ptr != NULL) {
512 successor_ptr = successor_ptr->left_ptr;
513 }
514
515 const bool prev_successor_black = RBTREE_NODE_IS_BLACK(successor_ptr);
516
517 const int prev_successor_dir = RBTREE_CHILD_DIR(successor_ptr);
518
519 RBTREE_NODE_TYPE *const prev_successor_parent_ptr = RBTREE_NODE_GET_PARENT_PTR(successor_ptr);
520
521 RBTREE_NODE_TYPE *const prev_successor_child_ptr = successor_ptr->right_ptr;
522
523 {
524 if (RBTREE_NODE_GET_PARENT_PTR(successor_ptr) != node_ptr) {
525 RBTREE_NODE_TRANSPLANT(rootptr_ptr, successor_ptr, successor_ptr->right_ptr);
526
527 successor_ptr->right_ptr = node_ptr->right_ptr;
528 RBTREE_NODE_SET_PARENT_PTR(node_ptr->right_ptr, successor_ptr);
529 }
530 RBTREE_NODE_TRANSPLANT(rootptr_ptr, node_ptr, successor_ptr);
531
532 successor_ptr->left_ptr = node_ptr->left_ptr;
533 RBTREE_NODE_SET_PARENT_PTR(node_ptr->left_ptr, successor_ptr);
534
535 RBTREE_NODE_SET_COLOR_TO_COLOR_OF_OTHER(successor_ptr, node_ptr);
536 }
537
538 if (prev_successor_child_ptr != NULL) {
539 assert(prev_successor_black);
540 assert(RBTREE_NODE_IS_RED(prev_successor_child_ptr));
541
542 RBTREE_NODE_SET_COLOR_TO_BLACK(prev_successor_child_ptr);
543 }
544 else if (prev_successor_child_ptr == NULL && prev_successor_black) {
545 RBTREE_NODE_TYPE *actual_successor_ptr =
546 (prev_successor_parent_ptr == node_ptr) ? successor_ptr : prev_successor_parent_ptr;
547
548 RBTREE_DELETE_FIXUP(rootptr_ptr, actual_successor_ptr, prev_successor_dir);
549 }
550 }
551
552 node_ptr->left_ptr = node_ptr->right_ptr = NULL;
553 RBTREE_NODE_SET_PARENT_PTR(node_ptr, NULL);
554
555 return node_ptr;
556}
557
559
560static inline RBTREE_NODE_TYPE *JOIN(internal, JOIN(RBTREE_NAME, rotate_dir))(RBTREE_NODE_TYPE **rootptr_ptr,
561 RBTREE_NODE_TYPE *P, const int dir)
562{
563 /* Right rotate around P:
564 P S
565 / \ / \
566 S T --> .. P
567 / \ / \ ⟳ / \
568 .. C .. .. C T
569 / \ / \ / \
570 .. .. .. .. .. ..
571
572 Left rotate around P:
573 P S
574 / \ / \
575 T S P ..
576 / \ / \ --> / \
577 .. .. C .. ↺ T C
578 / \ / \ / \
579 .. .. .. .. .. ..
580 */
581
582 RBTREE_NODE_TYPE *G = RBTREE_NODE_GET_PARENT_PTR(P);
583 RBTREE_NODE_TYPE *S = P->child_ptrs[1 - dir];
584 assert(S != NULL);
585 RBTREE_NODE_TYPE *C = S->child_ptrs[dir];
586
587 P->child_ptrs[1 - dir] = C;
588 if (C != NULL) {
589 RBTREE_NODE_SET_PARENT_PTR(C, P);
590 }
591
592 S->child_ptrs[dir] = P;
593 RBTREE_NODE_SET_PARENT_PTR(P, S);
594
595 RBTREE_NODE_SET_PARENT_PTR(S, G);
596 if (G != NULL) {
597 G->child_ptrs[P == G->left_ptr ? 0 : 1] = S;
598 }
599 else {
600 *rootptr_ptr = S;
601 }
602 return S;
603}
604
605static inline void JOIN(internal, JOIN(RBTREE_NAME, insert_fixup))(RBTREE_NODE_TYPE **rootptr_ptr, RBTREE_NODE_TYPE *N)
606{
607 assert(RBTREE_NODE_IS_RED(N));
608 assert(N != *rootptr_ptr);
609
610 RBTREE_NODE_TYPE *P = RBTREE_NODE_GET_PARENT_PTR(N); // parent
611 RBTREE_NODE_TYPE *G = NULL; // grandparent
612 RBTREE_NODE_TYPE *U = NULL; // uncle
613
614 do {
615 if (RBTREE_NODE_IS_BLACK(P)) {
616 return;
617 }
618 if ((G = RBTREE_NODE_GET_PARENT_PTR(P)) == NULL) {
619 RBTREE_NODE_SET_COLOR_TO_BLACK(P);
620 return;
621 }
622 const int dir = RBTREE_CHILD_DIR(P);
623 U = G->child_ptrs[1 - dir];
624
625 if (U == NULL || RBTREE_NODE_IS_BLACK(U)) {
626 if (N == P->child_ptrs[1 - dir]) {
627 RBTREE_ROTATE_DIR(rootptr_ptr, P, dir);
628 N = P;
629 P = G->child_ptrs[dir];
630 }
631 RBTREE_NODE_SET_COLOR_TO_BLACK(P);
632 RBTREE_NODE_SET_COLOR_TO_RED(G);
633 RBTREE_ROTATE_DIR(rootptr_ptr, G, 1 - dir);
634 return;
635 }
636
637 RBTREE_NODE_SET_COLOR_TO_BLACK(P);
638 RBTREE_NODE_SET_COLOR_TO_BLACK(U);
639 RBTREE_NODE_SET_COLOR_TO_RED(G);
640
641 N = G;
642 P = RBTREE_NODE_GET_PARENT_PTR(N);
643 } while (P != NULL);
644}
645
646static inline void JOIN(internal, JOIN(RBTREE_NAME, node_transplant))(RBTREE_NODE_TYPE **rootptr_ptr,
647 RBTREE_NODE_TYPE *src_node,
648 RBTREE_NODE_TYPE *dest_node)
649{
650 RBTREE_NODE_TYPE *src_node_parent_ptr = RBTREE_NODE_GET_PARENT_PTR(src_node);
651
652 if (src_node_parent_ptr == NULL) {
653 *rootptr_ptr = dest_node;
654 }
655 else {
656 src_node_parent_ptr->child_ptrs[RBTREE_CHILD_DIR(src_node)] = dest_node;
657 }
658
659 if (dest_node != NULL) {
660 RBTREE_NODE_SET_PARENT_PTR(dest_node, src_node_parent_ptr);
661 }
662}
663
664static inline void JOIN(internal, JOIN(RBTREE_NAME, delete_fixup))(RBTREE_NODE_TYPE **rootptr_ptr, RBTREE_NODE_TYPE *P,
665 int dir)
666{
667 RBTREE_NODE_TYPE *N = NULL; // node (temp)
668 RBTREE_NODE_TYPE *S = NULL; // sibling
669 RBTREE_NODE_TYPE *C = NULL; // close nephew
670 RBTREE_NODE_TYPE *D = NULL; // distant nephew
671
672 do {
673 S = P->child_ptrs[1 - dir];
674 D = S->child_ptrs[1 - dir];
675 C = S->child_ptrs[dir];
676
677 if (RBTREE_NODE_IS_RED(S)) {
678 goto Case_3;
679 }
680 if (D != NULL && RBTREE_NODE_IS_RED(D)) {
681 goto Case_6;
682 }
683 if (C != NULL && RBTREE_NODE_IS_RED(C)) {
684 goto Case_5;
685 }
686 if (RBTREE_NODE_IS_RED(P)) {
687 goto Case_4;
688 }
689 RBTREE_NODE_SET_COLOR_TO_RED(S);
690
691 N = P;
692 P = RBTREE_NODE_GET_PARENT_PTR(N);
693 } while (P != NULL && (dir = RBTREE_CHILD_DIR(N), true));
694
695 return;
696Case_3:
697 RBTREE_ROTATE_DIR(rootptr_ptr, P, dir);
698 RBTREE_NODE_SET_COLOR_TO_RED(P);
699 RBTREE_NODE_SET_COLOR_TO_BLACK(S);
700 S = C;
701 D = S->child_ptrs[1 - dir];
702 if (D != NULL && RBTREE_NODE_IS_RED(D)) {
703 goto Case_6;
704 }
705 C = S->child_ptrs[dir];
706 if (C != NULL && RBTREE_NODE_IS_RED(C)) {
707 goto Case_5;
708 }
709Case_4:
710 RBTREE_NODE_SET_COLOR_TO_RED(S);
711 RBTREE_NODE_SET_COLOR_TO_BLACK(P);
712 return;
713Case_5:
714 RBTREE_ROTATE_DIR(rootptr_ptr, S, 1 - dir);
715 RBTREE_NODE_SET_COLOR_TO_RED(S);
716 RBTREE_NODE_SET_COLOR_TO_BLACK(C);
717 D = S;
718 S = C;
719Case_6:
720 RBTREE_ROTATE_DIR(rootptr_ptr, P, dir);
721 RBTREE_NODE_SET_COLOR_TO_COLOR_OF_OTHER(S, P);
722 RBTREE_NODE_SET_COLOR_TO_BLACK(P);
723 RBTREE_NODE_SET_COLOR_TO_BLACK(D);
724 return;
725}
727
728#endif
729
730// }}}
731
732// macro undefs: {{{
733
734#undef NAME
735#undef KEY_TYPE
736#undef VALUE_TYPE
737#undef KEY_IS_STRICTLY_LESS
738#undef ALLOW_DUPLICATES
739#undef KEY_MEMBER_IS_FIRST
740#undef FUNCTION_DEFINITIONS
741#undef TYPE_DEFINITIONS
742
743#undef RBTREE_NAME
744#undef RBTREE_TYPE
745#undef RBTREE_NODE_TYPE
746
747#undef RBTREE_NODE_IS_RED
748#undef RBTREE_NODE_IS_BLACK
749#undef RBTREE_NODE_GET_PARENT_PTR
750#undef RBTREE_NODE_TRANSPLANT
751#undef RBTREE_NODE_SET_COLOR_TO_COLOR_OF_OTHER
752#undef RBTREE_NODE_SET_COLOR_TO_RED
753#undef RBTREE_NODE_SET_COLOR_TO_BLACK
754#undef RBTREE_NODE_SET_PARENT_PTR
755
756#undef RBTREE_CONTAINS_KEY
757#undef RBTREE_INSERT_FIXUP
758#undef RBTREE_DELETE_FIXUP
759#undef RBTREE_CHILD_DIR
760
761// }}}
762
763#ifdef __cplusplus
764}
765#endif
766
767// vim: ft=c fdm=marker
KEY_TYPE
#define KEY_TYPE
The key type. This must be manually defined before including this header file.
Definition fhashtable_template.h:166
FUNCTION_LINKAGE
#define FUNCTION_LINKAGE
Specify function linkage e.g. static inline.
Definition fstack_template.h:146
JOIN
#define JOIN(a, b)
First expand tokens, then paste them together with a _ in between.
Definition rbtree_template.h:64
KEY_TYPE
#define KEY_TYPE
The key type. This must be manually defined before including this header file.
Definition rbtree_template.h:90
KEY_IS_STRICTLY_LESS
#define KEY_IS_STRICTLY_LESS(a, b)
Used to compare two keys. This must be manually defined before including this header file.
Definition rbtree_template.h:109
rbtree_node::child_ptrs
rbtree_node_type * child_ptrs[2]
array of child pointers
Definition rbtree_template.h:186
rbtree_node::__parent_ptr_with_color_bit
uintptr_t __parent_ptr_with_color_bit
Definition rbtree_template.h:179
rbtree_node::left_ptr
rbtree_node_type * left_ptr
pointer to left node
Definition rbtree_template.h:183
rbtree_node::key
KEY_TYPE key
node key
Definition rbtree_template.h:189
rbtree_node::right_ptr
rbtree_node_type * right_ptr
pointer to right node
Definition rbtree_template.h:184