BitVector.cpp revision b74e7190e86d559712747e5cdb31a0d390b7af7d 
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*) calloc(count, sizeof(u4));
46    return bv;
47}
48
49/*
50 * Free a BitVector.
51 */
52void 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 */
68int dvmAllocBit(BitVector* pBits)
69{
70    unsigned int word, bit;
71
72retry:
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 */
102void 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 */
130void 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 */
140void 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 */
151void 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 */
167bool 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 */
178int 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 */
205static 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 */
218void 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 */
229bool 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 */
248bool 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 */
267bool 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 */
281void 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 */
289int 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 */
316bool 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