Signed-off-by: NAlexey Klimov <alexey.klimov@linaro.org>
Signed-off-by: NJonathan Corbet <corbet@lwn.net>

Fixed multiple spelling errors.
Acked-by: NRandy Dunlap <rdunlap@infradead.org>
Signed-off-by: NCarlos E. Garcia <carlos@cgarcia.org>
Signed-off-by: NJiri Kosina <jkosina@suse.cz>

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: NMichel Lespinasse <walken@google.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Hillf Danton <dhillf@gmail.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

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: NMichel Lespinasse <walken@google.com>
Acked-by: NRik 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: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

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

Cc: Pekka Enberg <penberg@cs.helsinki.fi>
Cc: David Woodhouse <David.Woodhouse@intel.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Acked-by: NIngo Molnar <mingo@elte.hu>
Acked-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
Signed-off-by: NSasha Levin <levinsasha928@gmail.com>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>

Remove anticipatory block I/O scheduler info from Documentation/
since the code has been deleted.
Signed-off-by: NRandy Dunlap <randy.dunlap@oracle.com>
Reported-by: N"Robert P. J. Day" <rpjday@crashcourse.ca>
Cc: Jens Axboe <axboe@kernel.dk>
Signed-off-by: NJens Axboe <jaxboe@fusionio.com>

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: NVenkatesh Pallipadi <venkatesh.pallipadi@intel.com>
LKML-Reference: <20100210232343.GA11465@linux-os.sc.intel.com>
Signed-off-by: NSuresh Siddha <suresh.b.siddha@intel.com>
Signed-off-by: NH. Peter Anvin <hpa@zytor.com>

Reviewed-by: NWANG Cong <xiyou.wangcong@gmail.com>
Signed-off-by: NJiri Kosina <jkosina@suse.cz>

 The first formal parameter of the rb_link_node() is a pointer, and the
 "node" is define a data struct (pls see line 67 and line 73 in the
 doc), so the actual parameter should use "&data->node".
Signed-off-by: NFigo.zhang <figo.zhang@kolorific.com>
Signed-off-by: NJiri Kosina <jkosina@suse.cz>

Documentation for lib/rbtree.c.
Signed-off-by: NRob Landley <rob@landley.net>
Cc: "Randy.Dunlap" <rdunlap@xenotime.net>
Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>