bitmap.h 11 KB

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