diff options
author | Mark Fasheh <mfasheh@suse.de> | 2016-01-20 13:49:25 -0800 |
---|---|---|
committer | David Sterba <dsterba@suse.com> | 2016-02-26 17:27:58 +0100 |
commit | 282dd33a432a890a99c33812c385a5086acac618 (patch) | |
tree | 8f41b25d4b8e914584597a78ee890801db7c2bda /rbtree_augmented.h | |
parent | 154d28dd99da6fd3aef2621ead327c09c0d87bb6 (diff) |
btrfs-progs: Import interval tree implemenation from Linux v4.0-rc7.
While I had the chance, I compared the rbtre code in btrfs-progs to that of
the latest kernel. No new bug fixes need importing, however rbtree.h and
rbtree_augmented.h get documentation updates
Signed-off-by: Mark Fasheh <mfasheh@suse.de>
Signed-off-by: David Sterba <dsterba@suse.com>
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) |