PostgreSQL Source Code  git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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_find_great (RBTree *rbt, const RBTNode *data, bool equal_match)
 
RBTNoderbt_find_less (RBTree *rbt, const RBTNode *data, bool equal_match)
 
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

typedef struct RBTNode RBTNode

◆ RBTOrderControl

◆ RBTree

typedef struct RBTree RBTree

Definition at line 1 of file rbtree.h.

◆ RBTreeIterator

Definition at line 1 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:36
@ RightLeftWalk
Definition: rbtree.h:38
@ LeftRightWalk
Definition: rbtree.h:37

Function Documentation

◆ rbt_begin_iterate()

void rbt_begin_iterate ( RBTree rbt,
RBTOrderControl  ctrl,
RBTreeIterator iter 
)

Definition at line 802 of file rbtree.c.

803 {
804  /* Common initialization for all traversal orders */
805  iter->rbt = rbt;
806  iter->last_visited = NULL;
807  iter->is_over = (rbt->root == RBTNIL);
808 
809  switch (ctrl)
810  {
811  case LeftRightWalk: /* visit left, then self, then right */
813  break;
814  case RightLeftWalk: /* visit right, then self, then left */
816  break;
817  default:
818  elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
819  }
820 }
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
static RBTNode * rbt_right_left_iterator(RBTreeIterator *iter)
Definition: rbtree.c:747
#define RBTNIL
Definition: rbtree.c:61
static RBTNode * rbt_left_right_iterator(RBTreeIterator *iter)
Definition: rbtree.c:705
bool is_over
Definition: rbtree.h:53
RBTree * rbt
Definition: rbtree.h:50
RBTNode *(* iterate)(RBTreeIterator *iter)
Definition: rbtree.h:51
RBTNode * last_visited
Definition: rbtree.h:52
RBTNode * root
Definition: rbtree.c:43

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().

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

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 }
#define Assert(condition)
Definition: c.h:863
void * palloc(Size size)
Definition: mcxt.c:1317
void * arg
tree
Definition: radixtree.h:1834
Definition: rbtree.h:24
Definition: rbtree.c:42

References arg, Assert, palloc(), RBTNIL, and tree.

Referenced by create_int_rbtree(), and ginInitBA().

◆ rbt_delete()

void rbt_delete ( RBTree rbt,
RBTNode node 
)

Definition at line 695 of file rbtree.c.

696 {
697  rbt_delete_node(rbt, node);
698 }
static void rbt_delete_node(RBTree *rbt, RBTNode *z)
Definition: rbtree.c:619

References rbt_delete_node().

Referenced by testdelete(), and testfindltgt().

◆ rbt_find()

RBTNode* rbt_find ( RBTree rbt,
const RBTNode data 
)

Definition at line 145 of file rbtree.c.

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 }
const void * data
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:743
struct RBTNode * left
Definition: rbtree.h:26
struct RBTNode * right
Definition: rbtree.h:27
void * arg
Definition: rbtree.c:54
rbt_comparator comparator
Definition: rbtree.c:49

References RBTree::arg, cmp(), RBTree::comparator, data, RBTNode::left, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by testdelete(), and testfind().

◆ rbt_find_great()

RBTNode* rbt_find_great ( RBTree rbt,
const RBTNode data,
bool  equal_match 
)

Definition at line 172 of file rbtree.c.

173 {
174  RBTNode *node = rbt->root;
175  RBTNode *greater = NULL;
176 
177  while (node != RBTNIL)
178  {
179  int cmp = rbt->comparator(data, node, rbt->arg);
180 
181  if (equal_match && cmp == 0)
182  return node;
183  else if (cmp < 0)
184  {
185  greater = node;
186  node = node->left;
187  }
188  else
189  node = node->right;
190  }
191 
192  return greater;
193 }

References RBTree::arg, cmp(), RBTree::comparator, data, RBTNode::left, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by testfindltgt().

◆ rbt_find_less()

RBTNode* rbt_find_less ( RBTree rbt,
const RBTNode data,
bool  equal_match 
)

Definition at line 203 of file rbtree.c.

204 {
205  RBTNode *node = rbt->root;
206  RBTNode *lesser = NULL;
207 
208  while (node != RBTNIL)
209  {
210  int cmp = rbt->comparator(data, node, rbt->arg);
211 
212  if (equal_match && cmp == 0)
213  return node;
214  else if (cmp > 0)
215  {
216  lesser = node;
217  node = node->right;
218  }
219  else
220  node = node->left;
221  }
222 
223  return lesser;
224 }

References RBTree::arg, cmp(), RBTree::comparator, data, RBTNode::left, RBTNIL, RBTNode::right, and RBTree::root.

Referenced by testfindltgt().

◆ rbt_insert()

RBTNode* rbt_insert ( RBTree rbt,
const RBTNode data,
bool isNew 
)

Definition at line 453 of file rbtree.c.

454 {
455  RBTNode *current,
456  *parent,
457  *x;
458  int cmp;
459 
460  /* find where node belongs */
461  current = rbt->root;
462  parent = NULL;
463  cmp = 0; /* just to prevent compiler warning */
464 
465  while (current != RBTNIL)
466  {
467  cmp = rbt->comparator(data, current, rbt->arg);
468  if (cmp == 0)
469  {
470  /*
471  * Found node with given key. Apply combiner.
472  */
473  rbt->combiner(current, data, rbt->arg);
474  *isNew = false;
475  return current;
476  }
477  parent = current;
478  current = (cmp < 0) ? current->left : current->right;
479  }
480 
481  /*
482  * Value is not present, so create a new node containing data.
483  */
484  *isNew = true;
485 
486  x = rbt->allocfunc(rbt->arg);
487 
488  x->color = RBTRED;
489 
490  x->left = RBTNIL;
491  x->right = RBTNIL;
492  x->parent = parent;
493  rbt_copy_data(rbt, x, data);
494 
495  /* insert node in tree */
496  if (parent)
497  {
498  if (cmp < 0)
499  parent->left = x;
500  else
501  parent->right = x;
502  }
503  else
504  {
505  rbt->root = x;
506  }
507 
508  rbt_insert_fixup(rbt, x);
509 
510  return x;
511 }
int x
Definition: isn.c:70
static void rbt_insert_fixup(RBTree *rbt, RBTNode *x)
Definition: rbtree.c:344
static void rbt_copy_data(RBTree *rbt, RBTNode *dest, const RBTNode *src)
Definition: rbtree.c:127
#define RBTRED
Definition: rbtree.c:36
rbt_allocfunc allocfunc
Definition: rbtree.c:51
rbt_combiner combiner
Definition: rbtree.c:50

References RBTree::allocfunc, RBTree::arg, cmp(), RBTree::combiner, RBTree::comparator, data, RBTNode::left, rbt_copy_data(), rbt_insert_fixup(), RBTNIL, RBTRED, RBTNode::right, RBTree::root, and x.

Referenced by ginInsertBAEntry(), and rbt_populate().

◆ rbt_iterate()

RBTNode* rbt_iterate ( RBTreeIterator iter)

Definition at line 826 of file rbtree.c.

827 {
828  if (iter->is_over)
829  return NULL;
830 
831  return iter->iterate(iter);
832 }

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

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

◆ rbt_leftmost()

RBTNode* rbt_leftmost ( RBTree rbt)

Definition at line 235 of file rbtree.c.

236 {
237  RBTNode *node = rbt->root;
238  RBTNode *leftmost = rbt->root;
239 
240  while (node != RBTNIL)
241  {
242  leftmost = node;
243  node = node->left;
244  }
245 
246  if (leftmost != RBTNIL)
247  return leftmost;
248 
249  return NULL;
250 }

References RBTNode::left, RBTNIL, and RBTree::root.

Referenced by testdelete(), and testleftmost().