[Mesa-dev] [PATCH v3 05/16] util: rb-tree: A simple, invasive, red-black tree

[Lionel Landwerlin]

On 22/06/18 16:41, Chris Wilson wrote:
> Quoting Lionel Landwerlin (2018-06-21 17:29:04)
>> From: Jason Ekstrand <jason at jlekstrand.net>
>>
>> This is a simple, invasive, liberally licensed red-black tree
>> implementation. It's an invasive data structure similar to the
>> Linux kernel linked-list where the intention is that you embed a
> s/linked-list/rbtree/
>
> Might as well compare like for like.
>
>> rb_node struct the data structure you intend to put into the
>> tree.
>>
>> The implementation is mostly based on the one in "Introduction to
>> Algorithms", third edition, by Cormen, Leiserson, Rivest, and
>> Stein. There were a few other key design points:
>>
>>   * It's an invasive data structure similar to the [Linux kernel
>>     linked list].
>>
>>   * It uses NULL for leaves instead of a sentinel. This means a few
>>     algorithms differ a small bit from the ones in "Introduction to
>>     Algorithms".
>>
>>   * All search operations are inlined so that the compiler can
>>     optimize away the function pointer call.
>> ---
>>   src/util/Makefile.sources |   2 +
>>   src/util/meson.build      |   2 +
>>   src/util/rb_tree.c        | 421 ++++++++++++++++++++++++++++++++++++++
>>   src/util/rb_tree.h        | 269 ++++++++++++++++++++++++
> No tester? Insert/remove 1,000,000 u32 and check the post-order is 
> sorted and has correct coloring? (I'm stealing ideas from 
> kernel/lib/rbtree_test.c fwiw.) -Chris
I've written a test generating N random insertions/deletions, will send 
later.

-
Lionel