Re: Red-Black tree traversal tests

Victor Drobny <v(dot)drobny(at)postgrespro(dot)ru> writes:
> On 2017-09-08 15:23, Thomas Munro wrote:
>> It's trying to call rb->combiner which is null.

> Thank you for pointing on it. Here is a fixed version.

Actually, I think we *do* want the tests to call the combiner
occasionally ...

I whacked this around quite a bit and had gotten it to a state
that I thought was committable, when it occurred to me to wonder
why exactly we're going to this much effort to test the preorder
and postorder traversal logic. I'm inclined to think we should
rip that out, instead, because I can think of no reason that
anyone would ever want to use it in Postgres.

I'll make that argument in a separate thread, so it gets a little
more visibility in the pgsql-hackers firehose.

In the meantime, here's my version. Notable changes:

* Got rid of separate .h file; seemed pointless, especially
since the combiner function needs to know what the test
expectations are.
* Corrected the random-permutation algorithm.
* Made the preorder/postorder check logic more paranoid
(though I now feel that was a waste of effort).
* Improved English grammar in a lot of comments.
* Added some more test cases; code coverage report shows
that this exercises every non-error-case line in rbtree.c.
* Added an rbtree "rb_root()" function to avoid the unsafe
casting the previous version did to get the root pointer.
* Removed the assumption that the nil element is unique;
now it just knows that a leaf element points to itself.

We could dispense with rb_root(), as well as the test code's knowledge
about RBNIL representation, if we dropped the preorder/postorder cases
... which is another good reason to do so.

regards, tom lane