path: root/rbtree_augmented.h
diff options
authorMark Fasheh <>2016-01-20 13:49:25 -0800
committerDavid Sterba <>2016-02-26 17:27:58 +0100
commit282dd33a432a890a99c33812c385a5086acac618 (patch)
tree8f41b25d4b8e914584597a78ee890801db7c2bda /rbtree_augmented.h
parent154d28dd99da6fd3aef2621ead327c09c0d87bb6 (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 <> Signed-off-by: David Sterba <>
Diffstat (limited to 'rbtree_augmented.h')
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)