1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
5 #include <ccan/bitmap/bitmap.h>
9 #define BIT_ALIGN_DOWN(n) ((n) & ~(BITMAP_WORD_BITS - 1))
10 #define BIT_ALIGN_UP(n) BIT_ALIGN_DOWN((n) + BITMAP_WORD_BITS - 1)
12 void bitmap_zero_range(bitmap *bitmap, unsigned long n, unsigned long m)
14 unsigned long an = BIT_ALIGN_UP(n);
15 unsigned long am = BIT_ALIGN_DOWN(m);
16 bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS);
17 bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS));
22 BITMAP_WORD(bitmap, n) &= ~bitmap_bswap(headmask & tailmask);
27 BITMAP_WORD(bitmap, n) &= ~bitmap_bswap(headmask);
30 memset(&BITMAP_WORD(bitmap, an), 0,
31 (am - an) / BITMAP_WORD_BITS * sizeof(bitmap_word));
34 BITMAP_WORD(bitmap, m) &= ~bitmap_bswap(tailmask);
37 void bitmap_fill_range(bitmap *bitmap, unsigned long n, unsigned long m)
39 unsigned long an = BIT_ALIGN_UP(n);
40 unsigned long am = BIT_ALIGN_DOWN(m);
41 bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS);
42 bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS));
47 BITMAP_WORD(bitmap, n) |= bitmap_bswap(headmask & tailmask);
52 BITMAP_WORD(bitmap, n) |= bitmap_bswap(headmask);
55 memset(&BITMAP_WORD(bitmap, an), 0xff,
56 (am - an) / BITMAP_WORD_BITS * sizeof(bitmap_word));
59 BITMAP_WORD(bitmap, m) |= bitmap_bswap(tailmask);
62 static int bitmap_clz(bitmap_word w)
65 return __builtin_clzl(w);
68 bitmap_word mask = 1UL << (BITMAP_WORD_BITS - 1);
79 unsigned long bitmap_ffs(const bitmap *bitmap,
80 unsigned long n, unsigned long m)
82 unsigned long an = BIT_ALIGN_UP(n);
83 unsigned long am = BIT_ALIGN_DOWN(m);
84 bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS);
85 bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS));
90 bitmap_word w = bitmap_bswap(BITMAP_WORD(bitmap, n));
92 w &= (headmask & tailmask);
94 return w ? am + bitmap_clz(w) : m;
98 bitmap_word w = bitmap_bswap(BITMAP_WORD(bitmap, n));
103 return BIT_ALIGN_DOWN(n) + bitmap_clz(w);
107 bitmap_word w = bitmap_bswap(BITMAP_WORD(bitmap, an));
110 return an + bitmap_clz(w);
112 an += BITMAP_WORD_BITS;
116 bitmap_word w = bitmap_bswap(BITMAP_WORD(bitmap, m));
121 return am + bitmap_clz(w);