bitmap.h 8.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267
  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. * bitmap_zero(dst, nbits) *dst = 0UL
  24. * bitmap_fill(dst, nbits) *dst = ~0UL
  25. * bitmap_copy(dst, src, nbits) *dst = *src
  26. * bitmap_and(dst, src1, src2, nbits) *dst = *src1 & *src2
  27. * bitmap_or(dst, src1, src2, nbits) *dst = *src1 | *src2
  28. * bitmap_xor(dst, src1, src2, nbits) *dst = *src1 ^ *src2
  29. * bitmap_andnot(dst, src1, src2, nbits) *dst = *src1 & ~(*src2)
  30. * bitmap_complement(dst, src, nbits) *dst = ~(*src)
  31. * bitmap_equal(src1, src2, nbits) Are *src1 and *src2 equal?
  32. * bitmap_intersects(src1, src2, nbits) Do *src1 and *src2 overlap?
  33. * bitmap_subset(src1, src2, nbits) Is *src1 a subset of *src2?
  34. * bitmap_empty(src, nbits) Are all bits zero in *src?
  35. * bitmap_full(src, nbits) Are all bits set in *src?
  36. * bitmap_weight(src, nbits) Hamming Weight: number set bits
  37. * bitmap_shift_right(dst, src, n, nbits) *dst = *src >> n
  38. * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n
  39. * bitmap_remap(dst, src, old, new, nbits) *dst = map(old, new)(src)
  40. * bitmap_bitremap(oldbit, old, new, nbits) newbit = map(old, new)(oldbit)
  41. * bitmap_scnprintf(buf, len, src, nbits) Print bitmap src to buf
  42. * bitmap_parse(ubuf, ulen, dst, nbits) Parse bitmap dst from user buf
  43. * bitmap_scnlistprintf(buf, len, src, nbits) Print bitmap src as list to buf
  44. * bitmap_parselist(buf, dst, nbits) Parse bitmap dst from list
  45. */
  46. /*
  47. * Also the following operations in asm/bitops.h apply to bitmaps.
  48. *
  49. * set_bit(bit, addr) *addr |= bit
  50. * clear_bit(bit, addr) *addr &= ~bit
  51. * change_bit(bit, addr) *addr ^= bit
  52. * test_bit(bit, addr) Is bit set in *addr?
  53. * test_and_set_bit(bit, addr) Set bit and return old value
  54. * test_and_clear_bit(bit, addr) Clear bit and return old value
  55. * test_and_change_bit(bit, addr) Change bit and return old value
  56. * find_first_zero_bit(addr, nbits) Position first zero bit in *addr
  57. * find_first_bit(addr, nbits) Position first set bit in *addr
  58. * find_next_zero_bit(addr, nbits, bit) Position next zero bit in *addr >= bit
  59. * find_next_bit(addr, nbits, bit) Position next set bit in *addr >= bit
  60. */
  61. /*
  62. * The DECLARE_BITMAP(name,bits) macro, in linux/types.h, can be used
  63. * to declare an array named 'name' of just enough unsigned longs to
  64. * contain all bit positions from 0 to 'bits' - 1.
  65. */
  66. /*
  67. * lib/bitmap.c provides these functions:
  68. */
  69. extern int __bitmap_empty(const unsigned long *bitmap, int bits);
  70. extern int __bitmap_full(const unsigned long *bitmap, int bits);
  71. extern int __bitmap_equal(const unsigned long *bitmap1,
  72. const unsigned long *bitmap2, int bits);
  73. extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
  74. int bits);
  75. extern void __bitmap_shift_right(unsigned long *dst,
  76. const unsigned long *src, int shift, int bits);
  77. extern void __bitmap_shift_left(unsigned long *dst,
  78. const unsigned long *src, int shift, int bits);
  79. extern void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
  80. const unsigned long *bitmap2, int bits);
  81. extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
  82. const unsigned long *bitmap2, int bits);
  83. extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
  84. const unsigned long *bitmap2, int bits);
  85. extern void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
  86. const unsigned long *bitmap2, int bits);
  87. extern int __bitmap_intersects(const unsigned long *bitmap1,
  88. const unsigned long *bitmap2, int bits);
  89. extern int __bitmap_subset(const unsigned long *bitmap1,
  90. const unsigned long *bitmap2, int bits);
  91. extern int __bitmap_weight(const unsigned long *bitmap, int bits);
  92. extern int bitmap_scnprintf(char *buf, unsigned int len,
  93. const unsigned long *src, int nbits);
  94. extern int bitmap_parse(const char __user *ubuf, unsigned int ulen,
  95. unsigned long *dst, int nbits);
  96. extern int bitmap_scnlistprintf(char *buf, unsigned int len,
  97. const unsigned long *src, int nbits);
  98. extern int bitmap_parselist(const char *buf, unsigned long *maskp,
  99. int nmaskbits);
  100. extern void bitmap_remap(unsigned long *dst, const unsigned long *src,
  101. const unsigned long *old, const unsigned long *new, int bits);
  102. extern int bitmap_bitremap(int oldbit,
  103. const unsigned long *old, const unsigned long *new, int bits);
  104. extern int bitmap_find_free_region(unsigned long *bitmap, int bits, int order);
  105. extern void bitmap_release_region(unsigned long *bitmap, int pos, int order);
  106. extern int bitmap_allocate_region(unsigned long *bitmap, int pos, int order);
  107. #define BITMAP_LAST_WORD_MASK(nbits) \
  108. ( \
  109. ((nbits) % BITS_PER_LONG) ? \
  110. (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \
  111. )
  112. static inline void bitmap_zero(unsigned long *dst, int nbits)
  113. {
  114. if (nbits <= BITS_PER_LONG)
  115. *dst = 0UL;
  116. else {
  117. int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
  118. memset(dst, 0, len);
  119. }
  120. }
  121. static inline void bitmap_fill(unsigned long *dst, int nbits)
  122. {
  123. size_t nlongs = BITS_TO_LONGS(nbits);
  124. if (nlongs > 1) {
  125. int len = (nlongs - 1) * sizeof(unsigned long);
  126. memset(dst, 0xff, len);
  127. }
  128. dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
  129. }
  130. static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
  131. int nbits)
  132. {
  133. if (nbits <= BITS_PER_LONG)
  134. *dst = *src;
  135. else {
  136. int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
  137. memcpy(dst, src, len);
  138. }
  139. }
  140. static inline void bitmap_and(unsigned long *dst, const unsigned long *src1,
  141. const unsigned long *src2, int nbits)
  142. {
  143. if (nbits <= BITS_PER_LONG)
  144. *dst = *src1 & *src2;
  145. else
  146. __bitmap_and(dst, src1, src2, nbits);
  147. }
  148. static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
  149. const unsigned long *src2, int nbits)
  150. {
  151. if (nbits <= BITS_PER_LONG)
  152. *dst = *src1 | *src2;
  153. else
  154. __bitmap_or(dst, src1, src2, nbits);
  155. }
  156. static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
  157. const unsigned long *src2, int nbits)
  158. {
  159. if (nbits <= BITS_PER_LONG)
  160. *dst = *src1 ^ *src2;
  161. else
  162. __bitmap_xor(dst, src1, src2, nbits);
  163. }
  164. static inline void bitmap_andnot(unsigned long *dst, const unsigned long *src1,
  165. const unsigned long *src2, int nbits)
  166. {
  167. if (nbits <= BITS_PER_LONG)
  168. *dst = *src1 & ~(*src2);
  169. else
  170. __bitmap_andnot(dst, src1, src2, nbits);
  171. }
  172. static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
  173. int nbits)
  174. {
  175. if (nbits <= BITS_PER_LONG)
  176. *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits);
  177. else
  178. __bitmap_complement(dst, src, nbits);
  179. }
  180. static inline int bitmap_equal(const unsigned long *src1,
  181. const unsigned long *src2, int nbits)
  182. {
  183. if (nbits <= BITS_PER_LONG)
  184. return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
  185. else
  186. return __bitmap_equal(src1, src2, nbits);
  187. }
  188. static inline int bitmap_intersects(const unsigned long *src1,
  189. const unsigned long *src2, int nbits)
  190. {
  191. if (nbits <= BITS_PER_LONG)
  192. return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
  193. else
  194. return __bitmap_intersects(src1, src2, nbits);
  195. }
  196. static inline int bitmap_subset(const unsigned long *src1,
  197. const unsigned long *src2, int nbits)
  198. {
  199. if (nbits <= BITS_PER_LONG)
  200. return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
  201. else
  202. return __bitmap_subset(src1, src2, nbits);
  203. }
  204. static inline int bitmap_empty(const unsigned long *src, int nbits)
  205. {
  206. if (nbits <= BITS_PER_LONG)
  207. return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
  208. else
  209. return __bitmap_empty(src, nbits);
  210. }
  211. static inline int bitmap_full(const unsigned long *src, int nbits)
  212. {
  213. if (nbits <= BITS_PER_LONG)
  214. return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
  215. else
  216. return __bitmap_full(src, nbits);
  217. }
  218. static inline int bitmap_weight(const unsigned long *src, int nbits)
  219. {
  220. return __bitmap_weight(src, nbits);
  221. }
  222. static inline void bitmap_shift_right(unsigned long *dst,
  223. const unsigned long *src, int n, int nbits)
  224. {
  225. if (nbits <= BITS_PER_LONG)
  226. *dst = *src >> n;
  227. else
  228. __bitmap_shift_right(dst, src, n, nbits);
  229. }
  230. static inline void bitmap_shift_left(unsigned long *dst,
  231. const unsigned long *src, int n, int nbits)
  232. {
  233. if (nbits <= BITS_PER_LONG)
  234. *dst = (*src << n) & BITMAP_LAST_WORD_MASK(nbits);
  235. else
  236. __bitmap_shift_left(dst, src, n, nbits);
  237. }
  238. #endif /* __ASSEMBLY__ */
  239. #endif /* __LINUX_BITMAP_H */