summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLai Jiangshan <laijs@cn.fujitsu.com>2014-10-14 02:53:48 +0400
committerLinus Torvalds <torvalds@linux-foundation.org>2014-10-14 04:18:21 +0400
commita841b65921a959c759da6b5c8d5dc21966b4cf86 (patch)
tree0c6219d08ab58143375375a6e3802b1e7ed85701
parentf8da964dfbdca0eb14f9bf67be4ab6d256f90b7f (diff)
downloadlinux-a841b65921a959c759da6b5c8d5dc21966b4cf86.tar.xz
rbtree: add comment to rb_insert_augmented()
The comment is copied from Documentation/rbtree.txt, but this comment is so important that it should also be in the code. Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com> Acked-by: Michel Lespinasse <walken@google.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
-rw-r--r--include/linux/rbtree_augmented.h10
1 files changed, 10 insertions, 0 deletions
diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
index fea49b5da12a..378c5ee75f78 100644
--- a/include/linux/rbtree_augmented.h
+++ b/include/linux/rbtree_augmented.h
@@ -43,6 +43,16 @@ struct rb_augment_callbacks {
extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
+/*
+ * Fixup the rbtree and update the augmented information when rebalancing.
+ *
+ * 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.
+ * If rb_augment_inserted() rebalances the rbtree, it will callback into
+ * a user provided function to update the augmented information on the
+ * affected subtrees.
+ */
static inline void
rb_insert_augmented(struct rb_node *node, struct rb_root *root,
const struct rb_augment_callbacks *augment)