PostgreSQL Source Code git master
Data Structures | Macros | Functions | Variables
rbtree.c File Reference
#include "postgres.h"
#include "lib/rbtree.h"
Include dependency graph for rbtree.c:

Go to the source code of this file.

Data Structures

struct   RBTree
 

Macros

#define  RBTBLACK   (0)
 
#define  RBTRED   (1)
 
#define  RBTNIL   (&sentinel)
 

Functions

RBTree *  rbt_create (Size node_size, rbt_comparator comparator, rbt_combiner combiner, rbt_allocfunc allocfunc, rbt_freefunc freefunc, void *arg)
 
static void  rbt_copy_data (RBTree *rbt, RBTNode *dest, const RBTNode *src)
 
RBTNode *  rbt_find (RBTree *rbt, const RBTNode *data)
 
RBTNode *  rbt_find_great (RBTree *rbt, const RBTNode *data, bool equal_match)
 
RBTNode *  rbt_find_less (RBTree *rbt, const RBTNode *data, bool equal_match)
 
RBTNode *  rbt_leftmost (RBTree *rbt)
 
static void  rbt_rotate_left (RBTree *rbt, RBTNode *x)
 
static void  rbt_rotate_right (RBTree *rbt, RBTNode *x)
 
static void  rbt_insert_fixup (RBTree *rbt, RBTNode *x)
 
RBTNode *  rbt_insert (RBTree *rbt, const RBTNode *data, bool *isNew)
 
static void  rbt_delete_fixup (RBTree *rbt, RBTNode *x)
 
static void  rbt_delete_node (RBTree *rbt, RBTNode *z)
 
void  rbt_delete (RBTree *rbt, RBTNode *node)
 
static RBTNode *  rbt_left_right_iterator (RBTreeIterator *iter)
 
static RBTNode *  rbt_right_left_iterator (RBTreeIterator *iter)
 
void  rbt_begin_iterate (RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
 
RBTNode *  rbt_iterate (RBTreeIterator *iter)
 

Variables

static RBTNode  sentinel
 

Macro Definition Documentation

◆ RBTBLACK

#define RBTBLACK   (0)

Definition at line 35 of file rbtree.c.

◆ RBTNIL

#define RBTNIL   (&sentinel)

Definition at line 61 of file rbtree.c.

◆ RBTRED

#define RBTRED   (1)

Definition at line 36 of file rbtree.c.

Function Documentation

◆ rbt_begin_iterate()

void rbt_begin_iterate ( RBTree *  rbt,
RBTOrderControl  ctrl,
RBTreeIterator *  iter 
)

Definition at line 802 of file rbtree.c.

803{
804 /* Common initialization for all traversal orders */
805 iter->rbt = rbt;
806 iter->last_visited = NULL;
807 iter->is_over = (rbt->root == RBTNIL);
808
809 switch (ctrl)
810 {
811 case LeftRightWalk: /* visit left, then self, then right */
813 break;
814 case RightLeftWalk: /* visit right, then self, then left */
816 break;
817 default:
818 elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
819 }
820}
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:226
static RBTNode * rbt_right_left_iterator(RBTreeIterator *iter)
Definition: rbtree.c:747
static RBTNode * rbt_left_right_iterator(RBTreeIterator *iter)
Definition: rbtree.c:705
#define RBTNIL
Definition: rbtree.c:61
@ RightLeftWalk
Definition: rbtree.h:38
@ LeftRightWalk
Definition: rbtree.h:37
RBTNode *(* iterate)(RBTreeIterator *iter)
Definition: rbtree.h:51
bool is_over
Definition: rbtree.h:53
RBTree * rbt
Definition: rbtree.h:50
RBTNode * last_visited
Definition: rbtree.h:52
RBTNode * root
Definition: rbtree.c:43

References elog, ERROR, RBTreeIterator::is_over, RBTreeIterator::iterate, RBTreeIterator::last_visited, LeftRightWalk, RBTreeIterator::rbt, rbt_left_right_iterator(), rbt_right_left_iterator(), RBTNIL, RightLeftWalk, and RBTree::root.

Referenced by ginBeginBAScan(), testleftright(), and testrightleft().

◆ rbt_copy_data()

static void rbt_copy_data ( RBTree *  rbt,
RBTNode *  dest,
const RBTNode *  src 
)
inlinestatic

Definition at line 127 of file rbtree.c.

128{
129 memcpy(dest + 1, src + 1, rbt->node_size - sizeof(RBTNode));
130}
dest
Definition: rbtree.h:24
Size node_size
Definition: rbtree.c:47

References generate_unaccent_rules::dest, and RBTree::node_size.

Referenced by rbt_delete_node(), and rbt_insert().

◆ rbt_create()

RBTree * rbt_create ( Size  node_size,
rbt_comparator  comparator,
rbt_combiner  combiner,
rbt_allocfunc  allocfunc,
rbt_freefunc  freefunc,
void *  arg 
)

Definition at line 102 of file rbtree.c.

108{
109 RBTree *tree = (RBTree *) palloc(sizeof(RBTree));
110
111 Assert(node_size > sizeof(RBTNode));
112
113 tree->root = RBTNIL;
114 tree->node_size = node_size;
115 tree->comparator = comparator;
116 tree->combiner = combiner;
117 tree->allocfunc = allocfunc;
118 tree->freefunc = freefunc;
119
120 tree->arg = arg;
121
122 return tree;
123}
Assert(PointerIsAligned(start, uint64))
void * palloc(Size size)
Definition: mcxt.c:1365
void * arg
tree
Definition: radixtree.h:1828
Definition: rbtree.c:42

References arg, Assert(), palloc(), RBTNIL, and tree.

Referenced by create_int_rbtree(), and ginInitBA().

◆ rbt_delete()

void rbt_delete ( RBTree *  rbt,
RBTNode *  node 
)

Definition at line 695 of file rbtree.c.

696{
697 rbt_delete_node(rbt, node);
698}
static void rbt_delete_node(RBTree *rbt, RBTNode *z)
Definition: rbtree.c:619

References rbt_delete_node().

Referenced by testdelete(), and testfindltgt().

◆ rbt_delete_fixup()

static void rbt_delete_fixup ( RBTree *  rbt,
RBTNode *  x 
)
static

Definition at line 521 of file rbtree.c.

522{
523 /*
524 * x is always a black node. Initially, it is the former child of the
525 * deleted node. Each iteration of this loop moves it higher up in the
526 * tree.
527 */
528 while (x != rbt->root && x->color == RBTBLACK)
529 {
530 /*
531 * Left and right cases are symmetric. Any nodes that are children of
532 * x have a black-height one less than the remainder of the nodes in
533 * the tree. We rotate and recolor nodes to move the problem up the
534 * tree: at some stage we'll either fix the problem, or reach the root
535 * (where the black-height is allowed to decrease).
536 */
537 if (x == x->parent->left)
538 {
539 RBTNode *w = x->parent->right;
540
541 if (w->color == RBTRED)
542 {
543 w->color = RBTBLACK;
544 x->parent->color = RBTRED;
545
546 rbt_rotate_left(rbt, x->parent);
547 w = x->parent->right;
548 }
549
550 if (w->left->color == RBTBLACK && w->right->color == RBTBLACK)
551 {
552 w->color = RBTRED;
553
554 x = x->parent;
555 }
556 else
557 {
558 if (w->right->color == RBTBLACK)
559 {
560 w->left->color = RBTBLACK;
561 w->color = RBTRED;
562
563 rbt_rotate_right(rbt, w);
564 w = x->parent->right;
565 }
566 w->color = x->parent->color;
567 x->parent->color = RBTBLACK;
568 w->right->color = RBTBLACK;
569
570 rbt_rotate_left(rbt, x->parent);
571 x = rbt->root; /* Arrange for loop to terminate. */
572 }
573 }
574 else
575 {
576 RBTNode *w = x->parent->left;
577
578 if (w->color == RBTRED)
579 {
580 w->color = RBTBLACK;
581 x->parent->color = RBTRED;
582
583 rbt_rotate_right(rbt, x->parent);
584 w = x->parent->left;
585 }
586
587 if (w->right->color == RBTBLACK && w->left->color == RBTBLACK)
588 {
589 w->color = RBTRED;
590
591 x = x->parent;
592 }
593 else
594 {
595 if (w->left->color == RBTBLACK)
596 {
597 w->right->color = RBTBLACK;
598 w->color = RBTRED;
599
600 rbt_rotate_left(rbt, w);
601 w = x->parent->left;
602 }
603 w->color = x->parent->color;
604 x->parent->color = RBTBLACK;
605 w->left->color = RBTBLACK;
606
607 rbt_rotate_right(rbt, x->parent);
608 x = rbt->root; /* Arrange for loop to terminate. */
609 }
610 }
611 }
612 x->color = RBTBLACK;
613}
x
int x
Definition: isn.c:75
static void rbt_rotate_right(RBTree *rbt, RBTNode *x)
Definition: rbtree.c:300
#define RBTBLACK
Definition: rbtree.c:35
static void rbt_rotate_left(RBTree *rbt, RBTNode *x)
Definition: rbtree.c:263
#define RBTRED
Definition: rbtree.c:36
char color
Definition: rbtree.h:25
struct RBTNode * left
Definition: rbtree.h:26
struct RBTNode * right
Definition: rbtree.h:27

References RBTNode::color, RBTNode::left, rbt_rotate_left(), rbt_rotate_right(), RBTBLACK, RBTRED, RBTNode::right, RBTree::root, and x.

Referenced by rbt_delete_node().

◆ rbt_delete_node()

static void rbt_delete_node ( RBTree *  rbt,
RBTNode *  z 
)
static

Definition at line 619 of file rbtree.c.

620{
621 RBTNode *x,
622 *y;
623
624 /* This is just paranoia: we should only get called on a valid node */
625 if (!z || z == RBTNIL)
626 return;
627
628 /*
629 * y is the node that will actually be removed from the tree. This will
630 * be z if z has fewer than two children, or the tree successor of z
631 * otherwise.
632 */
633 if (z->left == RBTNIL || z->right == RBTNIL)
634 {
635 /* y has a RBTNIL node as a child */
636 y = z;
637 }
638 else
639 {
640 /* find tree successor */
641 y = z->right;
642 while (y->left != RBTNIL)
643 y = y->left;
644 }
645
646 /* x is y's only child */
647 if (y->left != RBTNIL)
648 x = y->left;
649 else
650 x = y->right;
651
652 /* Remove y from the tree. */
653 x->parent = y->parent;
654 if (y->parent)
655 {
656 if (y == y->parent->left)
657 y->parent->left = x;
658 else
659 y->parent->right = x;
660 }
661 else
662 {
663 rbt->root = x;
664 }
665
666 /*
667 * If we removed the tree successor of z rather than z itself, then move
668 * the data for the removed node to the one we were supposed to remove.
669 */
670 if (y != z)
671 rbt_copy_data(rbt, z, y);
672
673 /*
674 * Removing a black node might make some paths from root to leaf contain
675 * fewer black nodes than others, or it might make two red nodes adjacent.
676 */
677 if (y->color == RBTBLACK)
678 rbt_delete_fixup(rbt, x);
679
680 /* Now we can recycle the y node */
681 if (rbt->freefunc)
682 rbt->freefunc(y, rbt->arg);
683}
y
int y
Definition: isn.c:76
static void rbt_delete_fixup(RBTree *rbt, RBTNode *x)
Definition: rbtree.c:521
static void rbt_copy_data(RBTree *rbt, RBTNode *dest, const RBTNode *src)
Definition: rbtree.c:127
void * arg
Definition: rbtree.c:54
rbt_freefunc freefunc
Definition: rbtree.c:52

References RBTree::arg, RBTree::freefunc, RBTNode::left, rbt_copy_data(), rbt_delete_fixup(), RBTBLACK, RBTNIL, RBTNode::right, RBTree::root, x, and y.

Referenced by rbt_delete().

◆ rbt_find()

RBTNode * rbt_find ( RBTree *  rbt,
const RBTNode *  data 
)

Definition at line 145 of file rbtree.c.

146{
147 RBTNode *node = rbt->root;
148
149 while (node != RBTNIL)
150 {
151 int cmp = rbt->comparator(data, node, rbt->arg);
152
153 if (cmp == 0)
154 return node;
155 else if (cmp < 0)
156 node = node->left;
157 else
158 node = node->right;
159 }
160
161 return NULL;
162}
const void * data
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:743
rbt_comparator comparator
Definition: rbtree.c:49

References RBTree::arg, cmp(), RBTree::comparator, data, RBTNode::left, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by testdelete(), and testfind().

◆ rbt_find_great()

RBTNode * rbt_find_great ( RBTree *  rbt,
const RBTNode *  data,
bool  equal_match 
)

Definition at line 172 of file rbtree.c.

173{
174 RBTNode *node = rbt->root;
175 RBTNode *greater = NULL;
176
177 while (node != RBTNIL)
178 {
179 int cmp = rbt->comparator(data, node, rbt->arg);
180
181 if (equal_match && cmp == 0)
182 return node;
183 else if (cmp < 0)
184 {
185 greater = node;
186 node = node->left;
187 }
188 else
189 node = node->right;
190 }
191
192 return greater;
193}

References RBTree::arg, cmp(), RBTree::comparator, data, RBTNode::left, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by testfindltgt().

◆ rbt_find_less()

RBTNode * rbt_find_less ( RBTree *  rbt,
const RBTNode *  data,
bool  equal_match 
)

Definition at line 203 of file rbtree.c.

204{
205 RBTNode *node = rbt->root;
206 RBTNode *lesser = NULL;
207
208 while (node != RBTNIL)
209 {
210 int cmp = rbt->comparator(data, node, rbt->arg);
211
212 if (equal_match && cmp == 0)
213 return node;
214 else if (cmp > 0)
215 {
216 lesser = node;
217 node = node->right;
218 }
219 else
220 node = node->left;
221 }
222
223 return lesser;
224}

References RBTree::arg, cmp(), RBTree::comparator, data, RBTNode::left, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by testfindltgt().

◆ rbt_insert()

RBTNode * rbt_insert ( RBTree *  rbt,
const RBTNode *  data,
bool *  isNew 
)

Definition at line 453 of file rbtree.c.

454{
455 RBTNode *current,
456 *parent,
457 *x;
458 int cmp;
459
460 /* find where node belongs */
461 current = rbt->root;
462 parent = NULL;
463 cmp = 0; /* just to prevent compiler warning */
464
465 while (current != RBTNIL)
466 {
467 cmp = rbt->comparator(data, current, rbt->arg);
468 if (cmp == 0)
469 {
470 /*
471 * Found node with given key. Apply combiner.
472 */
473 rbt->combiner(current, data, rbt->arg);
474 *isNew = false;
475 return current;
476 }
477 parent = current;
478 current = (cmp < 0) ? current->left : current->right;
479 }
480
481 /*
482 * Value is not present, so create a new node containing data.
483 */
484 *isNew = true;
485
486 x = rbt->allocfunc(rbt->arg);
487
488 x->color = RBTRED;
489
490 x->left = RBTNIL;
491 x->right = RBTNIL;
492 x->parent = parent;
493 rbt_copy_data(rbt, x, data);
494
495 /* insert node in tree */
496 if (parent)
497 {
498 if (cmp < 0)
499 parent->left = x;
500 else
501 parent->right = x;
502 }
503 else
504 {
505 rbt->root = x;
506 }
507
508 rbt_insert_fixup(rbt, x);
509
510 return x;
511}
static void rbt_insert_fixup(RBTree *rbt, RBTNode *x)
Definition: rbtree.c:344
rbt_allocfunc allocfunc
Definition: rbtree.c:51
rbt_combiner combiner
Definition: rbtree.c:50

References RBTree::allocfunc, RBTree::arg, cmp(), RBTree::combiner, RBTree::comparator, data, RBTNode::left, rbt_copy_data(), rbt_insert_fixup(), RBTNIL, RBTRED, RBTNode::right, RBTree::root, and x.

Referenced by ginInsertBAEntry(), and rbt_populate().

◆ rbt_insert_fixup()

static void rbt_insert_fixup ( RBTree *  rbt,
RBTNode *  x 
)
static

Definition at line 344 of file rbtree.c.

345{
346 /*
347 * x is always a red node. Initially, it is the newly inserted node. Each
348 * iteration of this loop moves it higher up in the tree.
349 */
350 while (x != rbt->root && x->parent->color == RBTRED)
351 {
352 /*
353 * x and x->parent are both red. Fix depends on whether x->parent is
354 * a left or right child. In either case, we define y to be the
355 * "uncle" of x, that is, the other child of x's grandparent.
356 *
357 * If the uncle is red, we flip the grandparent to red and its two
358 * children to black. Then we loop around again to check whether the
359 * grandparent still has a problem.
360 *
361 * If the uncle is black, we will perform one or two "rotations" to
362 * balance the tree. Either x or x->parent will take the
363 * grandparent's position in the tree and recolored black, and the
364 * original grandparent will be recolored red and become a child of
365 * that node. This always leaves us with a valid red-black tree, so
366 * the loop will terminate.
367 */
368 if (x->parent == x->parent->parent->left)
369 {
370 RBTNode *y = x->parent->parent->right;
371
372 if (y->color == RBTRED)
373 {
374 /* uncle is RBTRED */
375 x->parent->color = RBTBLACK;
376 y->color = RBTBLACK;
377 x->parent->parent->color = RBTRED;
378
379 x = x->parent->parent;
380 }
381 else
382 {
383 /* uncle is RBTBLACK */
384 if (x == x->parent->right)
385 {
386 /* make x a left child */
387 x = x->parent;
388 rbt_rotate_left(rbt, x);
389 }
390
391 /* recolor and rotate */
392 x->parent->color = RBTBLACK;
393 x->parent->parent->color = RBTRED;
394
395 rbt_rotate_right(rbt, x->parent->parent);
396 }
397 }
398 else
399 {
400 /* mirror image of above code */
401 RBTNode *y = x->parent->parent->left;
402
403 if (y->color == RBTRED)
404 {
405 /* uncle is RBTRED */
406 x->parent->color = RBTBLACK;
407 y->color = RBTBLACK;
408 x->parent->parent->color = RBTRED;
409
410 x = x->parent->parent;
411 }
412 else
413 {
414 /* uncle is RBTBLACK */
415 if (x == x->parent->left)
416 {
417 x = x->parent;
418 rbt_rotate_right(rbt, x);
419 }
420 x->parent->color = RBTBLACK;
421 x->parent->parent->color = RBTRED;
422
423 rbt_rotate_left(rbt, x->parent->parent);
424 }
425 }
426 }
427
428 /*
429 * The root may already have been black; if not, the black-height of every
430 * node in the tree increases by one.
431 */
432 rbt->root->color = RBTBLACK;
433}

References RBTNode::color, rbt_rotate_left(), rbt_rotate_right(), RBTBLACK, RBTRED, RBTree::root, x, and y.

Referenced by rbt_insert().

◆ rbt_iterate()

RBTNode * rbt_iterate ( RBTreeIterator *  iter )

Definition at line 826 of file rbtree.c.

827{
828 if (iter->is_over)
829 return NULL;
830
831 return iter->iterate(iter);
832}

References RBTreeIterator::is_over, and RBTreeIterator::iterate.

Referenced by ginGetBAEntry(), testleftright(), and testrightleft().

◆ rbt_left_right_iterator()

static RBTNode * rbt_left_right_iterator ( RBTreeIterator *  iter )
static

Definition at line 705 of file rbtree.c.

706{
707 if (iter->last_visited == NULL)
708 {
709 iter->last_visited = iter->rbt->root;
710 while (iter->last_visited->left != RBTNIL)
711 iter->last_visited = iter->last_visited->left;
712
713 return iter->last_visited;
714 }
715
716 if (iter->last_visited->right != RBTNIL)
717 {
718 iter->last_visited = iter->last_visited->right;
719 while (iter->last_visited->left != RBTNIL)
720 iter->last_visited = iter->last_visited->left;
721
722 return iter->last_visited;
723 }
724
725 for (;;)
726 {
727 RBTNode *came_from = iter->last_visited;
728
729 iter->last_visited = iter->last_visited->parent;
730 if (iter->last_visited == NULL)
731 {
732 iter->is_over = true;
733 break;
734 }
735
736 if (iter->last_visited->left == came_from)
737 break; /* came from left sub-tree, return current
738 * node */
739
740 /* else - came from right sub-tree, continue to move up */
741 }
742
743 return iter->last_visited;
744}
struct RBTNode * parent
Definition: rbtree.h:28

References RBTreeIterator::is_over, RBTreeIterator::last_visited, RBTNode::left, RBTNode::parent, RBTreeIterator::rbt, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by rbt_begin_iterate().

◆ rbt_leftmost()

RBTNode * rbt_leftmost ( RBTree *  rbt )

Definition at line 235 of file rbtree.c.

236{
237 RBTNode *node = rbt->root;
238 RBTNode *leftmost = rbt->root;
239
240 while (node != RBTNIL)
241 {
242 leftmost = node;
243 node = node->left;
244 }
245
246 if (leftmost != RBTNIL)
247 return leftmost;
248
249 return NULL;
250}

References RBTNode::left, RBTNIL, and RBTree::root.

Referenced by testdelete(), and testleftmost().

◆ rbt_right_left_iterator()

static RBTNode * rbt_right_left_iterator ( RBTreeIterator *  iter )
static

Definition at line 747 of file rbtree.c.

748{
749 if (iter->last_visited == NULL)
750 {
751 iter->last_visited = iter->rbt->root;
752 while (iter->last_visited->right != RBTNIL)
753 iter->last_visited = iter->last_visited->right;
754
755 return iter->last_visited;
756 }
757
758 if (iter->last_visited->left != RBTNIL)
759 {
760 iter->last_visited = iter->last_visited->left;
761 while (iter->last_visited->right != RBTNIL)
762 iter->last_visited = iter->last_visited->right;
763
764 return iter->last_visited;
765 }
766
767 for (;;)
768 {
769 RBTNode *came_from = iter->last_visited;
770
771 iter->last_visited = iter->last_visited->parent;
772 if (iter->last_visited == NULL)
773 {
774 iter->is_over = true;
775 break;
776 }
777
778 if (iter->last_visited->right == came_from)
779 break; /* came from right sub-tree, return current
780 * node */
781
782 /* else - came from left sub-tree, continue to move up */
783 }
784
785 return iter->last_visited;
786}

References RBTreeIterator::is_over, RBTreeIterator::last_visited, RBTNode::left, RBTNode::parent, RBTreeIterator::rbt, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by rbt_begin_iterate().

◆ rbt_rotate_left()

static void rbt_rotate_left ( RBTree *  rbt,
RBTNode *  x 
)
static

Definition at line 263 of file rbtree.c.

264{
265 RBTNode *y = x->right;
266
267 /* establish x->right link */
268 x->right = y->left;
269 if (y->left != RBTNIL)
270 y->left->parent = x;
271
272 /* establish y->parent link */
273 if (y != RBTNIL)
274 y->parent = x->parent;
275 if (x->parent)
276 {
277 if (x == x->parent->left)
278 x->parent->left = y;
279 else
280 x->parent->right = y;
281 }
282 else
283 {
284 rbt->root = y;
285 }
286
287 /* link x and y */
288 y->left = x;
289 if (x != RBTNIL)
290 x->parent = y;
291}

References RBTNIL, RBTree::root, x, and y.

Referenced by rbt_delete_fixup(), and rbt_insert_fixup().

◆ rbt_rotate_right()

static void rbt_rotate_right ( RBTree *  rbt,
RBTNode *  x 
)
static

Definition at line 300 of file rbtree.c.

301{
302 RBTNode *y = x->left;
303
304 /* establish x->left link */
305 x->left = y->right;
306 if (y->right != RBTNIL)
307 y->right->parent = x;
308
309 /* establish y->parent link */
310 if (y != RBTNIL)
311 y->parent = x->parent;
312 if (x->parent)
313 {
314 if (x == x->parent->right)
315 x->parent->right = y;
316 else
317 x->parent->left = y;
318 }
319 else
320 {
321 rbt->root = y;
322 }
323
324 /* link x and y */
325 y->right = x;
326 if (x != RBTNIL)
327 x->parent = y;
328}

References RBTNIL, RBTree::root, x, and y.

Referenced by rbt_delete_fixup(), and rbt_insert_fixup().

Variable Documentation

◆ sentinel

RBTNode sentinel
static
Initial value:
=
{
.color = RBTBLACK,.left = RBTNIL,.right = RBTNIL,.parent = NULL
}

Definition at line 63 of file rbtree.c.

AltStyle によって変換されたページ (->オリジナル) /