vm/BitVector.cpp

   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 }