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