Split BitVector into its own file.
This just pulls the BitVector stuff out into separate files.
IIRC the motivation for building Misc.c for ARM rather than Thumb was
the bit-manipulation going on in BitVector (e.g. the use of ffs()),
so I switched that around in the makefile.
The only change of any substance was relocation of the kBitVectorGrowth
define from the .h to the .c.
Change-Id: Ib35fda81809081bd629b4f344e41f21966e1441c
diff --git a/vm/BitVector.c b/vm/BitVector.c
new file mode 100644
index 0000000..68f19b0
--- /dev/null
+++ b/vm/BitVector.c
@@ -0,0 +1,214 @@
+/*
+ * 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>
+
+#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(int startBits, bool expandable)
+{
+ BitVector* bv;
+ int count;
+
+ assert(sizeof(bv->storage[0]) == 4); /* assuming 32-bit units */
+ assert(startBits >= 0);
+
+ bv = (BitVector*) malloc(sizeof(BitVector));
+
+ count = (startBits + 31) >> 5;
+
+ bv->storageSize = count;
+ bv->expandable = expandable;
+ bv->storage = (u4*) malloc(count * sizeof(u4));
+ memset(bv->storage, 0x00, 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)
+{
+ 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 >= 0 && 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".
+ *
+ * Returns "false" if the bit is outside the range of the vector and we're
+ * not allowed to expand.
+ */
+bool dvmSetBit(BitVector* pBits, int num)
+{
+ assert(num >= 0);
+ if (num >= pBits->storageSize * (int)sizeof(u4) * 8) {
+ if (!pBits->expandable)
+ return false;
+
+ /* Round up to word boundaries for "num+1" bits */
+ int newSize = (num + 1 + 31) >> 5;
+ assert(newSize > pBits->storageSize);
+ pBits->storage = (u4*)realloc(pBits->storage, newSize * sizeof(u4));
+ memset(&pBits->storage[pBits->storageSize], 0x00,
+ (newSize - pBits->storageSize) * sizeof(u4));
+ pBits->storageSize = newSize;
+ }
+
+ pBits->storage[num >> 5] |= 1 << (num & 0x1f);
+ return true;
+}
+
+/*
+ * Mark the specified bit as "clear".
+ */
+void dvmClearBit(BitVector* pBits, int num)
+{
+ assert(num >= 0 && num < (int) pBits->storageSize * (int)sizeof(u4) * 8);
+
+ pBits->storage[num >> 5] &= ~(1 << (num & 0x1f));
+}
+
+/*
+ * Mark all bits bit as "clear".
+ */
+void dvmClearAllBits(BitVector* pBits)
+{
+ int count = pBits->storageSize;
+ memset(pBits->storage, 0, count * sizeof(u4));
+}
+
+/*
+ * Determine whether or not the specified bit is set.
+ */
+bool dvmIsBitSet(const BitVector* pBits, int num)
+{
+ assert(num >= 0 && num < (int) pBits->storageSize * (int)sizeof(u4) * 8);
+
+ 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)
+{
+ int word;
+ 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;
+}
+
+/*
+ * Copy a whole vector to the other. Only do that when the both vectors have
+ * the same size and attribute.
+ */
+bool dvmCopyBitVector(BitVector *dest, const BitVector *src)
+{
+ if (dest->storageSize != src->storageSize ||
+ dest->expandable != src->expandable)
+ return false;
+ memcpy(dest->storage, src->storage, sizeof(u4) * dest->storageSize);
+ return true;
+}
+
+/*
+ * Intersect two bit vectores and merge the result on top of the pre-existing
+ * value in 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;
+
+ int i;
+ for (i = 0; i < dest->storageSize; i++) {
+ dest->storage[i] |= src1->storage[i] & src2->storage[i];
+ }
+ return true;
+}
diff --git a/vm/BitVector.h b/vm/BitVector.h
new file mode 100644
index 0000000..94abe7b
--- /dev/null
+++ b/vm/BitVector.h
@@ -0,0 +1,69 @@
+/*
+ * 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.
+ */
+
+/*
+ * Miscellaneous utility functions.
+ */
+#ifndef _DALVIK_BITVECTOR
+#define _DALVIK_BITVECTOR
+
+/*
+ * Expanding bitmap, used for tracking resources. Bits are numbered starting
+ * from zero.
+ *
+ * All operations on a BitVector are unsynchronized.
+ */
+typedef struct BitVector {
+ bool expandable; /* expand bitmap if we run out? */
+ int storageSize; /* current size, in 32-bit words */
+ u4* storage;
+} BitVector;
+
+/* allocate a bit vector with enough space to hold "startBits" bits */
+BitVector* dvmAllocBitVector(int startBits, bool expandable);
+void dvmFreeBitVector(BitVector* pBits);
+
+/*
+ * dvmAllocBit always allocates the first possible bit. If we run out of
+ * space in the bitmap, and it's not marked expandable, dvmAllocBit
+ * returns -1.
+ *
+ * dvmSetBit sets the specified bit, expanding the vector if necessary
+ * (and possible).
+ *
+ * dvmIsBitSet returns "true" if the bit is set.
+ */
+int dvmAllocBit(BitVector* pBits);
+bool dvmSetBit(BitVector* pBits, int num);
+void dvmClearBit(BitVector* pBits, int num);
+void dvmClearAllBits(BitVector* pBits);
+bool dvmIsBitSet(const BitVector* pBits, int num);
+
+/* count the number of bits that have been set */
+int dvmCountSetBits(const BitVector* pBits);
+
+/* copy one vector to the other compatible one */
+bool dvmCopyBitVector(BitVector *dest, const BitVector *src);
+
+/*
+ * Intersect two bit vectores and merge the result on top of the pre-existing
+ * value in the dest vector.
+ */
+bool dvmIntersectBitVectors(BitVector *dest, const BitVector *src1,
+ const BitVector *src2);
+
+
+#endif /*_DALVIK_BITVECTOR*/
diff --git a/vm/Dalvik.h b/vm/Dalvik.h
index 83c607c..7164ec4 100644
--- a/vm/Dalvik.h
+++ b/vm/Dalvik.h
@@ -26,6 +26,7 @@
#include "Inlines.h"
#include "Misc.h"
#include "Bits.h"
+#include "BitVector.h"
#include "libdex/SysUtil.h"
#include "libdex/DexFile.h"
#include "libdex/DexProto.h"
diff --git a/vm/Dvm.mk b/vm/Dvm.mk
index 43cdc41..18165d2 100644
--- a/vm/Dvm.mk
+++ b/vm/Dvm.mk
@@ -97,6 +97,7 @@
AllocTracker.c \
Atomic.c.arm \
AtomicCache.c \
+ BitVector.c.arm \
CheckJni.c \
Ddm.c \
Debugger.c \
@@ -111,7 +112,7 @@
Jni.c \
JarFile.c \
LinearAlloc.c \
- Misc.c.arm \
+ Misc.c \
Native.c \
PointerSet.c \
Profile.c \
diff --git a/vm/Misc.c b/vm/Misc.c
index b7404fd..f8d23ca 100644
--- a/vm/Misc.c
+++ b/vm/Misc.c
@@ -13,6 +13,7 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
+
/*
* Miscellaneous utility functions.
*/
@@ -195,195 +196,6 @@
/*
- * Allocate a bit vector with enough space to hold at least the specified
- * number of bits.
- */
-BitVector* dvmAllocBitVector(int startBits, bool expandable)
-{
- BitVector* bv;
- int count;
-
- assert(sizeof(bv->storage[0]) == 4); /* assuming 32-bit units */
- assert(startBits >= 0);
-
- bv = (BitVector*) malloc(sizeof(BitVector));
-
- count = (startBits + 31) >> 5;
-
- bv->storageSize = count;
- bv->expandable = expandable;
- bv->storage = (u4*) malloc(count * sizeof(u4));
- memset(bv->storage, 0x00, 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)
-{
- 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 >= 0 && 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".
- *
- * Returns "false" if the bit is outside the range of the vector and we're
- * not allowed to expand.
- */
-bool dvmSetBit(BitVector* pBits, int num)
-{
- assert(num >= 0);
- if (num >= pBits->storageSize * (int)sizeof(u4) * 8) {
- if (!pBits->expandable)
- return false;
-
- /* Round up to word boundaries for "num+1" bits */
- int newSize = (num + 1 + 31) >> 5;
- assert(newSize > pBits->storageSize);
- pBits->storage = (u4*)realloc(pBits->storage, newSize * sizeof(u4));
- memset(&pBits->storage[pBits->storageSize], 0x00,
- (newSize - pBits->storageSize) * sizeof(u4));
- pBits->storageSize = newSize;
- }
-
- pBits->storage[num >> 5] |= 1 << (num & 0x1f);
- return true;
-}
-
-/*
- * Mark the specified bit as "clear".
- */
-void dvmClearBit(BitVector* pBits, int num)
-{
- assert(num >= 0 && num < (int) pBits->storageSize * (int)sizeof(u4) * 8);
-
- pBits->storage[num >> 5] &= ~(1 << (num & 0x1f));
-}
-
-/*
- * Mark all bits bit as "clear".
- */
-void dvmClearAllBits(BitVector* pBits)
-{
- int count = pBits->storageSize;
- memset(pBits->storage, 0, count * sizeof(u4));
-}
-
-/*
- * Determine whether or not the specified bit is set.
- */
-bool dvmIsBitSet(const BitVector* pBits, int num)
-{
- assert(num >= 0 && num < (int) pBits->storageSize * (int)sizeof(u4) * 8);
-
- 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)
-{
- int word;
- 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;
-}
-
-/*
- * Copy a whole vector to the other. Only do that when the both vectors have
- * the same size and attribute.
- */
-bool dvmCopyBitVector(BitVector *dest, const BitVector *src)
-{
- if (dest->storageSize != src->storageSize ||
- dest->expandable != src->expandable)
- return false;
- memcpy(dest->storage, src->storage, sizeof(u4) * dest->storageSize);
- return true;
-}
-
-/*
- * Intersect two bit vectores and merge the result on top of the pre-existing
- * value in 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;
-
- int i;
- for (i = 0; i < dest->storageSize; i++) {
- dest->storage[i] |= src1->storage[i] & src2->storage[i];
- }
- return true;
-}
-
-/*
* Return a newly-allocated string in which all occurrences of '.' have
* been changed to '/'. If we find a '/' in the original string, NULL
* is returned to avoid ambiguity.
diff --git a/vm/Misc.h b/vm/Misc.h
index 44f853b..ee0a4eb 100644
--- a/vm/Misc.h
+++ b/vm/Misc.h
@@ -130,54 +130,6 @@
/*
- * Expanding bitmap, used for tracking resources. Bits are numbered starting
- * from zero.
- *
- * All operations on a BitVector are unsynchronized.
- */
-typedef struct BitVector {
- bool expandable; /* expand bitmap if we run out? */
- int storageSize; /* current size, in 32-bit words */
- u4* storage;
-} BitVector;
-
-/* allocate a bit vector with enough space to hold "startBits" bits */
-BitVector* dvmAllocBitVector(int startBits, bool expandable);
-void dvmFreeBitVector(BitVector* pBits);
-
-/*
- * dvmAllocBit always allocates the first possible bit. If we run out of
- * space in the bitmap, and it's not marked expandable, dvmAllocBit
- * returns -1.
- *
- * dvmSetBit sets the specified bit, expanding the vector if necessary
- * (and possible).
- *
- * dvmIsBitSet returns "true" if the bit is set.
- */
-int dvmAllocBit(BitVector* pBits);
-bool dvmSetBit(BitVector* pBits, int num);
-void dvmClearBit(BitVector* pBits, int num);
-void dvmClearAllBits(BitVector* pBits);
-bool dvmIsBitSet(const BitVector* pBits, int num);
-
-/* count the number of bits that have been set */
-int dvmCountSetBits(const BitVector* pBits);
-
-/* copy one vector to the other compatible one */
-bool dvmCopyBitVector(BitVector *dest, const BitVector *src);
-
-/*
- * Intersect two bit vectores and merge the result on top of the pre-existing
- * value in the dest vector.
- */
-bool dvmIntersectBitVectors(BitVector *dest, const BitVector *src1,
- const BitVector *src2);
-
-#define kBitVectorGrowth 4 /* increase by 4 u4s when limit hit */
-
-
-/*
* Return a newly-allocated string in which all occurrences of '.' have
* been changed to '/'. If we find a '/' in the original string, NULL
* is returned to avoid ambiguity.