1 // SPDX-License-Identifier: GPL-2.0+
2 #ifndef __LINUX_BITMAP_H
3 #define __LINUX_BITMAP_H
4
5 #include <asm/types.h>
6 #include <linux/types.h>
7 #include <linux/bitops.h>
8
9 #define small_const_nbits(nbits) \
10 (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
11
bitmap_zero(unsigned long * dst,int nbits)12 static inline void bitmap_zero(unsigned long *dst, int nbits)
13 {
14 if (small_const_nbits(nbits)) {
15 *dst = 0UL;
16 } else {
17 int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
18
19 memset(dst, 0, len);
20 }
21 }
22
23 static inline unsigned long
find_next_bit(const unsigned long * addr,unsigned long size,unsigned long offset)24 find_next_bit(const unsigned long *addr, unsigned long size,
25 unsigned long offset)
26 {
27 const unsigned long *p = addr + BIT_WORD(offset);
28 unsigned long result = offset & ~(BITS_PER_LONG - 1);
29 unsigned long tmp;
30
31 if (offset >= size)
32 return size;
33 size -= result;
34 offset %= BITS_PER_LONG;
35 if (offset) {
36 tmp = *(p++);
37 tmp &= (~0UL << offset);
38 if (size < BITS_PER_LONG)
39 goto found_first;
40 if (tmp)
41 goto found_middle;
42 size -= BITS_PER_LONG;
43 result += BITS_PER_LONG;
44 }
45 while (size & ~(BITS_PER_LONG - 1)) {
46 tmp = *(p++);
47 if ((tmp))
48 goto found_middle;
49 result += BITS_PER_LONG;
50 size -= BITS_PER_LONG;
51 }
52 if (!size)
53 return result;
54 tmp = *p;
55
56 found_first:
57 tmp &= (~0UL >> (BITS_PER_LONG - size));
58 if (tmp == 0UL) /* Are any bits set? */
59 return result + size; /* Nope. */
60 found_middle:
61 return result + __ffs(tmp);
62 }
63
64 /*
65 * Find the first set bit in a memory region.
66 */
find_first_bit(const unsigned long * addr,unsigned long size)67 static inline unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
68 {
69 unsigned long idx;
70
71 for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
72 if (addr[idx])
73 return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
74 }
75
76 return size;
77 }
78
79 #define for_each_set_bit(bit, addr, size) \
80 for ((bit) = find_first_bit((addr), (size)); \
81 (bit) < (size); \
82 (bit) = find_next_bit((addr), (size), (bit) + 1))
83
84 #endif /* __LINUX_BITMAP_H */
85