__rb_erase_color(child, parent, root);
}
-static void ext2fs_rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
-{
- struct rb_node *parent;
-
-up:
- func(node, data);
- parent = ext2fs_rb_parent(node);
- if (!parent)
- return;
-
- if (node == parent->rb_left && parent->rb_right)
- func(parent->rb_right, data);
- else if (parent->rb_left)
- func(parent->rb_left, data);
-
- node = parent;
- goto up;
-}
-
-/*
- * after inserting @node into the tree, update the tree to account for
- * both the new entry and any damage done by rebalance
- */
-void ext2fs_rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
-{
- if (node->rb_left)
- node = node->rb_left;
- else if (node->rb_right)
- node = node->rb_right;
-
- ext2fs_rb_augment_path(node, func, data);
-}
-
-/*
- * before removing the node, find the deepest node on the rebalance path
- * that will still be there after @node gets removed
- */
-struct rb_node *ext2fs_rb_augment_erase_begin(struct rb_node *node)
-{
- struct rb_node *deepest;
-
- if (!node->rb_right && !node->rb_left)
- deepest = ext2fs_rb_parent(node);
- else if (!node->rb_right)
- deepest = node->rb_left;
- else if (!node->rb_left)
- deepest = node->rb_right;
- else {
- deepest = ext2fs_rb_next(node);
- if (deepest->rb_right)
- deepest = deepest->rb_right;
- else if (ext2fs_rb_parent(deepest) != node)
- deepest = ext2fs_rb_parent(deepest);
- }
-
- return deepest;
-}
-
-/*
- * after removal, update the tree to account for the removed entry
- * and any rebalance damage.
- */
-void ext2fs_rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
-{
- if (node)
- ext2fs_rb_augment_path(node, func, data);
-}
-
/*
* This function returns the first node (in sort order) of the tree.
*/
extern void ext2fs_rb_insert_color(struct rb_node *, struct rb_root *);
extern void ext2fs_rb_erase(struct rb_node *, struct rb_root *);
-typedef void (*rb_augment_f)(struct rb_node *node, void *data);
-
-extern void ext2fs_rb_augment_insert(struct rb_node *node,
- rb_augment_f func, void *data);
-extern struct rb_node *ext2fs_rb_augment_erase_begin(struct rb_node *node);
-extern void ext2fs_rb_augment_erase_end(struct rb_node *node,
- rb_augment_f func, void *data);
-
/* Find logical next and previous nodes in a tree */
extern struct rb_node *ext2fs_rb_next(struct rb_node *);
extern struct rb_node *ext2fs_rb_prev(struct rb_node *);