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.
33 static bool verifySorted(PointerSet* pSet)
35 const void* last = NULL;
38 for (i = 0; i < pSet->count; i++) {
39 const void* cur = pSet->list[i];
50 * Allocate a new PointerSet.
52 * Returns NULL on failure.
54 PointerSet* dvmPointerSetAlloc(int initialSize)
56 PointerSet* pSet = calloc(1, sizeof(PointerSet));
58 if (initialSize > 0) {
59 pSet->list = malloc(sizeof(const void*) * initialSize);
60 if (pSet->list == NULL) {
64 pSet->alloc = initialSize;
72 * Free up a PointerSet.
74 void dvmPointerSetFree(PointerSet* pSet)
79 if (pSet->list != NULL) {
87 * Clear the contents of a pointer set.
89 void dvmPointerSetClear(PointerSet* pSet)
95 * Get the number of pointers currently stored in the list.
97 int dvmPointerSetGetCount(const PointerSet* pSet)
103 * Get the Nth entry from the list.
105 const void* dvmPointerSetGetEntry(const PointerSet* pSet, int i)
107 return pSet->list[i];
111 * Insert a new entry into the list. If it already exists, this returns
112 * without doing anything.
114 * Returns "true" if the value was added.
116 bool dvmPointerSetAddEntry(PointerSet* pSet, const void* ptr)
120 if (dvmPointerSetHas(pSet, ptr, &nearby))
123 /* ensure we have space to add one more */
124 if (pSet->count == pSet->alloc) {
126 const void** newList;
128 if (pSet->alloc == 0)
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);
138 pSet->list = newList;
141 if (pSet->count == 0) {
146 * Determine the insertion index. The binary search might have
147 * terminated "above" or "below" the value.
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);
153 } else if (ptr < pSet->list[nearby]) {
154 //LOGD("nearby=%d %p, inserting %p at +0\n",
155 // nearby, pSet->list[nearby], ptr);
157 //LOGD("nearby+1=%d %p, inserting %p at +1\n",
158 // nearby+1, pSet->list[nearby+1], ptr);
163 * Move existing values, if necessary.
165 if (nearby != pSet->count) {
167 memmove(&pSet->list[nearby+1], &pSet->list[nearby],
168 (pSet->count - nearby) * sizeof(pSet->list[0]));
172 pSet->list[nearby] = ptr;
175 assert(verifySorted(pSet));
180 * Returns "true" if the element was successfully removed.
182 bool dvmPointerSetRemoveEntry(PointerSet* pSet, const void* ptr)
186 if (!dvmPointerSetHas(pSet, ptr, &where))
189 if (where != pSet->count-1) {
191 memmove(&pSet->list[where], &pSet->list[where+1],
192 (pSet->count-1 - where) * sizeof(pSet->list[0]));
196 pSet->list[pSet->count] = (const void*) 0xdecadead; // debug
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.
204 bool dvmPointerSetHas(const PointerSet* pSet, const void* ptr, int* pIndex)
211 /* array is sorted, use a binary search */
214 const void* listVal = pSet->list[mid];
218 } else if (ptr < listVal) {
220 } else /* listVal == ptr */ {
233 * Compute the intersection of the set and the array of pointers passed in.
235 * Any pointer in "pSet" that does not appear in "ptrArray" is removed.
237 void dvmPointerSetIntersect(PointerSet* pSet, const void** ptrArray, int count)
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 */
250 /* no match, remove entry */
251 if (i != pSet->count-1) {
253 memmove(&pSet->list[i], &pSet->list[i+1],
254 (pSet->count-1 - i) * sizeof(pSet->list[0]));
258 pSet->list[pSet->count] = (const void*) 0xdecadead; // debug
259 i--; /* adjust loop counter */
265 * Print the list contents to stdout. For debugging.
267 void dvmPointerSetDump(const PointerSet* pSet)
270 for (i = 0; i < pSet->count; i++)
271 printf(" %p", pSet->list[i]);