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.) -Chris _______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/mesa-dev
