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