libceph: DEFINE_RB_FUNCS macro

Given

    struct foo {
        u64 id;
        struct rb_node bar_node;
    };

generate insert_bar(), erase_bar() and lookup_bar() functions with

    DEFINE_RB_FUNCS(bar, struct foo, id, bar_node)

The key is assumed to be an integer (u64, int, etc), compared with
< and >.  nodefld has to be initialized with RB_CLEAR_NODE().

Start using it for MDS, MON and OSD requests and OSD sessions.

Signed-off-by: Ilya Dryomov <idryomov@gmail.com>

1 files changed, 57 insertions, 0 deletions

diff --git a/include/linux/ceph/libceph.h b/include/linux/ceph/libceph.h
index db92a8d4926e..690985daad1c 100644
--- a/include/linux/ceph/libceph.h
+++ b/include/linux/ceph/libceph.h
@@ -180,6 +180,63 @@ static inline int calc_pages_for(u64 off, u64 len)
                 (off >> PAGE_SHIFT);
 }
 
+/*
+ * These are not meant to be generic - an integer key is assumed.
+ */
+#define DEFINE_RB_INSDEL_FUNCS(name, type, keyfld, nodefld)             \
+static void insert_##name(struct rb_root *root, type *t)                \
+{                                                                       \
+        struct rb_node **n = &root->rb_node;                            \
+        struct rb_node *parent = NULL;                                  \
+                                                                        \
+        BUG_ON(!RB_EMPTY_NODE(&t->nodefld));                            \
+                                                                        \
+        while (*n) {                                                    \
+                type *cur = rb_entry(*n, type, nodefld);                \
+                                                                        \
+                parent = *n;                                            \
+                if (t->keyfld < cur->keyfld)                            \
+                        n = &(*n)->rb_left;                             \
+                else if (t->keyfld > cur->keyfld)                       \
+                        n = &(*n)->rb_right;                            \
+                else                                                    \
+                        BUG();                                          \
+        }                                                               \
+                                                                        \
+        rb_link_node(&t->nodefld, parent, n);                           \
+        rb_insert_color(&t->nodefld, root);                             \
+}                                                                       \
+static void erase_##name(struct rb_root *root, type *t)                 \
+{                                                                       \
+        BUG_ON(RB_EMPTY_NODE(&t->nodefld));                             \
+        rb_erase(&t->nodefld, root);                                    \
+        RB_CLEAR_NODE(&t->nodefld);                                     \
+}
+
+#define DEFINE_RB_LOOKUP_FUNC(name, type, keyfld, nodefld)              \
+static type *lookup_##name(struct rb_root *root,                        \
+                           typeof(((type *)0)->keyfld) key)             \
+{                                                                       \
+        struct rb_node *n = root->rb_node;                              \
+                                                                        \
+        while (n) {                                                     \
+                type *cur = rb_entry(n, type, nodefld);                 \
+                                                                        \
+                if (key < cur->keyfld)                                  \
+                        n = n->rb_left;                                 \
+                else if (key > cur->keyfld)                             \
+                        n = n->rb_right;                                \
+                else                                                    \
+                        return cur;                                     \
+        }                                                               \
+                                                                        \
+        return NULL;                                                    \
+}
+
+#define DEFINE_RB_FUNCS(name, type, keyfld, nodefld)                    \
+DEFINE_RB_INSDEL_FUNCS(name, type, keyfld, nodefld)                     \
+DEFINE_RB_LOOKUP_FUNC(name, type, keyfld, nodefld)
+
 extern struct kmem_cache *ceph_inode_cachep;
 extern struct kmem_cache *ceph_cap_cachep;
 extern struct kmem_cache *ceph_cap_flush_cachep;