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 */ 29 struct 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 */ 36 struct BitVectorIterator { 37 BitVector *pBits; 38 u4 idx; 39 u4 bitSize; 40 }; 41 42 /* allocate a bit vector with enough space to hold "startBits" bits */ 43 BitVector* dvmAllocBitVector(unsigned int startBits, bool expandable); 44 void 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 */ 59 int dvmAllocBit(BitVector* pBits); 60 void dvmSetBit(BitVector* pBits, unsigned int num); 61 void dvmClearBit(BitVector* pBits, unsigned int num); 62 void dvmClearAllBits(BitVector* pBits); 63 void dvmSetInitialBits(BitVector* pBits, unsigned int numBits); 64 bool dvmIsBitSet(const BitVector* pBits, unsigned int num); 65 66 /* count the number of bits that have been set */ 67 int dvmCountSetBits(const BitVector* pBits); 68 69 /* copy one vector to another of equal size */ 70 void dvmCopyBitVector(BitVector *dest, const BitVector *src); 71 72 /* 73 * Intersect two bit vectors and store the result to the dest vector. 74 */ 75 bool 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 */ 81 bool 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 */ 90 bool dvmCheckMergeBitVectors(BitVector* dst, const BitVector* src); 91 92 /* 93 * Compare two bit vectors and return true if difference is seen. 94 */ 95 bool dvmCompareBitVectors(const BitVector *src1, const BitVector *src2); 96 97 /* Initialize the iterator structure */ 98 void dvmBitVectorIteratorInit(BitVector* pBits, BitVectorIterator* iterator); 99 100 /* Return the next position set to 1. -1 means end-of-vector reached */ 101 int dvmBitVectorIteratorNext(BitVectorIterator* iterator); 102 103 #endif // DALVIK_BITVECTOR_H_ 104