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 */
dvmAllocBitVector(unsigned int startBits,bool expandable)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 */
dvmFreeBitVector(BitVector * pBits)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 */
dvmAllocBit(BitVector * pBits)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 */
dvmSetBit(BitVector * pBits,unsigned int num)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 */
dvmClearBit(BitVector * pBits,unsigned int num)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 */
dvmClearAllBits(BitVector * pBits)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 */
dvmSetInitialBits(BitVector * pBits,unsigned int numBits)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 */
dvmIsBitSet(const BitVector * pBits,unsigned int num)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 */
dvmCountSetBits(const BitVector * pBits)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 */
checkSizes(const BitVector * bv1,const BitVector * bv2)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 */
dvmCopyBitVector(BitVector * dest,const BitVector * src)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 */
dvmIntersectBitVectors(BitVector * dest,const BitVector * src1,const BitVector * src2)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 */
dvmUnifyBitVectors(BitVector * dest,const BitVector * src1,const BitVector * src2)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 */
dvmCompareBitVectors(const BitVector * src1,const BitVector * src2)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 */
dvmBitVectorIteratorInit(BitVector * pBits,BitVectorIterator * iterator)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 */
dvmBitVectorIteratorNext(BitVectorIterator * iterator)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 */
dvmCheckMergeBitVectors(BitVector * dst,const BitVector * src)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 }
333