From: Maher Sanalla <msanalla@xxxxxxxxxx>
Removes ccan bitmap implementation, along with adjustments to the
ccan Makefile.
Signed-off-by: Maher Sanalla <msanalla@xxxxxxxxxx>
Reviewed-by: Avihai Horon <avihaih@xxxxxxxxxx>
Signed-off-by: Yishai Hadas <yishaih@xxxxxxxxxx>
---
ccan/CMakeLists.txt | 2 -
ccan/bitmap.c | 125 ---------------------------
ccan/bitmap.h | 239 ----------------------------------------------------
3 files changed, 366 deletions(-)
delete mode 100644 ccan/bitmap.c
delete mode 100644 ccan/bitmap.h
diff --git a/ccan/CMakeLists.txt b/ccan/CMakeLists.txt
index 5c5c6a2..d370a8e 100644
--- a/ccan/CMakeLists.txt
+++ b/ccan/CMakeLists.txt
@@ -1,6 +1,5 @@
publish_internal_headers(ccan
array_size.h
- bitmap.h
build_assert.h
check_type.h
compiler.h
@@ -13,7 +12,6 @@ publish_internal_headers(ccan
)
set(C_FILES
- bitmap.c
ilog.c
list.c
str.c
diff --git a/ccan/bitmap.c b/ccan/bitmap.c
deleted file mode 100644
index ea5531c..0000000
--- a/ccan/bitmap.c
+++ /dev/null
@@ -1,125 +0,0 @@
-/* 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
deleted file mode 100644
index ff0b8c8..0000000
--- a/ccan/bitmap.h
+++ /dev/null
@@ -1,239 +0,0 @@
-/* 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_ */
--
1.8.3.1
