Annotation of qemu/bitmap.c, revision 1.1.1.1

1.1       root        1: /*
                      2:  * Bitmap Module
                      3:  *
                      4:  * Stolen from linux/src/lib/bitmap.c
                      5:  *
                      6:  * Copyright (C) 2010 Corentin Chary
                      7:  *
                      8:  * This source code is licensed under the GNU General Public License,
                      9:  * Version 2.
                     10:  */
                     11: 
                     12: #include "bitops.h"
                     13: #include "bitmap.h"
                     14: 
                     15: /*
                     16:  * bitmaps provide an array of bits, implemented using an an
                     17:  * array of unsigned longs.  The number of valid bits in a
                     18:  * given bitmap does _not_ need to be an exact multiple of
                     19:  * BITS_PER_LONG.
                     20:  *
                     21:  * The possible unused bits in the last, partially used word
                     22:  * of a bitmap are 'don't care'.  The implementation makes
                     23:  * no particular effort to keep them zero.  It ensures that
                     24:  * their value will not affect the results of any operation.
                     25:  * The bitmap operations that return Boolean (bitmap_empty,
                     26:  * for example) or scalar (bitmap_weight, for example) results
                     27:  * carefully filter out these unused bits from impacting their
                     28:  * results.
                     29:  *
                     30:  * These operations actually hold to a slightly stronger rule:
                     31:  * if you don't input any bitmaps to these ops that have some
                     32:  * unused bits set, then they won't output any set unused bits
                     33:  * in output bitmaps.
                     34:  *
                     35:  * The byte ordering of bitmaps is more natural on little
                     36:  * endian architectures.
                     37:  */
                     38: 
                     39: int slow_bitmap_empty(const unsigned long *bitmap, int bits)
                     40: {
                     41:     int k, lim = bits/BITS_PER_LONG;
                     42: 
                     43:     for (k = 0; k < lim; ++k) {
                     44:         if (bitmap[k]) {
                     45:             return 0;
                     46:         }
                     47:     }
                     48:     if (bits % BITS_PER_LONG) {
                     49:         if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) {
                     50:             return 0;
                     51:         }
                     52:     }
                     53: 
                     54:     return 1;
                     55: }
                     56: 
                     57: int slow_bitmap_full(const unsigned long *bitmap, int bits)
                     58: {
                     59:     int k, lim = bits/BITS_PER_LONG;
                     60: 
                     61:     for (k = 0; k < lim; ++k) {
                     62:         if (~bitmap[k]) {
                     63:             return 0;
                     64:         }
                     65:     }
                     66: 
                     67:     if (bits % BITS_PER_LONG) {
                     68:         if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) {
                     69:             return 0;
                     70:         }
                     71:     }
                     72: 
                     73:     return 1;
                     74: }
                     75: 
                     76: int slow_bitmap_equal(const unsigned long *bitmap1,
                     77:                       const unsigned long *bitmap2, int bits)
                     78: {
                     79:     int k, lim = bits/BITS_PER_LONG;
                     80: 
                     81:     for (k = 0; k < lim; ++k) {
                     82:         if (bitmap1[k] != bitmap2[k]) {
                     83:             return 0;
                     84:         }
                     85:     }
                     86: 
                     87:     if (bits % BITS_PER_LONG) {
                     88:         if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) {
                     89:             return 0;
                     90:         }
                     91:     }
                     92: 
                     93:     return 1;
                     94: }
                     95: 
                     96: void slow_bitmap_complement(unsigned long *dst, const unsigned long *src,
                     97:                             int bits)
                     98: {
                     99:     int k, lim = bits/BITS_PER_LONG;
                    100: 
                    101:     for (k = 0; k < lim; ++k) {
                    102:         dst[k] = ~src[k];
                    103:     }
                    104: 
                    105:     if (bits % BITS_PER_LONG) {
                    106:         dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);
                    107:     }
                    108: }
                    109: 
                    110: int slow_bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
                    111:                     const unsigned long *bitmap2, int bits)
                    112: {
                    113:     int k;
                    114:     int nr = BITS_TO_LONGS(bits);
                    115:     unsigned long result = 0;
                    116: 
                    117:     for (k = 0; k < nr; k++) {
                    118:         result |= (dst[k] = bitmap1[k] & bitmap2[k]);
                    119:     }
                    120:     return result != 0;
                    121: }
                    122: 
                    123: void slow_bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
                    124:                     const unsigned long *bitmap2, int bits)
                    125: {
                    126:     int k;
                    127:     int nr = BITS_TO_LONGS(bits);
                    128: 
                    129:     for (k = 0; k < nr; k++) {
                    130:         dst[k] = bitmap1[k] | bitmap2[k];
                    131:     }
                    132: }
                    133: 
                    134: void slow_bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
                    135:                      const unsigned long *bitmap2, int bits)
                    136: {
                    137:     int k;
                    138:     int nr = BITS_TO_LONGS(bits);
                    139: 
                    140:     for (k = 0; k < nr; k++) {
                    141:         dst[k] = bitmap1[k] ^ bitmap2[k];
                    142:     }
                    143: }
                    144: 
                    145: int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
                    146:                        const unsigned long *bitmap2, int bits)
                    147: {
                    148:     int k;
                    149:     int nr = BITS_TO_LONGS(bits);
                    150:     unsigned long result = 0;
                    151: 
                    152:     for (k = 0; k < nr; k++) {
                    153:         result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
                    154:     }
                    155:     return result != 0;
                    156: }
                    157: 
                    158: #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG))
                    159: 
                    160: void bitmap_set(unsigned long *map, int start, int nr)
                    161: {
                    162:     unsigned long *p = map + BIT_WORD(start);
                    163:     const int size = start + nr;
                    164:     int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
                    165:     unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
                    166: 
                    167:     while (nr - bits_to_set >= 0) {
                    168:         *p |= mask_to_set;
                    169:         nr -= bits_to_set;
                    170:         bits_to_set = BITS_PER_LONG;
                    171:         mask_to_set = ~0UL;
                    172:         p++;
                    173:     }
                    174:     if (nr) {
                    175:         mask_to_set &= BITMAP_LAST_WORD_MASK(size);
                    176:         *p |= mask_to_set;
                    177:     }
                    178: }
                    179: 
                    180: void bitmap_clear(unsigned long *map, int start, int nr)
                    181: {
                    182:     unsigned long *p = map + BIT_WORD(start);
                    183:     const int size = start + nr;
                    184:     int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
                    185:     unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
                    186: 
                    187:     while (nr - bits_to_clear >= 0) {
                    188:         *p &= ~mask_to_clear;
                    189:         nr -= bits_to_clear;
                    190:         bits_to_clear = BITS_PER_LONG;
                    191:         mask_to_clear = ~0UL;
                    192:         p++;
                    193:     }
                    194:     if (nr) {
                    195:         mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
                    196:         *p &= ~mask_to_clear;
                    197:     }
                    198: }
                    199: 
                    200: #define ALIGN_MASK(x,mask)      (((x)+(mask))&~(mask))
                    201: 
                    202: /**
                    203:  * bitmap_find_next_zero_area - find a contiguous aligned zero area
                    204:  * @map: The address to base the search on
                    205:  * @size: The bitmap size in bits
                    206:  * @start: The bitnumber to start searching at
                    207:  * @nr: The number of zeroed bits we're looking for
                    208:  * @align_mask: Alignment mask for zero area
                    209:  *
                    210:  * The @align_mask should be one less than a power of 2; the effect is that
                    211:  * the bit offset of all zero areas this function finds is multiples of that
                    212:  * power of 2. A @align_mask of 0 means no alignment is required.
                    213:  */
                    214: unsigned long bitmap_find_next_zero_area(unsigned long *map,
                    215:                                         unsigned long size,
                    216:                                         unsigned long start,
                    217:                                         unsigned int nr,
                    218:                                         unsigned long align_mask)
                    219: {
                    220:     unsigned long index, end, i;
                    221: again:
                    222:     index = find_next_zero_bit(map, size, start);
                    223: 
                    224:     /* Align allocation */
                    225:     index = ALIGN_MASK(index, align_mask);
                    226: 
                    227:     end = index + nr;
                    228:     if (end > size) {
                    229:         return end;
                    230:     }
                    231:     i = find_next_bit(map, end, index);
                    232:     if (i < end) {
                    233:         start = i + 1;
                    234:         goto again;
                    235:     }
                    236:     return index;
                    237: }
                    238: 
                    239: int slow_bitmap_intersects(const unsigned long *bitmap1,
                    240:                            const unsigned long *bitmap2, int bits)
                    241: {
                    242:     int k, lim = bits/BITS_PER_LONG;
                    243: 
                    244:     for (k = 0; k < lim; ++k) {
                    245:         if (bitmap1[k] & bitmap2[k]) {
                    246:             return 1;
                    247:         }
                    248:     }
                    249: 
                    250:     if (bits % BITS_PER_LONG) {
                    251:         if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) {
                    252:             return 1;
                    253:         }
                    254:     }
                    255:     return 0;
                    256: }

unix.superglobalmegacorp.com