2 * Copyright (C) 2008 The Android Open Source Project
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 * Maintain an expanding set of unique pointer values.
22 * Sorted, expanding list of pointers.
31 * Verify that the set is in sorted order.
34 static bool verifySorted(PointerSet* pSet)
36 const void* last = NULL;
39 for (i = 0; i < pSet->count; i++) {
40 const void* cur = pSet->list[i];
51 * Allocate a new PointerSet.
53 * Returns NULL on failure.
55 PointerSet* dvmPointerSetAlloc(int initialSize)
57 PointerSet* pSet = (PointerSet*)calloc(1, sizeof(PointerSet));
59 if (initialSize > 0) {
60 pSet->list = (const void**)malloc(sizeof(void*) * initialSize);
61 if (pSet->list == NULL) {
65 pSet->alloc = initialSize;
73 * Free up a PointerSet.
75 void dvmPointerSetFree(PointerSet* pSet)
80 if (pSet->list != NULL) {
88 * Clear the contents of a pointer set.
90 void dvmPointerSetClear(PointerSet* pSet)
96 * Get the number of pointers currently stored in the list.
98 int dvmPointerSetGetCount(const PointerSet* pSet)
104 * Get the Nth entry from the list.
106 const void* dvmPointerSetGetEntry(const PointerSet* pSet, int i)
108 return pSet->list[i];
112 * Insert a new entry into the list. If it already exists, this returns
113 * without doing anything.
115 * Returns "true" if the value was added.
117 bool dvmPointerSetAddEntry(PointerSet* pSet, const void* ptr)
121 if (dvmPointerSetHas(pSet, ptr, &nearby))
124 /* ensure we have space to add one more */
125 if (pSet->count == pSet->alloc) {
127 const void** newList;
129 if (pSet->alloc == 0)
133 LOGVV("expanding %p to %d\n", pSet, pSet->alloc);
134 newList = (const void**)realloc(pSet->list, pSet->alloc * sizeof(void*));
135 if (newList == NULL) {
136 LOGE("Failed expanding ptr set (alloc=%d)\n", pSet->alloc);
139 pSet->list = newList;
142 if (pSet->count == 0) {
147 * Determine the insertion index. The binary search might have
148 * terminated "above" or "below" the value.
150 if (nearby != 0 && ptr < pSet->list[nearby-1]) {
151 //LOGD("nearby-1=%d %p, inserting %p at -1\n",
152 // nearby-1, pSet->list[nearby-1], ptr);
154 } else if (ptr < pSet->list[nearby]) {
155 //LOGD("nearby=%d %p, inserting %p at +0\n",
156 // nearby, pSet->list[nearby], ptr);
158 //LOGD("nearby+1=%d %p, inserting %p at +1\n",
159 // nearby+1, pSet->list[nearby+1], ptr);
164 * Move existing values, if necessary.
166 if (nearby != pSet->count) {
168 memmove(&pSet->list[nearby+1], &pSet->list[nearby],
169 (pSet->count - nearby) * sizeof(pSet->list[0]));
173 pSet->list[nearby] = ptr;
176 assert(verifySorted(pSet));
181 * Returns "true" if the element was successfully removed.
183 bool dvmPointerSetRemoveEntry(PointerSet* pSet, const void* ptr)
187 if (!dvmPointerSetHas(pSet, ptr, &where))
190 if (where != pSet->count-1) {
192 memmove(&pSet->list[where], &pSet->list[where+1],
193 (pSet->count-1 - where) * sizeof(pSet->list[0]));
197 pSet->list[pSet->count] = (const void*) 0xdecadead; // debug
202 * Returns the index if "ptr" appears in the list. If it doesn't appear,
203 * this returns a negative index for a nearby element.
205 bool dvmPointerSetHas(const PointerSet* pSet, const void* ptr, int* pIndex)
212 /* array is sorted, use a binary search */
215 const void* listVal = pSet->list[mid];
219 } else if (ptr < listVal) {
221 } else /* listVal == ptr */ {
234 * Compute the intersection of the set and the array of pointers passed in.
236 * Any pointer in "pSet" that does not appear in "ptrArray" is removed.
238 void dvmPointerSetIntersect(PointerSet* pSet, const void** ptrArray, int count)
242 for (i = 0; i < pSet->count; i++) {
243 for (j = 0; j < count; j++) {
244 if (pSet->list[i] == ptrArray[j]) {
245 /* match, keep this one */
251 /* no match, remove entry */
252 if (i != pSet->count-1) {
254 memmove(&pSet->list[i], &pSet->list[i+1],
255 (pSet->count-1 - i) * sizeof(pSet->list[0]));
259 pSet->list[pSet->count] = (const void*) 0xdecadead; // debug
260 i--; /* adjust loop counter */
266 * Print the list contents to stdout. For debugging.
268 void dvmPointerSetDump(const PointerSet* pSet)
270 LOGI("PointerSet %p\n", pSet);
272 for (i = 0; i < pSet->count; i++)
273 LOGI(" %2d: %p", i, pSet->list[i]);