1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2008 The Android Open Source Project 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License. 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License. 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Maintain an expanding set of unique pointer values. 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#include "Dalvik.h" 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Sorted, expanding list of pointers. 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectstruct PointerSet { 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project u2 alloc; 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project u2 count; 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void** list; 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project}; 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Verify that the set is in sorted order. 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectstatic bool verifySorted(PointerSet* pSet) 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void* last = NULL; 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i; 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (i = 0; i < pSet->count; i++) { 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void* cur = pSet->list[i]; 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (cur < last) 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project last = cur; 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Allocate a new PointerSet. 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns NULL on failure. 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source ProjectPointerSet* dvmPointerSetAlloc(int initialSize) 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project PointerSet* pSet = calloc(1, sizeof(PointerSet)); 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet != NULL) { 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (initialSize > 0) { 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->list = malloc(sizeof(const void*) * initialSize); 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet->list == NULL) { 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project free(pSet); 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return NULL; 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->alloc = initialSize; 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return pSet; 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Free up a PointerSet. 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmPointerSetFree(PointerSet* pSet) 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet == NULL) 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet->list != NULL) { 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project free(pSet->list); 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->list = NULL; 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project free(pSet); 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Clear the contents of a pointer set. 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmPointerSetClear(PointerSet* pSet) 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->count = 0; 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Get the number of pointers currently stored in the list. 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectint dvmPointerSetGetCount(const PointerSet* pSet) 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return pSet->count; 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Get the Nth entry from the list. 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectconst void* dvmPointerSetGetEntry(const PointerSet* pSet, int i) 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return pSet->list[i]; 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Insert a new entry into the list. If it already exists, this returns 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * without doing anything. 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns "true" if the value was added. 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectbool dvmPointerSetAddEntry(PointerSet* pSet, const void* ptr) 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int nearby; 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (dvmPointerSetHas(pSet, ptr, &nearby)) 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* ensure we have space to add one more */ 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet->count == pSet->alloc) { 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* time to expand */ 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void** newList; 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet->alloc == 0) 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->alloc = 4; 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project else 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->alloc *= 2; 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LOGVV("expanding %p to %d\n", pSet, pSet->alloc); 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newList = realloc(pSet->list, pSet->alloc * sizeof(const void*)); 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (newList == NULL) { 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LOGE("Failed expanding ptr set (alloc=%d)\n", pSet->alloc); 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmAbort(); 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->list = newList; 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet->count == 0) { 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* empty list */ 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(nearby == 0); 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Determine the insertion index. The binary search might have 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * terminated "above" or "below" the value. 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (nearby != 0 && ptr < pSet->list[nearby-1]) { 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project //LOGD("nearby-1=%d %p, inserting %p at -1\n", 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // nearby-1, pSet->list[nearby-1], ptr); 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project nearby--; 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (ptr < pSet->list[nearby]) { 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project //LOGD("nearby=%d %p, inserting %p at +0\n", 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // nearby, pSet->list[nearby], ptr); 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project //LOGD("nearby+1=%d %p, inserting %p at +1\n", 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // nearby+1, pSet->list[nearby+1], ptr); 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project nearby++; 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Move existing values, if necessary. 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (nearby != pSet->count) { 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* shift up */ 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project memmove(&pSet->list[nearby+1], &pSet->list[nearby], 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (pSet->count - nearby) * sizeof(pSet->list[0])); 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->list[nearby] = ptr; 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->count++; 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(verifySorted(pSet)); 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns "true" if the element was successfully removed. 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectbool dvmPointerSetRemoveEntry(PointerSet* pSet, const void* ptr) 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i, where; 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!dvmPointerSetHas(pSet, ptr, &where)) 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (where != pSet->count-1) { 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* shift down */ 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project memmove(&pSet->list[where], &pSet->list[where+1], 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (pSet->count-1 - where) * sizeof(pSet->list[0])); 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->count--; 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->list[pSet->count] = (const void*) 0xdecadead; // debug 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns the index if "ptr" appears in the list. If it doesn't appear, 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * this returns a negative index for a nearby element. 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectbool dvmPointerSetHas(const PointerSet* pSet, const void* ptr, int* pIndex) 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int hi, lo, mid; 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project lo = mid = 0; 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project hi = pSet->count-1; 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* array is sorted, use a binary search */ 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (lo <= hi) { 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mid = (lo + hi) / 2; 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void* listVal = pSet->list[mid]; 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ptr > listVal) { 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project lo = mid + 1; 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (ptr < listVal) { 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project hi = mid - 1; 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else /* listVal == ptr */ { 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pIndex != NULL) 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project *pIndex = mid; 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pIndex != NULL) 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project *pIndex = mid; 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Compute the intersection of the set and the array of pointers passed in. 234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Any pointer in "pSet" that does not appear in "ptrArray" is removed. 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmPointerSetIntersect(PointerSet* pSet, const void** ptrArray, int count) 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i, j; 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (i = 0; i < pSet->count; i++) { 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (j = 0; j < count; j++) { 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet->list[i] == ptrArray[j]) { 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* match, keep this one */ 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (j == count) { 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* no match, remove entry */ 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i != pSet->count-1) { 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* shift down */ 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project memmove(&pSet->list[i], &pSet->list[i+1], 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (pSet->count-1 - i) * sizeof(pSet->list[0])); 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->count--; 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->list[pSet->count] = (const void*) 0xdecadead; // debug 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i--; /* adjust loop counter */ 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Print the list contents to stdout. For debugging. 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmPointerSetDump(const PointerSet* pSet) 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i; 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (i = 0; i < pSet->count; i++) 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project printf(" %p", pSet->list[i]); 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 274