Re: Red-Black tree traversal tests

From: Victor Drobny <v(dot)drobny(at)postgrespro(dot)ru>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: Aleksander Alekseev <a(dot)alekseev(at)postgrespro(dot)ru>, Pgsql Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Red-Black tree traversal tests
Date: 2017-09-08 09:03:37
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

Dear Tom,

Thank you very much for your review. In the attachment you can find v2
of the patch.

On 2017-09-07 01:38, Tom Lane wrote:
> [ 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?

Done. I fixed all spelling mistakes that i found.

> * 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.

Now it is in UTF-8 without BOM. It seems that there is no such data in
the beginning
of the test.c

> * 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.
You are right. Done.
> * 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.

Deletion requires to get pointer to the tree node. Otherwise it could
the tree. It is mentioned in the description of the rb_delete function.
" * "node" must have previously been found via rb_find or rb_leftmost."

Insertion of the same elements is managed by the specific implementation
of the tree. One of the input arguments of the rb_create function is
combiner function that will be called in case of repeated insertion.

However, during looking through this i found that nobody checks that
combiner function(as well as comparator, freefunc and allocfunc) is
not NULL. So if it was not specified, postgres will fall. I think that
it is better to add this checks.

> I'll set this back to Waiting on Author. I do encourage you to finish
> it up.
> regards, tom lane

Victor Drobny
Postgres Professional:
The Russian Postgres Company

Attachment Content-Type Size
rbtree_test_2.patch text/x-diff 20.3 KB

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Robert Haas 2017-09-08 09:31:11 Re: GnuTLS support
Previous Message amul sul 2017-09-08 07:48:39 Re: Hash Functions