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 */
mzHashSize(size_t size)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 */
roundUpPower2(unsigned int val)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 */
mzHashTableCreate(size_t initialSize,HashFreeFunc freeFunc)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 */
mzHashTableClear(HashTable * pHashTable)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 */
mzHashTableFree(HashTable * pHashTable)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 */
countTombStones(HashTable * pHashTable)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 */
resizeHash(HashTable * pHashTable,int newSize)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 */
mzHashTableLookup(HashTable * pHashTable,unsigned int itemHash,void * item,HashCompareFunc cmpFunc,bool doAdd)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 */
mzHashTableRemove(HashTable * pHashTable,unsigned int itemHash,void * item)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 */
mzHashForeach(HashTable * pHashTable,HashForeachFunc func,void * arg)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 */
countProbes(HashTable * pHashTable,unsigned int itemHash,const void * item,HashCompareFunc cmpFunc)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 */
mzHashTableProbeCount(HashTable * pHashTable,HashCalcFunc calcFunc,HashCompareFunc cmpFunc)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