PostgreSQL Source Code git master
Data Structures | Typedefs | Enumerations | Functions
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

RBTree *  rbt_create (Size node_size, rbt_comparator comparator, rbt_combiner combiner, rbt_allocfunc allocfunc, rbt_freefunc freefunc, void *arg)
 
RBTNode *  rbt_find (RBTree *rbt, const RBTNode *data)
 
RBTNode *  rbt_find_great (RBTree *rbt, const RBTNode *data, bool equal_match)
 
RBTNode *  rbt_find_less (RBTree *rbt, const RBTNode *data, bool equal_match)
 
RBTNode *  rbt_leftmost (RBTree *rbt)
 
RBTNode *  rbt_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)
 
RBTNode *  rbt_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

typedef enum RBTOrderControl RBTOrderControl

◆ RBTree

typedef struct RBTree RBTree

Definition at line 32 of file rbtree.h.

◆ RBTreeIterator

typedef struct RBTreeIterator RBTreeIterator

Definition at line 46 of file rbtree.h.

Enumeration Type Documentation

◆ RBTOrderControl

enum 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:226
static RBTNode * rbt_right_left_iterator(RBTreeIterator *iter)
Definition: rbtree.c:747
static RBTNode * rbt_left_right_iterator(RBTreeIterator *iter)
Definition: rbtree.c:705
#define RBTNIL
Definition: rbtree.c:61
RBTNode *(* iterate)(RBTreeIterator *iter)
Definition: rbtree.h:51
bool is_over
Definition: rbtree.h:53
RBTree * rbt
Definition: rbtree.h:50
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}
Assert(PointerIsAligned(start, uint64))
void * palloc(Size size)
Definition: mcxt.c:1365
void * arg
tree
Definition: radixtree.h:1828
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}
x
int x
Definition: isn.c:75
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().

AltStyle によって変換されたページ (->オリジナル) /