diff options
Diffstat (limited to 'rbtree_augmented.h')
| -rw-r--r-- | rbtree_augmented.h | 10 |
1 files changed, 10 insertions, 0 deletions
diff --git a/rbtree_augmented.h b/rbtree_augmented.h index cbc96398..5d269784 100644 --- a/rbtree_augmented.h +++ b/rbtree_augmented.h @@ -46,6 +46,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) |