bitmap.h 9.5 KB

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