PostgreSQL Source Code  git master
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

RBTreerbt_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)
 
RBTNoderbt_find (RBTree *rbt, const RBTNode *data)
 
RBTNoderbt_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)
 
RBTNoderbt_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 RBTNoderbt_left_right_iterator (RBTreeIterator *iter)
 
static RBTNoderbt_right_left_iterator (RBTreeIterator *iter)
 
void rbt_begin_iterate (RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
 
RBTNoderbt_iterate (RBTreeIterator *iter)
 

Variables

static RBTNode sentinel
 

Macro Definition Documentation

◆ RBTBLACK

#define RBTBLACK   (0)

Definition at line 35 of file rbtree.c.

Referenced by rbt_delete_fixup(), rbt_delete_node(), and rbt_insert_fixup().

◆ RBTNIL

◆ RBTRED

#define RBTRED   (1)

Definition at line 36 of file rbtree.c.

Referenced by rbt_delete_fixup(), rbt_insert(), and rbt_insert_fixup().

Function Documentation

◆ rbt_begin_iterate()

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

Definition at line 740 of file rbtree.c.

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().

741 {
742  /* Common initialization for all traversal orders */
743  iter->rbt = rbt;
744  iter->last_visited = NULL;
745  iter->is_over = (rbt->root == RBTNIL);
746 
747  switch (ctrl)
748  {
749  case LeftRightWalk: /* visit left, then self, then right */
751  break;
752  case RightLeftWalk: /* visit right, then self, then left */
754  break;
755  default:
756  elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
757  }
758 }
static RBTNode * rbt_left_right_iterator(RBTreeIterator *iter)
Definition: rbtree.c:643
RBTNode * last_visited
Definition: rbtree.h:52
#define RBTNIL
Definition: rbtree.c:61
#define ERROR
Definition: elog.h:43
RBTNode * root
Definition: rbtree.c:43
bool is_over
Definition: rbtree.h:53
RBTNode *(* iterate)(RBTreeIterator *iter)
Definition: rbtree.h:51
#define elog(elevel,...)
Definition: elog.h:226
static RBTNode * rbt_right_left_iterator(RBTreeIterator *iter)
Definition: rbtree.c:685
RBTree * rbt
Definition: rbtree.h:50

◆ rbt_copy_data()

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

Definition at line 127 of file rbtree.c.

References RBTree::node_size.

Referenced by rbt_delete_node(), and rbt_insert().

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

◆ 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.

References RBTree::allocfunc, RBTree::arg, Assert, RBTree::combiner, RBTree::comparator, RBTree::freefunc, RBTree::node_size, palloc(), RBTNIL, and RBTree::root.

Referenced by create_int_rbtree(), and ginInitBA().

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 }
rbt_freefunc freefunc
Definition: rbtree.c:52
Size node_size
Definition: rbtree.c:47
#define RBTNIL
Definition: rbtree.c:61
RBTNode * root
Definition: rbtree.c:43
rbt_comparator comparator
Definition: rbtree.c:49
void * arg
Definition: rbtree.c:54
#define Assert(condition)
Definition: c.h:732
Definition: rbtree.h:23
void * palloc(Size size)
Definition: mcxt.c:949
Definition: rbtree.c:41
rbt_allocfunc allocfunc
Definition: rbtree.c:51
void * arg
rbt_combiner combiner
Definition: rbtree.c:50

◆ rbt_delete()

void rbt_delete ( RBTree rbt,
RBTNode node 
)

Definition at line 633 of file rbtree.c.

References rbt_delete_node().

Referenced by testdelete().

634 {
635  rbt_delete_node(rbt, node);
636 }
static void rbt_delete_node(RBTree *rbt, RBTNode *z)
Definition: rbtree.c:557

◆ rbt_delete_fixup()

static void rbt_delete_fixup ( RBTree rbt,
RBTNode x 
)
static

Definition at line 459 of file rbtree.c.

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

Referenced by rbt_delete_node().

460 {
461  /*
462  * x is always a black node. Initially, it is the former child of the
463  * deleted node. Each iteration of this loop moves it higher up in the
464  * tree.
465  */
466  while (x != rbt->root && x->color == RBTBLACK)
467  {
468  /*
469  * Left and right cases are symmetric. Any nodes that are children of
470  * x have a black-height one less than the remainder of the nodes in
471  * the tree. We rotate and recolor nodes to move the problem up the
472  * tree: at some stage we'll either fix the problem, or reach the root
473  * (where the black-height is allowed to decrease).
474  */
475  if (x == x->parent->left)
476  {
477  RBTNode *w = x->parent->right;
478 
479  if (w->color == RBTRED)
480  {
481  w->color = RBTBLACK;
482  x->parent->color = RBTRED;
483 
484  rbt_rotate_left(rbt, x->parent);
485  w = x->parent->right;
486  }
487 
488  if (w->left->color == RBTBLACK && w->right->color == RBTBLACK)
489  {
490  w->color = RBTRED;
491 
492  x = x->parent;
493  }
494  else
495  {
496  if (w->right->color == RBTBLACK)
497  {
498  w->left->color = RBTBLACK;
499  w->color = RBTRED;
500 
501  rbt_rotate_right(rbt, w);
502  w = x->parent->right;
503  }
504  w->color = x->parent->color;
505  x->parent->color = RBTBLACK;
506  w->right->color = RBTBLACK;
507 
508  rbt_rotate_left(rbt, x->parent);
509  x = rbt->root; /* Arrange for loop to terminate. */
510  }
511  }
512  else
513  {
514  RBTNode *w = x->parent->left;
515 
516  if (w->color == RBTRED)
517  {
518  w->color = RBTBLACK;
519  x->parent->color = RBTRED;
520 
521  rbt_rotate_right(rbt, x->parent);
522  w = x->parent->left;
523  }
524 
525  if (w->right->color == RBTBLACK && w->left->color == RBTBLACK)
526  {
527  w->color = RBTRED;
528 
529  x = x->parent;
530  }
531  else
532  {
533  if (w->left->color == RBTBLACK)
534  {
535  w->right->color = RBTBLACK;
536  w->color = RBTRED;
537 
538  rbt_rotate_left(rbt, w);
539  w = x->parent->left;
540  }
541  w->color = x->parent->color;
542  x->parent->color = RBTBLACK;
543  w->left->color = RBTBLACK;
544 
545  rbt_rotate_right(rbt, x->parent);
546  x = rbt->root; /* Arrange for loop to terminate. */
547  }
548  }
549  }
550  x->color = RBTBLACK;
551 }
#define RBTRED
Definition: rbtree.c:36
struct RBTNode * left
Definition: rbtree.h:26
RBTNode * root
Definition: rbtree.c:43
static void rbt_rotate_right(RBTree *rbt, RBTNode *x)
Definition: rbtree.c:238
struct RBTNode * parent
Definition: rbtree.h:28
#define RBTBLACK
Definition: rbtree.c:35
struct RBTNode * right
Definition: rbtree.h:27
char color
Definition: rbtree.h:25
static void rbt_rotate_left(RBTree *rbt, RBTNode *x)
Definition: rbtree.c:201
Definition: rbtree.h:23

◆ rbt_delete_node()

static void rbt_delete_node ( RBTree rbt,
RBTNode z 
)
static

Definition at line 557 of file rbtree.c.

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

Referenced by rbt_delete().

558 {
559  RBTNode *x,
560  *y;
561 
562  /* This is just paranoia: we should only get called on a valid node */
563  if (!z || z == RBTNIL)
564  return;
565 
566  /*
567  * y is the node that will actually be removed from the tree. This will
568  * be z if z has fewer than two children, or the tree successor of z
569  * otherwise.
570  */
571  if (z->left == RBTNIL || z->right == RBTNIL)
572  {
573  /* y has a RBTNIL node as a child */
574  y = z;
575  }
576  else
577  {
578  /* find tree successor */
579  y = z->right;
580  while (y->left != RBTNIL)
581  y = y->left;
582  }
583 
584  /* x is y's only child */
585  if (y->left != RBTNIL)
586  x = y->left;
587  else
588  x = y->right;
589 
590  /* Remove y from the tree. */
591  x->parent = y->parent;
592  if (y->parent)
593  {
594  if (y == y->parent->left)
595  y->parent->left = x;
596  else
597  y->parent->right = x;
598  }
599  else
600  {
601  rbt->root = x;
602  }
603 
604  /*
605  * If we removed the tree successor of z rather than z itself, then move
606  * the data for the removed node to the one we were supposed to remove.
607  */
608  if (y != z)
609  rbt_copy_data(rbt, z, y);
610 
611  /*
612  * Removing a black node might make some paths from root to leaf contain
613  * fewer black nodes than others, or it might make two red nodes adjacent.
614  */
615  if (y->color == RBTBLACK)
616  rbt_delete_fixup(rbt, x);
617 
618  /* Now we can recycle the y node */
619  if (rbt->freefunc)
620  rbt->freefunc(y, rbt->arg);
621 }
static void rbt_copy_data(RBTree *rbt, RBTNode *dest, const RBTNode *src)
Definition: rbtree.c:127
static void rbt_delete_fixup(RBTree *rbt, RBTNode *x)
Definition: rbtree.c:459
struct RBTNode * left
Definition: rbtree.h:26
rbt_freefunc freefunc
Definition: rbtree.c:52
#define RBTNIL
Definition: rbtree.c:61
RBTNode * root
Definition: rbtree.c:43
struct RBTNode * parent
Definition: rbtree.h:28
#define RBTBLACK
Definition: rbtree.c:35
struct RBTNode * right
Definition: rbtree.h:27
char color
Definition: rbtree.h:25
void * arg
Definition: rbtree.c:54
Definition: rbtree.h:23

◆ rbt_find()

RBTNode* rbt_find ( RBTree rbt,
const RBTNode data 
)

Definition at line 145 of file rbtree.c.

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

Referenced by testdelete(), and testfind().

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 }
struct RBTNode * left
Definition: rbtree.h:26
#define RBTNIL
Definition: rbtree.c:61
RBTNode * root
Definition: rbtree.c:43
rbt_comparator comparator
Definition: rbtree.c:49
struct RBTNode * right
Definition: rbtree.h:27
void * arg
Definition: rbtree.c:54
Definition: rbtree.h:23
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742

◆ rbt_insert()

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

Definition at line 391 of file rbtree.c.

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

Referenced by ginInsertBAEntry(), and rbt_populate().

392 {
393  RBTNode *current,
394  *parent,
395  *x;
396  int cmp;
397 
398  /* find where node belongs */
399  current = rbt->root;
400  parent = NULL;
401  cmp = 0; /* just to prevent compiler warning */
402 
403  while (current != RBTNIL)
404  {
405  cmp = rbt->comparator(data, current, rbt->arg);
406  if (cmp == 0)
407  {
408  /*
409  * Found node with given key. Apply combiner.
410  */
411  rbt->combiner(current, data, rbt->arg);
412  *isNew = false;
413  return current;
414  }
415  parent = current;
416  current = (cmp < 0) ? current->left : current->right;
417  }
418 
419  /*
420  * Value is not present, so create a new node containing data.
421  */
422  *isNew = true;
423 
424  x = rbt->allocfunc(rbt->arg);
425 
426  x->color = RBTRED;
427 
428  x->left = RBTNIL;
429  x->right = RBTNIL;
430  x->parent = parent;
431  rbt_copy_data(rbt, x, data);
432 
433  /* insert node in tree */
434  if (parent)
435  {
436  if (cmp < 0)
437  parent->left = x;
438  else
439  parent->right = x;
440  }
441  else
442  {
443  rbt->root = x;
444  }
445 
446  rbt_insert_fixup(rbt, x);
447 
448  return x;
449 }
static void rbt_copy_data(RBTree *rbt, RBTNode *dest, const RBTNode *src)
Definition: rbtree.c:127
#define RBTRED
Definition: rbtree.c:36
struct RBTNode * left
Definition: rbtree.h:26
static void rbt_insert_fixup(RBTree *rbt, RBTNode *x)
Definition: rbtree.c:282
#define RBTNIL
Definition: rbtree.c:61
RBTNode * root
Definition: rbtree.c:43
rbt_comparator comparator
Definition: rbtree.c:49
struct RBTNode * parent
Definition: rbtree.h:28
struct RBTNode * right
Definition: rbtree.h:27
char color
Definition: rbtree.h:25
void * arg
Definition: rbtree.c:54
Definition: rbtree.h:23
rbt_allocfunc allocfunc
Definition: rbtree.c:51
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742
rbt_combiner combiner
Definition: rbtree.c:50

◆ rbt_insert_fixup()

static void rbt_insert_fixup ( RBTree rbt,
RBTNode x 
)
static

Definition at line 282 of file rbtree.c.

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

Referenced by rbt_insert().

283 {
284  /*
285  * x is always a red node. Initially, it is the newly inserted node. Each
286  * iteration of this loop moves it higher up in the tree.
287  */
288  while (x != rbt->root && x->parent->color == RBTRED)
289  {
290  /*
291  * x and x->parent are both red. Fix depends on whether x->parent is
292  * a left or right child. In either case, we define y to be the
293  * "uncle" of x, that is, the other child of x's grandparent.
294  *
295  * If the uncle is red, we flip the grandparent to red and its two
296  * children to black. Then we loop around again to check whether the
297  * grandparent still has a problem.
298  *
299  * If the uncle is black, we will perform one or two "rotations" to
300  * balance the tree. Either x or x->parent will take the
301  * grandparent's position in the tree and recolored black, and the
302  * original grandparent will be recolored red and become a child of
303  * that node. This always leaves us with a valid red-black tree, so
304  * the loop will terminate.
305  */
306  if (x->parent == x->parent->parent->left)
307  {
308  RBTNode *y = x->parent->parent->right;
309 
310  if (y->color == RBTRED)
311  {
312  /* uncle is RBTRED */
313  x->parent->color = RBTBLACK;
314  y->color = RBTBLACK;
315  x->parent->parent->color = RBTRED;
316 
317  x = x->parent->parent;
318  }
319  else
320  {
321  /* uncle is RBTBLACK */
322  if (x == x->parent->right)
323  {
324  /* make x a left child */
325  x = x->parent;
326  rbt_rotate_left(rbt, x);
327  }
328 
329  /* recolor and rotate */
330  x->parent->color = RBTBLACK;
331  x->parent->parent->color = RBTRED;
332 
333  rbt_rotate_right(rbt, x->parent->parent);
334  }
335  }
336  else
337  {
338  /* mirror image of above code */
339  RBTNode *y = x->parent->parent->left;
340 
341  if (y->color == RBTRED)
342  {
343  /* uncle is RBTRED */
344  x->parent->color = RBTBLACK;
345  y->color = RBTBLACK;
346  x->parent->parent->color = RBTRED;
347 
348  x = x->parent->parent;
349  }
350  else
351  {
352  /* uncle is RBTBLACK */
353  if (x == x->parent->left)
354  {
355  x = x->parent;
356  rbt_rotate_right(rbt, x);
357  }
358  x->parent->color = RBTBLACK;
359  x->parent->parent->color = RBTRED;
360 
361  rbt_rotate_left(rbt, x->parent->parent);
362  }
363  }
364  }
365 
366  /*
367  * The root may already have been black; if not, the black-height of every
368  * node in the tree increases by one.
369  */
370  rbt->root->color = RBTBLACK;
371 }
#define RBTRED
Definition: rbtree.c:36
struct RBTNode * left
Definition: rbtree.h:26
RBTNode * root
Definition: rbtree.c:43
static void rbt_rotate_right(RBTree *rbt, RBTNode *x)
Definition: rbtree.c:238
struct RBTNode * parent
Definition: rbtree.h:28
#define RBTBLACK
Definition: rbtree.c:35
struct RBTNode * right
Definition: rbtree.h:27
char color
Definition: rbtree.h:25
static void rbt_rotate_left(RBTree *rbt, RBTNode *x)
Definition: rbtree.c:201
Definition: rbtree.h:23

◆ rbt_iterate()

RBTNode* rbt_iterate ( RBTreeIterator iter)

Definition at line 764 of file rbtree.c.

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

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

765 {
766  if (iter->is_over)
767  return NULL;
768 
769  return iter->iterate(iter);
770 }
bool is_over
Definition: rbtree.h:53
RBTNode *(* iterate)(RBTreeIterator *iter)
Definition: rbtree.h:51

◆ rbt_left_right_iterator()

static RBTNode* rbt_left_right_iterator ( RBTreeIterator iter)
static

Definition at line 643 of file rbtree.c.

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

Referenced by rbt_begin_iterate().

644 {
645  if (iter->last_visited == NULL)
646  {
647  iter->last_visited = iter->rbt->root;
648  while (iter->last_visited->left != RBTNIL)
649  iter->last_visited = iter->last_visited->left;
650 
651  return iter->last_visited;
652  }
653 
654  if (iter->last_visited->right != RBTNIL)
655  {
656  iter->last_visited = iter->last_visited->right;
657  while (iter->last_visited->left != RBTNIL)
658  iter->last_visited = iter->last_visited->left;
659 
660  return iter->last_visited;
661  }
662 
663  for (;;)
664  {
665  RBTNode *came_from = iter->last_visited;
666 
667  iter->last_visited = iter->last_visited->parent;
668  if (iter->last_visited == NULL)
669  {
670  iter->is_over = true;
671  break;
672  }
673 
674  if (iter->last_visited->left == came_from)
675  break; /* came from left sub-tree, return current
676  * node */
677 
678  /* else - came from right sub-tree, continue to move up */
679  }
680 
681  return iter->last_visited;
682 }
struct RBTNode * left
Definition: rbtree.h:26
RBTNode * last_visited
Definition: rbtree.h:52
#define RBTNIL
Definition: rbtree.c:61
RBTNode * root
Definition: rbtree.c:43
bool is_over
Definition: rbtree.h:53
struct RBTNode * parent
Definition: rbtree.h:28
struct RBTNode * right
Definition: rbtree.h:27
Definition: rbtree.h:23
RBTree * rbt
Definition: rbtree.h:50

◆ rbt_leftmost()

RBTNode* rbt_leftmost ( RBTree rbt)

Definition at line 173 of file rbtree.c.

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

Referenced by testdelete(), and testleftmost().

174 {
175  RBTNode *node = rbt->root;
176  RBTNode *leftmost = rbt->root;
177 
178  while (node != RBTNIL)
179  {
180  leftmost = node;
181  node = node->left;
182  }
183 
184  if (leftmost != RBTNIL)
185  return leftmost;
186 
187  return NULL;
188 }
struct RBTNode * left
Definition: rbtree.h:26
#define RBTNIL
Definition: rbtree.c:61
RBTNode * root
Definition: rbtree.c:43
Definition: rbtree.h:23

◆ rbt_right_left_iterator()

static RBTNode* rbt_right_left_iterator ( RBTreeIterator iter)
static

Definition at line 685 of file rbtree.c.

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

Referenced by rbt_begin_iterate().

686 {
687  if (iter->last_visited == NULL)
688  {
689  iter->last_visited = iter->rbt->root;
690  while (iter->last_visited->right != RBTNIL)
691  iter->last_visited = iter->last_visited->right;
692 
693  return iter->last_visited;
694  }
695 
696  if (iter->last_visited->left != RBTNIL)
697  {
698  iter->last_visited = iter->last_visited->left;
699  while (iter->last_visited->right != RBTNIL)
700  iter->last_visited = iter->last_visited->right;
701 
702  return iter->last_visited;
703  }
704 
705  for (;;)
706  {
707  RBTNode *came_from = iter->last_visited;
708 
709  iter->last_visited = iter->last_visited->parent;
710  if (iter->last_visited == NULL)
711  {
712  iter->is_over = true;
713  break;
714  }
715 
716  if (iter->last_visited->right == came_from)
717  break; /* came from right sub-tree, return current
718  * node */
719 
720  /* else - came from left sub-tree, continue to move up */
721  }
722 
723  return iter->last_visited;
724 }
struct RBTNode * left
Definition: rbtree.h:26
RBTNode * last_visited
Definition: rbtree.h:52
#define RBTNIL
Definition: rbtree.c:61
RBTNode * root
Definition: rbtree.c:43
bool is_over
Definition: rbtree.h:53
struct RBTNode * parent
Definition: rbtree.h:28
struct RBTNode * right
Definition: rbtree.h:27
Definition: rbtree.h:23
RBTree * rbt
Definition: rbtree.h:50

◆ rbt_rotate_left()

static void rbt_rotate_left ( RBTree rbt,
RBTNode x 
)
static

Definition at line 201 of file rbtree.c.

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

Referenced by rbt_delete_fixup(), and rbt_insert_fixup().

202 {
203  RBTNode *y = x->right;
204 
205  /* establish x->right link */
206  x->right = y->left;
207  if (y->left != RBTNIL)
208  y->left->parent = x;
209 
210  /* establish y->parent link */
211  if (y != RBTNIL)
212  y->parent = x->parent;
213  if (x->parent)
214  {
215  if (x == x->parent->left)
216  x->parent->left = y;
217  else
218  x->parent->right = y;
219  }
220  else
221  {
222  rbt->root = y;
223  }
224 
225  /* link x and y */
226  y->left = x;
227  if (x != RBTNIL)
228  x->parent = y;
229 }
struct RBTNode * left
Definition: rbtree.h:26
#define RBTNIL
Definition: rbtree.c:61
RBTNode * root
Definition: rbtree.c:43
struct RBTNode * parent
Definition: rbtree.h:28
struct RBTNode * right
Definition: rbtree.h:27
Definition: rbtree.h:23

◆ rbt_rotate_right()

static void rbt_rotate_right ( RBTree rbt,
RBTNode x 
)
static

Definition at line 238 of file rbtree.c.

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

Referenced by rbt_delete_fixup(), and rbt_insert_fixup().

239 {
240  RBTNode *y = x->left;
241 
242  /* establish x->left link */
243  x->left = y->right;
244  if (y->right != RBTNIL)
245  y->right->parent = x;
246 
247  /* establish y->parent link */
248  if (y != RBTNIL)
249  y->parent = x->parent;
250  if (x->parent)
251  {
252  if (x == x->parent->right)
253  x->parent->right = y;
254  else
255  x->parent->left = y;
256  }
257  else
258  {
259  rbt->root = y;
260  }
261 
262  /* link x and y */
263  y->right = x;
264  if (x != RBTNIL)
265  x->parent = y;
266 }
struct RBTNode * left
Definition: rbtree.h:26
#define RBTNIL
Definition: rbtree.c:61
RBTNode * root
Definition: rbtree.c:43
struct RBTNode * parent
Definition: rbtree.h:28
struct RBTNode * right
Definition: rbtree.h:27
Definition: rbtree.h:23

Variable Documentation

◆ sentinel

RBTNode sentinel
static
Initial value:
=
{
}
#define RBTNIL
Definition: rbtree.c:61
#define RBTBLACK
Definition: rbtree.c:35

Definition at line 63 of file rbtree.c.