Re: Red-Black tree traversal tests

From: Aleksander Alekseev <a(dot)alekseev(at)postgrespro(dot)ru>
To: Victor Drobny <v(dot)drobny(at)postgrespro(dot)ru>
Cc: Pgsql Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Red-Black tree traversal tests
Date: 2017-08-01 09:54:47
Message-ID: 20170801095446.GA22764@e733.localdomain
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers

Hi Victor,

> Postgres now has its own red-black tree implementation. This tree has 4
> types of traversals. In the attachment, you can find module test that
> checks the correctness of tree traversal strategies.
> I hope that someone can find it useful.

Great job! However, according to lcov report, some procedures declared
in rbtree.c are still not test covered even with your patch,

* rb_find
* rb_leftmost
* rb_delete + dependencies (rb_delete_fixup, etc)

You can generate a corresponding report using this script [1].

I must say, I was a little surprised that rb_find is not used anywhere
in PostgreSQL code. Turned out that rbtree currently is used only by GIN
and it uses a small subset of all procedures.

If it's not too much trouble perhaps you could write a few more test so
we would have 100% test coverage for rbtree, could modify it safely and
be sure that it actually works when someone will need the rest of its


Best regards,
Aleksander Alekseev

In response to


Browse pgsql-hackers by date

  From Date Subject
Next Message Aleksander Alekseev 2017-08-01 09:58:36 Re: Red-Black tree traversal tests
Previous Message Etsuro Fujita 2017-08-01 09:41:33 Re: map_partition_varattnos() and whole-row vars