Home | History | Annotate | Download | only in wrapsim 
      1 /*
      2  * Copyright 2007 The Android Open Source Project
      3  *
      4  * Simple bit vector.
      5  */
      6 #include "Common.h"
      7 
      8 #include <stdlib.h>
      9 #include <stdint.h>
     10 #include <string.h>
     11 #include <assert.h>
     12 
     13 #define kBitVectorGrowth    4   /* increase by 4 uint32_t when limit hit */
     14 
     15 
     16 /*
     17  * Allocate a bit vector with enough space to hold at least the specified
     18  * number of bits.
     19  */
     20 BitVector* wsAllocBitVector(int startBits, int isExpandable)
     21 {
     22     BitVector* bv;
     23     int count;
     24 
     25     assert(sizeof(bv->storage[0]) == 4);        /* assuming 32-bit units */
     26     assert(startBits > 0);
     27 
     28     bv = (BitVector*) malloc(sizeof(BitVector));
     29 
     30     count = (startBits + 31) >> 5;
     31 
     32     bv->storageSize = count;
     33     bv->isExpandable = isExpandable;
     34     bv->storage = (uint32_t*) malloc(count * sizeof(uint32_t));
     35     memset(bv->storage, 0xff, count * sizeof(uint32_t));
     36     return bv;
     37 }
     38 
     39 /*
     40  * Free a BitVector.
     41  */
     42 void wsFreeBitVector(BitVector* pBits)
     43 {
     44     if (pBits == NULL)
     45         return;
     46 
     47     free(pBits->storage);
     48     free(pBits);
     49 }
     50 
     51 /*
     52  * "Allocate" the first-available bit in the bitmap.
     53  *
     54  * This is not synchronized.  The caller is expected to hold some sort of
     55  * lock that prevents multiple threads from executing simultaneously in
     56  * dvmAllocBit/dvmFreeBit.
     57  *
     58  * The bitmap indicates which resources are free, so we use '1' to indicate
     59  * available and '0' to indicate allocated.
     60  */
     61 int wsAllocBit(BitVector* pBits)
     62 {
     63     int word, bit;
     64 
     65 retry:
     66     for (word = 0; word < pBits->storageSize; word++) {
     67         if (pBits->storage[word] != 0) {
     68             /*
     69              * There are unallocated bits in this word.  Return the first.
     70              */
     71             bit = ffs(pBits->storage[word]) -1;
     72             assert(bit >= 0 && bit < 32);
     73             pBits->storage[word] &= ~(1 << bit);
     74             return (word << 5) | bit;
     75         }
     76     }
     77 
     78     /*
     79      * Ran out of space, allocate more if we're allowed to.
     80      */
     81     if (!pBits->isExpandable)
     82         return -1;
     83 
     84     pBits->storage = realloc(pBits->storage,
     85                     (pBits->storageSize + kBitVectorGrowth) * sizeof(uint32_t));
     86     memset(&pBits->storage[pBits->storageSize], 0xff,
     87         kBitVectorGrowth * sizeof(uint32_t));
     88     pBits->storageSize += kBitVectorGrowth;
     89     goto retry;
     90 }
     91 
     92 /*
     93  * Mark the specified bit as "free".
     94  */
     95 void wsFreeBit(BitVector* pBits, int num)
     96 {
     97     assert(num >= 0 &&
     98            num < (int) pBits->storageSize * (int)sizeof(uint32_t) * 8);
     99 
    100     pBits->storage[num >> 5] |= 1 << (num & 0x1f);
    101 }
    102 
    103