bitmap.h (5090B)
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 14int __bitmap_weight(const unsigned long *bitmap, int bits); 15void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, 16 const unsigned long *bitmap2, int bits); 17int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, 18 const unsigned long *bitmap2, unsigned int bits); 19bool __bitmap_equal(const unsigned long *bitmap1, 20 const unsigned long *bitmap2, unsigned int bits); 21void bitmap_clear(unsigned long *map, unsigned int start, int len); 22bool __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 28static 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 38static 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 48static inline int bitmap_empty(const unsigned long *src, unsigned 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 56static inline int 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 64static inline 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 71static 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 */ 85static 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 */ 102static 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 */ 118static 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 */ 127static 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 */ 139size_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 */ 149static inline int 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 165static 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 176static 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 */