diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/backend/access/gin/ginbulk.c | 32 | ||||
| -rw-r--r-- | src/backend/lib/rbtree.c | 378 | ||||
| -rw-r--r-- | src/include/access/gin_private.h | 2 | ||||
| -rw-r--r-- | src/include/lib/rbtree.h | 58 |
4 files changed, 235 insertions, 235 deletions
diff --git a/src/backend/access/gin/ginbulk.c b/src/backend/access/gin/ginbulk.c index 4ff149e59af..82e282ae2c3 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); } /* @@ -162,8 +162,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) { @@ -255,7 +255,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); } /* @@ -271,7 +271,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 3d80090a8cd..8a40840edb2 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,9 +58,9 @@ 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}; /* * Values used in the RBTreeIterator.next_state field, with an @@ -75,22 +75,22 @@ typedef enum InvertedWalkNextStep } InvertedWalkNextStep; /* - * 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 @@ -107,18 +107,18 @@ typedef enum InvertedWalkNextStep * 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; @@ -130,11 +130,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)); } /********************************************************************** @@ -142,21 +142,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; @@ -170,26 +170,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; @@ -206,17 +206,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) { @@ -227,12 +227,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; } @@ -243,17 +243,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) { @@ -264,12 +264,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; } @@ -287,13 +287,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 @@ -313,60 +313,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); } } } @@ -375,13 +375,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 @@ -395,28 +395,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; } @@ -429,14 +429,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) @@ -448,10 +448,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; } @@ -464,14 +464,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 @@ -482,92 +482,92 @@ 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; - if (!z || z == RBNIL) + if (!z || z == RBTNIL) return; /* @@ -575,21 +575,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; @@ -605,7 +605,7 @@ rb_delete_node(RBTree *rb, RBNode *z) } else { - rb->root = x; + rbt->root = x; } /* @@ -613,55 +613,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; @@ -669,7 +669,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) @@ -688,22 +688,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; @@ -711,7 +711,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) @@ -730,16 +730,16 @@ rb_right_left_iterator(RBTreeIterator *iter) return iter->last_visited; } -static RBNode * -rb_direct_iterator(RBTreeIterator *iter) +static RBTNode * +rbt_direct_iterator(RBTreeIterator *iter) { if (iter->last_visited == NULL) { - iter->last_visited = iter->rb->root; + iter->last_visited = iter->rbt->root; return iter->last_visited; } - if (iter->last_visited->left != RBNIL) + if (iter->last_visited->left != RBTNIL) { iter->last_visited = iter->last_visited->left; return iter->last_visited; @@ -747,7 +747,7 @@ rb_direct_iterator(RBTreeIterator *iter) do { - if (iter->last_visited->right != RBNIL) + if (iter->last_visited->right != RBTNIL) { iter->last_visited = iter->last_visited->right; break; @@ -756,7 +756,7 @@ rb_direct_iterator(RBTreeIterator *iter) /* go up and one step right */ 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) @@ -765,7 +765,7 @@ rb_direct_iterator(RBTreeIterator *iter) break; } - if ((iter->last_visited->right != came_from) && (iter->last_visited->right != RBNIL)) + if ((iter->last_visited->right != came_from) && (iter->last_visited->right != RBTNIL)) { iter->last_visited = iter->last_visited->right; return iter->last_visited; @@ -777,11 +777,11 @@ rb_direct_iterator(RBTreeIterator *iter) return iter->last_visited; } -static RBNode * -rb_inverted_iterator(RBTreeIterator *iter) +static RBTNode * +rbt_inverted_iterator(RBTreeIterator *iter) { - RBNode *came_from; - RBNode *current; + RBTNode *came_from; + RBTNode *current; current = iter->last_visited; @@ -790,19 +790,19 @@ loop: { /* First call, begin from root */ case NextStepBegin: - current = iter->rb->root; + current = iter->rbt->root; iter->next_step = NextStepLeft; goto loop; case NextStepLeft: - while (current->left != RBNIL) + while (current->left != RBTNIL) current = current->left; iter->next_step = NextStepRight; goto loop; case NextStepRight: - if (current->right != RBNIL) + if (current->right != RBTNIL) { current = current->right; iter->next_step = NextStepLeft; @@ -839,39 +839,39 @@ loop: } /* - * 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 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; case DirectWalk: /* visit self, then left, then right */ - iter->iterate = rb_direct_iterator; + iter->iterate = rbt_direct_iterator; break; case InvertedWalk: /* visit left, then right, then self */ - iter->iterate = rb_inverted_iterator; + iter->iterate = rbt_inverted_iterator; iter->next_step = NextStepBegin; break; default: @@ -880,10 +880,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 f57ba5594c2..f57f6f55a95 100644 --- a/src/include/access/gin_private.h +++ b/src/include/access/gin_private.h @@ -392,7 +392,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 a7183bb0b48..bc32cf66c15 100644 --- a/src/include/lib/rbtree.h +++ b/src/include/lib/rbtree.h @@ -14,31 +14,31 @@ #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 */ DirectWalk, /* preorder: node, left child, right child */ InvertedWalk /* postorder: left child, right child, node */ -} RBOrderControl; +} RBTOrderControl; /* * RBTreeIterator holds state while traversing a tree. This is declared @@ -49,34 +49,34 @@ typedef struct RBTreeIterator RBTreeIterator; struct RBTreeIterator { - RBTree *rb; - RBNode *(*iterate) (RBTreeIterator *iter); - RBNode *last_visited; + RBTree *rbt; + RBTNode *(*iterate) (RBTreeIterator *iter); + RBTNode *last_visited; char next_step; 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 */ |