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/align.h> 7 #include <linux/bitops.h> 8 #include <linux/find.h> 9 #include <stdlib.h> 10 #include <linux/kernel.h> 11 12 #define DECLARE_BITMAP(name,bits) \ 13 unsigned long name[BITS_TO_LONGS(bits)] 14 15 unsigned int __bitmap_weight(const unsigned long *bitmap, int bits); 16 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, 17 const unsigned long *bitmap2, int bits); 18 bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, 19 const unsigned long *bitmap2, unsigned int bits); 20 bool __bitmap_equal(const unsigned long *bitmap1, 21 const unsigned long *bitmap2, unsigned int bits); 22 void __bitmap_clear(unsigned long *map, unsigned int start, int len); 23 bool __bitmap_intersects(const unsigned long *bitmap1, 24 const unsigned long *bitmap2, unsigned int bits); 25 26 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1))) 27 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) 28 29 #define bitmap_size(nbits) (ALIGN(nbits, BITS_PER_LONG) / BITS_PER_BYTE) 30 31 static inline void bitmap_zero(unsigned long *dst, unsigned int nbits) 32 { 33 if (small_const_nbits(nbits)) 34 *dst = 0UL; 35 else { 36 memset(dst, 0, bitmap_size(nbits)); 37 } 38 } 39 40 static inline void bitmap_fill(unsigned long *dst, unsigned int nbits) 41 { 42 unsigned int nlongs = BITS_TO_LONGS(nbits); 43 if (!small_const_nbits(nbits)) { 44 unsigned int len = (nlongs - 1) * sizeof(unsigned long); 45 memset(dst, 0xff, len); 46 } 47 dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits); 48 } 49 50 static inline bool bitmap_empty(const unsigned long *src, unsigned int nbits) 51 { 52 if (small_const_nbits(nbits)) 53 return ! (*src & BITMAP_LAST_WORD_MASK(nbits)); 54 55 return find_first_bit(src, nbits) == nbits; 56 } 57 58 static inline bool bitmap_full(const unsigned long *src, unsigned int nbits) 59 { 60 if (small_const_nbits(nbits)) 61 return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits)); 62 63 return find_first_zero_bit(src, nbits) == nbits; 64 } 65 66 static inline unsigned int bitmap_weight(const unsigned long *src, unsigned int nbits) 67 { 68 if (small_const_nbits(nbits)) 69 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits)); 70 return __bitmap_weight(src, nbits); 71 } 72 73 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1, 74 const unsigned long *src2, unsigned int nbits) 75 { 76 if (small_const_nbits(nbits)) 77 *dst = *src1 | *src2; 78 else 79 __bitmap_or(dst, src1, src2, nbits); 80 } 81 82 /** 83 * bitmap_zalloc - Allocate bitmap 84 * @nbits: Number of bits 85 */ 86 static inline unsigned long *bitmap_zalloc(int nbits) 87 { 88 return calloc(1, bitmap_size(nbits)); 89 } 90 91 /* 92 * bitmap_free - Free bitmap 93 * @bitmap: pointer to bitmap 94 */ 95 static inline void bitmap_free(unsigned long *bitmap) 96 { 97 free(bitmap); 98 } 99 100 /* 101 * bitmap_scnprintf - print bitmap list into buffer 102 * @bitmap: bitmap 103 * @nbits: size of bitmap 104 * @buf: buffer to store output 105 * @size: size of @buf 106 */ 107 size_t bitmap_scnprintf(unsigned long *bitmap, unsigned int nbits, 108 char *buf, size_t size); 109 110 /** 111 * bitmap_and - Do logical and on bitmaps 112 * @dst: resulting bitmap 113 * @src1: operand 1 114 * @src2: operand 2 115 * @nbits: size of bitmap 116 */ 117 static inline bool bitmap_and(unsigned long *dst, const unsigned long *src1, 118 const unsigned long *src2, unsigned int nbits) 119 { 120 if (small_const_nbits(nbits)) 121 return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0; 122 return __bitmap_and(dst, src1, src2, nbits); 123 } 124 125 #ifdef __LITTLE_ENDIAN 126 #define BITMAP_MEM_ALIGNMENT 8 127 #else 128 #define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long)) 129 #endif 130 #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1) 131 132 static inline bool bitmap_equal(const unsigned long *src1, 133 const unsigned long *src2, unsigned int nbits) 134 { 135 if (small_const_nbits(nbits)) 136 return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits)); 137 if (__builtin_constant_p(nbits & BITMAP_MEM_MASK) && 138 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT)) 139 return !memcmp(src1, src2, nbits / 8); 140 return __bitmap_equal(src1, src2, nbits); 141 } 142 143 static inline bool bitmap_intersects(const unsigned long *src1, 144 const unsigned long *src2, 145 unsigned int nbits) 146 { 147 if (small_const_nbits(nbits)) 148 return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0; 149 else 150 return __bitmap_intersects(src1, src2, nbits); 151 } 152 153 static inline void bitmap_clear(unsigned long *map, unsigned int start, 154 unsigned int nbits) 155 { 156 if (__builtin_constant_p(nbits) && nbits == 1) 157 __clear_bit(start, map); 158 else if (small_const_nbits(start + nbits)) 159 *map &= ~GENMASK(start + nbits - 1, start); 160 else if (__builtin_constant_p(start & BITMAP_MEM_MASK) && 161 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) && 162 __builtin_constant_p(nbits & BITMAP_MEM_MASK) && 163 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT)) 164 memset((char *)map + start / 8, 0, nbits / 8); 165 else 166 __bitmap_clear(map, start, nbits); 167 } 168 #endif /* _TOOLS_LINUX_BITMAP_H */ 169
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.