home *** CD-ROM | disk | FTP | other *** search
/ PC Welt 2006 November (DVD) / PCWELT_11_2006.ISO / casper / filesystem.squashfs / usr / src / linux-headers-2.6.17-6 / include / linux / bitmap.h < prev    next >
Encoding:
C/C++ Source or Header  |  2006-08-11  |  9.0 KB  |  271 lines
  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
  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)
  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
  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. /*
  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);
  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);
  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 */
  271.