diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/backend/access/gin/ginbulk.c | 32 | ||||
| -rw-r--r-- | src/backend/lib/rbtree.c | 349 | ||||
| -rw-r--r-- | src/include/access/gin_private.h | 2 | ||||
| -rw-r--r-- | src/include/lib/rbtree.h | 58 | ||||
| -rw-r--r-- | src/test/modules/test_rbtree/test_rbtree.c | 90 |
5 files changed, 267 insertions, 264 deletions
diff --git a/src/backend/access/gin/ginbulk.c b/src/backend/access/gin/ginbulk.c index 989c2a0c028..f2fbe6fa3f3 100644 --- a/src/backend/access/gin/ginbulk.c +++ b/src/backend/access/gin/ginbulk.c @@ -27,7 +27,7 @@ /* Combiner function for rbtree.c */ static void -ginCombineData(RBNode *existing, const RBNode *newdata, void *arg) +ginCombineData(RBTNode *existing, const RBTNode *newdata, void *arg) { GinEntryAccumulator *eo = (GinEntryAccumulator *) existing; const GinEntryAccumulator *en = (const GinEntryAccumulator *) newdata; @@ -69,7 +69,7 @@ ginCombineData(RBNode *existing, const RBNode *newdata, void *arg) /* Comparator function for rbtree.c */ static int -cmpEntryAccumulator(const RBNode *a, const RBNode *b, void *arg) +cmpEntryAccumulator(const RBTNode *a, const RBTNode *b, void *arg) { const GinEntryAccumulator *ea = (const GinEntryAccumulator *) a; const GinEntryAccumulator *eb = (const GinEntryAccumulator *) b; @@ -81,7 +81,7 @@ cmpEntryAccumulator(const RBNode *a, const RBNode *b, void *arg) } /* Allocator function for rbtree.c */ -static RBNode * +static RBTNode * ginAllocEntryAccumulator(void *arg) { BuildAccumulator *accum = (BuildAccumulator *) arg; @@ -89,7 +89,7 @@ ginAllocEntryAccumulator(void *arg) /* * Allocate memory by rather big chunks to decrease overhead. We have no - * need to reclaim RBNodes individually, so this costs nothing. + * need to reclaim RBTNodes individually, so this costs nothing. */ if (accum->entryallocator == NULL || accum->eas_used >= DEF_NENTRY) { @@ -98,11 +98,11 @@ ginAllocEntryAccumulator(void *arg) accum->eas_used = 0; } - /* Allocate new RBNode from current chunk */ + /* Allocate new RBTNode from current chunk */ ea = accum->entryallocator + accum->eas_used; accum->eas_used++; - return (RBNode *) ea; + return (RBTNode *) ea; } void @@ -112,12 +112,12 @@ ginInitBA(BuildAccumulator *accum) accum->allocatedMemory = 0; accum->entryallocator = NULL; accum->eas_used = 0; - accum->tree = rb_create(sizeof(GinEntryAccumulator), - cmpEntryAccumulator, - ginCombineData, - ginAllocEntryAccumulator, - NULL, /* no freefunc needed */ - (void *) accum); + accum->tree = rbt_create(sizeof(GinEntryAccumulator), + cmpEntryAccumulator, + ginCombineData, + ginAllocEntryAccumulator, + NULL, /* no freefunc needed */ + (void *) accum); } /* @@ -163,8 +163,8 @@ ginInsertBAEntry(BuildAccumulator *accum, /* temporarily set up single-entry itempointer list */ eatmp.list = heapptr; - ea = (GinEntryAccumulator *) rb_insert(accum->tree, (RBNode *) &eatmp, - &isNew); + ea = (GinEntryAccumulator *) rbt_insert(accum->tree, (RBTNode *) &eatmp, + &isNew); if (isNew) { @@ -256,7 +256,7 @@ qsortCompareItemPointers(const void *a, const void *b) void ginBeginBAScan(BuildAccumulator *accum) { - rb_begin_iterate(accum->tree, LeftRightWalk, &accum->tree_walk); + rbt_begin_iterate(accum->tree, LeftRightWalk, &accum->tree_walk); } /* @@ -272,7 +272,7 @@ ginGetBAEntry(BuildAccumulator *accum, GinEntryAccumulator *entry; ItemPointerData *list; - entry = (GinEntryAccumulator *) rb_iterate(&accum->tree_walk); + entry = (GinEntryAccumulator *) rbt_iterate(&accum->tree_walk); if (entry == NULL) return NULL; /* no more entries */ diff --git a/src/backend/lib/rbtree.c b/src/backend/lib/rbtree.c index a43d5938d59..c35928daad3 100644 --- a/src/backend/lib/rbtree.c +++ b/src/backend/lib/rbtree.c @@ -30,26 +30,26 @@ /* - * Colors of nodes (values of RBNode.color) + * Colors of nodes (values of RBTNode.color) */ -#define RBBLACK (0) -#define RBRED (1) +#define RBTBLACK (0) +#define RBTRED (1) /* * RBTree control structure */ struct RBTree { - RBNode *root; /* root node, or RBNIL if tree is empty */ + RBTNode *root; /* root node, or RBTNIL if tree is empty */ - /* Remaining fields are constant after rb_create */ + /* Remaining fields are constant after rbt_create */ Size node_size; /* actual size of tree nodes */ /* The caller-supplied manipulation functions */ - rb_comparator comparator; - rb_combiner combiner; - rb_allocfunc allocfunc; - rb_freefunc freefunc; + rbt_comparator comparator; + rbt_combiner combiner; + rbt_allocfunc allocfunc; + rbt_freefunc freefunc; /* Passthrough arg passed to all manipulation functions */ void *arg; }; @@ -58,28 +58,31 @@ struct RBTree * all leafs are sentinels, use customized NIL name to prevent * collision with system-wide constant NIL which is actually NULL */ -#define RBNIL (&sentinel) +#define RBTNIL (&sentinel) -static RBNode sentinel = {RBBLACK, RBNIL, RBNIL, NULL}; +static RBTNode sentinel = +{ + RBTBLACK, RBTNIL, RBTNIL, NULL +}; /* - * rb_create: create an empty RBTree + * rbt_create: create an empty RBTree * * Arguments are: - * node_size: actual size of tree nodes (> sizeof(RBNode)) + * node_size: actual size of tree nodes (> sizeof(RBTNode)) * The manipulation functions: - * comparator: compare two RBNodes for less/equal/greater + * comparator: compare two RBTNodes for less/equal/greater * combiner: merge an existing tree entry with a new one - * allocfunc: allocate a new RBNode - * freefunc: free an old RBNode + * allocfunc: allocate a new RBTNode + * freefunc: free an old RBTNode * arg: passthrough pointer that will be passed to the manipulation functions * * Note that the combiner's righthand argument will be a "proposed" tree node, - * ie the input to rb_insert, in which the RBNode fields themselves aren't + * ie the input to rbt_insert, in which the RBTNode fields themselves aren't * valid. Similarly, either input to the comparator may be a "proposed" node. * This shouldn't matter since the functions aren't supposed to look at the - * RBNode fields, only the extra fields of the struct the RBNode is embedded + * RBTNode fields, only the extra fields of the struct the RBTNode is embedded * in. * * The freefunc should just be pfree or equivalent; it should NOT attempt @@ -96,18 +99,18 @@ static RBNode sentinel = {RBBLACK, RBNIL, RBNIL, NULL}; * the RBTree node if you feel the urge. */ RBTree * -rb_create(Size node_size, - rb_comparator comparator, - rb_combiner combiner, - rb_allocfunc allocfunc, - rb_freefunc freefunc, - void *arg) +rbt_create(Size node_size, + rbt_comparator comparator, + rbt_combiner combiner, + rbt_allocfunc allocfunc, + rbt_freefunc freefunc, + void *arg) { RBTree *tree = (RBTree *) palloc(sizeof(RBTree)); - Assert(node_size > sizeof(RBNode)); + Assert(node_size > sizeof(RBTNode)); - tree->root = RBNIL; + tree->root = RBTNIL; tree->node_size = node_size; tree->comparator = comparator; tree->combiner = combiner; @@ -119,11 +122,11 @@ rb_create(Size node_size, return tree; } -/* Copy the additional data fields from one RBNode to another */ +/* Copy the additional data fields from one RBTNode to another */ static inline void -rb_copy_data(RBTree *rb, RBNode *dest, const RBNode *src) +rbt_copy_data(RBTree *rbt, RBTNode *dest, const RBTNode *src) { - memcpy(dest + 1, src + 1, rb->node_size - sizeof(RBNode)); + memcpy(dest + 1, src + 1, rbt->node_size - sizeof(RBTNode)); } /********************************************************************** @@ -131,21 +134,21 @@ rb_copy_data(RBTree *rb, RBNode *dest, const RBNode *src) **********************************************************************/ /* - * rb_find: search for a value in an RBTree + * rbt_find: search for a value in an RBTree * - * data represents the value to try to find. Its RBNode fields need not + * data represents the value to try to find. Its RBTNode fields need not * be valid, it's the extra data in the larger struct that is of interest. * * Returns the matching tree entry, or NULL if no match is found. */ -RBNode * -rb_find(RBTree *rb, const RBNode *data) +RBTNode * +rbt_find(RBTree *rbt, const RBTNode *data) { - RBNode *node = rb->root; + RBTNode *node = rbt->root; - while (node != RBNIL) + while (node != RBTNIL) { - int cmp = rb->comparator(data, node, rb->arg); + int cmp = rbt->comparator(data, node, rbt->arg); if (cmp == 0) return node; @@ -159,26 +162,26 @@ rb_find(RBTree *rb, const RBNode *data) } /* - * rb_leftmost: fetch the leftmost (smallest-valued) tree node. + * rbt_leftmost: fetch the leftmost (smallest-valued) tree node. * Returns NULL if tree is empty. * * Note: in the original implementation this included an unlink step, but - * that's a bit awkward. Just call rb_delete on the result if that's what + * that's a bit awkward. Just call rbt_delete on the result if that's what * you want. */ -RBNode * -rb_leftmost(RBTree *rb) +RBTNode * +rbt_leftmost(RBTree *rbt) { - RBNode *node = rb->root; - RBNode *leftmost = rb->root; + RBTNode *node = rbt->root; + RBTNode *leftmost = rbt->root; - while (node != RBNIL) + while (node != RBTNIL) { leftmost = node; node = node->left; } - if (leftmost != RBNIL) + if (leftmost != RBTNIL) return leftmost; return NULL; @@ -195,17 +198,17 @@ rb_leftmost(RBTree *rb) * child of that node. */ static void -rb_rotate_left(RBTree *rb, RBNode *x) +rbt_rotate_left(RBTree *rbt, RBTNode *x) { - RBNode *y = x->right; + RBTNode *y = x->right; /* establish x->right link */ x->right = y->left; - if (y->left != RBNIL) + if (y->left != RBTNIL) y->left->parent = x; /* establish y->parent link */ - if (y != RBNIL) + if (y != RBTNIL) y->parent = x->parent; if (x->parent) { @@ -216,12 +219,12 @@ rb_rotate_left(RBTree *rb, RBNode *x) } else { - rb->root = y; + rbt->root = y; } /* link x and y */ y->left = x; - if (x != RBNIL) + if (x != RBTNIL) x->parent = y; } @@ -232,17 +235,17 @@ rb_rotate_left(RBTree *rb, RBNode *x) * child of that node. */ static void -rb_rotate_right(RBTree *rb, RBNode *x) +rbt_rotate_right(RBTree *rbt, RBTNode *x) { - RBNode *y = x->left; + RBTNode *y = x->left; /* establish x->left link */ x->left = y->right; - if (y->right != RBNIL) + if (y->right != RBTNIL) y->right->parent = x; /* establish y->parent link */ - if (y != RBNIL) + if (y != RBTNIL) y->parent = x->parent; if (x->parent) { @@ -253,12 +256,12 @@ rb_rotate_right(RBTree *rb, RBNode *x) } else { - rb->root = y; + rbt->root = y; } /* link x and y */ y->right = x; - if (x != RBNIL) + if (x != RBTNIL) x->parent = y; } @@ -276,13 +279,13 @@ rb_rotate_right(RBTree *rb, RBNode *x) * the invariant that every leaf has equal black-height.) */ static void -rb_insert_fixup(RBTree *rb, RBNode *x) +rbt_insert_fixup(RBTree *rbt, RBTNode *x) { /* * x is always a red node. Initially, it is the newly inserted node. Each * iteration of this loop moves it higher up in the tree. */ - while (x != rb->root && x->parent->color == RBRED) + while (x != rbt->root && x->parent->color == RBTRED) { /* * x and x->parent are both red. Fix depends on whether x->parent is @@ -302,60 +305,60 @@ rb_insert_fixup(RBTree *rb, RBNode *x) */ if (x->parent == x->parent->parent->left) { - RBNode *y = x->parent->parent->right; + RBTNode *y = x->parent->parent->right; - if (y->color == RBRED) + if (y->color == RBTRED) { - /* uncle is RBRED */ - x->parent->color = RBBLACK; - y->color = RBBLACK; - x->parent->parent->color = RBRED; + /* uncle is RBTRED */ + x->parent->color = RBTBLACK; + y->color = RBTBLACK; + x->parent->parent->color = RBTRED; x = x->parent->parent; } else { - /* uncle is RBBLACK */ + /* uncle is RBTBLACK */ if (x == x->parent->right) { /* make x a left child */ x = x->parent; - rb_rotate_left(rb, x); + rbt_rotate_left(rbt, x); } /* recolor and rotate */ - x->parent->color = RBBLACK; - x->parent->parent->color = RBRED; + x->parent->color = RBTBLACK; + x->parent->parent->color = RBTRED; - rb_rotate_right(rb, x->parent->parent); + rbt_rotate_right(rbt, x->parent->parent); } } else { /* mirror image of above code */ - RBNode *y = x->parent->parent->left; + RBTNode *y = x->parent->parent->left; - if (y->color == RBRED) + if (y->color == RBTRED) { - /* uncle is RBRED */ - x->parent->color = RBBLACK; - y->color = RBBLACK; - x->parent->parent->color = RBRED; + /* uncle is RBTRED */ + x->parent->color = RBTBLACK; + y->color = RBTBLACK; + x->parent->parent->color = RBTRED; x = x->parent->parent; } else { - /* uncle is RBBLACK */ + /* uncle is RBTBLACK */ if (x == x->parent->left) { x = x->parent; - rb_rotate_right(rb, x); + rbt_rotate_right(rbt, x); } - x->parent->color = RBBLACK; - x->parent->parent->color = RBRED; + x->parent->color = RBTBLACK; + x->parent->parent->color = RBTRED; - rb_rotate_left(rb, x->parent->parent); + rbt_rotate_left(rbt, x->parent->parent); } } } @@ -364,13 +367,13 @@ rb_insert_fixup(RBTree *rb, RBNode *x) * The root may already have been black; if not, the black-height of every * node in the tree increases by one. */ - rb->root->color = RBBLACK; + rbt->root->color = RBTBLACK; } /* - * rb_insert: insert a new value into the tree. + * rbt_insert: insert a new value into the tree. * - * data represents the value to insert. Its RBNode fields need not + * data represents the value to insert. Its RBTNode fields need not * be valid, it's the extra data in the larger struct that is of interest. * * If the value represented by "data" is not present in the tree, then @@ -384,28 +387,28 @@ rb_insert_fixup(RBTree *rb, RBNode *x) * "data" is unmodified in either case; it's typically just a local * variable in the caller. */ -RBNode * -rb_insert(RBTree *rb, const RBNode *data, bool *isNew) +RBTNode * +rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew) { - RBNode *current, + RBTNode *current, *parent, *x; int cmp; /* find where node belongs */ - current = rb->root; + current = rbt->root; parent = NULL; cmp = 0; /* just to prevent compiler warning */ - while (current != RBNIL) + while (current != RBTNIL) { - cmp = rb->comparator(data, current, rb->arg); + cmp = rbt->comparator(data, current, rbt->arg); if (cmp == 0) { /* * Found node with given key. Apply combiner. */ - rb->combiner(current, data, rb->arg); + rbt->combiner(current, data, rbt->arg); *isNew = false; return current; } @@ -418,14 +421,14 @@ rb_insert(RBTree *rb, const RBNode *data, bool *isNew) */ *isNew = true; - x = rb->allocfunc(rb->arg); + x = rbt->allocfunc(rbt->arg); - x->color = RBRED; + x->color = RBTRED; - x->left = RBNIL; - x->right = RBNIL; + x->left = RBTNIL; + x->right = RBTNIL; x->parent = parent; - rb_copy_data(rb, x, data); + rbt_copy_data(rbt, x, data); /* insert node in tree */ if (parent) @@ -437,10 +440,10 @@ rb_insert(RBTree *rb, const RBNode *data, bool *isNew) } else { - rb->root = x; + rbt->root = x; } - rb_insert_fixup(rb, x); + rbt_insert_fixup(rbt, x); return x; } @@ -453,14 +456,14 @@ rb_insert(RBTree *rb, const RBNode *data, bool *isNew) * Maintain Red-Black tree balance after deleting a black node. */ static void -rb_delete_fixup(RBTree *rb, RBNode *x) +rbt_delete_fixup(RBTree *rbt, RBTNode *x) { /* * x is always a black node. Initially, it is the former child of the * deleted node. Each iteration of this loop moves it higher up in the * tree. */ - while (x != rb->root && x->color == RBBLACK) + while (x != rbt->root && x->color == RBTBLACK) { /* * Left and right cases are symmetric. Any nodes that are children of @@ -471,93 +474,93 @@ rb_delete_fixup(RBTree *rb, RBNode *x) */ if (x == x->parent->left) { - RBNode *w = x->parent->right; + RBTNode *w = x->parent->right; - if (w->color == RBRED) + if (w->color == RBTRED) { - w->color = RBBLACK; - x->parent->color = RBRED; + w->color = RBTBLACK; + x->parent->color = RBTRED; - rb_rotate_left(rb, x->parent); + rbt_rotate_left(rbt, x->parent); w = x->parent->right; } - if (w->left->color == RBBLACK && w->right->color == RBBLACK) + if (w->left->color == RBTBLACK && w->right->color == RBTBLACK) { - w->color = RBRED; + w->color = RBTRED; x = x->parent; } else { - if (w->right->color == RBBLACK) + if (w->right->color == RBTBLACK) { - w->left->color = RBBLACK; - w->color = RBRED; + w->left->color = RBTBLACK; + w->color = RBTRED; - rb_rotate_right(rb, w); + rbt_rotate_right(rbt, w); w = x->parent->right; } w->color = x->parent->color; - x->parent->color = RBBLACK; - w->right->color = RBBLACK; + x->parent->color = RBTBLACK; + w->right->color = RBTBLACK; - rb_rotate_left(rb, x->parent); - x = rb->root; /* Arrange for loop to terminate. */ + rbt_rotate_left(rbt, x->parent); + x = rbt->root; /* Arrange for loop to terminate. */ } } else { - RBNode *w = x->parent->left; + RBTNode *w = x->parent->left; - if (w->color == RBRED) + if (w->color == RBTRED) { - w->color = RBBLACK; - x->parent->color = RBRED; + w->color = RBTBLACK; + x->parent->color = RBTRED; - rb_rotate_right(rb, x->parent); + rbt_rotate_right(rbt, x->parent); w = x->parent->left; } - if (w->right->color == RBBLACK && w->left->color == RBBLACK) + if (w->right->color == RBTBLACK && w->left->color == RBTBLACK) { - w->color = RBRED; + w->color = RBTRED; x = x->parent; } else { - if (w->left->color == RBBLACK) + if (w->left->color == RBTBLACK) { - w->right->color = RBBLACK; - w->color = RBRED; + w->right->color = RBTBLACK; + w->color = RBTRED; - rb_rotate_left(rb, w); + rbt_rotate_left(rbt, w); w = x->parent->left; } w->color = x->parent->color; - x->parent->color = RBBLACK; - w->left->color = RBBLACK; + x->parent->color = RBTBLACK; + w->left->color = RBTBLACK; - rb_rotate_right(rb, x->parent); - x = rb->root; /* Arrange for loop to terminate. */ + rbt_rotate_right(rbt, x->parent); + x = rbt->root; /* Arrange for loop to terminate. */ } } } - x->color = RBBLACK; + x->color = RBTBLACK; } /* * Delete node z from tree. */ static void -rb_delete_node(RBTree *rb, RBNode *z) +rbt_delete_node(RBTree *rbt, RBTNode *z) { - RBNode *x, + RBTNode *x, *y; /* This is just paranoia: we should only get called on a valid node */ - if (!z || z == RBNIL) + if (!z || z == RBTNIL) return; /* @@ -565,21 +568,21 @@ rb_delete_node(RBTree *rb, RBNode *z) * be z if z has fewer than two children, or the tree successor of z * otherwise. */ - if (z->left == RBNIL || z->right == RBNIL) + if (z->left == RBTNIL || z->right == RBTNIL) { - /* y has a RBNIL node as a child */ + /* y has a RBTNIL node as a child */ y = z; } else { /* find tree successor */ y = z->right; - while (y->left != RBNIL) + while (y->left != RBTNIL) y = y->left; } /* x is y's only child */ - if (y->left != RBNIL) + if (y->left != RBTNIL) x = y->left; else x = y->right; @@ -595,7 +598,7 @@ rb_delete_node(RBTree *rb, RBNode *z) } else { - rb->root = x; + rbt->root = x; } /* @@ -603,55 +606,55 @@ rb_delete_node(RBTree *rb, RBNode *z) * the data for the removed node to the one we were supposed to remove. */ if (y != z) - rb_copy_data(rb, z, y); + rbt_copy_data(rbt, z, y); /* * Removing a black node might make some paths from root to leaf contain * fewer black nodes than others, or it might make two red nodes adjacent. */ - if (y->color == RBBLACK) - rb_delete_fixup(rb, x); + if (y->color == RBTBLACK) + rbt_delete_fixup(rbt, x); /* Now we can recycle the y node */ - if (rb->freefunc) - rb->freefunc(y, rb->arg); + if (rbt->freefunc) + rbt->freefunc(y, rbt->arg); } /* - * rb_delete: remove the given tree entry + * rbt_delete: remove the given tree entry * - * "node" must have previously been found via rb_find or rb_leftmost. + * "node" must have previously been found via rbt_find or rbt_leftmost. * It is caller's responsibility to free any subsidiary data attached - * to the node before calling rb_delete. (Do *not* try to push that + * to the node before calling rbt_delete. (Do *not* try to push that * responsibility off to the freefunc, as some other physical node * may be the one actually freed!) */ void -rb_delete(RBTree *rb, RBNode *node) +rbt_delete(RBTree *rbt, RBTNode *node) { - rb_delete_node(rb, node); + rbt_delete_node(rbt, node); } /********************************************************************** * Traverse * **********************************************************************/ -static RBNode * -rb_left_right_iterator(RBTreeIterator *iter) +static RBTNode * +rbt_left_right_iterator(RBTreeIterator *iter) { if (iter->last_visited == NULL) { - iter->last_visited = iter->rb->root; - while (iter->last_visited->left != RBNIL) + iter->last_visited = iter->rbt->root; + while (iter->last_visited->left != RBTNIL) iter->last_visited = iter->last_visited->left; return iter->last_visited; } - if (iter->last_visited->right != RBNIL) + if (iter->last_visited->right != RBTNIL) { iter->last_visited = iter->last_visited->right; - while (iter->last_visited->left != RBNIL) + while (iter->last_visited->left != RBTNIL) iter->last_visited = iter->last_visited->left; return iter->last_visited; @@ -659,7 +662,7 @@ rb_left_right_iterator(RBTreeIterator *iter) for (;;) { - RBNode *came_from = iter->last_visited; + RBTNode *came_from = iter->last_visited; iter->last_visited = iter->last_visited->parent; if (iter->last_visited == NULL) @@ -678,22 +681,22 @@ rb_left_right_iterator(RBTreeIterator *iter) return iter->last_visited; } -static RBNode * -rb_right_left_iterator(RBTreeIterator *iter) +static RBTNode * +rbt_right_left_iterator(RBTreeIterator *iter) { if (iter->last_visited == NULL) { - iter->last_visited = iter->rb->root; - while (iter->last_visited->right != RBNIL) + iter->last_visited = iter->rbt->root; + while (iter->last_visited->right != RBTNIL) iter->last_visited = iter->last_visited->right; return iter->last_visited; } - if (iter->last_visited->left != RBNIL) + if (iter->last_visited->left != RBTNIL) { iter->last_visited = iter->last_visited->left; - while (iter->last_visited->right != RBNIL) + while (iter->last_visited->right != RBTNIL) iter->last_visited = iter->last_visited->right; return iter->last_visited; @@ -701,7 +704,7 @@ rb_right_left_iterator(RBTreeIterator *iter) for (;;) { - RBNode *came_from = iter->last_visited; + RBTNode *came_from = iter->last_visited; iter->last_visited = iter->last_visited->parent; if (iter->last_visited == NULL) @@ -721,33 +724,33 @@ rb_right_left_iterator(RBTreeIterator *iter) } /* - * rb_begin_iterate: prepare to traverse the tree in any of several orders + * rbt_begin_iterate: prepare to traverse the tree in any of several orders * - * After calling rb_begin_iterate, call rb_iterate repeatedly until it + * After calling rbt_begin_iterate, call rbt_iterate repeatedly until it * returns NULL or the traversal stops being of interest. * * If the tree is changed during traversal, results of further calls to - * rb_iterate are unspecified. Multiple concurrent iterators on the same + * rbt_iterate are unspecified. Multiple concurrent iterators on the same * tree are allowed. * * The iterator state is stored in the 'iter' struct. The caller should * treat it as an opaque struct. */ void -rb_begin_iterate(RBTree *rb, RBOrderControl ctrl, RBTreeIterator *iter) +rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter) { /* Common initialization for all traversal orders */ - iter->rb = rb; + iter->rbt = rbt; iter->last_visited = NULL; - iter->is_over = (rb->root == RBNIL); + iter->is_over = (rbt->root == RBTNIL); switch (ctrl) { case LeftRightWalk: /* visit left, then self, then right */ - iter->iterate = rb_left_right_iterator; + iter->iterate = rbt_left_right_iterator; break; case RightLeftWalk: /* visit right, then self, then left */ - iter->iterate = rb_right_left_iterator; + iter->iterate = rbt_right_left_iterator; break; default: elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl); @@ -755,10 +758,10 @@ rb_begin_iterate(RBTree *rb, RBOrderControl ctrl, RBTreeIterator *iter) } /* - * rb_iterate: return the next node in traversal order, or NULL if no more + * rbt_iterate: return the next node in traversal order, or NULL if no more */ -RBNode * -rb_iterate(RBTreeIterator *iter) +RBTNode * +rbt_iterate(RBTreeIterator *iter) { if (iter->is_over) return NULL; diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h index f0baac65869..81bf8734ce3 100644 --- a/src/include/access/gin_private.h +++ b/src/include/access/gin_private.h @@ -391,7 +391,7 @@ extern bool ginvalidate(Oid opclassoid); /* ginbulk.c */ typedef struct GinEntryAccumulator { - RBNode rbnode; + RBTNode rbtnode; Datum key; GinNullCategory category; OffsetNumber attnum; diff --git a/src/include/lib/rbtree.h b/src/include/lib/rbtree.h index c46db47a750..51e4ed321cb 100644 --- a/src/include/lib/rbtree.h +++ b/src/include/lib/rbtree.h @@ -14,29 +14,29 @@ #define RBTREE_H /* - * RBNode is intended to be used as the first field of a larger struct, + * RBTNode is intended to be used as the first field of a larger struct, * whose additional fields carry whatever payload data the caller needs * for a tree entry. (The total size of that larger struct is passed to - * rb_create.) RBNode is declared here to support this usage, but + * rbt_create.) RBTNode is declared here to support this usage, but * callers must treat it as an opaque struct. */ -typedef struct RBNode +typedef struct RBTNode { char color; /* node's current color, red or black */ - struct RBNode *left; /* left child, or RBNIL if none */ - struct RBNode *right; /* right child, or RBNIL if none */ - struct RBNode *parent; /* parent, or NULL (not RBNIL!) if none */ -} RBNode; + struct RBTNode *left; /* left child, or RBTNIL if none */ + struct RBTNode *right; /* right child, or RBTNIL if none */ + struct RBTNode *parent; /* parent, or NULL (not RBTNIL!) if none */ +} RBTNode; /* Opaque struct representing a whole tree */ typedef struct RBTree RBTree; /* Available tree iteration orderings */ -typedef enum RBOrderControl +typedef enum RBTOrderControl { LeftRightWalk, /* inorder: left child, node, right child */ RightLeftWalk /* reverse inorder: right, node, left */ -} RBOrderControl; +} RBTOrderControl; /* * RBTreeIterator holds state while traversing a tree. This is declared @@ -47,33 +47,33 @@ typedef struct RBTreeIterator RBTreeIterator; struct RBTreeIterator { - RBTree *rb; - RBNode *(*iterate) (RBTreeIterator *iter); - RBNode *last_visited; + RBTree *rbt; + RBTNode *(*iterate) (RBTreeIterator *iter); + RBTNode *last_visited; bool is_over; }; /* Support functions to be provided by caller */ -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); +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); -extern RBTree *rb_create(Size node_size, - rb_comparator comparator, - rb_combiner combiner, - rb_allocfunc allocfunc, - rb_freefunc freefunc, - void *arg); +extern RBTree *rbt_create(Size node_size, + rbt_comparator comparator, + rbt_combiner combiner, + rbt_allocfunc allocfunc, + rbt_freefunc freefunc, + void *arg); -extern RBNode *rb_find(RBTree *rb, const RBNode *data); -extern RBNode *rb_leftmost(RBTree *rb); +extern RBTNode *rbt_find(RBTree *rbt, const RBTNode *data); +extern RBTNode *rbt_leftmost(RBTree *rbt); -extern RBNode *rb_insert(RBTree *rb, const RBNode *data, bool *isNew); -extern void rb_delete(RBTree *rb, RBNode *node); +extern RBTNode *rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew); +extern void rbt_delete(RBTree *rbt, RBTNode *node); -extern void rb_begin_iterate(RBTree *rb, RBOrderControl ctrl, - RBTreeIterator *iter); -extern RBNode *rb_iterate(RBTreeIterator *iter); +extern void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, + RBTreeIterator *iter); +extern RBTNode *rbt_iterate(RBTreeIterator *iter); #endif /* RBTREE_H */ diff --git a/src/test/modules/test_rbtree/test_rbtree.c b/src/test/modules/test_rbtree/test_rbtree.c index 1274b9995d8..e12284cd8ca 100644 --- a/src/test/modules/test_rbtree/test_rbtree.c +++ b/src/test/modules/test_rbtree/test_rbtree.c @@ -25,7 +25,7 @@ PG_MODULE_MAGIC; */ typedef struct IntRBTreeNode { - RBNode rbnode; + RBTNode rbtnode; int key; } IntRBTreeNode; @@ -35,7 +35,7 @@ typedef struct IntRBTreeNode * since none of our test keys are negative. */ static int -irb_cmp(const RBNode *a, const RBNode *b, void *arg) +irbt_cmp(const RBTNode *a, const RBTNode *b, void *arg) { const IntRBTreeNode *ea = (const IntRBTreeNode *) a; const IntRBTreeNode *eb = (const IntRBTreeNode *) b; @@ -48,7 +48,7 @@ irb_cmp(const RBNode *a, const RBNode *b, void *arg) * try to combine unequal keys. */ static void -irb_combine(RBNode *existing, const RBNode *newdata, void *arg) +irbt_combine(RBTNode *existing, const RBTNode *newdata, void *arg) { const IntRBTreeNode *eexist = (const IntRBTreeNode *) existing; const IntRBTreeNode *enew = (const IntRBTreeNode *) newdata; @@ -59,15 +59,15 @@ irb_combine(RBNode *existing, const RBNode *newdata, void *arg) } /* Node allocator */ -static RBNode * -irb_alloc(void *arg) +static RBTNode * +irbt_alloc(void *arg) { - return (RBNode *) palloc(sizeof(IntRBTreeNode)); + return (RBTNode *) palloc(sizeof(IntRBTreeNode)); } /* Node freer */ static void -irb_free(RBNode *node, void *arg) +irbt_free(RBTNode *node, void *arg) { pfree(node); } @@ -78,12 +78,12 @@ irb_free(RBNode *node, void *arg) static RBTree * create_int_rbtree(void) { - return rb_create(sizeof(IntRBTreeNode), - irb_cmp, - irb_combine, - irb_alloc, - irb_free, - NULL); + return rbt_create(sizeof(IntRBTreeNode), + irbt_cmp, + irbt_combine, + irbt_alloc, + irbt_free, + NULL); } /* @@ -123,7 +123,7 @@ GetPermutation(int size) * 0, step, 2*step, 3*step, ..., inserting them in random order */ static void -rb_populate(RBTree *tree, int size, int step) +rbt_populate(RBTree *tree, int size, int step) { int *permutation = GetPermutation(size); IntRBTreeNode node; @@ -134,9 +134,9 @@ rb_populate(RBTree *tree, int size, int step) for (i = 0; i < size; i++) { node.key = step * permutation[i]; - rb_insert(tree, (RBNode *) &node, &isNew); + rbt_insert(tree, (RBTNode *) &node, &isNew); if (!isNew) - elog(ERROR, "unexpected !isNew result from rb_insert"); + elog(ERROR, "unexpected !isNew result from rbt_insert"); } /* @@ -146,9 +146,9 @@ rb_populate(RBTree *tree, int size, int step) if (size > 0) { node.key = step * permutation[0]; - rb_insert(tree, (RBNode *) &node, &isNew); + rbt_insert(tree, (RBTNode *) &node, &isNew); if (isNew) - elog(ERROR, "unexpected isNew result from rb_insert"); + elog(ERROR, "unexpected isNew result from rbt_insert"); } pfree(permutation); @@ -169,17 +169,17 @@ testleftright(int size) int count = 0; /* check iteration over empty tree */ - rb_begin_iterate(tree, LeftRightWalk, &iter); - if (rb_iterate(&iter) != NULL) + rbt_begin_iterate(tree, LeftRightWalk, &iter); + if (rbt_iterate(&iter) != NULL) elog(ERROR, "left-right walk over empty tree produced an element"); /* fill tree with consecutive natural numbers */ - rb_populate(tree, size, 1); + rbt_populate(tree, size, 1); /* iterate over the tree */ - rb_begin_iterate(tree, LeftRightWalk, &iter); + rbt_begin_iterate(tree, LeftRightWalk, &iter); - while ((node = (IntRBTreeNode *) rb_iterate(&iter)) != NULL) + while ((node = (IntRBTreeNode *) rbt_iterate(&iter)) != NULL) { /* check that order is increasing */ if (node->key <= lastKey) @@ -209,17 +209,17 @@ testrightleft(int size) int count = 0; /* check iteration over empty tree */ - rb_begin_iterate(tree, RightLeftWalk, &iter); - if (rb_iterate(&iter) != NULL) + rbt_begin_iterate(tree, RightLeftWalk, &iter); + if (rbt_iterate(&iter) != NULL) elog(ERROR, "right-left walk over empty tree produced an element"); /* fill tree with consecutive natural numbers */ - rb_populate(tree, size, 1); + rbt_populate(tree, size, 1); /* iterate over the tree */ - rb_begin_iterate(tree, RightLeftWalk, &iter); + rbt_begin_iterate(tree, RightLeftWalk, &iter); - while ((node = (IntRBTreeNode *) rb_iterate(&iter)) != NULL) + while ((node = (IntRBTreeNode *) rbt_iterate(&iter)) != NULL) { /* check that order is decreasing */ if (node->key >= lastKey) @@ -235,7 +235,7 @@ testrightleft(int size) } /* - * Check the correctness of the rb_find operation by searching for + * Check the correctness of the rbt_find operation by searching for * both elements we inserted and elements we didn't. */ static void @@ -245,7 +245,7 @@ testfind(int size) int i; /* Insert even integers from 0 to 2 * (size-1) */ - rb_populate(tree, size, 2); + rbt_populate(tree, size, 2); /* Check that all inserted elements can be found */ for (i = 0; i < size; i++) @@ -254,7 +254,7 @@ testfind(int size) IntRBTreeNode *resultNode; node.key = 2 * i; - resultNode = (IntRBTreeNode *) rb_find(tree, (RBNode *) &node); + resultNode = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &node); if (resultNode == NULL) elog(ERROR, "inserted element was not found"); if (node.key != resultNode->key) @@ -271,14 +271,14 @@ testfind(int size) IntRBTreeNode *resultNode; node.key = i; - resultNode = (IntRBTreeNode *) rb_find(tree, (RBNode *) &node); + resultNode = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &node); if (resultNode != NULL) elog(ERROR, "not-inserted element was found"); } } /* - * Check the correctness of the rb_leftmost operation. + * Check the correctness of the rbt_leftmost operation. * This operation should always return the smallest element of the tree. */ static void @@ -288,20 +288,20 @@ testleftmost(int size) IntRBTreeNode *result; /* Check that empty tree has no leftmost element */ - if (rb_leftmost(tree) != NULL) + if (rbt_leftmost(tree) != NULL) elog(ERROR, "leftmost node of empty tree is not NULL"); /* fill tree with consecutive natural numbers */ - rb_populate(tree, size, 1); + rbt_populate(tree, size, 1); /* Check that leftmost element is the smallest one */ - result = (IntRBTreeNode *) rb_leftmost(tree); + result = (IntRBTreeNode *) rbt_leftmost(tree); if (result == NULL || result->key != 0) - elog(ERROR, "rb_leftmost gave wrong result"); + elog(ERROR, "rbt_leftmost gave wrong result"); } /* - * Check the correctness of the rb_delete operation. + * Check the correctness of the rbt_delete operation. */ static void testdelete(int size, int delsize) @@ -312,7 +312,7 @@ testdelete(int size, int delsize) int i; /* fill tree with consecutive natural numbers */ - rb_populate(tree, size, 1); + rbt_populate(tree, size, 1); /* Choose unique ids to delete */ deleteIds = (int *) palloc(delsize * sizeof(int)); @@ -336,11 +336,11 @@ testdelete(int size, int delsize) find.key = deleteIds[i]; /* Locate the node to be deleted */ - node = (IntRBTreeNode *) rb_find(tree, (RBNode *) &find); + node = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &find); if (node == NULL || node->key != deleteIds[i]) elog(ERROR, "expected element was not found during deleting"); /* Delete it */ - rb_delete(tree, (RBNode *) node); + rbt_delete(tree, (RBTNode *) node); } /* Check that deleted elements are deleted */ @@ -350,7 +350,7 @@ testdelete(int size, int delsize) IntRBTreeNode *result; node.key = i; - result = (IntRBTreeNode *) rb_find(tree, (RBNode *) &node); + result = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &node); if (chosen[i]) { /* Deleted element should be absent */ @@ -375,15 +375,15 @@ testdelete(int size, int delsize) continue; find.key = i; /* Locate the node to be deleted */ - node = (IntRBTreeNode *) rb_find(tree, (RBNode *) &find); + node = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &find); if (node == NULL || node->key != i) elog(ERROR, "expected element was not found during deleting"); /* Delete it */ - rb_delete(tree, (RBNode *) node); + rbt_delete(tree, (RBTNode *) node); } /* Tree should now be empty */ - if (rb_leftmost(tree) != NULL) + if (rbt_leftmost(tree) != NULL) elog(ERROR, "deleting all elements failed"); pfree(deleteIds); |