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  * Hash table.  The dominant calls are add and lookup, with removals
     18  * happening very infrequently.  We use probing, and don't worry much
     19  * about tombstone removal.
     20  */
     21 #include "Dalvik.h"
     22 
     23 #include <stdlib.h>
     24 
     25 /* table load factor, i.e. how full can it get before we resize */
     26 //#define LOAD_NUMER  3       // 75%
     27 //#define LOAD_DENOM  4
     28 #define LOAD_NUMER  5       // 62.5%
     29 #define LOAD_DENOM  8
     30 //#define LOAD_NUMER  1       // 50%
     31 //#define LOAD_DENOM  2
     32 
     33 /*
     34  * Compute the capacity needed for a table to hold "size" elements.
     35  */
     36 size_t dvmHashSize(size_t size) {
     37     return (size * LOAD_DENOM) / LOAD_NUMER +1;
     38 }
     39 
     40 
     41 /*
     42  * Create and initialize a hash table.
     43  */
     44 HashTable* dvmHashTableCreate(size_t initialSize, HashFreeFunc freeFunc)
     45 {
     46     HashTable* pHashTable;
     47 
     48     assert(initialSize > 0);
     49 
     50     pHashTable = (HashTable*) malloc(sizeof(*pHashTable));
     51     if (pHashTable == NULL)
     52         return NULL;
     53 
     54     dvmInitMutex(&pHashTable->lock);
     55 
     56     pHashTable->tableSize = dexRoundUpPower2(initialSize);
     57     pHashTable->numEntries = pHashTable->numDeadEntries = 0;
     58     pHashTable->freeFunc = freeFunc;
     59     pHashTable->pEntries =
     60         (HashEntry*) calloc(pHashTable->tableSize, sizeof(HashEntry));
     61     if (pHashTable->pEntries == NULL) {
     62         free(pHashTable);
     63         return NULL;
     64     }
     65 
     66     return pHashTable;
     67 }
     68 
     69 /*
     70  * Clear out all entries.
     71  */
     72 void dvmHashTableClear(HashTable* pHashTable)
     73 {
     74     HashEntry* pEnt;
     75     int i;
     76 
     77     pEnt = pHashTable->pEntries;
     78     for (i = 0; i < pHashTable->tableSize; i++, pEnt++) {
     79         if (pEnt->data == HASH_TOMBSTONE) {
     80             // nuke entry
     81             pEnt->data = NULL;
     82         } else if (pEnt->data != NULL) {
     83             // call free func then nuke entry
     84             if (pHashTable->freeFunc != NULL)
     85                 (*pHashTable->freeFunc)(pEnt->data);
     86             pEnt->data = NULL;
     87         }
     88     }
     89 
     90     pHashTable->numEntries = 0;
     91     pHashTable->numDeadEntries = 0;
     92 }
     93 
     94 /*
     95  * Free the table.
     96  */
     97 void dvmHashTableFree(HashTable* pHashTable)
     98 {
     99     if (pHashTable == NULL)
    100         return;
    101     dvmHashTableClear(pHashTable);
    102     free(pHashTable->pEntries);
    103     free(pHashTable);
    104 }
    105 
    106 #ifndef NDEBUG
    107 /*
    108  * Count up the number of tombstone entries in the hash table.
    109  */
    110 static int countTombStones(HashTable* pHashTable)
    111 {
    112     int i, count;
    113 
    114     for (count = i = 0; i < pHashTable->tableSize; i++) {
    115         if (pHashTable->pEntries[i].data == HASH_TOMBSTONE)
    116             count++;
    117     }
    118     return count;
    119 }
    120 #endif
    121 
    122 /*
    123  * Resize a hash table.  We do this when adding an entry increased the
    124  * size of the table beyond its comfy limit.
    125  *
    126  * This essentially requires re-inserting all elements into the new storage.
    127  *
    128  * If multiple threads can access the hash table, the table's lock should
    129  * have been grabbed before issuing the "lookup+add" call that led to the
    130  * resize, so we don't have a synchronization problem here.
    131  */
    132 static bool resizeHash(HashTable* pHashTable, int newSize)
    133 {
    134     HashEntry* pNewEntries;
    135     int i;
    136 
    137     assert(countTombStones(pHashTable) == pHashTable->numDeadEntries);
    138     //ALOGI("before: dead=%d", pHashTable->numDeadEntries);
    139 
    140     pNewEntries = (HashEntry*) calloc(newSize, sizeof(HashEntry));
    141     if (pNewEntries == NULL)
    142         return false;
    143 
    144     for (i = 0; i < pHashTable->tableSize; i++) {
    145         void* data = pHashTable->pEntries[i].data;
    146         if (data != NULL && data != HASH_TOMBSTONE) {
    147             int hashValue = pHashTable->pEntries[i].hashValue;
    148             int newIdx;
    149 
    150             /* probe for new spot, wrapping around */
    151             newIdx = hashValue & (newSize-1);
    152             while (pNewEntries[newIdx].data != NULL)
    153                 newIdx = (newIdx + 1) & (newSize-1);
    154 
    155             pNewEntries[newIdx].hashValue = hashValue;
    156             pNewEntries[newIdx].data = data;
    157         }
    158     }
    159 
    160     free(pHashTable->pEntries);
    161     pHashTable->pEntries = pNewEntries;
    162     pHashTable->tableSize = newSize;
    163     pHashTable->numDeadEntries = 0;
    164 
    165     assert(countTombStones(pHashTable) == 0);
    166     return true;
    167 }
    168 
    169 /*
    170  * Look up an entry.
    171  *
    172  * We probe on collisions, wrapping around the table.
    173  */
    174 void* dvmHashTableLookup(HashTable* pHashTable, u4 itemHash, void* item,
    175     HashCompareFunc cmpFunc, bool doAdd)
    176 {
    177     HashEntry* pEntry;
    178     HashEntry* pEnd;
    179     void* result = NULL;
    180 
    181     assert(pHashTable->tableSize > 0);
    182     assert(item != HASH_TOMBSTONE);
    183     assert(item != NULL);
    184 
    185     /* jump to the first entry and probe for a match */
    186     pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)];
    187     pEnd = &pHashTable->pEntries[pHashTable->tableSize];
    188     while (pEntry->data != NULL) {
    189         if (pEntry->data != HASH_TOMBSTONE &&
    190             pEntry->hashValue == itemHash &&
    191             (*cmpFunc)(pEntry->data, item) == 0)
    192         {
    193             /* match */
    194             //ALOGD("+++ match on entry %d", pEntry - pHashTable->pEntries);
    195             break;
    196         }
    197 
    198         pEntry++;
    199         if (pEntry == pEnd) {     /* wrap around to start */
    200             if (pHashTable->tableSize == 1)
    201                 break;      /* edge case - single-entry table */
    202             pEntry = pHashTable->pEntries;
    203         }
    204 
    205         //ALOGI("+++ look probing %d...", pEntry - pHashTable->pEntries);
    206     }
    207 
    208     if (pEntry->data == NULL) {
    209         if (doAdd) {
    210             pEntry->hashValue = itemHash;
    211             pEntry->data = item;
    212             pHashTable->numEntries++;
    213 
    214             /*
    215              * We've added an entry.  See if this brings us too close to full.
    216              */
    217             if ((pHashTable->numEntries+pHashTable->numDeadEntries) * LOAD_DENOM
    218                 > pHashTable->tableSize * LOAD_NUMER)
    219             {
    220                 if (!resizeHash(pHashTable, pHashTable->tableSize * 2)) {
    221                     /* don't really have a way to indicate failure */
    222                     ALOGE("Dalvik hash resize failure");
    223                     dvmAbort();
    224                 }
    225                 /* note "pEntry" is now invalid */
    226             } else {
    227                 //ALOGW("okay %d/%d/%d",
    228                 //    pHashTable->numEntries, pHashTable->tableSize,
    229                 //    (pHashTable->tableSize * LOAD_NUMER) / LOAD_DENOM);
    230             }
    231 
    232             /* full table is bad -- search for nonexistent never halts */
    233             assert(pHashTable->numEntries < pHashTable->tableSize);
    234             result = item;
    235         } else {
    236             assert(result == NULL);
    237         }
    238     } else {
    239         result = pEntry->data;
    240     }
    241 
    242     return result;
    243 }
    244 
    245 /*
    246  * Remove an entry from the table.
    247  *
    248  * Does NOT invoke the "free" function on the item.
    249  */
    250 bool dvmHashTableRemove(HashTable* pHashTable, u4 itemHash, void* item)
    251 {
    252     HashEntry* pEntry;
    253     HashEntry* pEnd;
    254 
    255     assert(pHashTable->tableSize > 0);
    256 
    257     /* jump to the first entry and probe for a match */
    258     pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)];
    259     pEnd = &pHashTable->pEntries[pHashTable->tableSize];
    260     while (pEntry->data != NULL) {
    261         if (pEntry->data == item) {
    262             //ALOGI("+++ stepping on entry %d", pEntry - pHashTable->pEntries);
    263             pEntry->data = HASH_TOMBSTONE;
    264             pHashTable->numEntries--;
    265             pHashTable->numDeadEntries++;
    266             return true;
    267         }
    268 
    269         pEntry++;
    270         if (pEntry == pEnd) {     /* wrap around to start */
    271             if (pHashTable->tableSize == 1)
    272                 break;      /* edge case - single-entry table */
    273             pEntry = pHashTable->pEntries;
    274         }
    275 
    276         //ALOGI("+++ del probing %d...", pEntry - pHashTable->pEntries);
    277     }
    278 
    279     return false;
    280 }
    281 
    282 /*
    283  * Scan every entry in the hash table and evaluate it with the specified
    284  * indirect function call. If the function returns 1, remove the entry from
    285  * the table.
    286  *
    287  * Does NOT invoke the "free" function on the item.
    288  *
    289  * Returning values other than 0 or 1 will abort the routine.
    290  */
    291 int dvmHashForeachRemove(HashTable* pHashTable, HashForeachRemoveFunc func)
    292 {
    293     int i, val, tableSize;
    294 
    295     tableSize = pHashTable->tableSize;
    296 
    297     for (i = 0; i < tableSize; i++) {
    298         HashEntry* pEnt = &pHashTable->pEntries[i];
    299 
    300         if (pEnt->data != NULL && pEnt->data != HASH_TOMBSTONE) {
    301             val = (*func)(pEnt->data);
    302             if (val == 1) {
    303                 pEnt->data = HASH_TOMBSTONE;
    304                 pHashTable->numEntries--;
    305                 pHashTable->numDeadEntries++;
    306             }
    307             else if (val != 0) {
    308                 return val;
    309             }
    310         }
    311     }
    312     return 0;
    313 }
    314 
    315 
    316 /*
    317  * Execute a function on every entry in the hash table.
    318  *
    319  * If "func" returns a nonzero value, terminate early and return the value.
    320  */
    321 int dvmHashForeach(HashTable* pHashTable, HashForeachFunc func, void* arg)
    322 {
    323     int i, val, tableSize;
    324 
    325     tableSize = pHashTable->tableSize;
    326 
    327     for (i = 0; i < tableSize; i++) {
    328         HashEntry* pEnt = &pHashTable->pEntries[i];
    329 
    330         if (pEnt->data != NULL && pEnt->data != HASH_TOMBSTONE) {
    331             val = (*func)(pEnt->data, arg);
    332             if (val != 0)
    333                 return val;
    334         }
    335     }
    336 
    337     return 0;
    338 }
    339 
    340 
    341 /*
    342  * Look up an entry, counting the number of times we have to probe.
    343  *
    344  * Returns -1 if the entry wasn't found.
    345  */
    346 static int countProbes(HashTable* pHashTable, u4 itemHash, const void* item,
    347     HashCompareFunc cmpFunc)
    348 {
    349     HashEntry* pEntry;
    350     HashEntry* pEnd;
    351     int count = 0;
    352 
    353     assert(pHashTable->tableSize > 0);
    354     assert(item != HASH_TOMBSTONE);
    355     assert(item != NULL);
    356 
    357     /* jump to the first entry and probe for a match */
    358     pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)];
    359     pEnd = &pHashTable->pEntries[pHashTable->tableSize];
    360     while (pEntry->data != NULL) {
    361         if (pEntry->data != HASH_TOMBSTONE &&
    362             pEntry->hashValue == itemHash &&
    363             (*cmpFunc)(pEntry->data, item) == 0)
    364         {
    365             /* match */
    366             break;
    367         }
    368 
    369         pEntry++;
    370         if (pEntry == pEnd) {     /* wrap around to start */
    371             if (pHashTable->tableSize == 1)
    372                 break;      /* edge case - single-entry table */
    373             pEntry = pHashTable->pEntries;
    374         }
    375 
    376         count++;
    377     }
    378     if (pEntry->data == NULL)
    379         return -1;
    380 
    381     return count;
    382 }
    383 
    384 /*
    385  * Evaluate the amount of probing required for the specified hash table.
    386  *
    387  * We do this by running through all entries in the hash table, computing
    388  * the hash value and then doing a lookup.
    389  *
    390  * The caller should lock the table before calling here.
    391  */
    392 void dvmHashTableProbeCount(HashTable* pHashTable, HashCalcFunc calcFunc,
    393     HashCompareFunc cmpFunc)
    394 {
    395     int numEntries, minProbe, maxProbe, totalProbe;
    396     HashIter iter;
    397 
    398     numEntries = maxProbe = totalProbe = 0;
    399     minProbe = 65536*32767;
    400 
    401     for (dvmHashIterBegin(pHashTable, &iter); !dvmHashIterDone(&iter);
    402         dvmHashIterNext(&iter))
    403     {
    404         const void* data = (const void*)dvmHashIterData(&iter);
    405         int count;
    406 
    407         count = countProbes(pHashTable, (*calcFunc)(data), data, cmpFunc);
    408 
    409         numEntries++;
    410 
    411         if (count < minProbe)
    412             minProbe = count;
    413         if (count > maxProbe)
    414             maxProbe = count;
    415         totalProbe += count;
    416     }
    417 
    418     ALOGI("Probe: min=%d max=%d, total=%d in %d (%d), avg=%.3f",
    419         minProbe, maxProbe, totalProbe, numEntries, pHashTable->tableSize,
    420         (float) totalProbe / (float) numEntries);
    421 }
    422