summaryrefslogtreecommitdiff
path: root/rbtree.h
diff options
context:
space:
mode:
authorMiao Xie <miaox@cn.fujitsu.com>2013-07-03 21:25:13 +0800
committerChris Mason <chris.mason@fusionio.com>2013-07-03 14:06:54 -0400
commitd35300269709a0588b3252373c70eb94df7520fe (patch)
tree23d456e3f13677ff0dadb16848cdd67d3a55fe44 /rbtree.h
parent615f2867854c186a37cb2e2e5a2e13e9ed4ab0df (diff)
Btrfs-progs: introduce common insert/search/delete functions for rb-tree
In fact, the code of many rb-tree insert/search/delete functions is similar, so we can abstract them, and implement common functions for rb-tree, and then simplify them. Signed-off-by: Miao Xie <miaox@cn.fujitsu.com> Signed-off-by: Chris Mason <chris.mason@fusionio.com>
Diffstat (limited to 'rbtree.h')
-rw-r--r--rbtree.h24
1 files changed, 21 insertions, 3 deletions
diff --git a/rbtree.h b/rbtree.h
index 8f717a92..48e5157e 100644
--- a/rbtree.h
+++ b/rbtree.h
@@ -111,11 +111,8 @@ struct rb_node
struct rb_root
{
struct rb_node *rb_node;
- void (*rotate_notify)(struct rb_node *old_parent, struct rb_node *node);
-
};
-
#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
#define rb_color(r) ((r)->rb_parent_color & 1)
#define rb_is_red(r) (!rb_color(r))
@@ -161,4 +158,25 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
*rb_link = node;
}
+/* The common insert/search/free functions */
+typedef int (*rb_compare_nodes)(struct rb_node *node1, struct rb_node *node2);
+typedef int (*rb_compare_keys)(struct rb_node *node, void *key);
+typedef void (*rb_free_node)(struct rb_node *node);
+
+int rb_insert(struct rb_root *root, struct rb_node *node,
+ rb_compare_nodes comp);
+/*
+ * In some cases, we need return the next node if we don't find the node we
+ * specify. At this time, we can use next_ret.
+ */
+struct rb_node *rb_search(struct rb_root *root, void *key, rb_compare_keys comp,
+ struct rb_node **next_ret);
+void rb_free_nodes(struct rb_root *root, rb_free_node free_node);
+
+#define FREE_RB_BASED_TREE(name, free_func) \
+static void free_##name##_tree(struct rb_root *root) \
+{ \
+ rb_free_nodes(root, free_func); \
+}
+
#endif /* _LINUX_RBTREE_H */