Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 1 | #ifndef __LINUX_BITMAP_H |
| 2 | #define __LINUX_BITMAP_H |
| 3 | |
| 4 | #ifndef __ASSEMBLY__ |
| 5 | |
| 6 | #include <linux/types.h> |
| 7 | #include <linux/bitops.h> |
| 8 | #include <linux/string.h> |
| 9 | |
| 10 | /* |
| 11 | * bitmaps provide bit arrays that consume one or more unsigned |
| 12 | * longs. The bitmap interface and available operations are listed |
| 13 | * here, in bitmap.h |
| 14 | * |
| 15 | * Function implementations generic to all architectures are in |
| 16 | * lib/bitmap.c. Functions implementations that are architecture |
| 17 | * specific are in various include/asm-<arch>/bitops.h headers |
| 18 | * and other arch/<arch> specific files. |
| 19 | * |
| 20 | * See lib/bitmap.c for more details. |
| 21 | */ |
| 22 | |
| 23 | /* |
| 24 | * The available bitmap operations and their rough meaning in the |
| 25 | * case that the bitmap is a single unsigned long are thus: |
| 26 | * |
| 27 | * bitmap_zero(dst, nbits) *dst = 0UL |
| 28 | * bitmap_fill(dst, nbits) *dst = ~0UL |
| 29 | * bitmap_copy(dst, src, nbits) *dst = *src |
| 30 | * bitmap_and(dst, src1, src2, nbits) *dst = *src1 & *src2 |
| 31 | * bitmap_or(dst, src1, src2, nbits) *dst = *src1 | *src2 |
| 32 | * bitmap_xor(dst, src1, src2, nbits) *dst = *src1 ^ *src2 |
| 33 | * bitmap_andnot(dst, src1, src2, nbits) *dst = *src1 & ~(*src2) |
| 34 | * bitmap_complement(dst, src, nbits) *dst = ~(*src) |
| 35 | * bitmap_equal(src1, src2, nbits) Are *src1 and *src2 equal? |
| 36 | * bitmap_intersects(src1, src2, nbits) Do *src1 and *src2 overlap? |
| 37 | * bitmap_subset(src1, src2, nbits) Is *src1 a subset of *src2? |
| 38 | * bitmap_empty(src, nbits) Are all bits zero in *src? |
| 39 | * bitmap_full(src, nbits) Are all bits set in *src? |
| 40 | * bitmap_weight(src, nbits) Hamming Weight: number set bits |
| 41 | * bitmap_shift_right(dst, src, n, nbits) *dst = *src >> n |
| 42 | * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n |
Paul Jackson | fb5eeee | 2005-10-30 15:02:33 -0800 | [diff] [blame] | 43 | * bitmap_remap(dst, src, old, new, nbits) *dst = map(old, new)(src) |
| 44 | * bitmap_bitremap(oldbit, old, new, nbits) newbit = map(old, new)(oldbit) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 45 | * bitmap_scnprintf(buf, len, src, nbits) Print bitmap src to buf |
| 46 | * bitmap_parse(ubuf, ulen, dst, nbits) Parse bitmap dst from user buf |
| 47 | * bitmap_scnlistprintf(buf, len, src, nbits) Print bitmap src as list to buf |
| 48 | * bitmap_parselist(buf, dst, nbits) Parse bitmap dst from list |
Paul Jackson | 87e2480 | 2006-03-24 03:15:44 -0800 | [diff] [blame] | 49 | * bitmap_find_free_region(bitmap, bits, order) Find and allocate bit region |
| 50 | * bitmap_release_region(bitmap, pos, order) Free specified bit region |
| 51 | * bitmap_allocate_region(bitmap, pos, order) Allocate specified bit region |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 52 | */ |
| 53 | |
| 54 | /* |
| 55 | * Also the following operations in asm/bitops.h apply to bitmaps. |
| 56 | * |
| 57 | * set_bit(bit, addr) *addr |= bit |
| 58 | * clear_bit(bit, addr) *addr &= ~bit |
| 59 | * change_bit(bit, addr) *addr ^= bit |
| 60 | * test_bit(bit, addr) Is bit set in *addr? |
| 61 | * test_and_set_bit(bit, addr) Set bit and return old value |
| 62 | * test_and_clear_bit(bit, addr) Clear bit and return old value |
| 63 | * test_and_change_bit(bit, addr) Change bit and return old value |
| 64 | * find_first_zero_bit(addr, nbits) Position first zero bit in *addr |
| 65 | * find_first_bit(addr, nbits) Position first set bit in *addr |
| 66 | * find_next_zero_bit(addr, nbits, bit) Position next zero bit in *addr >= bit |
| 67 | * find_next_bit(addr, nbits, bit) Position next set bit in *addr >= bit |
| 68 | */ |
| 69 | |
| 70 | /* |
| 71 | * The DECLARE_BITMAP(name,bits) macro, in linux/types.h, can be used |
| 72 | * to declare an array named 'name' of just enough unsigned longs to |
| 73 | * contain all bit positions from 0 to 'bits' - 1. |
| 74 | */ |
| 75 | |
| 76 | /* |
| 77 | * lib/bitmap.c provides these functions: |
| 78 | */ |
| 79 | |
| 80 | extern int __bitmap_empty(const unsigned long *bitmap, int bits); |
| 81 | extern int __bitmap_full(const unsigned long *bitmap, int bits); |
| 82 | extern int __bitmap_equal(const unsigned long *bitmap1, |
| 83 | const unsigned long *bitmap2, int bits); |
| 84 | extern void __bitmap_complement(unsigned long *dst, const unsigned long *src, |
| 85 | int bits); |
| 86 | extern void __bitmap_shift_right(unsigned long *dst, |
| 87 | const unsigned long *src, int shift, int bits); |
| 88 | extern void __bitmap_shift_left(unsigned long *dst, |
| 89 | const unsigned long *src, int shift, int bits); |
| 90 | extern void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, |
| 91 | const unsigned long *bitmap2, int bits); |
| 92 | extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, |
| 93 | const unsigned long *bitmap2, int bits); |
| 94 | extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, |
| 95 | const unsigned long *bitmap2, int bits); |
| 96 | extern void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, |
| 97 | const unsigned long *bitmap2, int bits); |
| 98 | extern int __bitmap_intersects(const unsigned long *bitmap1, |
| 99 | const unsigned long *bitmap2, int bits); |
| 100 | extern int __bitmap_subset(const unsigned long *bitmap1, |
| 101 | const unsigned long *bitmap2, int bits); |
| 102 | extern int __bitmap_weight(const unsigned long *bitmap, int bits); |
| 103 | |
| 104 | extern int bitmap_scnprintf(char *buf, unsigned int len, |
| 105 | const unsigned long *src, int nbits); |
| 106 | extern int bitmap_parse(const char __user *ubuf, unsigned int ulen, |
| 107 | unsigned long *dst, int nbits); |
| 108 | extern int bitmap_scnlistprintf(char *buf, unsigned int len, |
| 109 | const unsigned long *src, int nbits); |
| 110 | extern int bitmap_parselist(const char *buf, unsigned long *maskp, |
| 111 | int nmaskbits); |
Paul Jackson | fb5eeee | 2005-10-30 15:02:33 -0800 | [diff] [blame] | 112 | extern void bitmap_remap(unsigned long *dst, const unsigned long *src, |
| 113 | const unsigned long *old, const unsigned long *new, int bits); |
| 114 | extern int bitmap_bitremap(int oldbit, |
| 115 | const unsigned long *old, const unsigned long *new, int bits); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 116 | extern int bitmap_find_free_region(unsigned long *bitmap, int bits, int order); |
| 117 | extern void bitmap_release_region(unsigned long *bitmap, int pos, int order); |
| 118 | extern int bitmap_allocate_region(unsigned long *bitmap, int pos, int order); |
| 119 | |
| 120 | #define BITMAP_LAST_WORD_MASK(nbits) \ |
| 121 | ( \ |
| 122 | ((nbits) % BITS_PER_LONG) ? \ |
| 123 | (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \ |
| 124 | ) |
| 125 | |
| 126 | static inline void bitmap_zero(unsigned long *dst, int nbits) |
| 127 | { |
| 128 | if (nbits <= BITS_PER_LONG) |
| 129 | *dst = 0UL; |
| 130 | else { |
| 131 | int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); |
| 132 | memset(dst, 0, len); |
| 133 | } |
| 134 | } |
| 135 | |
| 136 | static inline void bitmap_fill(unsigned long *dst, int nbits) |
| 137 | { |
| 138 | size_t nlongs = BITS_TO_LONGS(nbits); |
| 139 | if (nlongs > 1) { |
| 140 | int len = (nlongs - 1) * sizeof(unsigned long); |
| 141 | memset(dst, 0xff, len); |
| 142 | } |
| 143 | dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits); |
| 144 | } |
| 145 | |
| 146 | static inline void bitmap_copy(unsigned long *dst, const unsigned long *src, |
| 147 | int nbits) |
| 148 | { |
| 149 | if (nbits <= BITS_PER_LONG) |
| 150 | *dst = *src; |
| 151 | else { |
| 152 | int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long); |
| 153 | memcpy(dst, src, len); |
| 154 | } |
| 155 | } |
| 156 | |
| 157 | static inline void bitmap_and(unsigned long *dst, const unsigned long *src1, |
| 158 | const unsigned long *src2, int nbits) |
| 159 | { |
| 160 | if (nbits <= BITS_PER_LONG) |
| 161 | *dst = *src1 & *src2; |
| 162 | else |
| 163 | __bitmap_and(dst, src1, src2, nbits); |
| 164 | } |
| 165 | |
| 166 | static inline void bitmap_or(unsigned long *dst, const unsigned long *src1, |
| 167 | const unsigned long *src2, int nbits) |
| 168 | { |
| 169 | if (nbits <= BITS_PER_LONG) |
| 170 | *dst = *src1 | *src2; |
| 171 | else |
| 172 | __bitmap_or(dst, src1, src2, nbits); |
| 173 | } |
| 174 | |
| 175 | static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1, |
| 176 | const unsigned long *src2, int nbits) |
| 177 | { |
| 178 | if (nbits <= BITS_PER_LONG) |
| 179 | *dst = *src1 ^ *src2; |
| 180 | else |
| 181 | __bitmap_xor(dst, src1, src2, nbits); |
| 182 | } |
| 183 | |
| 184 | static inline void bitmap_andnot(unsigned long *dst, const unsigned long *src1, |
| 185 | const unsigned long *src2, int nbits) |
| 186 | { |
| 187 | if (nbits <= BITS_PER_LONG) |
| 188 | *dst = *src1 & ~(*src2); |
| 189 | else |
| 190 | __bitmap_andnot(dst, src1, src2, nbits); |
| 191 | } |
| 192 | |
| 193 | static inline void bitmap_complement(unsigned long *dst, const unsigned long *src, |
| 194 | int nbits) |
| 195 | { |
| 196 | if (nbits <= BITS_PER_LONG) |
| 197 | *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits); |
| 198 | else |
| 199 | __bitmap_complement(dst, src, nbits); |
| 200 | } |
| 201 | |
| 202 | static inline int bitmap_equal(const unsigned long *src1, |
| 203 | const unsigned long *src2, int nbits) |
| 204 | { |
| 205 | if (nbits <= BITS_PER_LONG) |
| 206 | return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits)); |
| 207 | else |
| 208 | return __bitmap_equal(src1, src2, nbits); |
| 209 | } |
| 210 | |
| 211 | static inline int bitmap_intersects(const unsigned long *src1, |
| 212 | const unsigned long *src2, int nbits) |
| 213 | { |
| 214 | if (nbits <= BITS_PER_LONG) |
| 215 | return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0; |
| 216 | else |
| 217 | return __bitmap_intersects(src1, src2, nbits); |
| 218 | } |
| 219 | |
| 220 | static inline int bitmap_subset(const unsigned long *src1, |
| 221 | const unsigned long *src2, int nbits) |
| 222 | { |
| 223 | if (nbits <= BITS_PER_LONG) |
| 224 | return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits)); |
| 225 | else |
| 226 | return __bitmap_subset(src1, src2, nbits); |
| 227 | } |
| 228 | |
| 229 | static inline int bitmap_empty(const unsigned long *src, int nbits) |
| 230 | { |
| 231 | if (nbits <= BITS_PER_LONG) |
| 232 | return ! (*src & BITMAP_LAST_WORD_MASK(nbits)); |
| 233 | else |
| 234 | return __bitmap_empty(src, nbits); |
| 235 | } |
| 236 | |
| 237 | static inline int bitmap_full(const unsigned long *src, int nbits) |
| 238 | { |
| 239 | if (nbits <= BITS_PER_LONG) |
| 240 | return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits)); |
| 241 | else |
| 242 | return __bitmap_full(src, nbits); |
| 243 | } |
| 244 | |
| 245 | static inline int bitmap_weight(const unsigned long *src, int nbits) |
| 246 | { |
| 247 | return __bitmap_weight(src, nbits); |
| 248 | } |
| 249 | |
| 250 | static inline void bitmap_shift_right(unsigned long *dst, |
| 251 | const unsigned long *src, int n, int nbits) |
| 252 | { |
| 253 | if (nbits <= BITS_PER_LONG) |
| 254 | *dst = *src >> n; |
| 255 | else |
| 256 | __bitmap_shift_right(dst, src, n, nbits); |
| 257 | } |
| 258 | |
| 259 | static inline void bitmap_shift_left(unsigned long *dst, |
| 260 | const unsigned long *src, int n, int nbits) |
| 261 | { |
| 262 | if (nbits <= BITS_PER_LONG) |
| 263 | *dst = (*src << n) & BITMAP_LAST_WORD_MASK(nbits); |
| 264 | else |
| 265 | __bitmap_shift_left(dst, src, n, nbits); |
| 266 | } |
| 267 | |
| 268 | #endif /* __ASSEMBLY__ */ |
| 269 | |
| 270 | #endif /* __LINUX_BITMAP_H */ |