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

[Chris Wilson]

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