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 */
wsAllocBitVector(int startBits,int isExpandable)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 */
wsFreeBitVector(BitVector * pBits)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 */
wsAllocBit(BitVector * pBits)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 */
wsFreeBit(BitVector * pBits,int num)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