On Mon, Feb 26, 2018 at 04:40:40PM +0800, Yixian Liu wrote:
> This patch adds bitmap.c and bitmap.h to rdma-core/ccan to
> support bitmap operation, as they depends on endian.h,
> therefore, endian.h also is added.
Don't really want to include endian.h, and this is a non-starter:
> +add_definitions("-DHAVE_LITTLE_ENDIAN=1")
> +
And this header gets -Wshadow warnings.
Use this patch instead please:
>From 90e2ccb1d7294bc695c64dc3f8a36cd47f8021d0 Mon Sep 17 00:00:00 2001
From: Yixian Liu <liuyixian@xxxxxxxxxx>
Date: Mon, 26 Feb 2018 16:40:40 +0800
Subject: [PATCH] ccan: Add bitmap support for rdma-core
This patch adds bitmap.c and bitmap.h to rdma-core/ccan to
support bitmap operations.
The code is modified from the ccan version to work with -Wshadow and
to eliminate the need for endianness conversions. Ww
Signed-off-by: Yixian Liu <liuyixian@xxxxxxxxxx>
Signed-off-by: Jason Gunthorpe <jgg@xxxxxxxxxxxx>
---
buildlib/config.h.in | 1 +
ccan/CMakeLists.txt | 2 +
ccan/bitmap.c | 125 +++++++++++++++++++++++++++
ccan/bitmap.h | 239 +++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 367 insertions(+)
create mode 100644 ccan/bitmap.c
create mode 100644 ccan/bitmap.h
diff --git a/buildlib/config.h.in b/buildlib/config.h.in
index 316b712c0d0da9..f10c02ecbaf201 100644
--- a/buildlib/config.h.in
+++ b/buildlib/config.h.in
@@ -5,6 +5,7 @@
#define HAVE_BUILTIN_TYPES_COMPATIBLE_P 1
#define HAVE_TYPEOF 1
#define HAVE_ISBLANK 1
+#define HAVE_BUILTIN_CLZL 1
// FIXME: Remove this, The cmake version hard-requires new style CLOEXEC support
#define STREAM_CLOEXEC "e"
diff --git a/ccan/CMakeLists.txt b/ccan/CMakeLists.txt
index b5de515eb9ba17..1793af73988f79 100644
--- a/ccan/CMakeLists.txt
+++ b/ccan/CMakeLists.txt
@@ -1,4 +1,5 @@
publish_internal_headers(ccan
+ bitmap.h
build_assert.h
check_type.h
container_of.h
@@ -9,6 +10,7 @@ publish_internal_headers(ccan
)
set(C_FILES
+ bitmap.c
list.c
str.c
)
diff --git a/ccan/bitmap.c b/ccan/bitmap.c
new file mode 100644
index 00000000000000..ea5531cd75b691
--- /dev/null
+++ b/ccan/bitmap.c
@@ -0,0 +1,125 @@
+/* Licensed under LGPLv2.1+ - see LICENSE file for details */
+
+#include "config.h"
+
+#include <ccan/bitmap.h>
+
+#include <assert.h>
+
+#define BIT_ALIGN_DOWN(n) ((n) & ~(BITMAP_WORD_BITS - 1))
+#define BIT_ALIGN_UP(n) BIT_ALIGN_DOWN((n) + BITMAP_WORD_BITS - 1)
+
+void bitmap_zero_range(bitmap *bmap, unsigned long n, unsigned long m)
+{
+ unsigned long an = BIT_ALIGN_UP(n);
+ unsigned long am = BIT_ALIGN_DOWN(m);
+ bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS);
+ bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS));
+
+ assert(m >= n);
+
+ if (am < an) {
+ BITMAP_WORD(bmap, n) &= ~bitmap_bswap(headmask & tailmask);
+ return;
+ }
+
+ if (an > n)
+ BITMAP_WORD(bmap, n) &= ~bitmap_bswap(headmask);
+
+ if (am > an)
+ memset(&BITMAP_WORD(bmap, an), 0,
+ (am - an) / BITMAP_WORD_BITS * sizeof(bitmap_word));
+
+ if (m > am)
+ BITMAP_WORD(bmap, m) &= ~bitmap_bswap(tailmask);
+}
+
+void bitmap_fill_range(bitmap *bmap, unsigned long n, unsigned long m)
+{
+ unsigned long an = BIT_ALIGN_UP(n);
+ unsigned long am = BIT_ALIGN_DOWN(m);
+ bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS);
+ bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS));
+
+ assert(m >= n);
+
+ if (am < an) {
+ BITMAP_WORD(bmap, n) |= bitmap_bswap(headmask & tailmask);
+ return;
+ }
+
+ if (an > n)
+ BITMAP_WORD(bmap, n) |= bitmap_bswap(headmask);
+
+ if (am > an)
+ memset(&BITMAP_WORD(bmap, an), 0xff,
+ (am - an) / BITMAP_WORD_BITS * sizeof(bitmap_word));
+
+ if (m > am)
+ BITMAP_WORD(bmap, m) |= bitmap_bswap(tailmask);
+}
+
+static int bitmap_clz(bitmap_word w)
+{
+#if HAVE_BUILTIN_CLZL
+ return __builtin_clzl(w);
+#else
+ int lz = 0;
+ bitmap_word mask = 1UL << (BITMAP_WORD_BITS - 1);
+
+ while (!(w & mask)) {
+ lz++;
+ mask >>= 1;
+ }
+
+ return lz;
+#endif
+}
+
+unsigned long bitmap_ffs(const bitmap *bmap,
+ unsigned long n, unsigned long m)
+{
+ unsigned long an = BIT_ALIGN_UP(n);
+ unsigned long am = BIT_ALIGN_DOWN(m);
+ bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS);
+ bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS));
+
+ assert(m >= n);
+
+ if (am < an) {
+ bitmap_word w = bitmap_bswap(BITMAP_WORD(bmap, n));
+
+ w &= (headmask & tailmask);
+
+ return w ? am + bitmap_clz(w) : m;
+ }
+
+ if (an > n) {
+ bitmap_word w = bitmap_bswap(BITMAP_WORD(bmap, n));
+
+ w &= headmask;
+
+ if (w)
+ return BIT_ALIGN_DOWN(n) + bitmap_clz(w);
+ }
+
+ while (an < am) {
+ bitmap_word w = bitmap_bswap(BITMAP_WORD(bmap, an));
+
+ if (w)
+ return an + bitmap_clz(w);
+
+ an += BITMAP_WORD_BITS;
+ }
+
+ if (m > am) {
+ bitmap_word w = bitmap_bswap(BITMAP_WORD(bmap, m));
+
+ w &= tailmask;
+
+ if (w)
+ return am + bitmap_clz(w);
+ }
+
+ return m;
+}
diff --git a/ccan/bitmap.h b/ccan/bitmap.h
new file mode 100644
index 00000000000000..ff0b8c83da46b1
--- /dev/null
+++ b/ccan/bitmap.h
@@ -0,0 +1,239 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
+#ifndef CCAN_BITMAP_H_
+#define CCAN_BITMAP_H_
+
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+#include <limits.h>
+
+typedef unsigned long bitmap_word;
+
+#define BITMAP_WORD_BITS (sizeof(bitmap_word) * CHAR_BIT)
+#define BITMAP_NWORDS(_n) \
+ (((_n) + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
+
+/*
+ * We wrap each word in a structure for type checking.
+ */
+typedef struct {
+ bitmap_word w;
+} bitmap;
+
+#define BITMAP_DECLARE(_name, _nbits) \
+ bitmap (_name)[BITMAP_NWORDS(_nbits)]
+
+static inline size_t bitmap_sizeof(unsigned long nbits)
+{
+ return BITMAP_NWORDS(nbits) * sizeof(bitmap_word);
+}
+
+static inline bitmap_word bitmap_bswap(bitmap_word w)
+{
+ /* We do not need to have the bitmap in any specific endianness */
+ return w;
+}
+
+#define BITMAP_WORD(_bm, _n) ((_bm)[(_n) / BITMAP_WORD_BITS].w)
+#define BITMAP_WORDBIT(_n) \
+ (bitmap_bswap(1UL << (BITMAP_WORD_BITS - ((_n) % BITMAP_WORD_BITS) - 1)))
+
+#define BITMAP_HEADWORDS(_nbits) \
+ ((_nbits) / BITMAP_WORD_BITS)
+#define BITMAP_HEADBYTES(_nbits) \
+ (BITMAP_HEADWORDS(_nbits) * sizeof(bitmap_word))
+
+#define BITMAP_TAILWORD(_bm, _nbits) \
+ ((_bm)[BITMAP_HEADWORDS(_nbits)].w)
+#define BITMAP_HASTAIL(_nbits) (((_nbits) % BITMAP_WORD_BITS) != 0)
+#define BITMAP_TAILBITS(_nbits) \
+ (bitmap_bswap(~(-1UL >> ((_nbits) % BITMAP_WORD_BITS))))
+#define BITMAP_TAIL(_bm, _nbits) \
+ (BITMAP_TAILWORD(_bm, _nbits) & BITMAP_TAILBITS(_nbits))
+
+static inline void bitmap_set_bit(bitmap *bmap, unsigned long n)
+{
+ BITMAP_WORD(bmap, n) |= BITMAP_WORDBIT(n);
+}
+
+static inline void bitmap_clear_bit(bitmap *bmap, unsigned long n)
+{
+ BITMAP_WORD(bmap, n) &= ~BITMAP_WORDBIT(n);
+}
+
+static inline void bitmap_change_bit(bitmap *bmap, unsigned long n)
+{
+ BITMAP_WORD(bmap, n) ^= BITMAP_WORDBIT(n);
+}
+
+static inline bool bitmap_test_bit(const bitmap *bmap, unsigned long n)
+{
+ return !!(BITMAP_WORD(bmap, n) & BITMAP_WORDBIT(n));
+}
+
+void bitmap_zero_range(bitmap *bmap, unsigned long n, unsigned long m);
+void bitmap_fill_range(bitmap *bmap, unsigned long n, unsigned long m);
+
+static inline void bitmap_zero(bitmap *bmap, unsigned long nbits)
+{
+ memset(bmap, 0, bitmap_sizeof(nbits));
+}
+
+static inline void bitmap_fill(bitmap *bmap, unsigned long nbits)
+{
+ memset(bmap, 0xff, bitmap_sizeof(nbits));
+}
+
+static inline void bitmap_copy(bitmap *dst, const bitmap *src,
+ unsigned long nbits)
+{
+ memcpy(dst, src, bitmap_sizeof(nbits));
+}
+
+#define BITMAP_DEF_BINOP(_name, _op) \
+ static inline void bitmap_##_name(bitmap *dst, bitmap *src1, bitmap *src2, \
+ unsigned long nbits) \
+ { \
+ unsigned long i = 0; \
+ for (i = 0; i < BITMAP_NWORDS(nbits); i++) { \
+ dst[i].w = src1[i].w _op src2[i].w; \
+ } \
+ }
+
+BITMAP_DEF_BINOP(and, &)
+BITMAP_DEF_BINOP(or, |)
+BITMAP_DEF_BINOP(xor, ^)
+BITMAP_DEF_BINOP(andnot, & ~)
+
+#undef BITMAP_DEF_BINOP
+
+static inline void bitmap_complement(bitmap *dst, const bitmap *src,
+ unsigned long nbits)
+{
+ unsigned long i;
+
+ for (i = 0; i < BITMAP_NWORDS(nbits); i++)
+ dst[i].w = ~src[i].w;
+}
+
+static inline bool bitmap_equal(const bitmap *src1, const bitmap *src2,
+ unsigned long nbits)
+{
+ return (memcmp(src1, src2, BITMAP_HEADBYTES(nbits)) == 0)
+ && (!BITMAP_HASTAIL(nbits)
+ || (BITMAP_TAIL(src1, nbits) == BITMAP_TAIL(src2, nbits)));
+}
+
+static inline bool bitmap_intersects(const bitmap *src1, const bitmap *src2,
+ unsigned long nbits)
+{
+ unsigned long i;
+
+ for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
+ if (src1[i].w & src2[i].w)
+ return true;
+ }
+ if (BITMAP_HASTAIL(nbits) &&
+ (BITMAP_TAIL(src1, nbits) & BITMAP_TAIL(src2, nbits)))
+ return true;
+ return false;
+}
+
+static inline bool bitmap_subset(const bitmap *src1, const bitmap *src2,
+ unsigned long nbits)
+{
+ unsigned long i;
+
+ for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
+ if (src1[i].w & ~src2[i].w)
+ return false;
+ }
+ if (BITMAP_HASTAIL(nbits) &&
+ (BITMAP_TAIL(src1, nbits) & ~BITMAP_TAIL(src2, nbits)))
+ return false;
+ return true;
+}
+
+static inline bool bitmap_full(const bitmap *bmap, unsigned long nbits)
+{
+ unsigned long i;
+
+ for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
+ if (bmap[i].w != -1UL)
+ return false;
+ }
+ if (BITMAP_HASTAIL(nbits) &&
+ (BITMAP_TAIL(bmap, nbits) != BITMAP_TAILBITS(nbits)))
+ return false;
+
+ return true;
+}
+
+static inline bool bitmap_empty(const bitmap *bmap, unsigned long nbits)
+{
+ unsigned long i;
+
+ for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
+ if (bmap[i].w != 0)
+ return false;
+ }
+ if (BITMAP_HASTAIL(nbits) && (BITMAP_TAIL(bmap, nbits) != 0))
+ return false;
+
+ return true;
+}
+
+unsigned long bitmap_ffs(const bitmap *bmap,
+ unsigned long n, unsigned long m);
+
+/*
+ * Allocation functions
+ */
+static inline bitmap *bitmap_alloc(unsigned long nbits)
+{
+ return malloc(bitmap_sizeof(nbits));
+}
+
+static inline bitmap *bitmap_alloc0(unsigned long nbits)
+{
+ bitmap *bmap;
+
+ bmap = bitmap_alloc(nbits);
+ if (bmap)
+ bitmap_zero(bmap, nbits);
+ return bmap;
+}
+
+static inline bitmap *bitmap_alloc1(unsigned long nbits)
+{
+ bitmap *bmap;
+
+ bmap = bitmap_alloc(nbits);
+ if (bmap)
+ bitmap_fill(bmap, nbits);
+ return bmap;
+}
+
+static inline bitmap *bitmap_realloc0(bitmap *bmap, unsigned long obits,
+ unsigned long nbits)
+{
+ bmap = realloc(bmap, bitmap_sizeof(nbits));
+
+ if ((nbits > obits) && bmap)
+ bitmap_zero_range(bmap, obits, nbits);
+
+ return bmap;
+}
+
+static inline bitmap *bitmap_realloc1(bitmap *bmap, unsigned long obits,
+ unsigned long nbits)
+{
+ bmap = realloc(bmap, bitmap_sizeof(nbits));
+
+ if ((nbits > obits) && bmap)
+ bitmap_fill_range(bmap, obits, nbits);
+
+ return bmap;
+}
+
+#endif /* CCAN_BITMAP_H_ */
--
2.16.1
--
To unsubscribe from this list: send the line "unsubscribe linux-rdma" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
