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