util: rb-tree: A simple, invasive, red-black tree

Graphics / Mesa 3D Graphics Library / Mesa - Jason Ekstrand [jlekstrand.net] - 5 July 2018 10:57 EDT

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 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.

2602ea89d5 util: rb-tree: A simple, invasive, red-black tree
src/util/Makefile.sources | 2 +
src/util/meson.build | 2 +
src/util/rb_tree.c | 421 ++++++++++++++++++++++++++++++++++++++++++++++
src/util/rb_tree.h | 269 +++++++++++++++++++++++++++++
4 files changed, 694 insertions(+)

Upstream: cgit.freedesktop.org


  • Share