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 */
26size_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 */
35unsigned 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 */
51HashTable* 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 */
77void 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 */
102void 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 */
115static 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 */
137static 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 */
179void* 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 */
255bool 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 */
292int 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 */
315int 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 */
361void 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