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

[Jason Ekstrand]

On Fri, Jun 22, 2018 at 8:41 AM, Chris Wilson <chris at chris-wilson.co.uk>
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.)
>

I already wrote a tester here:

https://github.com/jekstrand/rb-tree

It basically does that.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.freedesktop.org/archives/mesa-dev/attachments/20180622/490141ea/attachment.html>