summaryrefslogtreecommitdiffstats
path: root/include
diff options
context:
space:
mode:
authorIlya Dryomov <idryomov@gmail.com>2017-06-19 12:18:05 +0200
committerIlya Dryomov <idryomov@gmail.com>2017-07-07 17:25:17 +0200
commit76f827a7b1faaaebc53f89d184e95ea3a0b8dd71 (patch)
treec37c66afbd422e72ec26e4642193eff4270610fd /include
parentlibceph: avoid unnecessary pi lookups in calc_target() (diff)
downloadlinux-76f827a7b1faaaebc53f89d184e95ea3a0b8dd71.tar.xz
linux-76f827a7b1faaaebc53f89d184e95ea3a0b8dd71.zip
libceph: make DEFINE_RB_* helpers more general
Initially for ceph_pg_mapping, ceph_spg_mapping and ceph_hobject_id, compared with ceph_pg_compare(), ceph_spg_compare() and hoid_compare() respectively. Signed-off-by: Ilya Dryomov <idryomov@gmail.com>
Diffstat (limited to 'include')
-rw-r--r--include/linux/ceph/libceph.h49
1 files changed, 37 insertions, 12 deletions
diff --git a/include/linux/ceph/libceph.h b/include/linux/ceph/libceph.h
index 3229ae6c7846..8a79587e1317 100644
--- a/include/linux/ceph/libceph.h
+++ b/include/linux/ceph/libceph.h
@@ -184,10 +184,11 @@ 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) \
+#define RB_BYVAL(a) (a)
+#define RB_BYPTR(a) (&(a))
+#define RB_CMP3WAY(a, b) ((a) < (b) ? -1 : (a) > (b))
+
+#define DEFINE_RB_INSDEL_FUNCS2(name, type, keyfld, cmpexp, keyexp, nodefld) \
static void insert_##name(struct rb_root *root, type *t) \
{ \
struct rb_node **n = &root->rb_node; \
@@ -197,11 +198,13 @@ static void insert_##name(struct rb_root *root, type *t) \
\
while (*n) { \
type *cur = rb_entry(*n, type, nodefld); \
+ int cmp; \
\
parent = *n; \
- if (t->keyfld < cur->keyfld) \
+ cmp = cmpexp(keyexp(t->keyfld), keyexp(cur->keyfld)); \
+ if (cmp < 0) \
n = &(*n)->rb_left; \
- else if (t->keyfld > cur->keyfld) \
+ else if (cmp > 0) \
n = &(*n)->rb_right; \
else \
BUG(); \
@@ -217,19 +220,24 @@ static void erase_##name(struct rb_root *root, type *t) \
RB_CLEAR_NODE(&t->nodefld); \
}
-#define DEFINE_RB_LOOKUP_FUNC(name, type, keyfld, nodefld) \
-extern type __lookup_##name##_key; \
-static type *lookup_##name(struct rb_root *root, \
- typeof(__lookup_##name##_key.keyfld) key) \
+/*
+ * @lookup_param_type is a parameter and not constructed from (@type,
+ * @keyfld) with typeof() because adding const is too unwieldy.
+ */
+#define DEFINE_RB_LOOKUP_FUNC2(name, type, keyfld, cmpexp, keyexp, \
+ lookup_param_type, nodefld) \
+static type *lookup_##name(struct rb_root *root, lookup_param_type key) \
{ \
struct rb_node *n = root->rb_node; \
\
while (n) { \
type *cur = rb_entry(n, type, nodefld); \
+ int cmp; \
\
- if (key < cur->keyfld) \
+ cmp = cmpexp(key, keyexp(cur->keyfld)); \
+ if (cmp < 0) \
n = n->rb_left; \
- else if (key > cur->keyfld) \
+ else if (cmp > 0) \
n = n->rb_right; \
else \
return cur; \
@@ -238,6 +246,23 @@ static type *lookup_##name(struct rb_root *root, \
return NULL; \
}
+#define DEFINE_RB_FUNCS2(name, type, keyfld, cmpexp, keyexp, \
+ lookup_param_type, nodefld) \
+DEFINE_RB_INSDEL_FUNCS2(name, type, keyfld, cmpexp, keyexp, nodefld) \
+DEFINE_RB_LOOKUP_FUNC2(name, type, keyfld, cmpexp, keyexp, \
+ lookup_param_type, nodefld)
+
+/*
+ * Shorthands for integer keys.
+ */
+#define DEFINE_RB_INSDEL_FUNCS(name, type, keyfld, nodefld) \
+DEFINE_RB_INSDEL_FUNCS2(name, type, keyfld, RB_CMP3WAY, RB_BYVAL, nodefld)
+
+#define DEFINE_RB_LOOKUP_FUNC(name, type, keyfld, nodefld) \
+extern type __lookup_##name##_key; \
+DEFINE_RB_LOOKUP_FUNC2(name, type, keyfld, RB_CMP3WAY, RB_BYVAL, \
+ typeof(__lookup_##name##_key.keyfld), nodefld)
+
#define DEFINE_RB_FUNCS(name, type, keyfld, nodefld) \
DEFINE_RB_INSDEL_FUNCS(name, type, keyfld, nodefld) \
DEFINE_RB_LOOKUP_FUNC(name, type, keyfld, nodefld)