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