• Jason Ekstrand's avatar
    util: rb-tree: A simple, invasive, red-black tree · 2602ea89
    Jason Ekstrand authored
    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's avatarLionel Landwerlin <lionel.g.landwerlin@intel.com>
    2602ea89
rb_tree.c 11.5 KB