summaryrefslogtreecommitdiffstats
path: root/src/util/meson.build
diff options
context:
space:
mode:
authorJason Ekstrand <[email protected]>2018-04-05 08:21:49 -0700
committerLionel Landwerlin <[email protected]>2018-07-05 11:57:45 +0100
commit2602ea89d55cd1004bbec46c8ff1ac1ad1510940 (patch)
treef97c0dace92b5693ffc2cc4814fb26941d0b6fa8 /src/util/meson.build
parent144b40db541183ba2ee18efa4e1531aabcf9c6e8 (diff)
util: rb-tree: A simple, invasive, red-black tree
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. Reviewed-by: Lionel Landwerlin <[email protected]>
Diffstat (limited to 'src/util/meson.build')
-rw-r--r--src/util/meson.build2
1 files changed, 2 insertions, 0 deletions
diff --git a/src/util/meson.build b/src/util/meson.build
index 1713864b4f7..1838719d271 100644
--- a/src/util/meson.build
+++ b/src/util/meson.build
@@ -56,6 +56,8 @@ files_mesa_util = files(
'ralloc.h',
'rand_xor.c',
'rand_xor.h',
+ 'rb_tree.c',
+ 'rb_tree.h',
'register_allocate.c',
'register_allocate.h',
'rgtc.c',