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  RBTNode
 
struct  RBTreeIterator
 

Typedefs

typedef struct RBTNode RBTNode
 
typedef struct RBTree RBTree
 
typedef enum RBTOrderControl RBTOrderControl
 
typedef struct RBTreeIterator RBTreeIterator
 
typedef int(* rbt_comparator) (const RBTNode *a, const RBTNode *b, void *arg)
 
typedef void(* rbt_combiner) (RBTNode *existing, const RBTNode *newdata, void *arg)
 
typedef RBTNode *(* rbt_allocfunc) (void *arg)
 
typedef void(* rbt_freefunc) (RBTNode *x, void *arg)
 

Enumerations

enum  RBTOrderControl { LeftRightWalk, RightLeftWalk }
 

Functions

RBTreerbt_create (Size node_size, rbt_comparator comparator, rbt_combiner combiner, rbt_allocfunc allocfunc, rbt_freefunc freefunc, void *arg)
 
RBTNoderbt_find (RBTree *rbt, const RBTNode *data)
 
RBTNoderbt_leftmost (RBTree *rbt)
 
RBTNoderbt_insert (RBTree *rbt, const RBTNode *data, bool *isNew)
 
void rbt_delete (RBTree *rbt, RBTNode *node)
 
void rbt_begin_iterate (RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
 
RBTNoderbt_iterate (RBTreeIterator *iter)
 

Typedef Documentation

◆ rbt_allocfunc

typedef RBTNode*(* rbt_allocfunc) (void *arg)

Definition at line 59 of file rbtree.h.

◆ rbt_combiner

typedef void(* rbt_combiner) (RBTNode *existing, const RBTNode *newdata, void *arg)

Definition at line 58 of file rbtree.h.

◆ rbt_comparator

typedef int(* rbt_comparator) (const RBTNode *a, const RBTNode *b, void *arg)

Definition at line 57 of file rbtree.h.

◆ rbt_freefunc

typedef void(* rbt_freefunc) (RBTNode *x, void *arg)

Definition at line 60 of file rbtree.h.

◆ RBTNode

◆ RBTOrderControl

◆ RBTree

Definition at line 32 of file rbtree.h.

◆ RBTreeIterator

Definition at line 46 of file rbtree.h.

Enumeration Type Documentation

◆ RBTOrderControl

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 */
RBTOrderControl
Definition: rbtree.h:35

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_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:924
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_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_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_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