2 * Copyright (C) 2008 The Android Open Source Project
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 * Implementation of an expandable bit vector.
25 #define kBitVectorGrowth 4 /* increase by 4 u4s when limit hit */
29 * Allocate a bit vector with enough space to hold at least the specified
32 BitVector* dvmAllocBitVector(unsigned int startBits, bool expandable)
37 assert(sizeof(bv->storage[0]) == 4); /* assuming 32-bit units */
39 bv = (BitVector*) malloc(sizeof(BitVector));
41 count = (startBits + 31) >> 5;
43 bv->storageSize = count;
44 bv->expandable = expandable;
45 bv->storage = (u4*) malloc(count * sizeof(u4));
46 memset(bv->storage, 0x00, count * sizeof(u4));
53 void dvmFreeBitVector(BitVector* pBits)
63 * "Allocate" the first-available bit in the bitmap.
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.
69 int dvmAllocBit(BitVector* pBits)
71 unsigned int word, bit;
74 for (word = 0; word < pBits->storageSize; word++) {
75 if (pBits->storage[word] != 0xffffffff) {
77 * There are unallocated bits in this word. Return the first.
79 bit = ffs(~(pBits->storage[word])) -1;
81 pBits->storage[word] |= 1 << bit;
82 return (word << 5) | bit;
87 * Ran out of space, allocate more if we're allowed to.
89 if (!pBits->expandable)
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;
101 * Mark the specified bit as "set".
103 void dvmSetBit(BitVector* pBits, unsigned int num)
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);
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));
120 memset(&pBits->storage[pBits->storageSize], 0x00,
121 (newSize - pBits->storageSize) * sizeof(u4));
122 pBits->storageSize = newSize;
125 pBits->storage[num >> 5] |= 1 << (num & 0x1f);
129 * Mark the specified bit as "clear".
131 void dvmClearBit(BitVector* pBits, unsigned int num)
133 assert(num < pBits->storageSize * sizeof(u4) * 8);
135 pBits->storage[num >> 5] &= ~(1 << (num & 0x1f));
139 * Mark all bits bit as "clear".
141 void dvmClearAllBits(BitVector* pBits)
143 unsigned int count = pBits->storageSize;
144 memset(pBits->storage, 0, count * sizeof(u4));
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
152 void dvmSetInitialBits(BitVector* pBits, unsigned int numBits)
155 assert(((numBits + 31) >> 5) <= pBits->storageSize);
156 for (idx = 0; idx < (numBits >> 5); idx++) {
157 pBits->storage[idx] = -1;
159 unsigned int remNumBits = numBits & 0x1f;
161 pBits->storage[idx] = (1 << remNumBits) - 1;
166 * Determine whether or not the specified bit is set.
168 bool dvmIsBitSet(const BitVector* pBits, unsigned int num)
170 assert(num < pBits->storageSize * sizeof(u4) * 8);
172 unsigned int val = pBits->storage[num >> 5] & (1 << (num & 0x1f));
177 * Count the number of bits that are set.
179 int dvmCountSetBits(const BitVector* pBits)
182 unsigned int count = 0;
184 for (word = 0; word < pBits->storageSize; word++) {
185 u4 val = pBits->storage[word];
188 if (val == 0xffffffff) {
191 /* count the number of '1' bits */
204 * If the vector sizes don't match, log an error and abort.
206 static void checkSizes(const BitVector* bv1, const BitVector* bv2)
208 if (bv1->storageSize != bv2->storageSize) {
209 ALOGE("Mismatched vector sizes (%d, %d)",
210 bv1->storageSize, bv2->storageSize);
216 * Copy a whole vector to the other. Only do that when the both vectors have
219 void dvmCopyBitVector(BitVector *dest, const BitVector *src)
221 /* if dest is expandable and < src, we could expand dest to match */
222 checkSizes(dest, src);
224 memcpy(dest->storage, src->storage, sizeof(u4) * dest->storageSize);
228 * Intersect two bit vectors and store the result to the dest vector.
230 bool dvmIntersectBitVectors(BitVector *dest, const BitVector *src1,
231 const BitVector *src2)
233 if (dest->storageSize != src1->storageSize ||
234 dest->storageSize != src2->storageSize ||
235 dest->expandable != src1->expandable ||
236 dest->expandable != src2->expandable)
240 for (idx = 0; idx < dest->storageSize; idx++) {
241 dest->storage[idx] = src1->storage[idx] & src2->storage[idx];
247 * Unify two bit vectors and store the result to the dest vector.
249 bool dvmUnifyBitVectors(BitVector *dest, const BitVector *src1,
250 const BitVector *src2)
252 if (dest->storageSize != src1->storageSize ||
253 dest->storageSize != src2->storageSize ||
254 dest->expandable != src1->expandable ||
255 dest->expandable != src2->expandable)
259 for (idx = 0; idx < dest->storageSize; idx++) {
260 dest->storage[idx] = src1->storage[idx] | src2->storage[idx];
266 * Compare two bit vectors and return true if difference is seen.
268 bool dvmCompareBitVectors(const BitVector *src1, const BitVector *src2)
270 if (src1->storageSize != src2->storageSize ||
271 src1->expandable != src2->expandable)
275 for (idx = 0; idx < src1->storageSize; idx++) {
276 if (src1->storage[idx] != src2->storage[idx]) return true;
281 /* Initialize the iterator structure */
282 void dvmBitVectorIteratorInit(BitVector* pBits, BitVectorIterator* iterator)
284 iterator->pBits = pBits;
285 iterator->bitSize = pBits->storageSize * sizeof(u4) * 8;
289 /* Return the next position set to 1. -1 means end-of-element reached */
290 int dvmBitVectorIteratorNext(BitVectorIterator* iterator)
292 const BitVector* pBits = iterator->pBits;
293 u4 bitIndex = iterator->idx;
295 assert(iterator->bitSize == pBits->storageSize * sizeof(u4) * 8);
296 if (bitIndex >= iterator->bitSize) return -1;
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;
306 /* No more set bits */
312 * Merge the contents of "src" into "dst", checking to see if this causes
313 * any changes to occur. This is a logical OR.
315 * Returns "true" if the contents of the destination vector were modified.
317 bool dvmCheckMergeBitVectors(BitVector* dst, const BitVector* src)
319 bool changed = false;
321 checkSizes(dst, src);
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;