<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Jun 22, 2018 at 8:41 AM, Chris Wilson <span dir="ltr"><<a href="mailto:chris@chris-wilson.co.uk" target="_blank">chris@chris-wilson.co.uk</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Quoting Lionel Landwerlin (2018-06-21 17:29:04)<br>
<span class="gmail-">> From: Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>><br>
> <br>
> This is a simple, invasive, liberally licensed red-black tree<br>
> implementation. It's an invasive data structure similar to the<br>
> Linux kernel linked-list where the intention is that you embed a<br>
<br>
</span>s/linked-list/rbtree/<br>
<br>
Might as well compare like for like.<br>
<span class="gmail-"><br>
> rb_node struct the data structure you intend to put into the<br>
> tree.<br>
> <br>
> The implementation is mostly based on the one in "Introduction to<br>
> Algorithms", third edition, by Cormen, Leiserson, Rivest, and<br>
> Stein. There were a few other key design points:<br>
> <br>
>  * It's an invasive data structure similar to the [Linux kernel<br>
>    linked list].<br>
> <br>
>  * It uses NULL for leaves instead of a sentinel. This means a few<br>
>    algorithms differ a small bit from the ones in "Introduction to<br>
>    Algorithms".<br>
> <br>
>  * All search operations are inlined so that the compiler can<br>
>    optimize away the function pointer call.<br>
> ---<br>
>  src/util/Makefile.sources |   2 +<br>
>  src/util/meson.build      |   2 +<br>
>  src/util/rb_tree.c        | 421 ++++++++++++++++++++++++++++++<wbr>++++++++<br>
>  src/util/rb_tree.h        | 269 ++++++++++++++++++++++++<br>
<br>
</span>No tester? Insert/remove 1,000,000 u32 and check the post-order is sorted<br>
and has correct coloring? (I'm stealing ideas from<br>
kernel/lib/rbtree_test.c fwiw.)<br></blockquote><div><br></div><div>I already wrote a tester here:</div><div><br></div><div><a href="https://github.com/jekstrand/rb-tree">https://github.com/jekstrand/rb-tree</a></div><div><br></div><div>It basically does that.<br></div></div><br></div></div>