vm/BitVector.cpp - platform/dalvik - Git at Google

 /*
  * Copyright (C) 2008 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 /*
  * Implementation of an expandable bit vector.
  */
 #include "Dalvik.h"

 #include <stdlib.h>
 #include <strings.h>

 #define kBitVectorGrowth    4   /* increase by 4 u4s when limit hit */


 /*
  * Allocate a bit vector with enough space to hold at least the specified
  * number of bits.
  */
 BitVector* dvmAllocBitVector(unsigned int startBits, bool expandable)
 {
     BitVector* bv;
     unsigned int count;

     assert(sizeof(bv->storage[0]) == 4);        /* assuming 32-bit units */

     bv = (BitVector*) malloc(sizeof(BitVector));

     count = (startBits + 31) >> 5;

     bv->storageSize = count;
     bv->expandable = expandable;
     bv->storage = (u4*) calloc(count, sizeof(u4));
     return bv;
 }

 /*
  * Free a BitVector.
  */
 void dvmFreeBitVector(BitVector* pBits)
 {
     if (pBits == NULL)
         return;

     free(pBits->storage);
     free(pBits);
 }

 /*
  * "Allocate" the first-available bit in the bitmap.
  *
  * This is not synchronized.  The caller is expected to hold some sort of
  * lock that prevents multiple threads from executing simultaneously in
  * dvmAllocBit/dvmFreeBit.
  */
 int dvmAllocBit(BitVector* pBits)
 {
     unsigned int word, bit;

 retry:
     for (word = 0; word < pBits->storageSize; word++) {
         if (pBits->storage[word] != 0xffffffff) {
             /*
              * There are unallocated bits in this word.  Return the first.
              */
             bit = ffs(~(pBits->storage[word])) -1;
             assert(bit < 32);
             pBits->storage[word] |= 1 << bit;
             return (word << 5) | bit;
         }
     }

     /*
      * Ran out of space, allocate more if we're allowed to.
      */
     if (!pBits->expandable)
         return -1;

     pBits->storage = (u4*)realloc(pBits->storage,
                     (pBits->storageSize + kBitVectorGrowth) * sizeof(u4));
     memset(&pBits->storage[pBits->storageSize], 0x00,
         kBitVectorGrowth * sizeof(u4));
     pBits->storageSize += kBitVectorGrowth;
     goto retry;
 }

 /*
  * Mark the specified bit as "set".
  */
 void dvmSetBit(BitVector* pBits, unsigned int num)
 {
     if (num >= pBits->storageSize * sizeof(u4) * 8) {
         if (!pBits->expandable) {
             ALOGE("Attempt to set bit outside valid range (%d, limit is %d)",
                 num, pBits->storageSize * sizeof(u4) * 8);
             dvmAbort();
         }

         /* Round up to word boundaries for "num+1" bits */
         unsigned int newSize = (num + 1 + 31) >> 5;
         assert(newSize > pBits->storageSize);
         pBits->storage = (u4*)realloc(pBits->storage, newSize * sizeof(u4));
         if (pBits->storage == NULL) {
             ALOGE("BitVector expansion to %d failed", newSize * sizeof(u4));
             dvmAbort();
         }
         memset(&pBits->storage[pBits->storageSize], 0x00,
             (newSize - pBits->storageSize) * sizeof(u4));
         pBits->storageSize = newSize;
     }

     pBits->storage[num >> 5] |= 1 << (num & 0x1f);
 }

 /*
  * Mark the specified bit as "clear".
  */
 void dvmClearBit(BitVector* pBits, unsigned int num)
 {
     assert(num < pBits->storageSize * sizeof(u4) * 8);

     pBits->storage[num >> 5] &= ~(1 << (num & 0x1f));
 }

 /*
  * Mark all bits bit as "clear".
  */
 void dvmClearAllBits(BitVector* pBits)
 {
     unsigned int count = pBits->storageSize;
     memset(pBits->storage, 0, count * sizeof(u4));
 }

 /*
  * Mark specified number of bits as "set". Cannot set all bits like ClearAll
  * since there might be unused bits - setting those to one will confuse the
  * iterator.
  */
 void dvmSetInitialBits(BitVector* pBits, unsigned int numBits)
 {
     unsigned int idx;
     assert(((numBits + 31) >> 5) <= pBits->storageSize);
     for (idx = 0; idx < (numBits >> 5); idx++) {
         pBits->storage[idx] = -1;
     }
     unsigned int remNumBits = numBits & 0x1f;
     if (remNumBits) {
         pBits->storage[idx] = (1 << remNumBits) - 1;
     }
 }

 /*
  * Determine whether or not the specified bit is set.
  */
 bool dvmIsBitSet(const BitVector* pBits, unsigned int num)
 {
     assert(num < pBits->storageSize * sizeof(u4) * 8);

     unsigned int val = pBits->storage[num >> 5] & (1 << (num & 0x1f));
     return (val != 0);
 }

 /*
  * Count the number of bits that are set.
  */
 int dvmCountSetBits(const BitVector* pBits)
 {
     unsigned int word;
     unsigned int count = 0;

     for (word = 0; word < pBits->storageSize; word++) {
         u4 val = pBits->storage[word];

         if (val != 0) {
             if (val == 0xffffffff) {
                 count += 32;
             } else {
                 /* count the number of '1' bits */
                 while (val != 0) {
                     val &= val - 1;
                     count++;
                 }
             }
         }
     }

     return count;
 }

 /*
  * If the vector sizes don't match, log an error and abort.
  */
 static void checkSizes(const BitVector* bv1, const BitVector* bv2)
 {
     if (bv1->storageSize != bv2->storageSize) {
         ALOGE("Mismatched vector sizes (%d, %d)",
             bv1->storageSize, bv2->storageSize);
         dvmAbort();
     }
 }

 /*
  * Copy a whole vector to the other. Only do that when the both vectors have
  * the same size.
  */
 void dvmCopyBitVector(BitVector *dest, const BitVector *src)
 {
     /* if dest is expandable and < src, we could expand dest to match */
     checkSizes(dest, src);

     memcpy(dest->storage, src->storage, sizeof(u4) * dest->storageSize);
 }

 /*
  * Intersect two bit vectors and store the result to the dest vector.
  */
 bool dvmIntersectBitVectors(BitVector *dest, const BitVector *src1,
                             const BitVector *src2)
 {
     if (dest->storageSize != src1->storageSize ||
         dest->storageSize != src2->storageSize ||
         dest->expandable != src1->expandable ||
         dest->expandable != src2->expandable)
         return false;

     unsigned int idx;
     for (idx = 0; idx < dest->storageSize; idx++) {
         dest->storage[idx] = src1->storage[idx] & src2->storage[idx];
     }
     return true;
 }

 /*
  * Unify two bit vectors and store the result to the dest vector.
  */
 bool dvmUnifyBitVectors(BitVector *dest, const BitVector *src1,
                         const BitVector *src2)
 {
     if (dest->storageSize != src1->storageSize ||
         dest->storageSize != src2->storageSize ||
         dest->expandable != src1->expandable ||
         dest->expandable != src2->expandable)
         return false;

     unsigned int idx;
     for (idx = 0; idx < dest->storageSize; idx++) {
         dest->storage[idx] = src1->storage[idx] | src2->storage[idx];
     }
     return true;
 }

 /*
  * Compare two bit vectors and return true if difference is seen.
  */
 bool dvmCompareBitVectors(const BitVector *src1, const BitVector *src2)
 {
     if (src1->storageSize != src2->storageSize ||
         src1->expandable != src2->expandable)
         return true;

     unsigned int idx;
     for (idx = 0; idx < src1->storageSize; idx++) {
         if (src1->storage[idx] != src2->storage[idx]) return true;
     }
     return false;
 }

 /* Initialize the iterator structure */
 void dvmBitVectorIteratorInit(BitVector* pBits, BitVectorIterator* iterator)
 {
     iterator->pBits = pBits;
     iterator->bitSize = pBits->storageSize * sizeof(u4) * 8;
     iterator->idx = 0;
 }

 /* Return the next position set to 1. -1 means end-of-element reached */
 int dvmBitVectorIteratorNext(BitVectorIterator* iterator)
 {
     const BitVector* pBits = iterator->pBits;
     u4 bitIndex = iterator->idx;

     assert(iterator->bitSize == pBits->storageSize * sizeof(u4) * 8);
     if (bitIndex >= iterator->bitSize) return -1;

     for (; bitIndex < iterator->bitSize; bitIndex++) {
         unsigned int wordIndex = bitIndex >> 5;
         unsigned int mask = 1 << (bitIndex & 0x1f);
         if (pBits->storage[wordIndex] & mask) {
             iterator->idx = bitIndex+1;
             return bitIndex;
         }
     }
     /* No more set bits */
     return -1;
 }


 /*
  * Merge the contents of "src" into "dst", checking to see if this causes
  * any changes to occur.  This is a logical OR.
  *
  * Returns "true" if the contents of the destination vector were modified.
  */
 bool dvmCheckMergeBitVectors(BitVector* dst, const BitVector* src)
 {
     bool changed = false;

     checkSizes(dst, src);

     unsigned int idx;
     for (idx = 0; idx < dst->storageSize; idx++) {
         u4 merged = src->storage[idx] | dst->storage[idx];
         if (dst->storage[idx] != merged) {
             dst->storage[idx] = merged;
             changed = true;
         }
     }

     return changed;
 }
	/*
	* Copyright (C) 2008 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	/*
	* Implementation of an expandable bit vector.
	*/
	#include "Dalvik.h"

	#include <stdlib.h>
	#include <strings.h>

	#define kBitVectorGrowth 4 /* increase by 4 u4s when limit hit */


	/*
	* Allocate a bit vector with enough space to hold at least the specified
	* number of bits.
	*/
	BitVector* dvmAllocBitVector(unsigned int startBits, bool expandable)
	{
	BitVector* bv;
	unsigned int count;

	assert(sizeof(bv->storage[0]) == 4); /* assuming 32-bit units */

	bv = (BitVector*) malloc(sizeof(BitVector));

	count = (startBits + 31) >> 5;

	bv->storageSize = count;
	bv->expandable = expandable;
	bv->storage = (u4*) calloc(count, sizeof(u4));
	return bv;
	}

	/*
	* Free a BitVector.
	*/
	void dvmFreeBitVector(BitVector* pBits)
	{
	if (pBits == NULL)
	return;

	free(pBits->storage);
	free(pBits);
	}

	/*
	* "Allocate" the first-available bit in the bitmap.
	*
	* This is not synchronized. The caller is expected to hold some sort of
	* lock that prevents multiple threads from executing simultaneously in
	* dvmAllocBit/dvmFreeBit.
	*/
	int dvmAllocBit(BitVector* pBits)
	{
	unsigned int word, bit;

	retry:
	for (word = 0; word < pBits->storageSize; word++) {
	if (pBits->storage[word] != 0xffffffff) {
	/*
	* There are unallocated bits in this word. Return the first.
	*/
	bit = ffs(~(pBits->storage[word])) -1;
	assert(bit < 32);
	pBits->storage[word] \|= 1 << bit;
	return (word << 5) \| bit;
	}
	}

	/*
	* Ran out of space, allocate more if we're allowed to.
	*/
	if (!pBits->expandable)
	return -1;

	pBits->storage = (u4*)realloc(pBits->storage,
	(pBits->storageSize + kBitVectorGrowth) * sizeof(u4));
	memset(&pBits->storage[pBits->storageSize], 0x00,
	kBitVectorGrowth * sizeof(u4));
	pBits->storageSize += kBitVectorGrowth;
	goto retry;
	}

	/*
	* Mark the specified bit as "set".
	*/
	void dvmSetBit(BitVector* pBits, unsigned int num)
	{
	if (num >= pBits->storageSize * sizeof(u4) * 8) {
	if (!pBits->expandable) {
	ALOGE("Attempt to set bit outside valid range (%d, limit is %d)",
	num, pBits->storageSize * sizeof(u4) * 8);
	dvmAbort();
	}

	/* Round up to word boundaries for "num+1" bits */
	unsigned int newSize = (num + 1 + 31) >> 5;
	assert(newSize > pBits->storageSize);
	pBits->storage = (u4)realloc(pBits->storage, newSize sizeof(u4));
	if (pBits->storage == NULL) {
	ALOGE("BitVector expansion to %d failed", newSize * sizeof(u4));
	dvmAbort();
	}
	memset(&pBits->storage[pBits->storageSize], 0x00,
	(newSize - pBits->storageSize) * sizeof(u4));
	pBits->storageSize = newSize;
	}

	pBits->storage[num >> 5] \|= 1 << (num & 0x1f);
	}

	/*
	* Mark the specified bit as "clear".
	*/
	void dvmClearBit(BitVector* pBits, unsigned int num)
	{
	assert(num < pBits->storageSize * sizeof(u4) * 8);

	pBits->storage[num >> 5] &= ~(1 << (num & 0x1f));
	}

	/*
	* Mark all bits bit as "clear".
	*/
	void dvmClearAllBits(BitVector* pBits)
	{
	unsigned int count = pBits->storageSize;
	memset(pBits->storage, 0, count * sizeof(u4));
	}

	/*
	* Mark specified number of bits as "set". Cannot set all bits like ClearAll
	* since there might be unused bits - setting those to one will confuse the
	* iterator.
	*/
	void dvmSetInitialBits(BitVector* pBits, unsigned int numBits)
	{
	unsigned int idx;
	assert(((numBits + 31) >> 5) <= pBits->storageSize);
	for (idx = 0; idx < (numBits >> 5); idx++) {
	pBits->storage[idx] = -1;
	}
	unsigned int remNumBits = numBits & 0x1f;
	if (remNumBits) {
	pBits->storage[idx] = (1 << remNumBits) - 1;
	}
	}

	/*
	* Determine whether or not the specified bit is set.
	*/
	bool dvmIsBitSet(const BitVector* pBits, unsigned int num)
	{
	assert(num < pBits->storageSize * sizeof(u4) * 8);

	unsigned int val = pBits->storage[num >> 5] & (1 << (num & 0x1f));
	return (val != 0);
	}

	/*
	* Count the number of bits that are set.
	*/
	int dvmCountSetBits(const BitVector* pBits)
	{
	unsigned int word;
	unsigned int count = 0;

	for (word = 0; word < pBits->storageSize; word++) {
	u4 val = pBits->storage[word];

	if (val != 0) {
	if (val == 0xffffffff) {
	count += 32;
	} else {
	/* count the number of '1' bits */
	while (val != 0) {
	val &= val - 1;
	count++;
	}
	}
	}
	}

	return count;
	}

	/*
	* If the vector sizes don't match, log an error and abort.
	*/
	static void checkSizes(const BitVector* bv1, const BitVector* bv2)
	{
	if (bv1->storageSize != bv2->storageSize) {
	ALOGE("Mismatched vector sizes (%d, %d)",
	bv1->storageSize, bv2->storageSize);
	dvmAbort();
	}
	}

	/*
	* Copy a whole vector to the other. Only do that when the both vectors have
	* the same size.
	*/
	void dvmCopyBitVector(BitVector dest, const BitVector src)
	{
	/* if dest is expandable and < src, we could expand dest to match */
	checkSizes(dest, src);

	memcpy(dest->storage, src->storage, sizeof(u4) * dest->storageSize);
	}

	/*
	* Intersect two bit vectors and store the result to the dest vector.
	*/
	bool dvmIntersectBitVectors(BitVector dest, const BitVector src1,
	const BitVector *src2)
	{
	if (dest->storageSize != src1->storageSize \|\|
	dest->storageSize != src2->storageSize \|\|
	dest->expandable != src1->expandable \|\|
	dest->expandable != src2->expandable)
	return false;

	unsigned int idx;
	for (idx = 0; idx < dest->storageSize; idx++) {
	dest->storage[idx] = src1->storage[idx] & src2->storage[idx];
	}
	return true;
	}

	/*
	* Unify two bit vectors and store the result to the dest vector.
	*/
	bool dvmUnifyBitVectors(BitVector dest, const BitVector src1,
	const BitVector *src2)
	{
	if (dest->storageSize != src1->storageSize \|\|
	dest->storageSize != src2->storageSize \|\|
	dest->expandable != src1->expandable \|\|
	dest->expandable != src2->expandable)
	return false;

	unsigned int idx;
	for (idx = 0; idx < dest->storageSize; idx++) {
	dest->storage[idx] = src1->storage[idx] \| src2->storage[idx];
	}
	return true;
	}

	/*
	* Compare two bit vectors and return true if difference is seen.
	*/
	bool dvmCompareBitVectors(const BitVector src1, const BitVector src2)
	{
	if (src1->storageSize != src2->storageSize \|\|
	src1->expandable != src2->expandable)
	return true;

	unsigned int idx;
	for (idx = 0; idx < src1->storageSize; idx++) {
	if (src1->storage[idx] != src2->storage[idx]) return true;
	}
	return false;
	}

	/* Initialize the iterator structure */
	void dvmBitVectorIteratorInit(BitVector* pBits, BitVectorIterator* iterator)
	{
	iterator->pBits = pBits;
	iterator->bitSize = pBits->storageSize * sizeof(u4) * 8;
	iterator->idx = 0;
	}

	/* Return the next position set to 1. -1 means end-of-element reached */
	int dvmBitVectorIteratorNext(BitVectorIterator* iterator)
	{
	const BitVector* pBits = iterator->pBits;
	u4 bitIndex = iterator->idx;

	assert(iterator->bitSize == pBits->storageSize * sizeof(u4) * 8);
	if (bitIndex >= iterator->bitSize) return -1;

	for (; bitIndex < iterator->bitSize; bitIndex++) {
	unsigned int wordIndex = bitIndex >> 5;
	unsigned int mask = 1 << (bitIndex & 0x1f);
	if (pBits->storage[wordIndex] & mask) {
	iterator->idx = bitIndex+1;
	return bitIndex;
	}
	}
	/* No more set bits */
	return -1;
	}


	/*
	* Merge the contents of "src" into "dst", checking to see if this causes
	* any changes to occur. This is a logical OR.
	*
	* Returns "true" if the contents of the destination vector were modified.
	*/
	bool dvmCheckMergeBitVectors(BitVector* dst, const BitVector* src)
	{
	bool changed = false;

	checkSizes(dst, src);

	unsigned int idx;
	for (idx = 0; idx < dst->storageSize; idx++) {
	u4 merged = src->storage[idx] \| dst->storage[idx];
	if (dst->storage[idx] != merged) {
	dst->storage[idx] = merged;
	changed = true;
	}
	}

	return changed;
	}