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