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

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

◆ rb_allocfunc

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

Definition at line 59 of file rbtree.h.

◆ rb_combiner

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

Definition at line 58 of file rbtree.h.

◆ rb_comparator

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

Definition at line 57 of file rbtree.h.

◆ rb_freefunc

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

Definition at line 60 of file rbtree.h.

◆ RBNode

◆ RBOrderControl

◆ RBTree

Definition at line 32 of file rbtree.h.

◆ RBTreeIterator

Definition at line 46 of file rbtree.h.

Enumeration Type Documentation

◆ RBOrderControl

Enumerator
LeftRightWalk 
RightLeftWalk 

Definition at line 35 of file rbtree.h.

36 {
37  LeftRightWalk, /* inorder: left child, node, right child */
38  RightLeftWalk /* reverse inorder: right, node, left */
RBOrderControl
Definition: rbtree.h:35

Function Documentation

◆ rb_begin_iterate()

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
#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
RBNode *(* iterate)(RBTreeIterator *iter)
Definition: rbtree.h:51
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

◆ rb_create()

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, 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:670
RBNode * root
Definition: rbtree.c:43
void * palloc(Size size)
Definition: mcxt.c:848
Definition: rbtree.c:41
void * arg

◆ rb_delete()

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

◆ rb_find()

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

◆ rb_insert()

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

◆ rb_iterate()

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 }
bool is_over
Definition: rbtree.h:53
RBNode *(* iterate)(RBTreeIterator *iter)
Definition: rbtree.h:51

◆ rb_leftmost()

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