File:  [Qemu by Fabrice Bellard] / qemu / bitmap.h
Revision 1.1.1.1 (vendor branch): download - view: text, annotated - select for diffs
Tue Apr 24 18:55:34 2018 UTC (3 years, 3 months ago) by root
Branches: qemu, MAIN
CVS tags: qemu1000, qemu0151, HEAD
qemu 0.15.1

    1: /*
    2:  * Bitmap Module
    3:  *
    4:  * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com>
    5:  *
    6:  * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h
    7:  *
    8:  * This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
    9:  * See the COPYING.LIB file in the top-level directory.
   10:  */
   11: 
   12: #ifndef BITMAP_H
   13: #define BITMAP_H
   14: 
   15: #include "qemu-common.h"
   16: #include "bitops.h"
   17: 
   18: /*
   19:  * The available bitmap operations and their rough meaning in the
   20:  * case that the bitmap is a single unsigned long are thus:
   21:  *
   22:  * Note that nbits should be always a compile time evaluable constant.
   23:  * Otherwise many inlines will generate horrible code.
   24:  *
   25:  * bitmap_zero(dst, nbits)			*dst = 0UL
   26:  * bitmap_fill(dst, nbits)			*dst = ~0UL
   27:  * bitmap_copy(dst, src, nbits)			*dst = *src
   28:  * bitmap_and(dst, src1, src2, nbits)		*dst = *src1 & *src2
   29:  * bitmap_or(dst, src1, src2, nbits)		*dst = *src1 | *src2
   30:  * bitmap_xor(dst, src1, src2, nbits)		*dst = *src1 ^ *src2
   31:  * bitmap_andnot(dst, src1, src2, nbits)	*dst = *src1 & ~(*src2)
   32:  * bitmap_complement(dst, src, nbits)		*dst = ~(*src)
   33:  * bitmap_equal(src1, src2, nbits)		Are *src1 and *src2 equal?
   34:  * bitmap_intersects(src1, src2, nbits) 	Do *src1 and *src2 overlap?
   35:  * bitmap_empty(src, nbits)			Are all bits zero in *src?
   36:  * bitmap_full(src, nbits)			Are all bits set in *src?
   37:  * bitmap_set(dst, pos, nbits)			Set specified bit area
   38:  * bitmap_clear(dst, pos, nbits)		Clear specified bit area
   39:  * bitmap_find_next_zero_area(buf, len, pos, n, mask)	Find bit free area
   40:  */
   41: 
   42: /*
   43:  * Also the following operations apply to bitmaps.
   44:  *
   45:  * set_bit(bit, addr)			*addr |= bit
   46:  * clear_bit(bit, addr)			*addr &= ~bit
   47:  * change_bit(bit, addr)		*addr ^= bit
   48:  * test_bit(bit, addr)			Is bit set in *addr?
   49:  * test_and_set_bit(bit, addr)		Set bit and return old value
   50:  * test_and_clear_bit(bit, addr)	Clear bit and return old value
   51:  * test_and_change_bit(bit, addr)	Change bit and return old value
   52:  * find_first_zero_bit(addr, nbits)	Position first zero bit in *addr
   53:  * find_first_bit(addr, nbits)		Position first set bit in *addr
   54:  * find_next_zero_bit(addr, nbits, bit)	Position next zero bit in *addr >= bit
   55:  * find_next_bit(addr, nbits, bit)	Position next set bit in *addr >= bit
   56:  */
   57: 
   58: #define BITMAP_LAST_WORD_MASK(nbits)                                    \
   59:     (                                                                   \
   60:         ((nbits) % BITS_PER_LONG) ?                                     \
   61:         (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL                       \
   62:         )
   63: 
   64: #define DECLARE_BITMAP(name,bits)                  \
   65: 	unsigned long name[BITS_TO_LONGS(bits)]
   66: 
   67: #define small_nbits(nbits)                      \
   68: 	((nbits) <= BITS_PER_LONG)
   69: 
   70: int slow_bitmap_empty(const unsigned long *bitmap, int bits);
   71: int slow_bitmap_full(const unsigned long *bitmap, int bits);
   72: int slow_bitmap_equal(const unsigned long *bitmap1,
   73:                    const unsigned long *bitmap2, int bits);
   74: void slow_bitmap_complement(unsigned long *dst, const unsigned long *src,
   75:                          int bits);
   76: void slow_bitmap_shift_right(unsigned long *dst,
   77:                           const unsigned long *src, int shift, int bits);
   78: void slow_bitmap_shift_left(unsigned long *dst,
   79:                          const unsigned long *src, int shift, int bits);
   80: int slow_bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
   81:                  const unsigned long *bitmap2, int bits);
   82: void slow_bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
   83:                  const unsigned long *bitmap2, int bits);
   84: void slow_bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
   85:                   const unsigned long *bitmap2, int bits);
   86: int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
   87:                     const unsigned long *bitmap2, int bits);
   88: int slow_bitmap_intersects(const unsigned long *bitmap1,
   89: 			const unsigned long *bitmap2, int bits);
   90: 
   91: static inline unsigned long *bitmap_new(int nbits)
   92: {
   93:     int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
   94:     return qemu_mallocz(len);
   95: }
   96: 
   97: static inline void bitmap_zero(unsigned long *dst, int nbits)
   98: {
   99:     if (small_nbits(nbits)) {
  100:         *dst = 0UL;
  101:     } else {
  102:         int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
  103:         memset(dst, 0, len);
  104:     }
  105: }
  106: 
  107: static inline void bitmap_fill(unsigned long *dst, int nbits)
  108: {
  109:     size_t nlongs = BITS_TO_LONGS(nbits);
  110:     if (!small_nbits(nbits)) {
  111:         int len = (nlongs - 1) * sizeof(unsigned long);
  112:         memset(dst, 0xff,  len);
  113:     }
  114:     dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
  115: }
  116: 
  117: static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
  118:                                int nbits)
  119: {
  120:     if (small_nbits(nbits)) {
  121:         *dst = *src;
  122:     } else {
  123:         int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
  124:         memcpy(dst, src, len);
  125:     }
  126: }
  127: 
  128: static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
  129:                              const unsigned long *src2, int nbits)
  130: {
  131:     if (small_nbits(nbits)) {
  132:         return (*dst = *src1 & *src2) != 0;
  133:     }
  134:     return slow_bitmap_and(dst, src1, src2, nbits);
  135: }
  136: 
  137: static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
  138: 			const unsigned long *src2, int nbits)
  139: {
  140:     if (small_nbits(nbits)) {
  141:         *dst = *src1 | *src2;
  142:     } else {
  143:         slow_bitmap_or(dst, src1, src2, nbits);
  144:     }
  145: }
  146: 
  147: static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
  148: 			const unsigned long *src2, int nbits)
  149: {
  150:     if (small_nbits(nbits)) {
  151:         *dst = *src1 ^ *src2;
  152:     } else {
  153:         slow_bitmap_xor(dst, src1, src2, nbits);
  154:     }
  155: }
  156: 
  157: static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
  158: 			const unsigned long *src2, int nbits)
  159: {
  160:     if (small_nbits(nbits)) {
  161:         return (*dst = *src1 & ~(*src2)) != 0;
  162:     }
  163:     return slow_bitmap_andnot(dst, src1, src2, nbits);
  164: }
  165: 
  166: static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
  167: 			int nbits)
  168: {
  169:     if (small_nbits(nbits)) {
  170:         *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits);
  171:     } else {
  172:         slow_bitmap_complement(dst, src, nbits);
  173:     }
  174: }
  175: 
  176: static inline int bitmap_equal(const unsigned long *src1,
  177: 			const unsigned long *src2, int nbits)
  178: {
  179:     if (small_nbits(nbits)) {
  180:         return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
  181:     } else {
  182:         return slow_bitmap_equal(src1, src2, nbits);
  183:     }
  184: }
  185: 
  186: static inline int bitmap_empty(const unsigned long *src, int nbits)
  187: {
  188:     if (small_nbits(nbits)) {
  189:         return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
  190:     } else {
  191:         return slow_bitmap_empty(src, nbits);
  192:     }
  193: }
  194: 
  195: static inline int bitmap_full(const unsigned long *src, int nbits)
  196: {
  197:     if (small_nbits(nbits)) {
  198:         return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
  199:     } else {
  200:         return slow_bitmap_full(src, nbits);
  201:     }
  202: }
  203: 
  204: static inline int bitmap_intersects(const unsigned long *src1,
  205: 			const unsigned long *src2, int nbits)
  206: {
  207:     if (small_nbits(nbits)) {
  208:         return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
  209:     } else {
  210:         return slow_bitmap_intersects(src1, src2, nbits);
  211:     }
  212: }
  213: 
  214: void bitmap_set(unsigned long *map, int i, int len);
  215: void bitmap_clear(unsigned long *map, int start, int nr);
  216: unsigned long bitmap_find_next_zero_area(unsigned long *map,
  217: 					 unsigned long size,
  218: 					 unsigned long start,
  219: 					 unsigned int nr,
  220: 					 unsigned long align_mask);
  221: 
  222: #endif /* BITMAP_H */

unix.superglobalmegacorp.com