> > It seems clear to me that the existing arrangement is hazardous for
> > any RBTree that hasn't got exactly one consumer. I think
> > Aleksander's plan to decouple the iteration state is probably a good
> > one (NB: I've not read the patch, so this is not an endorsement of
> > details). I'd go so far as to say that we should remove the old API
> > as being dangerous, rather than preserve it on
> > backwards-compatibility grounds. We make bigger changes than that in
> > internal APIs all the time.
>
> Glad to hear it! I would like to propose a patch that removes the old
> API. I have a few questions though.
>
> Would you like it to be a separate patch, or all-in-one patch is fine
> in this case? I also would like to include unit/property-based tests in
> this (these) patch (patches). However as I understand there are
> currently no unit tests in PostgreSQL at all, only integration/system
> tests. Any advice how to do it better?
OK, here is a patch. I think we could call it a _replacement_ of an old API, so
there is probably no need in two separate patches. I still don't know how to
include unit test and whether they should be included at all. Thus for now
unit/property-based tests could be found only on GitHub [1].
As usual, if you have any questions, suggestions or notes regarding this patch,
please let me know.
[1] https://github.com/afiskon/c-algorithms/tree/master/test
--
Best regards,
Aleksander Alekseev
diff --git a/src/backend/access/gin/ginbulk.c b/src/backend/access/gin/ginbulk.c
index d6422ea..eac76c4 100644
--- a/src/backend/access/gin/ginbulk.c
+++ b/src/backend/access/gin/ginbulk.c
@@ -255,7 +255,7 @@ qsortCompareItemPointers(const void *a, const void *b)
void
ginBeginBAScan(BuildAccumulator *accum)
{
- rb_begin_iterate(accum->tree, LeftRightWalk);
+ rb_begin_left_right_walk(accum->tree, &accum->tree_walk);
}
/*
@@ -271,7 +271,7 @@ ginGetBAEntry(BuildAccumulator *accum,
GinEntryAccumulator *entry;
ItemPointerData *list;
- entry = (GinEntryAccumulator *) rb_iterate(accum->tree);
+ entry = (GinEntryAccumulator *) rb_left_right_walk(&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 4fa8a1d..4368492 100644
--- a/src/backend/lib/rbtree.c
+++ b/src/backend/lib/rbtree.c
@@ -28,18 +28,6 @@
#include "lib/rbtree.h"
-
-/*
- * Values of RBNode.iteratorState
- *
- * Note that iteratorState has an undefined value except in nodes that are
- * currently being visited by an active iteration.
- */
-#define InitialState (0)
-#define FirstStepDone (1)
-#define SecondStepDone (2)
-#define ThirdStepDone (3)
-
/*
* Colors of nodes (values of RBNode.color)
*/
@@ -53,10 +41,6 @@ struct RBTree
{
RBNode *root; /* root node, or RBNIL if tree is empty */
- /* Iteration state */
- RBNode *cur; /* current iteration node */
- RBNode *(*iterate) (RBTree *rb);
-
/* Remaining fields are constant after rb_create */
Size node_size; /* actual size of tree nodes */
@@ -75,7 +59,7 @@ struct RBTree
*/
#define RBNIL (&sentinel)
-static RBNode sentinel = {InitialState, RBBLACK, RBNIL, RBNIL, NULL};
+static RBNode sentinel = {RBBLACK, RBNIL, RBNIL, NULL};
/*
@@ -123,8 +107,6 @@ rb_create(Size node_size,
Assert(node_size > sizeof(RBNode));
tree->root = RBNIL;
- tree->cur = RBNIL;
- tree->iterate = NULL;
tree->node_size = node_size;
tree->comparator = comparator;
tree->combiner = combiner;
@@ -201,6 +183,28 @@ rb_leftmost(RBTree *rb)
return NULL;
}
+/*
+ * rb_rightmost: fetch the rightmost (highest-valued) tree node.
+ * Returns NULL if tree is empty.
+ */
+RBNode *
+rb_rightmost(RBTree *rb)
+{
+ RBNode *node = rb->root;
+ RBNode *rightmost = rb->root;
+
+ while (node != RBNIL)
+ {
+ rightmost = node;
+ node = node->right;
+ }
+
+ if (rightmost != RBNIL)
+ return rightmost;
+
+ return NULL;
+}
+
/**********************************************************************
* Insertion *
**********************************************************************/
@@ -437,7 +441,6 @@ rb_insert(RBTree *rb, const RBNode *data, bool *isNew)
x = rb->allocfunc (rb->arg);
- x->iteratorState = InitialState;
x->color = RBRED;
x->left = RBNIL;
@@ -654,220 +657,276 @@ rb_delete(RBTree *rb, RBNode *node)
**********************************************************************/
/*
- * The iterator routines were originally coded in tail-recursion style,
- * which is nice to look at, but is trouble if your compiler isn't smart
- * enough to optimize it. Now we just use looping.
+ * Begin left right walk.
+ */
+void
+rb_begin_left_right_walk(RBTree *rb, RBTreeLeftRightWalk * lrw)
+{
+ lrw->rb = rb;
+ lrw->last_visited = NULL;
+ lrw->is_over = (lrw->rb->root == RBNIL);
+}
+
+/*
+ * Left right walk: get next node. Returns NULL if there is none.
*/
-#define descend(next_node) \
- do { \
- (next_node)->iteratorState = InitialState; \
- node = rb->cur = (next_node); \
- goto restart; \
- } while (0)
-
-#define ascend(next_node) \
- do { \
- node = rb->cur = (next_node); \
- goto restart; \
- } while (0)
-
-
-static RBNode *
-rb_left_right_iterator(RBTree *rb)
+RBNode *
+rb_left_right_walk(RBTreeLeftRightWalk * lrw)
{
- RBNode *node = rb->cur;
+ if (lrw->is_over)
+ return NULL;
-restart:
- switch (node->iteratorState)
+ if (lrw->last_visited == NULL)
{
- case InitialState:
- if (node->left != RBNIL)
- {
- node->iteratorState = FirstStepDone;
- descend(node->left);
- }
- /* FALL THROUGH */
- case FirstStepDone:
- node->iteratorState = SecondStepDone;
- return node;
- case SecondStepDone:
- if (node->right != RBNIL)
- {
- node->iteratorState = ThirdStepDone;
- descend(node->right);
- }
- /* FALL THROUGH */
- case ThirdStepDone:
- if (node->parent)
- ascend(node->parent);
- break;
- default:
- elog(ERROR, "unrecognized rbtree node state: %d",
- node->iteratorState);
+ lrw->last_visited = lrw->rb->root;
+ while (lrw->last_visited->left != RBNIL)
+ lrw->last_visited = lrw->last_visited->left;
+
+ return lrw->last_visited;
}
- return NULL;
-}
+ if (lrw->last_visited->right != RBNIL)
+ {
+ lrw->last_visited = lrw->last_visited->right;
+ while (lrw->last_visited->left != RBNIL)
+ lrw->last_visited = lrw->last_visited->left;
-static RBNode *
-rb_right_left_iterator(RBTree *rb)
-{
- RBNode *node = rb->cur;
+ return lrw->last_visited;
+ }
-restart:
- switch (node->iteratorState)
+ for (;;)
{
- case InitialState:
- if (node->right != RBNIL)
- {
- node->iteratorState = FirstStepDone;
- descend(node->right);
- }
- /* FALL THROUGH */
- case FirstStepDone:
- node->iteratorState = SecondStepDone;
- return node;
- case SecondStepDone:
- if (node->left != RBNIL)
- {
- node->iteratorState = ThirdStepDone;
- descend(node->left);
- }
- /* FALL THROUGH */
- case ThirdStepDone:
- if (node->parent)
- ascend(node->parent);
+ RBNode *came_from = lrw->last_visited;
+
+ lrw->last_visited = lrw->last_visited->parent;
+ if (lrw->last_visited == NULL)
+ {
+ lrw->is_over = true;
break;
- default:
- elog(ERROR, "unrecognized rbtree node state: %d",
- node->iteratorState);
+ }
+
+ if (lrw->last_visited->left == came_from)
+ break; /* came from left sub-tree, return current
+ * node */
+
+ /* else - came from right sub-tree, continue to move up */
}
- return NULL;
+ return lrw->last_visited;
+}
+
+/*
+ * Begin right left walk.
+ */
+void
+rb_begin_right_left_walk(RBTree *rb, RBTreeRightLeftWalk * rlw)
+{
+ rlw->rb = rb;
+ rlw->last_visited = NULL;
+ rlw->is_over = (rlw->rb->root == RBNIL);
}
-static RBNode *
-rb_direct_iterator(RBTree *rb)
+/*
+ * Right left walk: get next node. Returns NULL if there is none.
+ */
+RBNode *
+rb_right_left_walk(RBTreeRightLeftWalk * rlw)
{
- RBNode *node = rb->cur;
+ if (rlw->is_over)
+ return NULL;
-restart:
- switch (node->iteratorState)
+ if (rlw->last_visited == NULL)
{
- case InitialState:
- node->iteratorState = FirstStepDone;
- return node;
- case FirstStepDone:
- if (node->left != RBNIL)
- {
- node->iteratorState = SecondStepDone;
- descend(node->left);
- }
- /* FALL THROUGH */
- case SecondStepDone:
- if (node->right != RBNIL)
- {
- node->iteratorState = ThirdStepDone;
- descend(node->right);
- }
- /* FALL THROUGH */
- case ThirdStepDone:
- if (node->parent)
- ascend(node->parent);
- break;
- default:
- elog(ERROR, "unrecognized rbtree node state: %d",
- node->iteratorState);
+ rlw->last_visited = rlw->rb->root;
+ while (rlw->last_visited->right != RBNIL)
+ rlw->last_visited = rlw->last_visited->right;
+
+ return rlw->last_visited;
}
- return NULL;
-}
+ if (rlw->last_visited->left != RBNIL)
+ {
+ rlw->last_visited = rlw->last_visited->left;
+ while (rlw->last_visited->right != RBNIL)
+ rlw->last_visited = rlw->last_visited->right;
-static RBNode *
-rb_inverted_iterator(RBTree *rb)
-{
- RBNode *node = rb->cur;
+ return rlw->last_visited;
+ }
-restart:
- switch (node->iteratorState)
+ for (;;)
{
- case InitialState:
- if (node->left != RBNIL)
- {
- node->iteratorState = FirstStepDone;
- descend(node->left);
- }
- /* FALL THROUGH */
- case FirstStepDone:
- if (node->right != RBNIL)
- {
- node->iteratorState = SecondStepDone;
- descend(node->right);
- }
- /* FALL THROUGH */
- case SecondStepDone:
- node->iteratorState = ThirdStepDone;
- return node;
- case ThirdStepDone:
- if (node->parent)
- ascend(node->parent);
+ RBNode *came_from = rlw->last_visited;
+
+ rlw->last_visited = rlw->last_visited->parent;
+ if (rlw->last_visited == NULL)
+ {
+ rlw->is_over = true;
break;
- default:
- elog(ERROR, "unrecognized rbtree node state: %d",
- node->iteratorState);
+ }
+
+ if (rlw->last_visited->right == came_from)
+ break; /* came from right sub-tree, return current
+ * node */
+
+ /* else - came from left sub-tree, continue to move up */
}
- return NULL;
+ return rlw->last_visited;
}
/*
- * rb_begin_iterate: prepare to traverse the tree in any of several orders
- *
- * After calling rb_begin_iterate, call rb_iterate repeatedly until it
- * returns NULL or the traversal stops being of interest.
+ * Begin direct walk (a.k.a pre-order traversal).
*
- * If the tree is changed during traversal, results of further calls to
- * rb_iterate are unspecified.
+ * Pre-order traversal while duplicating nodes and edges can make a complete
+ * duplicate of a binary tree. It can also be used to make a prefix expression
+ * (Polish notation) from expression trees: traverse the expression tree
+ * pre-orderly.
*
- * Note: this used to return a separately palloc'd iterator control struct,
- * but that's a bit pointless since the data structure is incapable of
- * supporting multiple concurrent traversals. Now we just keep the state
- * in RBTree.
+ * https://en.wikipedia.org/wiki/Tree_traversal#Applications
*/
void
-rb_begin_iterate(RBTree *rb, RBOrderControl ctrl)
+rb_begin_direct_walk(RBTree *rb, RBTreeDirectWalk * dw)
+{
+ dw->rb = rb;
+ dw->last_visited = NULL;
+ dw->is_over = (dw->rb->root == RBNIL);
+}
+
+/*
+ * Direct walk: get next node. Returns NULL if there is none.
+ */
+RBNode *
+rb_direct_walk(RBTreeDirectWalk * dw)
{
- rb->cur = rb->root;
- if (rb->cur != RBNIL)
- rb->cur->iteratorState = InitialState;
+ if (dw->is_over)
+ return NULL;
- switch (ctrl)
+ if (dw->last_visited == NULL)
{
- case LeftRightWalk: /* visit left, then self, then right */
- rb->iterate = rb_left_right_iterator;
- break;
- case RightLeftWalk: /* visit right, then self, then left */
- rb->iterate = rb_right_left_iterator;
- break;
- case DirectWalk: /* visit self, then left, then right */
- rb->iterate = rb_direct_iterator;
- break;
- case InvertedWalk: /* visit left, then right, then self */
- rb->iterate = rb_inverted_iterator;
+ dw->last_visited = dw->rb->root;
+ return dw->last_visited;
+ }
+
+ if (dw->last_visited->left != RBNIL)
+ {
+ dw->last_visited = dw->last_visited->left;
+ return dw->last_visited;
+ }
+
+ do
+ {
+ if (dw->last_visited->right != RBNIL)
+ {
+ dw->last_visited = dw->last_visited->right;
break;
- default:
- elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
+ }
+
+ /* go up and one step right */
+ for (;;)
+ {
+ RBNode *came_from = dw->last_visited;
+
+ dw->last_visited = dw->last_visited->parent;
+ if (dw->last_visited == NULL)
+ {
+ dw->is_over = true;
+ break;
+ }
+
+ if ((dw->last_visited->right != came_from) && (dw->last_visited->right != RBNIL))
+ {
+ dw->last_visited = dw->last_visited->right;
+ return dw->last_visited;
+ }
+ }
}
+ while (dw->last_visited != NULL);
+
+ return dw->last_visited;
+}
+
+/*
+ * Begin inverted walk (a.k.a post-order traversal).
+ */
+void
+rb_begin_inverted_walk(RBTree *rb, RBTreeInvertedWalk * iw)
+{
+ iw->rb = rb;
+ iw->last_visited = NULL;
+ iw->next_step = NextStepNone;
+ iw->is_over = (iw->rb->root == RBNIL);
}
/*
- * rb_iterate: return the next node in traversal order, or NULL if no more
+ * Inverted walk: get next node. Returns NULL if there is none.
+ *
+ * Post-order traversal while deleting or freeing nodes and values can delete
+ * or free an entire binary tree. It can also generate a postfix
+ * representation of a binary tree.
+ *
+ * https://en.wikipedia.org/wiki/Tree_traversal#Applications
*/
RBNode *
-rb_iterate(RBTree *rb)
+rb_inverted_walk(RBTreeInvertedWalk * iw)
{
- if (rb->cur == RBNIL)
+ RBNode *came_from;
+
+ if (iw->is_over)
return NULL;
- return rb->iterate(rb);
+ if (iw->last_visited == NULL)
+ {
+ iw->last_visited = iw->rb->root;
+ iw->next_step = NextStepLeft;
+ }
+
+loop:
+ switch (iw->next_step)
+ {
+ case NextStepLeft:
+ came_from = iw->last_visited;
+ while (iw->last_visited->left != RBNIL)
+ iw->last_visited = iw->last_visited->left;
+
+ iw->next_step = NextStepRight;
+ goto loop;
+
+ case NextStepRight:
+ if (iw->last_visited->right != RBNIL)
+ {
+ iw->last_visited = iw->last_visited->right;
+ iw->next_step = NextStepLeft;
+ goto loop;
+ }
+ else /* not moved - return current, then go up */
+ iw->next_step = NextStepUp;
+ break;
+ case NextStepUp:
+ for (;;)
+ {
+ came_from = iw->last_visited;
+ iw->last_visited = iw->last_visited->parent;
+ if (iw->last_visited == NULL)
+ {
+ iw->is_over = true;
+ break; /* end of iteration */
+ }
+
+ if (came_from == iw->last_visited->right)
+ {
+ /* return current, then continue to go up */
+ break;
+ }
+
+ /* otherwise we came from the left */
+ iw->next_step = NextStepRight;
+ goto loop;
+ }
+ break;
+ default: /* should never happen but is usefull during
+ * debugging */
+ elog(ERROR, "Unexpected next step value during inverted walk: %d\n", iw->next_step);
+ }
+
+ return iw->last_visited;
}
diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h
index 68cfe0c..3438fb8 100644
--- a/src/include/access/gin_private.h
+++ b/src/include/access/gin_private.h
@@ -919,6 +919,7 @@ typedef struct
GinEntryAccumulator *entryallocator;
uint32 eas_used;
RBTree *tree;
+ RBTreeLeftRightWalk tree_walk;
} BuildAccumulator;
extern void ginInitBA(BuildAccumulator *accum);
diff --git a/src/include/lib/rbtree.h b/src/include/lib/rbtree.h
index 73e83c3..efec1d2 100644
--- a/src/include/lib/rbtree.h
+++ b/src/include/lib/rbtree.h
@@ -22,7 +22,6 @@
*/
typedef struct RBNode
{
- char iteratorState; /* workspace for iterating through tree */
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 */
@@ -32,15 +31,6 @@ typedef struct RBNode
/* Opaque struct representing a whole tree */
typedef struct RBTree RBTree;
-/* Available tree iteration orderings */
-typedef enum RBOrderControl
-{
- 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;
-
/* 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);
@@ -56,11 +46,58 @@ extern RBTree *rb_create(Size node_size,
extern RBNode *rb_find(RBTree *rb, const RBNode *data);
extern RBNode *rb_leftmost(RBTree *rb);
+extern RBNode *rb_rightmost(RBTree *rb);
extern RBNode *rb_insert(RBTree *rb, const RBNode *data, bool *isNew);
extern void rb_delete(RBTree *rb, RBNode *node);
-extern void rb_begin_iterate(RBTree *rb, RBOrderControl ctrl);
-extern RBNode *rb_iterate(RBTree *rb);
+typedef enum RBTreeNextStep
+{
+ NextStepNone,
+ NextStepUp,
+ NextStepLeft,
+ NextStepRight
+} RBTreeNextStep;
+
+typedef struct
+{
+ RBTree *rb;
+ RBNode *last_visited;
+ bool is_over;
+} RBTreeLeftRightWalk;
+
+extern void rb_begin_left_right_walk(RBTree *rb, RBTreeLeftRightWalk * lrw);
+extern RBNode *rb_left_right_walk(RBTreeLeftRightWalk * lrw);
+
+typedef struct
+{
+ RBTree *rb;
+ RBNode *last_visited;
+ bool is_over;
+} RBTreeRightLeftWalk;
+
+extern void rb_begin_right_left_walk(RBTree *rb, RBTreeRightLeftWalk * rlw);
+extern RBNode *rb_right_left_walk(RBTreeRightLeftWalk * rlw);
+
+typedef struct
+{
+ RBTree *rb;
+ RBNode *last_visited;
+ bool is_over;
+} RBTreeDirectWalk;
+
+extern void rb_begin_direct_walk(RBTree *rb, RBTreeDirectWalk * dw);
+extern RBNode *rb_direct_walk(RBTreeDirectWalk * dw);
+
+typedef struct
+{
+ RBTree *rb;
+ RBNode *last_visited;
+ RBTreeNextStep next_step;
+ bool is_over;
+} RBTreeInvertedWalk;
+
+extern void rb_begin_inverted_walk(RBTree *rb, RBTreeInvertedWalk * dw);
+extern RBNode *rb_inverted_walk(RBTreeInvertedWalk * dw);
#endif /* RBTREE_H */
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
