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