aboutsummaryrefslogtreecommitdiffstats
path: root/Documentation/rbtree.txt
diff options
context:
space:
mode:
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
196Augmented rbtree is an rbtree with "some" additional data stored in each node. 196Augmented rbtree is an rbtree with "some" additional data stored in each node.
197This data can be used to augment some new functionality to rbtree. 197This data can be used to augment some new functionality to rbtree.
198Augmented rbtree is an optional feature built on top of basic rbtree 198Augmented rbtree is an optional feature built on top of basic rbtree
199infrastructure. rbtree user who wants this feature will have an augment 199infrastructure. An rbtree user who wants this feature will have to call the
200callback function in rb_root initialized. 200augmentation functions with the user provided augmentation callback
201 201when inserting and erasing nodes.
202This callback function will be called from rbtree core routines whenever 202
203a node has a change in one or both of its children. It is the responsibility 203On insertion, the user must call rb_augment_insert() once the new node is in
204of the callback function to recalculate the additional data that is in the 204place. This will cause the augmentation function callback to be called for
205rb node using new children information. Note that if this new additional 205each node between the new node and the root which has been affected by the
206data affects the parent node's additional data, then callback function has 206insertion.
207to handle it and do the recursive updates. 207
208When erasing a node, the user must call rb_augment_erase_begin() first to
209retrieve the deepest node on the rebalance path. Then, after erasing the
210original node, the user must call rb_augment_erase_end() with the deepest
211node found earlier. This will cause the augmentation function to be called
212for each affected node between the deepest node and the root.
208 213
209 214
210Interval tree is an example of augmented rb tree. Reference - 215Interval tree is an example of augmented rb tree. Reference -