PostgreSQL Source Code: src/include/lib/rbtree.h File Reference (original) (raw)
Go to the source code of this file.
| 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) |
| 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) |
◆ rbt_allocfunc
◆ rbt_combiner
◆ rbt_comparator
◆ rbt_freefunc
◆ RBTNode
◆ RBTOrderControl
◆ RBTreeIterator
◆ RBTOrderControl
| Enumerator |
|---|
| LeftRightWalk |
| RightLeftWalk |
Definition at line 35 of file rbtree.h.
◆ rbt_begin_iterate()
Definition at line 802 of file rbtree.c.
803{
804
805 iter->rbt = rbt;
808
809 switch (ctrl)
810 {
811 case LeftRightWalk:
813 break;
814 case RightLeftWalk:
816 break;
817 default:
818 elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
819 }
820}
static RBTNode * rbt_right_left_iterator(RBTreeIterator *iter)
static RBTNode * rbt_left_right_iterator(RBTreeIterator *iter)
RBTNode *(* iterate)(RBTreeIterator *iter)
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()
◆ rbt_delete()
◆ rbt_find()
Definition at line 145 of file rbtree.c.
146{
148
149 while (node != RBTNIL)
150 {
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}
static int cmp(const chr *x, const chr *y, size_t len)
rbt_comparator comparator
References RBTree::arg, cmp(), RBTree::comparator, data, RBTNode::left, RBTNIL, RBTNode::right, and RBTree::root.
Referenced by testdelete(), and testfind().
◆ rbt_find_great()
◆ rbt_find_less()
◆ rbt_insert()
Definition at line 453 of file rbtree.c.
454{
456 *parent,
457 *x;
459
460
461 current = rbt->root;
462 parent = NULL;
463 cmp = 0;
464
465 while (current != RBTNIL)
466 {
468 if (cmp == 0)
469 {
470
471
472
474 *isNew = false;
475 return current;
476 }
477 parent = current;
478 current = (cmp < 0) ? current->left : current->right;
479 }
480
481
482
483
484 *isNew = true;
485
487
489
492 x->parent = parent;
494
495
496 if (parent)
497 {
498 if (cmp < 0)
500 else
502 }
503 else
504 {
506 }
507
509
510 return x;
511}
static void rbt_insert_fixup(RBTree *rbt, RBTNode *x)
static void rbt_copy_data(RBTree *rbt, RBTNode *dest, const RBTNode *src)
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().