Eric Lee / smarc-fsl-linux-kernel

14 Sep, 2015

1 commit

05 May, 2014

1 commit

09 Oct, 2012

2 commits

  • 9c079add0   rbtree: move augmented rbtree functionality to rbtree_augmented.h ... Browse Code »

    Provide rb_insert_augmented() and rb_erase_augmented() through a new
    rbtree_augmented.h include file. rb_erase_augmented() is defined there as
    an __always_inline function, in order to allow inlining of augmented
    rbtree callbacks into it. Since this generates a relatively large
    function, each augmented rbtree user should make sure to have a single
    call site.

    Signed-off-by: Michel Lespinasse
    Cc: Rik van Riel
    Cc: Hillf Danton
    Cc: Peter Zijlstra
    Cc: Catalin Marinas
    Cc: Andrea Arcangeli
    Cc: David Woodhouse
    Signed-off-by: Andrew Morton
    Signed-off-by: Linus Torvalds

    Michel Lespinasse
     
  • 14b94af0b   rbtree: faster augmented rbtree manipulation ... Browse Code »

    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
    Acked-by: Rik van Riel
    Cc: Peter Zijlstra
    Cc: Andrea Arcangeli
    Cc: David Woodhouse
    Signed-off-by: Andrew Morton
    Signed-off-by: Linus Torvalds

    Michel Lespinasse
     

25 Jul, 2011

1 commit

  • 2f175074e   Documentation: Update augmented rbtree documentation ... Browse Code »

    Current documentation referred to the old method of handling augmented
    trees. Update documentation to correspond with the changes done in
    commit b945d6b2554d ("rbtree: Undo augmented trees performance damage
    and regression").

    Cc: Pekka Enberg
    Cc: David Woodhouse
    Cc: Andrew Morton
    Acked-by: Ingo Molnar
    Acked-by: Peter Zijlstra
    Signed-off-by: Sasha Levin
    Signed-off-by: Linus Torvalds

    Sasha Levin
     

11 Nov, 2010

1 commit

19 Feb, 2010

1 commit

  • 17d9ddc72   rbtree: Add support for augmented rbtrees ... Browse Code »

    Add support for augmented rbtrees in core rbtree code.

    This will be used in subsequent patches, in x86 PAT code, which needs
    interval trees to efficiently keep track of PAT ranges.

    Signed-off-by: Venkatesh Pallipadi
    LKML-Reference:
    Signed-off-by: Suresh Siddha
    Signed-off-by: H. Peter Anvin

    Pallipadi, Venkatesh
     

13 Jun, 2009

2 commits

12 Feb, 2007

1 commit