Hello
While working on some new feature for PostgreSQL (which is still in
development and is irrelevant in this context) I noticed that current
RBTree implementation interface is following:
```
extern void rb_begin_iterate(RBTree *rb, RBOrderControl ctrl);
extern RBNode *rb_iterate(RBTree *rb);
```
As you see it doesn't allow to do multiple iterations over a single
tree. I believe it's a major flaw for a general-purpose container.
Proposed patch introduces a new iteration interface that doesn't has
such a flaw. Naturally I wrote some unit tests, but I was not sure where
exactly to place them in PostgreSQL source code. For now I've just
uploaded them to GitHub:
https://github.com/afiskon/c-algorithms-examples/blob/master/rbtree_example.c
According to these tests new implementation works as fast as current
implementation and produces exactly same results.
I didn't dare to remove current interface since in theory some
extensions can use it. Still I believe such a move is worth considering.
--
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..cbe256f 100644
--- a/src/backend/lib/rbtree.c
+++ b/src/backend/lib/rbtree.c
@@ -871,3 +871,278 @@ rb_iterate(RBTree *rb)
return rb->iterate(rb);
}
+
+/*
+ * 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.
+ */
+RBNode *
+rb_left_right_walk(RBTreeLeftRightWalk * lrw)
+{
+ if (lrw->is_over)
+ return NULL;
+
+ if (lrw->last_visited == NULL)
+ {
+ lrw->last_visited = lrw->rb->root;
+ while (lrw->last_visited->left != RBNIL)
+ lrw->last_visited = lrw->last_visited->left;
+
+ return lrw->last_visited;
+ }
+
+ 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;
+
+ return lrw->last_visited;
+ }
+
+ for (;;)
+ {
+ RBNode *came_from = lrw->last_visited;
+
+ lrw->last_visited = lrw->last_visited->parent;
+ if (lrw->last_visited == NULL)
+ {
+ lrw->is_over = true;
+ break;
+ }
+
+ 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 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);
+}
+
+/*
+ * Right left walk: get next node. Returns NULL if there is none.
+ */
+RBNode *
+rb_right_left_walk(RBTreeRightLeftWalk * rlw)
+{
+ if (rlw->is_over)
+ return NULL;
+
+ if (rlw->last_visited == NULL)
+ {
+ rlw->last_visited = rlw->rb->root;
+ while (rlw->last_visited->right != RBNIL)
+ rlw->last_visited = rlw->last_visited->right;
+
+ return rlw->last_visited;
+ }
+
+ 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;
+
+ return rlw->last_visited;
+ }
+
+ for (;;)
+ {
+ RBNode *came_from = rlw->last_visited;
+
+ rlw->last_visited = rlw->last_visited->parent;
+ if (rlw->last_visited == NULL)
+ {
+ rlw->is_over = true;
+ break;
+ }
+
+ 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 rlw->last_visited;
+}
+
+/*
+ * Begin direct walk (a.k.a pre-order traversal).
+ *
+ * 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.
+ *
+ * https://en.wikipedia.org/wiki/Tree_traversal#Applications
+ */
+void
+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)
+{
+ if (dw->is_over)
+ return NULL;
+
+ if (dw->last_visited == NULL)
+ {
+ 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;
+ }
+
+ /* 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);
+}
+
+/*
+ * 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_inverted_walk(RBTreeInvertedWalk * iw)
+{
+ RBNode *came_from;
+
+ if (iw->is_over)
+ return NULL;
+
+ 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:
+ fprintf(stderr, "Unexpected next step value during inverted walk: %d\n", iw->next_step);
+ exit(1);
+ }
+
+ 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..541f978 100644
--- a/src/include/lib/rbtree.h
+++ b/src/include/lib/rbtree.h
@@ -63,4 +63,53 @@ 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
