include/linux/bitmap.h

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 #ifndef _TOOLS_LINUX_BITMAP_H
0003 #define _TOOLS_LINUX_BITMAP_H
0004
0005 #include <string.h>
0006 #include <linux/bitops.h>
0007 #include <linux/find.h>
0008 #include <stdlib.h>
0009 #include <linux/kernel.h>
0010
0011 #define DECLARE_BITMAP(name,bits) \
0012     unsigned long name[BITS_TO_LONGS(bits)]
0013
0014 unsigned int __bitmap_weight(const unsigned long *bitmap, int bits);
0015 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
0016          const unsigned long *bitmap2, int bits);
0017 bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
0018          const unsigned long *bitmap2, unsigned int bits);
0019 bool __bitmap_equal(const unsigned long *bitmap1,
0020             const unsigned long *bitmap2, unsigned int bits);
0021 void bitmap_clear(unsigned long *map, unsigned int start, int len);
0022 bool __bitmap_intersects(const unsigned long *bitmap1,
0023              const unsigned long *bitmap2, unsigned int bits);
0024
0025 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
0026 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
0027
0028 static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
0029 {
0030     if (small_const_nbits(nbits))
0031         *dst = 0UL;
0032     else {
0033         int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
0034         memset(dst, 0, len);
0035     }
0036 }
0037
0038 static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
0039 {
0040     unsigned int nlongs = BITS_TO_LONGS(nbits);
0041     if (!small_const_nbits(nbits)) {
0042         unsigned int len = (nlongs - 1) * sizeof(unsigned long);
0043         memset(dst, 0xff,  len);
0044     }
0045     dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
0046 }
0047
0048 static inline bool bitmap_empty(const unsigned long *src, unsigned int nbits)
0049 {
0050     if (small_const_nbits(nbits))
0051         return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
0052
0053     return find_first_bit(src, nbits) == nbits;
0054 }
0055
0056 static inline bool bitmap_full(const unsigned long *src, unsigned int nbits)
0057 {
0058     if (small_const_nbits(nbits))
0059         return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
0060
0061     return find_first_zero_bit(src, nbits) == nbits;
0062 }
0063
0064 static inline unsigned int bitmap_weight(const unsigned long *src, unsigned int nbits)
0065 {
0066     if (small_const_nbits(nbits))
0067         return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
0068     return __bitmap_weight(src, nbits);
0069 }
0070
0071 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
0072                  const unsigned long *src2, unsigned int nbits)
0073 {
0074     if (small_const_nbits(nbits))
0075         *dst = *src1 | *src2;
0076     else
0077         __bitmap_or(dst, src1, src2, nbits);
0078 }
0079
0080 /**
0081  * test_and_set_bit - Set a bit and return its old value
0082  * @nr: Bit to set
0083  * @addr: Address to count from
0084  */
0085 static inline int test_and_set_bit(int nr, unsigned long *addr)
0086 {
0087     unsigned long mask = BIT_MASK(nr);
0088     unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
0089     unsigned long old;
0090
0091     old = *p;
0092     *p = old | mask;
0093
0094     return (old & mask) != 0;
0095 }
0096
0097 /**
0098  * test_and_clear_bit - Clear a bit and return its old value
0099  * @nr: Bit to clear
0100  * @addr: Address to count from
0101  */
0102 static inline int test_and_clear_bit(int nr, unsigned long *addr)
0103 {
0104     unsigned long mask = BIT_MASK(nr);
0105     unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr);
0106     unsigned long old;
0107
0108     old = *p;
0109     *p = old & ~mask;
0110
0111     return (old & mask) != 0;
0112 }
0113
0114 /**
0115  * bitmap_zalloc - Allocate bitmap
0116  * @nbits: Number of bits
0117  */
0118 static inline unsigned long *bitmap_zalloc(int nbits)
0119 {
0120     return calloc(1, BITS_TO_LONGS(nbits) * sizeof(unsigned long));
0121 }
0122
0123 /*
0124  * bitmap_free - Free bitmap
0125  * @bitmap: pointer to bitmap
0126  */
0127 static inline void bitmap_free(unsigned long *bitmap)
0128 {
0129     free(bitmap);
0130 }
0131
0132 /*
0133  * bitmap_scnprintf - print bitmap list into buffer
0134  * @bitmap: bitmap
0135  * @nbits: size of bitmap
0136  * @buf: buffer to store output
0137  * @size: size of @buf
0138  */
0139 size_t bitmap_scnprintf(unsigned long *bitmap, unsigned int nbits,
0140             char *buf, size_t size);
0141
0142 /**
0143  * bitmap_and - Do logical and on bitmaps
0144  * @dst: resulting bitmap
0145  * @src1: operand 1
0146  * @src2: operand 2
0147  * @nbits: size of bitmap
0148  */
0149 static inline bool bitmap_and(unsigned long *dst, const unsigned long *src1,
0150                  const unsigned long *src2, unsigned int nbits)
0151 {
0152     if (small_const_nbits(nbits))
0153         return (*dst = *src1 & *src2 & BITMAP_LAST_WORD_MASK(nbits)) != 0;
0154     return __bitmap_and(dst, src1, src2, nbits);
0155 }
0156
0157 #ifdef __LITTLE_ENDIAN
0158 #define BITMAP_MEM_ALIGNMENT 8
0159 #else
0160 #define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long))
0161 #endif
0162 #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
0163 #define IS_ALIGNED(x, a) (((x) & ((typeof(x))(a) - 1)) == 0)
0164
0165 static inline bool bitmap_equal(const unsigned long *src1,
0166                 const unsigned long *src2, unsigned int nbits)
0167 {
0168     if (small_const_nbits(nbits))
0169         return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
0170     if (__builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
0171         IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
0172         return !memcmp(src1, src2, nbits / 8);
0173     return __bitmap_equal(src1, src2, nbits);
0174 }
0175
0176 static inline bool bitmap_intersects(const unsigned long *src1,
0177                      const unsigned long *src2,
0178                      unsigned int nbits)
0179 {
0180     if (small_const_nbits(nbits))
0181         return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
0182     else
0183         return __bitmap_intersects(src1, src2, nbits);
0184 }
0185
0186 #endif /* _TOOLS_LINUX_BITMAP_H */