path: root/Documentation/rbtree.txt
diff options
authorMichel Lespinasse <>2012-10-08 16:31:33 -0700
committerLinus Torvalds <>2012-10-09 16:22:40 +0900
commit9c079add0d0f45220f4bb37febf0621137ec2d38 (patch)
treece6ba6d7e2d517a2004de856c882f2a08af12be2 /Documentation/rbtree.txt
parent147e615f83c2c36caf89e7a3bf78090ade6f266c (diff)
rbtree: move augmented rbtree functionality to rbtree_augmented.h
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 <>
Diffstat (limited to 'Documentation/rbtree.txt')
1 files changed, 13 insertions, 0 deletions
diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt
index 0a0b6dce3e08..61b6c48871a0 100644
--- a/Documentation/rbtree.txt
+++ b/Documentation/rbtree.txt
@@ -202,6 +202,14 @@ An rbtree user who wants this feature will have to call the augmentation
functions with the user provided augmentation callback when inserting
and erasing nodes.
+C files implementing augmented rbtree manipulation must include
+<linux/rbtree_augmented.h> instead of <linus/rbtree.h>. Note that
+linux/rbtree_augmented.h exposes some rbtree implementations details
+you are not expected to rely on; please stick to the documented APIs
+there and do not include <linux/rbtree_augmented.h> from header files
+either so as to minimize chances of your users accidentally relying on
+such implementation details.
On insertion, the user must update the augmented information on the path
leading to the inserted node, then call rb_link_node() as usual and
rb_augment_inserted() instead of the usual rb_insert_color() call.
@@ -227,6 +235,11 @@ In both cases, the callbacks are provided through struct rb_augment_callbacks.
subtree to a newly assigned subtree root AND recomputes the augmented
information for the former subtree root.
+The compiled code for rb_erase_augmented() may inline the propagation and
+copy callbacks, which results in a large function, so each augmented rbtree
+user should have a single rb_erase_augmented() call site in order to limit
+compiled code size.
Sample usage: