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
Message-ID: f0c91f2292d8464c29be7f81e55d179d@postgrespro.ru
Views: Raw Message | Whole Thread | Download mbox
Thread:
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.)

Fixed.

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

Done.

>
> * 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
break
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: http://www.postgrespro.com
The Russian Postgres Company

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

In response to

Responses

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