Home | History | Annotate | Download | only in vm 
      1 /*
      2  * Copyright (C) 2008 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 /*
     18  * Implementation of an expandable bit vector.
     19  */
     20 #include "Dalvik.h"
     21 
     22 #include <stdlib.h>
     23 #include <strings.h>
     24 
     25 #define kBitVectorGrowth    4   /* increase by 4 u4s when limit hit */
     26 
     27 
     28 /*
     29  * Allocate a bit vector with enough space to hold at least the specified
     30  * number of bits.
     31  */
     32 BitVector* dvmAllocBitVector(unsigned int startBits, bool expandable)
     33 {
     34     BitVector* bv;
     35     unsigned int count;
     36 
     37     assert(sizeof(bv->storage[0]) == 4);        /* assuming 32-bit units */
     38 
     39     bv = (BitVector*) malloc(sizeof(BitVector));
     40 
     41     count = (startBits + 31) >> 5;
     42 
     43     bv->storageSize = count;
     44     bv->expandable = expandable;
     45     bv->storage = (u4*) calloc(count, sizeof(u4));
     46     return bv;
     47 }
     48 
     49 /*
     50  * Free a BitVector.
     51  */
     52 void dvmFreeBitVector(BitVector* pBits)
     53 {
     54     if (pBits == NULL)
     55         return;
     56 
     57     free(pBits->storage);
     58     free(pBits);
     59 }
     60 
     61 /*
     62  * "Allocate" the first-available bit in the bitmap.
     63  *
     64  * This is not synchronized.  The caller is expected to hold some sort of
     65  * lock that prevents multiple threads from executing simultaneously in
     66  * dvmAllocBit/dvmFreeBit.
     67  */
     68 int dvmAllocBit(BitVector* pBits)
     69 {
     70     unsigned int word, bit;
     71 
     72 retry:
     73     for (word = 0; word < pBits->storageSize; word++) {
     74         if (pBits->storage[word] != 0xffffffff) {
     75             /*
     76              * There are unallocated bits in this word.  Return the first.
     77              */
     78             bit = ffs(~(pBits->storage[word])) -1;
     79             assert(bit < 32);
     80             pBits->storage[word] |= 1 << bit;
     81             return (word << 5) | bit;
     82         }
     83     }
     84 
     85     /*
     86      * Ran out of space, allocate more if we're allowed to.
     87      */
     88     if (!pBits->expandable)
     89         return -1;
     90 
     91     pBits->storage = (u4*)realloc(pBits->storage,
     92                     (pBits->storageSize + kBitVectorGrowth) * sizeof(u4));
     93     memset(&pBits->storage[pBits->storageSize], 0x00,
     94         kBitVectorGrowth * sizeof(u4));
     95     pBits->storageSize += kBitVectorGrowth;
     96     goto retry;
     97 }
     98 
     99 /*
    100  * Mark the specified bit as "set".
    101  */
    102 void dvmSetBit(BitVector* pBits, unsigned int num)
    103 {
    104     if (num >= pBits->storageSize * sizeof(u4) * 8) {
    105         if (!pBits->expandable) {
    106             ALOGE("Attempt to set bit outside valid range (%d, limit is %d)",
    107                 num, pBits->storageSize * sizeof(u4) * 8);
    108             dvmAbort();
    109         }
    110 
    111         /* Round up to word boundaries for "num+1" bits */
    112         unsigned int newSize = (num + 1 + 31) >> 5;
    113         assert(newSize > pBits->storageSize);
    114         pBits->storage = (u4*)realloc(pBits->storage, newSize * sizeof(u4));
    115         if (pBits->storage == NULL) {
    116             ALOGE("BitVector expansion to %d failed", newSize * sizeof(u4));
    117             dvmAbort();
    118         }
    119         memset(&pBits->storage[pBits->storageSize], 0x00,
    120             (newSize - pBits->storageSize) * sizeof(u4));
    121         pBits->storageSize = newSize;
    122     }
    123 
    124     pBits->storage[num >> 5] |= 1 << (num & 0x1f);
    125 }
    126 
    127 /*
    128  * Mark the specified bit as "clear".
    129  */
    130 void dvmClearBit(BitVector* pBits, unsigned int num)
    131 {
    132     assert(num < pBits->storageSize * sizeof(u4) * 8);
    133 
    134     pBits->storage[num >> 5] &= ~(1 << (num & 0x1f));
    135 }
    136 
    137 /*
    138  * Mark all bits bit as "clear".
    139  */
    140 void dvmClearAllBits(BitVector* pBits)
    141 {
    142     unsigned int count = pBits->storageSize;
    143     memset(pBits->storage, 0, count * sizeof(u4));
    144 }
    145 
    146 /*
    147  * Mark specified number of bits as "set". Cannot set all bits like ClearAll
    148  * since there might be unused bits - setting those to one will confuse the
    149  * iterator.
    150  */
    151 void dvmSetInitialBits(BitVector* pBits, unsigned int numBits)
    152 {
    153     unsigned int idx;
    154     assert(((numBits + 31) >> 5) <= pBits->storageSize);
    155     for (idx = 0; idx < (numBits >> 5); idx++) {
    156         pBits->storage[idx] = -1;
    157     }
    158     unsigned int remNumBits = numBits & 0x1f;
    159     if (remNumBits) {
    160         pBits->storage[idx] = (1 << remNumBits) - 1;
    161     }
    162 }
    163 
    164 /*
    165  * Determine whether or not the specified bit is set.
    166  */
    167 bool dvmIsBitSet(const BitVector* pBits, unsigned int num)
    168 {
    169     assert(num < pBits->storageSize * sizeof(u4) * 8);
    170 
    171     unsigned int val = pBits->storage[num >> 5] & (1 << (num & 0x1f));
    172     return (val != 0);
    173 }
    174 
    175 /*
    176  * Count the number of bits that are set.
    177  */
    178 int dvmCountSetBits(const BitVector* pBits)
    179 {
    180     unsigned int word;
    181     unsigned int count = 0;
    182 
    183     for (word = 0; word < pBits->storageSize; word++) {
    184         u4 val = pBits->storage[word];
    185 
    186         if (val != 0) {
    187             if (val == 0xffffffff) {
    188                 count += 32;
    189             } else {
    190                 /* count the number of '1' bits */
    191                 while (val != 0) {
    192                     val &= val - 1;
    193                     count++;
    194                 }
    195             }
    196         }
    197     }
    198 
    199     return count;
    200 }
    201 
    202 /*
    203  * If the vector sizes don't match, log an error and abort.
    204  */
    205 static void checkSizes(const BitVector* bv1, const BitVector* bv2)
    206 {
    207     if (bv1->storageSize != bv2->storageSize) {
    208         ALOGE("Mismatched vector sizes (%d, %d)",
    209             bv1->storageSize, bv2->storageSize);
    210         dvmAbort();
    211     }
    212 }
    213 
    214 /*
    215  * Copy a whole vector to the other. Only do that when the both vectors have
    216  * the same size.
    217  */
    218 void dvmCopyBitVector(BitVector *dest, const BitVector *src)
    219 {
    220     /* if dest is expandable and < src, we could expand dest to match */
    221     checkSizes(dest, src);
    222 
    223     memcpy(dest->storage, src->storage, sizeof(u4) * dest->storageSize);
    224 }
    225 
    226 /*
    227  * Intersect two bit vectors and store the result to the dest vector.
    228  */
    229 bool dvmIntersectBitVectors(BitVector *dest, const BitVector *src1,
    230                             const BitVector *src2)
    231 {
    232     if (dest->storageSize != src1->storageSize ||
    233         dest->storageSize != src2->storageSize ||
    234         dest->expandable != src1->expandable ||
    235         dest->expandable != src2->expandable)
    236         return false;
    237 
    238     unsigned int idx;
    239     for (idx = 0; idx < dest->storageSize; idx++) {
    240         dest->storage[idx] = src1->storage[idx] & src2->storage[idx];
    241     }
    242     return true;
    243 }
    244 
    245 /*
    246  * Unify two bit vectors and store the result to the dest vector.
    247  */
    248 bool dvmUnifyBitVectors(BitVector *dest, const BitVector *src1,
    249                         const BitVector *src2)
    250 {
    251     if (dest->storageSize != src1->storageSize ||
    252         dest->storageSize != src2->storageSize ||
    253         dest->expandable != src1->expandable ||
    254         dest->expandable != src2->expandable)
    255         return false;
    256 
    257     unsigned int idx;
    258     for (idx = 0; idx < dest->storageSize; idx++) {
    259         dest->storage[idx] = src1->storage[idx] | src2->storage[idx];
    260     }
    261     return true;
    262 }
    263 
    264 /*
    265  * Compare two bit vectors and return true if difference is seen.
    266  */
    267 bool dvmCompareBitVectors(const BitVector *src1, const BitVector *src2)
    268 {
    269     if (src1->storageSize != src2->storageSize ||
    270         src1->expandable != src2->expandable)
    271         return true;
    272 
    273     unsigned int idx;
    274     for (idx = 0; idx < src1->storageSize; idx++) {
    275         if (src1->storage[idx] != src2->storage[idx]) return true;
    276     }
    277     return false;
    278 }
    279 
    280 /* Initialize the iterator structure */
    281 void dvmBitVectorIteratorInit(BitVector* pBits, BitVectorIterator* iterator)
    282 {
    283     iterator->pBits = pBits;
    284     iterator->bitSize = pBits->storageSize * sizeof(u4) * 8;
    285     iterator->idx = 0;
    286 }
    287 
    288 /* Return the next position set to 1. -1 means end-of-element reached */
    289 int dvmBitVectorIteratorNext(BitVectorIterator* iterator)
    290 {
    291     const BitVector* pBits = iterator->pBits;
    292     u4 bitIndex = iterator->idx;
    293 
    294     assert(iterator->bitSize == pBits->storageSize * sizeof(u4) * 8);
    295     if (bitIndex >= iterator->bitSize) return -1;
    296 
    297     for (; bitIndex < iterator->bitSize; bitIndex++) {
    298         unsigned int wordIndex = bitIndex >> 5;
    299         unsigned int mask = 1 << (bitIndex & 0x1f);
    300         if (pBits->storage[wordIndex] & mask) {
    301             iterator->idx = bitIndex+1;
    302             return bitIndex;
    303         }
    304     }
    305     /* No more set bits */
    306     return -1;
    307 }
    308 
    309 
    310 /*
    311  * Merge the contents of "src" into "dst", checking to see if this causes
    312  * any changes to occur.  This is a logical OR.
    313  *
    314  * Returns "true" if the contents of the destination vector were modified.
    315  */
    316 bool dvmCheckMergeBitVectors(BitVector* dst, const BitVector* src)
    317 {
    318     bool changed = false;
    319 
    320     checkSizes(dst, src);
    321 
    322     unsigned int idx;
    323     for (idx = 0; idx < dst->storageSize; idx++) {
    324         u4 merged = src->storage[idx] | dst->storage[idx];
    325         if (dst->storage[idx] != merged) {
    326             dst->storage[idx] = merged;
    327             changed = true;
    328         }
    329     }
    330 
    331     return changed;
    332 }
    333