vm/BitVector.h

   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_