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)
 

Typedefs

typedef enum InvertedWalkNextStep InvertedWalkNextStep
 

Enumerations

enum  InvertedWalkNextStep { NextStepBegin, NextStepUp, NextStepLeft, NextStepRight }
 

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)
 
static RBNoderb_direct_iterator (RBTreeIterator *iter)
 
static RBNoderb_inverted_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().

Typedef Documentation

Enumeration Type Documentation

Enumerator
NextStepBegin 
NextStepUp 
NextStepLeft 
NextStepRight 

Definition at line 69 of file rbtree.c.

Function Documentation

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

Definition at line 855 of file rbtree.c.

References DirectWalk, elog, ERROR, InvertedWalk, RBTreeIterator::is_over, RBTreeIterator::iterate, RBTreeIterator::last_visited, LeftRightWalk, RBTreeIterator::next_step, NextStepBegin, NULL, RBTreeIterator::rb, rb_direct_iterator(), rb_inverted_iterator(), rb_left_right_iterator(), rb_right_left_iterator(), RBNIL, RightLeftWalk, and RBTree::root.

Referenced by ginBeginBAScan().

856 {
857  /* Common initialization for all traversal orders */
858  iter->rb = rb;
859  iter->last_visited = NULL;
860  iter->is_over = (rb->root == RBNIL);
861 
862  switch (ctrl)
863  {
864  case LeftRightWalk: /* visit left, then self, then right */
866  break;
867  case RightLeftWalk: /* visit right, then self, then left */
869  break;
870  case DirectWalk: /* visit self, then left, then right */
871  iter->iterate = rb_direct_iterator;
872  break;
873  case InvertedWalk: /* visit left, then right, then self */
875  iter->next_step = NextStepBegin;
876  break;
877  default:
878  elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
879  }
880 }
RBNode * last_visited
Definition: rbtree.h:54
RBNode *(* iterate)(RBTreeIterator *iter)
Definition: rbtree.h:53
char next_step
Definition: rbtree.h:55
#define ERROR
Definition: elog.h:43
#define RBNIL
Definition: rbtree.c:61
bool is_over
Definition: rbtree.h:56
static RBNode * rb_left_right_iterator(RBTreeIterator *iter)
Definition: rbtree.c:650
static RBNode * rb_direct_iterator(RBTreeIterator *iter)
Definition: rbtree.c:734
#define NULL
Definition: c.h:229
RBTree * rb
Definition: rbtree.h:52
static RBNode * rb_inverted_iterator(RBTreeIterator *iter)
Definition: rbtree.c:781
RBNode * root
Definition: rbtree.c:43
static RBNode * rb_right_left_iterator(RBTreeIterator *iter)
Definition: rbtree.c:692
#define elog
Definition: elog.h:219
static void rb_copy_data ( RBTree rb,
RBNode dest,
const RBNode src 
)
inlinestatic

Definition at line 135 of file rbtree.c.

References RBTree::node_size.

Referenced by rb_delete_node(), and rb_insert().

136 {
137  memcpy(dest + 1, src + 1, rb->node_size - sizeof(RBNode));
138 }
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 110 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 ginInitBA().

116 {
117  RBTree *tree = (RBTree *) palloc(sizeof(RBTree));
118 
119  Assert(node_size > sizeof(RBNode));
120 
121  tree->root = RBNIL;
122  tree->node_size = node_size;
123  tree->comparator = comparator;
124  tree->combiner = combiner;
125  tree->allocfunc = allocfunc;
126  tree->freefunc = freefunc;
127 
128  tree->arg = arg;
129 
130  return tree;
131 }
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:675
RBNode * root
Definition: rbtree.c:43
void * palloc(Size size)
Definition: mcxt.c:849
Definition: rbtree.c:41
void * arg
void rb_delete ( RBTree rb,
RBNode node 
)

Definition at line 640 of file rbtree.c.

References rb_delete_node().

641 {
642  rb_delete_node(rb, node);
643 }
static void rb_delete_node(RBTree *rb, RBNode *z)
Definition: rbtree.c:565
static void rb_delete_fixup ( RBTree rb,
RBNode x 
)
static

Definition at line 467 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().

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

566 {
567  RBNode *x,
568  *y;
569 
570  if (!z || z == RBNIL)
571  return;
572 
573  /*
574  * y is the node that will actually be removed from the tree. This will
575  * be z if z has fewer than two children, or the tree successor of z
576  * otherwise.
577  */
578  if (z->left == RBNIL || z->right == RBNIL)
579  {
580  /* y has a RBNIL node as a child */
581  y = z;
582  }
583  else
584  {
585  /* find tree successor */
586  y = z->right;
587  while (y->left != RBNIL)
588  y = y->left;
589  }
590 
591  /* x is y's only child */
592  if (y->left != RBNIL)
593  x = y->left;
594  else
595  x = y->right;
596 
597  /* Remove y from the tree. */
598  x->parent = y->parent;
599  if (y->parent)
600  {
601  if (y == y->parent->left)
602  y->parent->left = x;
603  else
604  y->parent->right = x;
605  }
606  else
607  {
608  rb->root = x;
609  }
610 
611  /*
612  * If we removed the tree successor of z rather than z itself, then move
613  * the data for the removed node to the one we were supposed to remove.
614  */
615  if (y != z)
616  rb_copy_data(rb, z, y);
617 
618  /*
619  * Removing a black node might make some paths from root to leaf contain
620  * fewer black nodes than others, or it might make two red nodes adjacent.
621  */
622  if (y->color == RBBLACK)
623  rb_delete_fixup(rb, x);
624 
625  /* Now we can recycle the y node */
626  if (rb->freefunc)
627  rb->freefunc(y, rb->arg);
628 }
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:135
RBNode * root
Definition: rbtree.c:43
#define RBBLACK
Definition: rbtree.c:35
static void rb_delete_fixup(RBTree *rb, RBNode *x)
Definition: rbtree.c:467
static RBNode* rb_direct_iterator ( RBTreeIterator iter)
static

Definition at line 734 of file rbtree.c.

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

Referenced by rb_begin_iterate().

735 {
736  if (iter->last_visited == NULL)
737  {
738  iter->last_visited = iter->rb->root;
739  return iter->last_visited;
740  }
741 
742  if (iter->last_visited->left != RBNIL)
743  {
744  iter->last_visited = iter->last_visited->left;
745  return iter->last_visited;
746  }
747 
748  do
749  {
750  if (iter->last_visited->right != RBNIL)
751  {
752  iter->last_visited = iter->last_visited->right;
753  break;
754  }
755 
756  /* go up and one step right */
757  for (;;)
758  {
759  RBNode *came_from = iter->last_visited;
760 
761  iter->last_visited = iter->last_visited->parent;
762  if (iter->last_visited == NULL)
763  {
764  iter->is_over = true;
765  break;
766  }
767 
768  if ((iter->last_visited->right != came_from) && (iter->last_visited->right != RBNIL))
769  {
770  iter->last_visited = iter->last_visited->right;
771  return iter->last_visited;
772  }
773  }
774  }
775  while (iter->last_visited != NULL);
776 
777  return iter->last_visited;
778 }
struct RBNode * left
Definition: rbtree.h:26
RBNode * last_visited
Definition: rbtree.h:54
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:56
#define NULL
Definition: c.h:229
RBTree * rb
Definition: rbtree.h:52
RBNode * root
Definition: rbtree.c:43
RBNode* rb_find ( RBTree rb,
const RBNode data 
)

Definition at line 153 of file rbtree.c.

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

154 {
155  RBNode *node = rb->root;
156 
157  while (node != RBNIL)
158  {
159  int cmp = rb->comparator(data, node, rb->arg);
160 
161  if (cmp == 0)
162  return node;
163  else if (cmp < 0)
164  node = node->left;
165  else
166  node = node->right;
167  }
168 
169  return NULL;
170 }
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
#define NULL
Definition: c.h:229
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 399 of file rbtree.c.

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

Referenced by ginInsertBAEntry().

400 {
401  RBNode *current,
402  *parent,
403  *x;
404  int cmp;
405 
406  /* find where node belongs */
407  current = rb->root;
408  parent = NULL;
409  cmp = 0; /* just to prevent compiler warning */
410 
411  while (current != RBNIL)
412  {
413  cmp = rb->comparator(data, current, rb->arg);
414  if (cmp == 0)
415  {
416  /*
417  * Found node with given key. Apply combiner.
418  */
419  rb->combiner(current, data, rb->arg);
420  *isNew = false;
421  return current;
422  }
423  parent = current;
424  current = (cmp < 0) ? current->left : current->right;
425  }
426 
427  /*
428  * Value is not present, so create a new node containing data.
429  */
430  *isNew = true;
431 
432  x = rb->allocfunc(rb->arg);
433 
434  x->color = RBRED;
435 
436  x->left = RBNIL;
437  x->right = RBNIL;
438  x->parent = parent;
439  rb_copy_data(rb, x, data);
440 
441  /* insert node in tree */
442  if (parent)
443  {
444  if (cmp < 0)
445  parent->left = x;
446  else
447  parent->right = x;
448  }
449  else
450  {
451  rb->root = x;
452  }
453 
454  rb_insert_fixup(rb, x);
455 
456  return x;
457 }
struct RBNode * left
Definition: rbtree.h:26
static void rb_insert_fixup(RBTree *rb, RBNode *x)
Definition: rbtree.c:290
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
#define NULL
Definition: c.h:229
static void rb_copy_data(RBTree *rb, RBNode *dest, const RBNode *src)
Definition: rbtree.c:135
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 290 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().

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

Definition at line 781 of file rbtree.c.

References Assert, RBTreeIterator::is_over, RBTreeIterator::last_visited, RBNode::left, RBTreeIterator::next_step, NextStepBegin, NextStepLeft, NextStepRight, NextStepUp, NULL, RBNode::parent, RBTreeIterator::rb, RBNIL, RBNode::right, and RBTree::root.

Referenced by rb_begin_iterate().

782 {
783  RBNode *came_from;
784  RBNode *current;
785 
786  current = iter->last_visited;
787 
788 loop:
789  switch ((InvertedWalkNextStep) iter->next_step)
790  {
791  /* First call, begin from root */
792  case NextStepBegin:
793  current = iter->rb->root;
794  iter->next_step = NextStepLeft;
795  goto loop;
796 
797  case NextStepLeft:
798  while (current->left != RBNIL)
799  current = current->left;
800 
801  iter->next_step = NextStepRight;
802  goto loop;
803 
804  case NextStepRight:
805  if (current->right != RBNIL)
806  {
807  current = current->right;
808  iter->next_step = NextStepLeft;
809  goto loop;
810  }
811  else /* not moved - return current, then go up */
812  iter->next_step = NextStepUp;
813  break;
814 
815  case NextStepUp:
816  came_from = current;
817  current = current->parent;
818  if (current == NULL)
819  {
820  iter->is_over = true;
821  break; /* end of iteration */
822  }
823  else if (came_from == current->right)
824  {
825  /* return current, then continue to go up */
826  break;
827  }
828  else
829  {
830  /* otherwise we came from the left */
831  Assert(came_from == current->left);
832  iter->next_step = NextStepRight;
833  goto loop;
834  }
835  }
836 
837  iter->last_visited = current;
838  return current;
839 }
struct RBNode * left
Definition: rbtree.h:26
RBNode * last_visited
Definition: rbtree.h:54
struct RBNode * right
Definition: rbtree.h:27
char next_step
Definition: rbtree.h:55
struct RBNode * parent
Definition: rbtree.h:28
Definition: rbtree.h:23
#define RBNIL
Definition: rbtree.c:61
bool is_over
Definition: rbtree.h:56
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
RBTree * rb
Definition: rbtree.h:52
RBNode * root
Definition: rbtree.c:43
InvertedWalkNextStep
Definition: rbtree.c:69
RBNode* rb_iterate ( RBTreeIterator iter)

Definition at line 886 of file rbtree.c.

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

Referenced by ginGetBAEntry().

887 {
888  if (iter->is_over)
889  return NULL;
890 
891  return iter->iterate(iter);
892 }
RBNode *(* iterate)(RBTreeIterator *iter)
Definition: rbtree.h:53
bool is_over
Definition: rbtree.h:56
#define NULL
Definition: c.h:229
static RBNode* rb_left_right_iterator ( RBTreeIterator iter)
static

Definition at line 650 of file rbtree.c.

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

Referenced by rb_begin_iterate().

651 {
652  if (iter->last_visited == NULL)
653  {
654  iter->last_visited = iter->rb->root;
655  while (iter->last_visited->left != RBNIL)
656  iter->last_visited = iter->last_visited->left;
657 
658  return iter->last_visited;
659  }
660 
661  if (iter->last_visited->right != RBNIL)
662  {
663  iter->last_visited = iter->last_visited->right;
664  while (iter->last_visited->left != RBNIL)
665  iter->last_visited = iter->last_visited->left;
666 
667  return iter->last_visited;
668  }
669 
670  for (;;)
671  {
672  RBNode *came_from = iter->last_visited;
673 
674  iter->last_visited = iter->last_visited->parent;
675  if (iter->last_visited == NULL)
676  {
677  iter->is_over = true;
678  break;
679  }
680 
681  if (iter->last_visited->left == came_from)
682  break; /* came from left sub-tree, return current
683  * node */
684 
685  /* else - came from right sub-tree, continue to move up */
686  }
687 
688  return iter->last_visited;
689 }
struct RBNode * left
Definition: rbtree.h:26
RBNode * last_visited
Definition: rbtree.h:54
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:56
#define NULL
Definition: c.h:229
RBTree * rb
Definition: rbtree.h:52
RBNode * root
Definition: rbtree.c:43
RBNode* rb_leftmost ( RBTree rb)

Definition at line 181 of file rbtree.c.

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

182 {
183  RBNode *node = rb->root;
184  RBNode *leftmost = rb->root;
185 
186  while (node != RBNIL)
187  {
188  leftmost = node;
189  node = node->left;
190  }
191 
192  if (leftmost != RBNIL)
193  return leftmost;
194 
195  return NULL;
196 }
struct RBNode * left
Definition: rbtree.h:26
Definition: rbtree.h:23
#define RBNIL
Definition: rbtree.c:61
#define NULL
Definition: c.h:229
RBNode * root
Definition: rbtree.c:43
static RBNode* rb_right_left_iterator ( RBTreeIterator iter)
static

Definition at line 692 of file rbtree.c.

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

Referenced by rb_begin_iterate().

693 {
694  if (iter->last_visited == NULL)
695  {
696  iter->last_visited = iter->rb->root;
697  while (iter->last_visited->right != RBNIL)
698  iter->last_visited = iter->last_visited->right;
699 
700  return iter->last_visited;
701  }
702 
703  if (iter->last_visited->left != RBNIL)
704  {
705  iter->last_visited = iter->last_visited->left;
706  while (iter->last_visited->right != RBNIL)
707  iter->last_visited = iter->last_visited->right;
708 
709  return iter->last_visited;
710  }
711 
712  for (;;)
713  {
714  RBNode *came_from = iter->last_visited;
715 
716  iter->last_visited = iter->last_visited->parent;
717  if (iter->last_visited == NULL)
718  {
719  iter->is_over = true;
720  break;
721  }
722 
723  if (iter->last_visited->right == came_from)
724  break; /* came from right sub-tree, return current
725  * node */
726 
727  /* else - came from left sub-tree, continue to move up */
728  }
729 
730  return iter->last_visited;
731 }
struct RBNode * left
Definition: rbtree.h:26
RBNode * last_visited
Definition: rbtree.h:54
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:56
#define NULL
Definition: c.h:229
RBTree * rb
Definition: rbtree.h:52
RBNode * root
Definition: rbtree.c:43
static void rb_rotate_left ( RBTree rb,
RBNode x 
)
static

Definition at line 209 of file rbtree.c.

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

Referenced by rb_delete_fixup(), and rb_insert_fixup().

210 {
211  RBNode *y = x->right;
212 
213  /* establish x->right link */
214  x->right = y->left;
215  if (y->left != RBNIL)
216  y->left->parent = x;
217 
218  /* establish y->parent link */
219  if (y != RBNIL)
220  y->parent = x->parent;
221  if (x->parent)
222  {
223  if (x == x->parent->left)
224  x->parent->left = y;
225  else
226  x->parent->right = y;
227  }
228  else
229  {
230  rb->root = y;
231  }
232 
233  /* link x and y */
234  y->left = x;
235  if (x != RBNIL)
236  x->parent = y;
237 }
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 246 of file rbtree.c.

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

Referenced by rb_delete_fixup(), and rb_insert_fixup().

247 {
248  RBNode *y = x->left;
249 
250  /* establish x->left link */
251  x->left = y->right;
252  if (y->right != RBNIL)
253  y->right->parent = x;
254 
255  /* establish y->parent link */
256  if (y != RBNIL)
257  y->parent = x->parent;
258  if (x->parent)
259  {
260  if (x == x->parent->right)
261  x->parent->right = y;
262  else
263  x->parent->left = y;
264  }
265  else
266  {
267  rb->root = y;
268  }
269 
270  /* link x and y */
271  y->right = x;
272  if (x != RBNIL)
273  x->parent = y;
274 }
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.