PointerSet.cpp revision fc75f3ed87b55d625b6054e18645da5cbdba31c6
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 */ 33e3c01dac83e6eea7f82fe81ed89cfbdd9791dbc9Carl Shapiro#ifndef NDEBUG 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectstatic bool verifySorted(PointerSet* pSet) 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void* last = NULL; 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i; 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (i = 0; i < pSet->count; i++) { 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void* cur = pSet->list[i]; 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (cur < last) 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project last = cur; 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 48e3c01dac83e6eea7f82fe81ed89cfbdd9791dbc9Carl Shapiro#endif 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Allocate a new PointerSet. 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns NULL on failure. 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source ProjectPointerSet* dvmPointerSetAlloc(int initialSize) 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 57fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro PointerSet* pSet = (PointerSet*)calloc(1, sizeof(PointerSet)); 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet != NULL) { 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (initialSize > 0) { 60fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro pSet->list = (const void**)malloc(sizeof(void*) * initialSize); 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet->list == NULL) { 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project free(pSet); 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return NULL; 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->alloc = initialSize; 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return pSet; 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Free up a PointerSet. 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmPointerSetFree(PointerSet* pSet) 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet == NULL) 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet->list != NULL) { 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project free(pSet->list); 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->list = NULL; 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project free(pSet); 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Clear the contents of a pointer set. 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmPointerSetClear(PointerSet* pSet) 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->count = 0; 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Get the number of pointers currently stored in the list. 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectint dvmPointerSetGetCount(const PointerSet* pSet) 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return pSet->count; 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Get the Nth entry from the list. 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectconst void* dvmPointerSetGetEntry(const PointerSet* pSet, int i) 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return pSet->list[i]; 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Insert a new entry into the list. If it already exists, this returns 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * without doing anything. 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns "true" if the value was added. 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectbool dvmPointerSetAddEntry(PointerSet* pSet, const void* ptr) 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int nearby; 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (dvmPointerSetHas(pSet, ptr, &nearby)) 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* ensure we have space to add one more */ 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet->count == pSet->alloc) { 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* time to expand */ 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void** newList; 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet->alloc == 0) 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->alloc = 4; 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project else 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->alloc *= 2; 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LOGVV("expanding %p to %d\n", pSet, pSet->alloc); 134fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro newList = (const void**)realloc(pSet->list, pSet->alloc * sizeof(void*)); 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (newList == NULL) { 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LOGE("Failed expanding ptr set (alloc=%d)\n", pSet->alloc); 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmAbort(); 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->list = newList; 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet->count == 0) { 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* empty list */ 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(nearby == 0); 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Determine the insertion index. The binary search might have 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * terminated "above" or "below" the value. 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (nearby != 0 && ptr < pSet->list[nearby-1]) { 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project //LOGD("nearby-1=%d %p, inserting %p at -1\n", 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // nearby-1, pSet->list[nearby-1], ptr); 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project nearby--; 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (ptr < pSet->list[nearby]) { 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project //LOGD("nearby=%d %p, inserting %p at +0\n", 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // nearby, pSet->list[nearby], ptr); 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project //LOGD("nearby+1=%d %p, inserting %p at +1\n", 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // nearby+1, pSet->list[nearby+1], ptr); 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project nearby++; 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Move existing values, if necessary. 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (nearby != pSet->count) { 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* shift up */ 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project memmove(&pSet->list[nearby+1], &pSet->list[nearby], 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (pSet->count - nearby) * sizeof(pSet->list[0])); 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->list[nearby] = ptr; 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->count++; 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(verifySorted(pSet)); 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns "true" if the element was successfully removed. 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectbool dvmPointerSetRemoveEntry(PointerSet* pSet, const void* ptr) 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 185e3c01dac83e6eea7f82fe81ed89cfbdd9791dbc9Carl Shapiro int where; 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!dvmPointerSetHas(pSet, ptr, &where)) 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (where != pSet->count-1) { 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* shift down */ 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project memmove(&pSet->list[where], &pSet->list[where+1], 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (pSet->count-1 - where) * sizeof(pSet->list[0])); 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->count--; 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->list[pSet->count] = (const void*) 0xdecadead; // debug 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns the index if "ptr" appears in the list. If it doesn't appear, 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * this returns a negative index for a nearby element. 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectbool dvmPointerSetHas(const PointerSet* pSet, const void* ptr, int* pIndex) 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int hi, lo, mid; 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project lo = mid = 0; 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project hi = pSet->count-1; 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* array is sorted, use a binary search */ 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (lo <= hi) { 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project mid = (lo + hi) / 2; 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void* listVal = pSet->list[mid]; 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ptr > listVal) { 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project lo = mid + 1; 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (ptr < listVal) { 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project hi = mid - 1; 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else /* listVal == ptr */ { 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pIndex != NULL) 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project *pIndex = mid; 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pIndex != NULL) 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project *pIndex = mid; 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Compute the intersection of the set and the array of pointers passed in. 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Any pointer in "pSet" that does not appear in "ptrArray" is removed. 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmPointerSetIntersect(PointerSet* pSet, const void** ptrArray, int count) 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i, j; 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (i = 0; i < pSet->count; i++) { 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (j = 0; j < count; j++) { 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pSet->list[i] == ptrArray[j]) { 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* match, keep this one */ 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (j == count) { 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* no match, remove entry */ 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (i != pSet->count-1) { 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* shift down */ 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project memmove(&pSet->list[i], &pSet->list[i+1], 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (pSet->count-1 - i) * sizeof(pSet->list[0])); 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->count--; 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pSet->list[pSet->count] = (const void*) 0xdecadead; // debug 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i--; /* adjust loop counter */ 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/* 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Print the list contents to stdout. For debugging. 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmPointerSetDump(const PointerSet* pSet) 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i; 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (i = 0; i < pSet->count; i++) 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project printf(" %p", pSet->list[i]); 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 274