Home | History | Annotate | Download | only in vm
      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 #ifndef NDEBUG
     34 static 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  */
     55 PointerSet* 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  */
     75 void 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  */
     90 void dvmPointerSetClear(PointerSet* pSet)
     91 {
     92     pSet->count = 0;
     93 }
     94 
     95 /*
     96  * Get the number of pointers currently stored in the list.
     97  */
     98 int dvmPointerSetGetCount(const PointerSet* pSet)
     99 {
    100     return pSet->count;
    101 }
    102 
    103 /*
    104  * Get the Nth entry from the list.
    105  */
    106 const 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  */
    117 bool 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             //LOGD("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             //LOGD("nearby=%d %p, inserting %p at +0",
    156             //    nearby, pSet->list[nearby], ptr);
    157         } else {
    158             //LOGD("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  */
    183 bool 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  */
    205 bool 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  */
    238 void 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  */
    268 void dvmPointerSetDump(const PointerSet* pSet)
    269 {
    270     LOGI("PointerSet %p", pSet);
    271     int i;
    272     for (i = 0; i < pSet->count; i++)
    273         LOGI(" %2d: %p", i, pSet->list[i]);
    274 }
    275