PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
rbtree.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  RBNode
 
struct  RBTreeIterator
 

Typedefs

typedef struct RBNode RBNode
 
typedef struct RBTree RBTree
 
typedef enum RBOrderControl RBOrderControl
 
typedef struct RBTreeIterator RBTreeIterator
 
typedef int(* rb_comparator )(const RBNode *a, const RBNode *b, void *arg)
 
typedef void(* rb_combiner )(RBNode *existing, const RBNode *newdata, void *arg)
 
typedef RBNode *(* rb_allocfunc )(void *arg)
 
typedef void(* rb_freefunc )(RBNode *x, void *arg)
 

Enumerations

enum  RBOrderControl { LeftRightWalk, RightLeftWalk, DirectWalk, InvertedWalk }
 

Functions

RBTreerb_create (Size node_size, rb_comparator comparator, rb_combiner combiner, rb_allocfunc allocfunc, rb_freefunc freefunc, void *arg)
 
RBNoderb_find (RBTree *rb, const RBNode *data)
 
RBNoderb_leftmost (RBTree *rb)
 
RBNoderb_insert (RBTree *rb, const RBNode *data, bool *isNew)
 
void rb_delete (RBTree *rb, RBNode *node)
 
void rb_begin_iterate (RBTree *rb, RBOrderControl ctrl, RBTreeIterator *iter)
 
RBNoderb_iterate (RBTreeIterator *iter)
 

Typedef Documentation

typedef RBNode*(* rb_allocfunc)(void *arg)

Definition at line 62 of file rbtree.h.

typedef void(* rb_combiner)(RBNode *existing, const RBNode *newdata, void *arg)

Definition at line 61 of file rbtree.h.

typedef int(* rb_comparator)(const RBNode *a, const RBNode *b, void *arg)

Definition at line 60 of file rbtree.h.

typedef void(* rb_freefunc)(RBNode *x, void *arg)

Definition at line 63 of file rbtree.h.

Definition at line 32 of file rbtree.h.

Definition at line 48 of file rbtree.h.

Enumeration Type Documentation

Enumerator
LeftRightWalk 
RightLeftWalk 
DirectWalk 
InvertedWalk 

Definition at line 35 of file rbtree.h.

36 {
37  LeftRightWalk, /* inorder: left child, node, right child */
38  RightLeftWalk, /* reverse inorder: right, node, left */
39  DirectWalk, /* preorder: node, left child, right child */
40  InvertedWalk /* postorder: left child, right child, node */
RBOrderControl
Definition: rbtree.h:35

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