BitVector.cpp revision c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2ef 
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 */
32BitVector* 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 */
53void 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 */
69int dvmAllocBit(BitVector* pBits)
70{
71    unsigned int word, bit;
72
73retry:
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 */
103void 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 */
131void 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 */
141void 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 */
152void 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 */
168bool 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 */
179int 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 */
206static 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 */
219void 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 */
230bool 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 */
249bool 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 */
268bool 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 */
282void 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 */
290int 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 */
317bool 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}
334