diff options
author | Carl Shapiro <cshapiro@google.com> | 2011-04-15 18:38:06 -0700 |
---|---|---|
committer | Carl Shapiro <cshapiro@google.com> | 2011-04-15 21:18:10 -0700 |
commit | d5c36b9040bd26a81219a7f399513526f9b46324 (patch) | |
tree | 921c49ef9ced8819389ef699ae61296741db71a5 /vm/PointerSet.cpp | |
parent | c469fa622ebadfa3defc73a064e2e724f0ab7c75 (diff) | |
download | android_dalvik-d5c36b9040bd26a81219a7f399513526f9b46324.tar.gz android_dalvik-d5c36b9040bd26a81219a7f399513526f9b46324.tar.bz2 android_dalvik-d5c36b9040bd26a81219a7f399513526f9b46324.zip |
Move the remaining non-compiler VM code into C++.
Change-Id: Id8693208d2741c55a7b0474d1264f2112019d11f
Diffstat (limited to 'vm/PointerSet.cpp')
-rw-r--r-- | vm/PointerSet.cpp | 274 |
1 files changed, 274 insertions, 0 deletions
diff --git a/vm/PointerSet.cpp b/vm/PointerSet.cpp new file mode 100644 index 000000000..ca7b537f2 --- /dev/null +++ b/vm/PointerSet.cpp @@ -0,0 +1,274 @@ +/* + * 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. + */ +/* + * Maintain an expanding set of unique pointer values. + */ +#include "Dalvik.h" + +/* + * Sorted, expanding list of pointers. + */ +struct PointerSet { + u2 alloc; + u2 count; + const void** list; +}; + +/* + * Verify that the set is in sorted order. + */ +#ifndef NDEBUG +static bool verifySorted(PointerSet* pSet) +{ + const void* last = NULL; + int i; + + for (i = 0; i < pSet->count; i++) { + const void* cur = pSet->list[i]; + if (cur < last) + return false; + last = cur; + } + + return true; +} +#endif + +/* + * Allocate a new PointerSet. + * + * Returns NULL on failure. + */ +PointerSet* dvmPointerSetAlloc(int initialSize) +{ + PointerSet* pSet = (PointerSet*)calloc(1, sizeof(PointerSet)); + if (pSet != NULL) { + if (initialSize > 0) { + pSet->list = (const void**)malloc(sizeof(void*) * initialSize); + if (pSet->list == NULL) { + free(pSet); + return NULL; + } + pSet->alloc = initialSize; + } + } + + return pSet; +} + +/* + * Free up a PointerSet. + */ +void dvmPointerSetFree(PointerSet* pSet) +{ + if (pSet == NULL) + return; + + if (pSet->list != NULL) { + free(pSet->list); + pSet->list = NULL; + } + free(pSet); +} + +/* + * Clear the contents of a pointer set. + */ +void dvmPointerSetClear(PointerSet* pSet) +{ + pSet->count = 0; +} + +/* + * Get the number of pointers currently stored in the list. + */ +int dvmPointerSetGetCount(const PointerSet* pSet) +{ + return pSet->count; +} + +/* + * Get the Nth entry from the list. + */ +const void* dvmPointerSetGetEntry(const PointerSet* pSet, int i) +{ + return pSet->list[i]; +} + +/* + * Insert a new entry into the list. If it already exists, this returns + * without doing anything. + * + * Returns "true" if the value was added. + */ +bool dvmPointerSetAddEntry(PointerSet* pSet, const void* ptr) +{ + int nearby; + + if (dvmPointerSetHas(pSet, ptr, &nearby)) + return false; + + /* ensure we have space to add one more */ + if (pSet->count == pSet->alloc) { + /* time to expand */ + const void** newList; + + if (pSet->alloc == 0) + pSet->alloc = 4; + else + pSet->alloc *= 2; + LOGVV("expanding %p to %d\n", pSet, pSet->alloc); + newList = (const void**)realloc(pSet->list, pSet->alloc * sizeof(void*)); + if (newList == NULL) { + LOGE("Failed expanding ptr set (alloc=%d)\n", pSet->alloc); + dvmAbort(); + } + pSet->list = newList; + } + + if (pSet->count == 0) { + /* empty list */ + assert(nearby == 0); + } else { + /* + * Determine the insertion index. The binary search might have + * terminated "above" or "below" the value. + */ + if (nearby != 0 && ptr < pSet->list[nearby-1]) { + //LOGD("nearby-1=%d %p, inserting %p at -1\n", + // nearby-1, pSet->list[nearby-1], ptr); + nearby--; + } else if (ptr < pSet->list[nearby]) { + //LOGD("nearby=%d %p, inserting %p at +0\n", + // nearby, pSet->list[nearby], ptr); + } else { + //LOGD("nearby+1=%d %p, inserting %p at +1\n", + // nearby+1, pSet->list[nearby+1], ptr); + nearby++; + } + + /* + * Move existing values, if necessary. + */ + if (nearby != pSet->count) { + /* shift up */ + memmove(&pSet->list[nearby+1], &pSet->list[nearby], + (pSet->count - nearby) * sizeof(pSet->list[0])); + } + } + + pSet->list[nearby] = ptr; + pSet->count++; + + assert(verifySorted(pSet)); + return true; +} + +/* + * Returns "true" if the element was successfully removed. + */ +bool dvmPointerSetRemoveEntry(PointerSet* pSet, const void* ptr) +{ + int where; + + if (!dvmPointerSetHas(pSet, ptr, &where)) + return false; + + if (where != pSet->count-1) { + /* shift down */ + memmove(&pSet->list[where], &pSet->list[where+1], + (pSet->count-1 - where) * sizeof(pSet->list[0])); + } + + pSet->count--; + pSet->list[pSet->count] = (const void*) 0xdecadead; // debug + return true; +} + +/* + * Returns the index if "ptr" appears in the list. If it doesn't appear, + * this returns a negative index for a nearby element. + */ +bool dvmPointerSetHas(const PointerSet* pSet, const void* ptr, int* pIndex) +{ + int hi, lo, mid; + + lo = mid = 0; + hi = pSet->count-1; + + /* array is sorted, use a binary search */ + while (lo <= hi) { + mid = (lo + hi) / 2; + const void* listVal = pSet->list[mid]; + + if (ptr > listVal) { + lo = mid + 1; + } else if (ptr < listVal) { + hi = mid - 1; + } else /* listVal == ptr */ { + if (pIndex != NULL) + *pIndex = mid; + return true; + } + } + + if (pIndex != NULL) + *pIndex = mid; + return false; +} + +/* + * Compute the intersection of the set and the array of pointers passed in. + * + * Any pointer in "pSet" that does not appear in "ptrArray" is removed. + */ +void dvmPointerSetIntersect(PointerSet* pSet, const void** ptrArray, int count) +{ + int i, j; + + for (i = 0; i < pSet->count; i++) { + for (j = 0; j < count; j++) { + if (pSet->list[i] == ptrArray[j]) { + /* match, keep this one */ + break; + } + } + + if (j == count) { + /* no match, remove entry */ + if (i != pSet->count-1) { + /* shift down */ + memmove(&pSet->list[i], &pSet->list[i+1], + (pSet->count-1 - i) * sizeof(pSet->list[0])); + } + + pSet->count--; + pSet->list[pSet->count] = (const void*) 0xdecadead; // debug + i--; /* adjust loop counter */ + } + } +} + +/* + * Print the list contents to stdout. For debugging. + */ +void dvmPointerSetDump(const PointerSet* pSet) +{ + LOGI("PointerSet %p\n", pSet); + int i; + for (i = 0; i < pSet->count; i++) + LOGI(" %2d: %p", i, pSet->list[i]); +} |