summaryrefslogtreecommitdiffstats
path: root/Documentation/rbtree.txt
diff options
context:
space:
mode:
authorSasha Levin <levinsasha928@gmail.com>2011-07-24 11:23:20 +0300
committerLinus Torvalds <torvalds@linux-foundation.org>2011-07-24 10:03:05 -0700
commit2f175074e6811974ee77ddeb026f4d21aa3eca4d (patch)
tree845cb1cc70e52bef69b9848578be720ce3d34a2a /Documentation/rbtree.txt
parent81d67439855a7f928d90965d832aa4f2fb677342 (diff)
downloadlinux-2f175074e6811974ee77ddeb026f4d21aa3eca4d.tar.gz
linux-2f175074e6811974ee77ddeb026f4d21aa3eca4d.tar.bz2
linux-2f175074e6811974ee77ddeb026f4d21aa3eca4d.zip
Documentation: Update augmented rbtree documentation
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>
Diffstat (limited to 'Documentation/rbtree.txt')
-rw-r--r--Documentation/rbtree.txt23
1 files changed, 14 insertions, 9 deletions
diff --git a/Documentation/rbtree.txt b/Documentation/rbtree.txt
index 19f8278c3854..8d32d85a5234 100644
--- a/Documentation/rbtree.txt
+++ b/Documentation/rbtree.txt
@@ -196,15 +196,20 @@ Support for Augmented rbtrees
Augmented rbtree is an rbtree with "some" additional data stored in each node.
This data can be used to augment some new functionality to rbtree.
Augmented rbtree is an optional feature built on top of basic rbtree
-infrastructure. rbtree user who wants this feature will have an augment
-callback function in rb_root initialized.
-
-This callback function will be called from rbtree core routines whenever
-a node has a change in one or both of its children. It is the responsibility
-of the callback function to recalculate the additional data that is in the
-rb node using new children information. Note that if this new additional
-data affects the parent node's additional data, then callback function has
-to handle it and do the recursive updates.
+infrastructure. 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.
+
+On insertion, the user must call rb_augment_insert() once the new node is in
+place. This will cause the augmentation function callback to be called for
+each node between the new node and the root which has been affected by the
+insertion.
+
+When erasing a node, the user must call rb_augment_erase_begin() first to
+retrieve the deepest node on the rebalance path. Then, after erasing the
+original node, the user must call rb_augment_erase_end() with the deepest
+node found earlier. This will cause the augmentation function to be called
+for each affected node between the deepest node and the root.
Interval tree is an example of augmented rb tree. Reference -