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 * Miscellaneous utility functions.
19 */
20#ifndef DALVIK_BITVECTOR_H_
21#define DALVIK_BITVECTOR_H_
22
23/*
24 * Expanding bitmap, used for tracking resources.  Bits are numbered starting
25 * from zero.
26 *
27 * All operations on a BitVector are unsynchronized.
28 */
29struct BitVector {
30    bool    expandable;     /* expand bitmap if we run out? */
31    u4      storageSize;    /* current size, in 32-bit words */
32    u4*     storage;
33};
34
35/* Handy iterator to walk through the bit positions set to 1 */
36struct BitVectorIterator {
37    BitVector *pBits;
38    u4 idx;
39    u4 bitSize;
40};
41
42/* allocate a bit vector with enough space to hold "startBits" bits */
43BitVector* dvmAllocBitVector(unsigned int startBits, bool expandable);
44void dvmFreeBitVector(BitVector* pBits);
45
46/*
47 * dvmAllocBit always allocates the first possible bit.  If we run out of
48 * space in the bitmap, and it's not marked expandable, dvmAllocBit
49 * returns -1.
50 *
51 * dvmSetBit sets the specified bit, expanding the vector if necessary
52 * (and possible).  Attempting to set a bit past the limit of a non-expandable
53 * bit vector will cause a fatal error.
54 *
55 * dvmSetInitialBits sets all bits in [0..numBits-1]. Won't expand the vector.
56 *
57 * dvmIsBitSet returns "true" if the bit is set.
58 */
59int dvmAllocBit(BitVector* pBits);
60void dvmSetBit(BitVector* pBits, unsigned int num);
61void dvmClearBit(BitVector* pBits, unsigned int num);
62void dvmClearAllBits(BitVector* pBits);
63void dvmSetInitialBits(BitVector* pBits, unsigned int numBits);
64bool dvmIsBitSet(const BitVector* pBits, unsigned int num);
65
66/* count the number of bits that have been set */
67int dvmCountSetBits(const BitVector* pBits);
68
69/* copy one vector to another of equal size */
70void dvmCopyBitVector(BitVector *dest, const BitVector *src);
71
72/*
73 * Intersect two bit vectors and store the result to the dest vector.
74 */
75bool dvmIntersectBitVectors(BitVector *dest, const BitVector *src1,
76                            const BitVector *src2);
77
78/*
79 * Unify two bit vectors and store the result to the dest vector.
80 */
81bool dvmUnifyBitVectors(BitVector *dest, const BitVector *src1,
82                        const BitVector *src2);
83
84/*
85 * Merge the contents of "src" into "dst", checking to see if this causes
86 * any changes to occur.
87 *
88 * Returns "true" if the contents of the destination vector were modified.
89 */
90bool dvmCheckMergeBitVectors(BitVector* dst, const BitVector* src);
91
92/*
93 * Compare two bit vectors and return true if difference is seen.
94 */
95bool dvmCompareBitVectors(const BitVector *src1, const BitVector *src2);
96
97/* Initialize the iterator structure */
98void dvmBitVectorIteratorInit(BitVector* pBits, BitVectorIterator* iterator);
99
100/* Return the next position set to 1. -1 means end-of-vector reached */
101int dvmBitVectorIteratorNext(BitVectorIterator* iterator);
102
103#endif  // DALVIK_BITVECTOR_H_
104