PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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 RBBLACK   (0)
 
#define RBRED   (1)
 
#define RBNIL   (&sentinel)
 

Functions

RBTreerb_create (Size node_size, rb_comparator comparator, rb_combiner combiner, rb_allocfunc allocfunc, rb_freefunc freefunc, void *arg)
 
static void rb_copy_data (RBTree *rb, RBNode *dest, const RBNode *src)
 
RBNoderb_find (RBTree *rb, const RBNode *data)
 
RBNoderb_leftmost (RBTree *rb)
 
static void rb_rotate_left (RBTree *rb, RBNode *x)
 
static void rb_rotate_right (RBTree *rb, RBNode *x)
 
static void rb_insert_fixup (RBTree *rb, RBNode *x)
 
RBNoderb_insert (RBTree *rb, const RBNode *data, bool *isNew)
 
static void rb_delete_fixup (RBTree *rb, RBNode *x)
 
static void rb_delete_node (RBTree *rb, RBNode *z)
 
void rb_delete (RBTree *rb, RBNode *node)
 
static RBNoderb_left_right_iterator (RBTreeIterator *iter)
 
static RBNoderb_right_left_iterator (RBTreeIterator *iter)
 
void rb_begin_iterate (RBTree *rb, RBOrderControl ctrl, RBTreeIterator *iter)
 
RBNoderb_iterate (RBTreeIterator *iter)
 

Variables

static RBNode sentinel = {RBBLACK, RBNIL, RBNIL, NULL}
 

Macro Definition Documentation

#define RBBLACK   (0)

Definition at line 35 of file rbtree.c.

Referenced by rb_delete_fixup(), rb_delete_node(), and rb_insert_fixup().

#define RBRED   (1)

Definition at line 36 of file rbtree.c.

Referenced by rb_delete_fixup(), rb_insert(), and rb_insert_fixup().

Function Documentation

void rb_begin_iterate ( RBTree rb,
RBOrderControl  ctrl,
RBTreeIterator iter 
)

Definition at line 737 of file rbtree.c.

References elog, ERROR, RBTreeIterator::is_over, RBTreeIterator::iterate, RBTreeIterator::last_visited, LeftRightWalk, RBTreeIterator::rb, rb_left_right_iterator(), rb_right_left_iterator(), RBNIL, RightLeftWalk, and RBTree::root.

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

738 {
739  /* Common initialization for all traversal orders */
740  iter->rb = rb;
741  iter->last_visited = NULL;
742  iter->is_over = (rb->root == RBNIL);
743 
744  switch (ctrl)
745  {
746  case LeftRightWalk: /* visit left, then self, then right */
748  break;
749  case RightLeftWalk: /* visit right, then self, then left */
751  break;
752  default:
753  elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
754  }
755 }
RBNode * last_visited
Definition: rbtree.h:52
RBNode *(* iterate)(RBTreeIterator *iter)
Definition: rbtree.h:51
#define ERROR
Definition: elog.h:43
#define RBNIL
Definition: rbtree.c:61
bool is_over
Definition: rbtree.h:53
static RBNode * rb_left_right_iterator(RBTreeIterator *iter)
Definition: rbtree.c:640
RBTree * rb
Definition: rbtree.h:50
RBNode * root
Definition: rbtree.c:43
static RBNode * rb_right_left_iterator(RBTreeIterator *iter)
Definition: rbtree.c:682
#define elog
Definition: elog.h:219
static void rb_copy_data ( RBTree rb,
RBNode dest,
const RBNode src 
)
inlinestatic

Definition at line 124 of file rbtree.c.

References RBTree::node_size.

Referenced by rb_delete_node(), and rb_insert().

125 {
126  memcpy(dest + 1, src + 1, rb->node_size - sizeof(RBNode));
127 }
Size node_size
Definition: rbtree.c:47
Definition: rbtree.h:23
RBTree* rb_create ( Size  node_size,
rb_comparator  comparator,
rb_combiner  combiner,
rb_allocfunc  allocfunc,
rb_freefunc  freefunc,
void *  arg 
)

Definition at line 99 of file rbtree.c.

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

Referenced by create_int_rbtree(), and ginInitBA().

105 {
106  RBTree *tree = (RBTree *) palloc(sizeof(RBTree));
107 
108  Assert(node_size > sizeof(RBNode));
109 
110  tree->root = RBNIL;
111  tree->node_size = node_size;
112  tree->comparator = comparator;
113  tree->combiner = combiner;
114  tree->allocfunc = allocfunc;
115  tree->freefunc = freefunc;
116 
117  tree->arg = arg;
118 
119  return tree;
120 }
rb_comparator comparator
Definition: rbtree.c:49
rb_allocfunc allocfunc
Definition: rbtree.c:51
Size node_size
Definition: rbtree.c:47
Definition: rbtree.h:23
rb_combiner combiner
Definition: rbtree.c:50
#define RBNIL
Definition: rbtree.c:61
rb_freefunc freefunc
Definition: rbtree.c:52
void * arg
Definition: rbtree.c:54
#define Assert(condition)
Definition: c.h:681
RBNode * root
Definition: rbtree.c:43
void * palloc(Size size)
Definition: mcxt.c:848
Definition: rbtree.c:41
void * arg
void rb_delete ( RBTree rb,
RBNode node 
)

Definition at line 630 of file rbtree.c.

References rb_delete_node().

Referenced by testdelete().

631 {
632  rb_delete_node(rb, node);
633 }
static void rb_delete_node(RBTree *rb, RBNode *z)
Definition: rbtree.c:554
static void rb_delete_fixup ( RBTree rb,
RBNode x 
)
static

Definition at line 456 of file rbtree.c.

References RBNode::color, RBNode::left, RBNode::parent, rb_rotate_left(), rb_rotate_right(), RBBLACK, RBRED, RBNode::right, and RBTree::root.

Referenced by rb_delete_node().

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

Definition at line 554 of file rbtree.c.

References RBTree::arg, RBNode::color, RBTree::freefunc, RBNode::left, RBNode::parent, rb_copy_data(), rb_delete_fixup(), RBBLACK, RBNIL, RBNode::right, and RBTree::root.

Referenced by rb_delete().

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

Definition at line 142 of file rbtree.c.

References RBTree::arg, cmp(), RBTree::comparator, RBNode::left, RBNIL, RBNode::right, and RBTree::root.

Referenced by testdelete(), and testfind().

143 {
144  RBNode *node = rb->root;
145 
146  while (node != RBNIL)
147  {
148  int cmp = rb->comparator(data, node, rb->arg);
149 
150  if (cmp == 0)
151  return node;
152  else if (cmp < 0)
153  node = node->left;
154  else
155  node = node->right;
156  }
157 
158  return NULL;
159 }
struct RBNode * left
Definition: rbtree.h:26
rb_comparator comparator
Definition: rbtree.c:49
struct RBNode * right
Definition: rbtree.h:27
Definition: rbtree.h:23
#define RBNIL
Definition: rbtree.c:61
void * arg
Definition: rbtree.c:54
RBNode * root
Definition: rbtree.c:43
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742
RBNode* rb_insert ( RBTree rb,
const RBNode data,
bool isNew 
)

Definition at line 388 of file rbtree.c.

References RBTree::allocfunc, RBTree::arg, cmp(), RBNode::color, RBTree::combiner, RBTree::comparator, RBNode::left, RBNode::parent, rb_copy_data(), rb_insert_fixup(), RBNIL, RBRED, RBNode::right, and RBTree::root.

Referenced by ginInsertBAEntry(), and rb_populate().

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

Definition at line 279 of file rbtree.c.

References RBNode::color, RBNode::left, RBNode::parent, rb_rotate_left(), rb_rotate_right(), RBBLACK, RBRED, RBNode::right, and RBTree::root.

Referenced by rb_insert().

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

Definition at line 761 of file rbtree.c.

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

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

762 {
763  if (iter->is_over)
764  return NULL;
765 
766  return iter->iterate(iter);
767 }
RBNode *(* iterate)(RBTreeIterator *iter)
Definition: rbtree.h:51
bool is_over
Definition: rbtree.h:53
static RBNode* rb_left_right_iterator ( RBTreeIterator iter)
static

Definition at line 640 of file rbtree.c.

References RBTreeIterator::is_over, RBTreeIterator::last_visited, RBNode::left, RBNode::parent, RBTreeIterator::rb, RBNIL, RBNode::right, and RBTree::root.

Referenced by rb_begin_iterate().

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

Definition at line 170 of file rbtree.c.

References RBNode::left, RBNIL, and RBTree::root.

Referenced by testdelete(), and testleftmost().

171 {
172  RBNode *node = rb->root;
173  RBNode *leftmost = rb->root;
174 
175  while (node != RBNIL)
176  {
177  leftmost = node;
178  node = node->left;
179  }
180 
181  if (leftmost != RBNIL)
182  return leftmost;
183 
184  return NULL;
185 }
struct RBNode * left
Definition: rbtree.h:26
Definition: rbtree.h:23
#define RBNIL
Definition: rbtree.c:61
RBNode * root
Definition: rbtree.c:43
static RBNode* rb_right_left_iterator ( RBTreeIterator iter)
static

Definition at line 682 of file rbtree.c.

References RBTreeIterator::is_over, RBTreeIterator::last_visited, RBNode::left, RBNode::parent, RBTreeIterator::rb, RBNIL, RBNode::right, and RBTree::root.

Referenced by rb_begin_iterate().

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

Definition at line 198 of file rbtree.c.

References RBNode::left, RBNode::parent, RBNIL, RBNode::right, and RBTree::root.

Referenced by rb_delete_fixup(), and rb_insert_fixup().

199 {
200  RBNode *y = x->right;
201 
202  /* establish x->right link */
203  x->right = y->left;
204  if (y->left != RBNIL)
205  y->left->parent = x;
206 
207  /* establish y->parent link */
208  if (y != RBNIL)
209  y->parent = x->parent;
210  if (x->parent)
211  {
212  if (x == x->parent->left)
213  x->parent->left = y;
214  else
215  x->parent->right = y;
216  }
217  else
218  {
219  rb->root = y;
220  }
221 
222  /* link x and y */
223  y->left = x;
224  if (x != RBNIL)
225  x->parent = y;
226 }
struct RBNode * left
Definition: rbtree.h:26
struct RBNode * right
Definition: rbtree.h:27
struct RBNode * parent
Definition: rbtree.h:28
Definition: rbtree.h:23
#define RBNIL
Definition: rbtree.c:61
RBNode * root
Definition: rbtree.c:43
static void rb_rotate_right ( RBTree rb,
RBNode x 
)
static

Definition at line 235 of file rbtree.c.

References RBNode::left, RBNode::parent, RBNIL, RBNode::right, and RBTree::root.

Referenced by rb_delete_fixup(), and rb_insert_fixup().

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

Variable Documentation

RBNode sentinel = {RBBLACK, RBNIL, RBNIL, NULL}
static

Definition at line 63 of file rbtree.c.