Annotation of qemu/bitmap.h, revision 1.1.1.2

1.1       root        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);
1.1.1.2 ! root       94:     return g_malloc0(len);
1.1       root       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