1 /* SPDX-License-Identifier: GPL-2.0 */ 2 #ifndef _TOOLS_LINUX_BITMAP_H 3 #define _TOOLS_LINUX_BITMAP_H 4 5 #include <string.h> 6 #include <linux/bitops.h> 7 #include <linux/find.h> 8 #include <stdlib.h> 9 #include <linux/kernel.h> 10 11 #define DECLARE_BITMAP(name,bits) \ 12 unsigned long name[BITS_TO_LONGS(bits)] 13 14 unsigned int __bitmap_weight(const unsigned long *bitmap, int bits); 15 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, 16 const unsigned long *bitmap2, int bits); 17 bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, 18 const unsigned long *bitmap2, unsigned int bits); 19 bool __bitmap_equal(const unsigned long *bitmap1, 20 const unsigned long *bitmap2, unsigned int bits); 21 void bitmap_clear(unsigned long *map, unsigned int start, int len); 22 bool __bitmap_intersects(const unsigned long *bitmap1, 23 const unsigned long *bitmap2, unsigned int bits); 24 25 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1))) 26 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) 27 28 static inline void bitmap_zero(unsigned long *dst, unsigned int nbits) 29 { 30 if (small_const_nbits(nbits)) 31 *dst = 0UL; 32 else { 33 int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); 34 memset(dst, 0, len); 35 } 36 } 37 38 static inline void bitmap_fill(unsigned long *dst, unsigned int nbits) 39 { 40 unsigned int nlongs = BITS_TO_LONGS(nbits); 41 if (!small_const_nbits(nbits)) { 42 unsigned int len = (nlongs - 1) * sizeof(unsigned long); 43 memset(dst, 0xff, len); 44 } 45 dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits); 46 } 47 48 static inline bool bitmap_empty(const unsigned long *src, unsigned int nbits) 49 { 50 if (small_const_nbits(nbits)) 51 return ! (*src & BITMAP_LAST_WORD_MASK(nbits)); 52 53 return find_first_bit(src, nbits) == nbits; 54 } 55 56 static inline bool bitmap_full(const unsigned long *src, unsigned int nbits) 57 { 58 if (small_const_nbits(nbits)) 59 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits)); 60 61 return find_first_zero_bit(src, nbits) == nbits; 62 } 63 64 static inline unsigned int bitmap_weight(const unsigned long *src, unsigned int nbits) 65 { 66 if (small_const_nbits(nbits)) 67 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits)); 68 return __bitmap_weight(src, nbits); 69 } 70 71 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1, 72 const unsigned long *src2, unsigned int nbits) 73 { 74 if (small_const_nbits(nbits)) 75 *dst = *src1 | *src2; 76 else 77 __bitmap_or(dst, src1, src2, nbits); 78 } 79 80 /** 81 * test_and_set_bit - Set a bit and return its old value 82 * @nr: Bit to set 83 * @addr: Address to count from 84 */ 85 static inline int test_and_set_bit(int nr, unsigned long *addr) 86 { 87 unsigned long mask = BIT_MASK(nr); 88 unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); 89 unsigned long old; 90 91 old = *p; 92 *p = old | mask; 93 94 return (old & mask) != 0; 95 } 96 97 /** 98 * test_and_clear_bit - Clear a bit and return its old value 99 * @nr: Bit to clear 100 * @addr: Address to count from 101 */ 102 static inline int test_and_clear_bit(int nr, unsigned long *addr) 103 { 104 unsigned long mask = BIT_MASK(nr); 105 unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); 106 unsigned long old; 107 108 old = *p; 109 *p = old & ~mask; 110 111 return (old & mask) != 0; 112 } 113 114 /** 115 * bitmap_zalloc - Allocate bitmap 116 * @nbits: Number of bits 117 */ 118 static inline unsigned long *bitmap_zalloc(int nbits) 119 { 120 return calloc(1, BITS_TO_LONGS(nbits) * sizeof(unsigned long)); 121 } 122 123 /* 124 * bitmap_free - Free bitmap 125 * @bitmap: pointer to bitmap 126 */ 127 static inline void bitmap_free(unsigned long *bitmap) 128 { 129 free(bitmap); 130 } 131 132 /* 133 * bitmap_scnprintf - print bitmap list into buffer 134 * @bitmap: bitmap 135 * @nbits: size of bitmap 136 * @buf: buffer to store output 137 * @size: size of @buf 138 */ 139 size_t bitmap_scnprintf(unsigned long *bitmap, unsigned int nbits, 140 char *buf, size_t size); 141 142 /** 143 * bitmap_and - Do logical and on bitmaps 144 * @dst: resulting bitmap 145 * @src1: operand 1 146 * @src2: operand 2 147 * @nbits: size of bitmap 148 */ 149 static inline bool bitmap_and(unsigned long *dst, const unsigned long *src1, 150 const unsigned long *src2, unsigned int nbits) 151 { 152 if (small_const_nbits(nbits)) 153 return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0; 154 return __bitmap_and(dst, src1, src2, nbits); 155 } 156 157 #ifdef __LITTLE_ENDIAN 158 #define BITMAP_MEM_ALIGNMENT 8 159 #else 160 #define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long)) 161 #endif 162 #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1) 163 #define IS_ALIGNED(x, a) (((x) & ((typeof(x))(a) - 1)) == 0) 164 165 static inline bool bitmap_equal(const unsigned long *src1, 166 const unsigned long *src2, unsigned int nbits) 167 { 168 if (small_const_nbits(nbits)) 169 return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits)); 170 if (__builtin_constant_p(nbits & BITMAP_MEM_MASK) && 171 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT)) 172 return !memcmp(src1, src2, nbits / 8); 173 return __bitmap_equal(src1, src2, nbits); 174 } 175 176 static inline bool bitmap_intersects(const unsigned long *src1, 177 const unsigned long *src2, 178 unsigned int nbits) 179 { 180 if (small_const_nbits(nbits)) 181 return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0; 182 else 183 return __bitmap_intersects(src1, src2, nbits); 184 } 185 186 #endif /* _TOOLS_LINUX_BITMAP_H */ 187