Re: Red-Black tree traversal tests

[ btw, please don't cc pgsql-hackers-owner, the list moderators don't
need the noise ]

Aleksander Alekseev <a(dot)alekseev(at)postgrespro(dot)ru> writes:
> I would say that this patch is in a pretty good shape now. And I see a
> 99% code coverage of rbtree.c. Let's see what committers think.

I took a quick look through the patch --- haven't tried to compile it
or anything like that --- and have a few comments:

* There's some typos, eg extention should be extension, triversal
should be traversal. Maybe try a spell checker?

* The diff complains about lack of file-ending newlines in several
places.

* There's something weird at the start of test.c:

@@ -0,0 +1,577 @@
+/*--------------------------------------------------------------------------

Maybe your compiler thinks that's a BOM? It's hard to see how it
compiles otherwise.

* I think it might be simpler to have the module expose just one SQL
function that invokes all these individual tests internally. Less
boilerplate text that way, and less to change if you add more tests
later. Also, you might consider passing in TEST_SIZE as an argument
of the SQL function instead of having it be hard-wired.

* We don't do C++-style (//) comments around here. Please use C
style. (You might consider running the code through pgindent,
which will convert those comments automatically.)

* It's also generally not per project style to use malloc/calloc/free
directly in backend code; and it's certainly not cool to use malloc or
calloc and then not check for a null result. Use palloc instead. Given
the short runtime of this test, you likely needn't be too worried about
pfree'ing stuff.

* _PG_init() declaration seems to be a leftover? <stdio.h> doesn't
belong here either, as postgres.h will bring that in for you.

* I know next to zip about red-black trees, but it disturbs me that
the traversal tests use trees whose values were inserted in strictly
increasing order. Seems like that's not proving as much as it could.
I wonder how hard it would be to insert those integers in random order.

* I'm not too pleased that the rb_find calls mostly just assume that
the find won't return NULL. You should be testing for that and reporting
the problem, not just dying on a null pointer crash if it happens.

* Possibly the tests should exercise rb_delete on keys *not* present.
And how about insertion of already-existing keys? Although that's
a bit outside the scope of testing traversal, so if you want to leave
it for some future expansion, that'd be OK.

I'll set this back to Waiting on Author. I do encourage you to finish
it up.

regards, tom lane