summaryrefslogtreecommitdiffstats
path: root/Documentation/rbtree.txt
AgeCommit message (Collapse)Author
2012-10-09rbtree: move augmented rbtree functionality to rbtree_augmented.hMichel Lespinasse
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 <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: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2012-10-09rbtree: faster augmented rbtree manipulationMichel Lespinasse
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> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Andrea Arcangeli <aarcange@redhat.com> Cc: David Woodhouse <dwmw2@infradead.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2011-07-24Documentation: Update augmented rbtree documentationSasha Levin
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 <penberg@cs.helsinki.fi> Cc: David Woodhouse <David.Woodhouse@intel.com> Cc: Andrew Morton <akpm@linux-foundation.org> Acked-by: Ingo Molnar <mingo@elte.hu> Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl> Signed-off-by: Sasha Levin <levinsasha928@gmail.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2010-11-11Documentation: remove anticipatory scheduler infoRandy Dunlap
Remove anticipatory block I/O scheduler info from Documentation/ since the code has been deleted. Signed-off-by: Randy Dunlap <randy.dunlap@oracle.com> Reported-by: "Robert P. J. Day" <rpjday@crashcourse.ca> Cc: Jens Axboe <axboe@kernel.dk> Signed-off-by: Jens Axboe <jaxboe@fusionio.com>
2010-02-18rbtree: Add support for augmented rbtreesPallipadi, Venkatesh
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 <venkatesh.pallipadi@intel.com> LKML-Reference: <20100210232343.GA11465@linux-os.sc.intel.com> Signed-off-by: Suresh Siddha <suresh.b.siddha@intel.com> Signed-off-by: H. Peter Anvin <hpa@zytor.com>
2009-06-12trivial: rbtree.txt: fix rb_entry() parameters in sample codeWang Tinggong
Reviewed-by: WANG Cong <xiyou.wangcong@gmail.com> Signed-off-by: Jiri Kosina <jkosina@suse.cz>
2009-06-12trivial: Documentation/rbtree.txt: cleanup kerneldoc of rbtree.txtfigo.zhang
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: Figo.zhang <figo.zhang@kolorific.com> Signed-off-by: Jiri Kosina <jkosina@suse.cz>
2007-02-11[PATCH] Documentation/rbtree.txtRob Landley
Documentation for lib/rbtree.c. Signed-off-by: Rob Landley <rob@landley.net> Cc: "Randy.Dunlap" <rdunlap@xenotime.net> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>