Messages in this thread | | | Date | Sun, 05 Aug 2012 22:12:34 -0400 | From | Rik van Riel <> | Subject | Re: [PATCH v2 8/9] rbtree: faster augmented rbtree manipulation |
| |
On 08/02/2012 06:34 PM, Michel Lespinasse wrote: > 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: Michel Lespinasse<walken@google.com>
Acked-by: Rik van Riel <riel@redhat.com>
-- All rights reversed
| |