• Michel Lespinasse's avatar
    rbtree: faster augmented rbtree manipulation · 14b94af0
    Michel Lespinasse authored
    Introduce new augmented rbtree APIs that allow minimal recalculation of
    augmented node information.
    
    A new callback is added to the rbtree insertion and erase rebalancing
    functions, to be called on each tree rotations. Such rotations preserve
    the subtree's root augmented value, but require recalculation of the one
    child that was previously located at the subtree root.
    
    In the insertion case, the handcoded search phase must be updated to
    maintain the augmented information on insertion, and then the rbtree
    coloring/rebalancing algorithms keep it up to date.
    
    In the erase case, things are more complicated since it is library
    code that manipulates the rbtree in order to remove internal nodes.
    This requires a couple additional callbacks to copy a subtree's
    augmented value when a new root is stitched in, and to recompute
    augmented values down the ancestry path when a node is removed from
    the tree.
    
    In order to preserve maximum speed for the non-augmented case,
    we provide two versions of each tree manipulation function.
    rb_insert_augmented() is the augmented equivalent of rb_insert_color(),
    and rb_erase_augmented() is the augmented equivalent of rb_erase().
    Signed-off-by: default avatarMichel Lespinasse <walken@google.com>
    Acked-by: default avatarRik van Riel <riel@redhat.com>
    Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
    Cc: Andrea Arcangeli <aarcange@redhat.com>
    Cc: David Woodhouse <dwmw2@infradead.org>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    14b94af0
rbtree.c 18.8 KB