On Fri, Jun 22, 2018 at 8:41 AM, Chris Wilson <ch...@chris-wilson.co.uk> wrote:
> Quoting Lionel Landwerlin (2018-06-21 17:29:04) > > From: Jason Ekstrand <ja...@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.
_______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/mesa-dev
