Re: [HACKERS] [Patch] RBTree iteration interface improvement

[Aleksander Alekseev]

> Ok, committed.
> 
> - Heikki

Thanks a lot for committing this patch and also for your contribution to
it!

-- 
Best regards,
Aleksander Alekseev


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] [Patch] RBTree iteration interface improvement

[Heikki Linnakangas]

On 08/26/2016 04:07 PM, Aleksander Alekseev wrote:

Another unrelated change in this patch is the addition of
rb_rightmost(). It's not used for anything, so I'm not sure what the
point is. Then again, there don't seem to be any callers of
rb_leftmost() either.


It's just something I needed in tests to reach a good percent of code
coverage. Implementation of rb_rightmost is trivial so we probably can do
without it.


Looking closer, we don't currently use any of the iterators besides the 
left-right iterator either. Nor rb_delete().



I think we should something like in the attached patch. It seems to pass
your test suite, but I haven't done any other testing on this. Does it
look OK to you?


Looks good to me.


Ok, committed.

- Heikki



--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] [Patch] RBTree iteration interface improvement

[Aleksander Alekseev]

Hello, Heikki.

Thank you for your attention to this patch!

> This also seems to change the API so that instead of a single 
> rb_begin_iterate()+rb_iterate() pair, there is a separate begin and 
> iterate function for each traversal order. That seems like an unrelated 
> change. Was there a particular reason for that? I think the old 
> rb_begin_iterate()+rb_iterate() functions were fine, we just need to 
> have a RBTreeIterator struct that's different from the tree itself.

I'm trying to avoid calling procedures by a pointer, an old habit. When
I started to work on this patch I just needed a RB-tree implementation
for a pet project. I took one from PostgreSQL code. Then I found this
flaw of iteration interface and decided to fix it. The idea to merge
this fix back to PostgreSQL code appeared later so I just wrote code the
way I like.

These days code performance depends on many factors like whether code
fits into cache, i.e not only on whether you call a procedure directly
or using a pointer. Until someone finds a real bottleneck here I think
current rb_begin_iterate()+rb_iterate() interface should do just fine.
 
> Another unrelated change in this patch is the addition of 
> rb_rightmost(). It's not used for anything, so I'm not sure what the 
> point is. Then again, there don't seem to be any callers of 
> rb_leftmost() either.

It's just something I needed in tests to reach a good percent of code
coverage. Implementation of rb_rightmost is trivial so we probably can do
without it.

> I think we should something like in the attached patch. It seems to pass 
> your test suite, but I haven't done any other testing on this. Does it
> look OK to you?

Looks good to me.

-- 
Best regards,
Aleksander Alekseev


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] [Patch] RBTree iteration interface improvement

[Heikki Linnakangas]

On 08/22/2016 01:00 PM, Aleksander Alekseev wrote:

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.


This also seems to change the API so that instead of a single 
rb_begin_iterate()+rb_iterate() pair, there is a separate begin and 
iterate function for each traversal order. That seems like an unrelated 
change. Was there a particular reason for that? I think the old 
rb_begin_iterate()+rb_iterate() functions were fine, we just need to 
have a RBTreeIterator struct that's different from the tree itself.


Note that the API actually used to be like that. rb_begin_iterate() used 
to return a palloc'd RBTreeIterator struct. It was changed in commit 
0454f131, because the implementation didn't support more than one 
iterator at a time, which made the separate struct pointless. But we're 
fixing that problem now.


Another unrelated change in this patch is the addition of 
rb_rightmost(). It's not used for anything, so I'm not sure what the 
point is. Then again, there don't seem to be any callers of 
rb_leftmost() either.


I think we should something like in the attached patch. It seems to pass 
your test suite, but I haven't done any other testing on this. Does it 
look OK to you?


- Heikki

diff --git a/src/backend/access/gin/ginbulk.c b/src/backend/access/gin/ginbulk.c
index d6422ea..71c64e4 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_iterate(accum->tree, LeftRightWalk, >tree_walk);
 }
 
 /*
@@ -271,7 +271,7 @@ ginGetBAEntry(BuildAccumulator *accum,
 	GinEntryAccumulator *entry;
 	ItemPointerData *list;
 
-	entry = (GinEntryAccumulator *) rb_iterate(accum->tree);
+	entry = (GinEntryAccumulator *) rb_iterate(>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..048366d 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,8 +59,19 @@ struct RBTree
  */
 #define RBNIL ()
 
-static RBNode sentinel = {InitialState, RBBLACK, RBNIL, RBNIL, NULL};
+static RBNode sentinel = {RBBLACK, RBNIL, RBNIL, NULL};
 
+/*
+ * Values used in the RBTreeIterator.next_state field, with an
+ * InvertedWalk iterator.
+ */
+typedef enum InvertedWalkNextStep
+{
+	NextStepBegin,
+	NextStepUp,
+	NextStepLeft,
+	NextStepRight
+} InvertedWalkNextStep;
 
 /*
  * rb_create: create an empty RBTree
@@ -123,8 +118,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;
@@ -437,7 +430,6 @@ rb_insert(RBTree *rb, const RBNode *data, bool *isNew)
 
 	x = rb->allocfunc (rb->arg);
 
-	x->iteratorState = InitialState;
 	x->color = RBRED;
 
 	x->left = RBNIL;
@@ -653,171 +645,194 @@ rb_delete(RBTree *rb, 

Re: [HACKERS] [Patch] RBTree iteration interface improvement

[Aleksander Alekseev]

> > 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, >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(>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 ()
 
-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 = 

Re: [HACKERS] [Patch] RBTree iteration interface improvement

[Aleksander Alekseev]

> > Having said that, though: if the iteration state is not part of the
> > object, it's not very clear whether we can behave sanely if someone
> > changes the tree while an iteration is open.  It will need careful
> > thought as to what sort of guarantees we can make about that.  If
> > it's too weak, then a separated-state version would have enough
> > hazards of its own that it's not necessarily any safer.  
> 
> +1 to all of that.
> 

The old API assumes that tree doesn't change during iteration. And it
doesn't do any checks about this. The new API behaves the same way. In
this sense patch at least doesn't make anything worse.

> 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?

-- 
Best regards,
Aleksander Alekseev


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] [Patch] RBTree iteration interface improvement

[Robert Haas]

On Thu, Jul 28, 2016 at 1:57 PM, Tom Lane  wrote:
> Aleksander Alekseev  writes:
>>> Can you explain use case where you need it?
>
>> ... Or maybe you have different objects, e.g. IndexScanDesc's, that should
>> iterate over some tree's independently somewhere in indexam.c
>> procedures. Exact order may depend on user's query so you don't even
>> control it.
>
> 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.
>
> Having said that, though: if the iteration state is not part of the
> object, it's not very clear whether we can behave sanely if someone
> changes the tree while an iteration is open.  It will need careful
> thought as to what sort of guarantees we can make about that.  If it's
> too weak, then a separated-state version would have enough hazards of
> its own that it's not necessarily any safer.

+1 to all of that.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] [Patch] RBTree iteration interface improvement

[Tom Lane]

Aleksander Alekseev  writes:
>> Can you explain use case where you need it?

> ... Or maybe you have different objects, e.g. IndexScanDesc's, that should
> iterate over some tree's independently somewhere in indexam.c
> procedures. Exact order may depend on user's query so you don't even
> control it.

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.

Having said that, though: if the iteration state is not part of the
object, it's not very clear whether we can behave sanely if someone
changes the tree while an iteration is open.  It will need careful
thought as to what sort of guarantees we can make about that.  If it's
too weak, then a separated-state version would have enough hazards of
its own that it's not necessarily any safer.

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] [Patch] RBTree iteration interface improvement

[Aleksander Alekseev]

> Can you explain use case where you need it?

Sure. You can consider RBTree as a container that always keeps its
elements in sorted order.  Now imagine you would like to write a code
like this:

```
/* iterate over items in sorted order */
while(item1 = left_right_walk(tree))
{

  /* another iteration, probably even in different procedure */
  while(item2 = left_right_walk(tree))
  {
/* ... some logic ... */
  }

}
```

Currently you can't do it.

Or maybe you have different objects, e.g. IndexScanDesc's, that should
iterate over some tree's independently somewhere in indexam.c
procedures. Exact order may depend on user's query so you don't even
control it.

-- 
Best regards,
Aleksander Alekseev


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] [Patch] RBTree iteration interface improvement

[Amit Kapila]

On Wed, Jul 27, 2016 at 7:56 PM, Aleksander Alekseev
 wrote:
> 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.
>

Can you explain use case where you need it?

-- 
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] [Patch] RBTree iteration interface improvement

[Aleksander Alekseev]

And as always, I didn't re-check a patch before sending it :) Here is a
corrected version without any fprintf's.

-- 
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, >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(>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..eb645a2 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 

[HACKERS] [Patch] RBTree iteration interface improvement

[Aleksander Alekseev]

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, >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(>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);
+}
+
+/*