diff options
Diffstat (limited to 'Documentation/core-api')
| -rw-r--r-- | Documentation/core-api/rbtree.rst | 27 |
1 files changed, 24 insertions, 3 deletions
diff --git a/Documentation/core-api/rbtree.rst b/Documentation/core-api/rbtree.rst index cce80e19087b..210045f128d6 100644 --- a/Documentation/core-api/rbtree.rst +++ b/Documentation/core-api/rbtree.rst @@ -257,8 +257,14 @@ When erasing a node, the user must call rb_erase_augmented() instead of rb_erase(). rb_erase_augmented() calls back into user provided functions to update the augmented information on affected subtrees. -In both cases, the callbacks are provided through struct rb_augment_callbacks. -3 callbacks must be defined: +Alternatively, rb_add_augmented_cached() performs the whole insertion into +a cached tree: it walks down to the insertion point, merges the new node's +augmented information into every node on that path, links the node and +rebalances. The new node's augmented information must already describe +the node alone when it is called. + +In all cases, the callbacks are provided through struct rb_augment_callbacks. +3 callbacks must be defined, plus a fourth one for rb_add_augmented_cached(): - A propagation callback, which updates the augmented value for a given node and its ancestors, up to a given stop point (or NULL to update @@ -271,6 +277,10 @@ 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. +- A merge callback, which folds the augmented value of a node being inserted + into the augmented value of one of its future ancestors. It is only used + by rb_add_augmented_cached(). + 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 @@ -395,8 +405,19 @@ Insertion/removal are defined using the following augmented callbacks:: old->__subtree_last = compute_subtree_last(old); } + static void augment_merge(struct rb_node *rb, struct rb_node *rb_new) + { + struct interval_tree_node *node = + rb_entry(rb, struct interval_tree_node, rb); + struct interval_tree_node *new = + rb_entry(rb_new, struct interval_tree_node, rb); + + if (node->__subtree_last < new->__subtree_last) + node->__subtree_last = new->__subtree_last; + } + static const struct rb_augment_callbacks augment_callbacks = { - augment_propagate, augment_copy, augment_rotate + augment_propagate, augment_copy, augment_rotate, augment_merge }; void interval_tree_insert(struct interval_tree_node *node, |