blob: ac08935d40205a561f0568aad6111e934ea5653b [file] [log] [blame]
The Android Open Source Projectc24a8e62009-03-03 19:28:42 -08001/*
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
Tianjie Xu74778142016-08-05 18:00:04 -070011#include <android-base/logging.h>
12
The Android Open Source Projectc24a8e62009-03-03 19:28:42 -080013#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);
The Android Open Source Projectc24a8e62009-03-03 19:28:42 -0800143
144 pNewEntries = (HashEntry*) calloc(newSize, sizeof(HashTable));
145 if (pNewEntries == NULL)
146 return false;
147
148 for (i = 0; i < pHashTable->tableSize; i++) {
149 void* data = pHashTable->pEntries[i].data;
150 if (data != NULL && data != HASH_TOMBSTONE) {
151 int hashValue = pHashTable->pEntries[i].hashValue;
152 int newIdx;
153
154 /* probe for new spot, wrapping around */
155 newIdx = hashValue & (newSize-1);
156 while (pNewEntries[newIdx].data != NULL)
157 newIdx = (newIdx + 1) & (newSize-1);
158
159 pNewEntries[newIdx].hashValue = hashValue;
160 pNewEntries[newIdx].data = data;
161 }
162 }
163
164 free(pHashTable->pEntries);
165 pHashTable->pEntries = pNewEntries;
166 pHashTable->tableSize = newSize;
167 pHashTable->numDeadEntries = 0;
168
169 assert(countTombStones(pHashTable) == 0);
170 return true;
171}
172
173/*
174 * Look up an entry.
175 *
176 * We probe on collisions, wrapping around the table.
177 */
178void* mzHashTableLookup(HashTable* pHashTable, unsigned int itemHash, void* item,
179 HashCompareFunc cmpFunc, bool doAdd)
180{
181 HashEntry* pEntry;
182 HashEntry* pEnd;
183 void* result = NULL;
184
185 assert(pHashTable->tableSize > 0);
186 assert(item != HASH_TOMBSTONE);
187 assert(item != NULL);
188
189 /* jump to the first entry and probe for a match */
190 pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)];
191 pEnd = &pHashTable->pEntries[pHashTable->tableSize];
192 while (pEntry->data != NULL) {
193 if (pEntry->data != HASH_TOMBSTONE &&
194 pEntry->hashValue == itemHash &&
195 (*cmpFunc)(pEntry->data, item) == 0)
196 {
197 /* match */
The Android Open Source Projectc24a8e62009-03-03 19:28:42 -0800198 break;
199 }
200
201 pEntry++;
202 if (pEntry == pEnd) { /* wrap around to start */
203 if (pHashTable->tableSize == 1)
204 break; /* edge case - single-entry table */
205 pEntry = pHashTable->pEntries;
206 }
The Android Open Source Projectc24a8e62009-03-03 19:28:42 -0800207 }
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 */
Tianjie Xu74778142016-08-05 18:00:04 -0700223 LOG(FATAL) << "Hash resize failure";
The Android Open Source Projectc24a8e62009-03-03 19:28:42 -0800224 }
225 /* note "pEntry" is now invalid */
The Android Open Source Projectc24a8e62009-03-03 19:28:42 -0800226 }
227
228 /* full table is bad -- search for nonexistent never halts */
229 assert(pHashTable->numEntries < pHashTable->tableSize);
230 result = item;
231 } else {
232 assert(result == NULL);
233 }
234 } else {
235 result = pEntry->data;
236 }
237
238 return result;
239}
240
241/*
242 * Remove an entry from the table.
243 *
244 * Does NOT invoke the "free" function on the item.
245 */
246bool mzHashTableRemove(HashTable* pHashTable, unsigned int itemHash, void* item)
247{
248 HashEntry* pEntry;
249 HashEntry* pEnd;
250
251 assert(pHashTable->tableSize > 0);
252
253 /* jump to the first entry and probe for a match */
254 pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)];
255 pEnd = &pHashTable->pEntries[pHashTable->tableSize];
256 while (pEntry->data != NULL) {
257 if (pEntry->data == item) {
The Android Open Source Projectc24a8e62009-03-03 19:28:42 -0800258 pEntry->data = HASH_TOMBSTONE;
259 pHashTable->numEntries--;
260 pHashTable->numDeadEntries++;
261 return true;
262 }
263
264 pEntry++;
265 if (pEntry == pEnd) { /* wrap around to start */
266 if (pHashTable->tableSize == 1)
267 break; /* edge case - single-entry table */
268 pEntry = pHashTable->pEntries;
269 }
The Android Open Source Projectc24a8e62009-03-03 19:28:42 -0800270 }
271
272 return false;
273}
274
275/*
276 * Execute a function on every entry in the hash table.
277 *
278 * If "func" returns a nonzero value, terminate early and return the value.
279 */
280int mzHashForeach(HashTable* pHashTable, HashForeachFunc func, void* arg)
281{
282 int i, val;
283
284 for (i = 0; i < pHashTable->tableSize; i++) {
285 HashEntry* pEnt = &pHashTable->pEntries[i];
286
287 if (pEnt->data != NULL && pEnt->data != HASH_TOMBSTONE) {
288 val = (*func)(pEnt->data, arg);
289 if (val != 0)
290 return val;
291 }
292 }
293
294 return 0;
295}
296
297
298/*
299 * Look up an entry, counting the number of times we have to probe.
300 *
301 * Returns -1 if the entry wasn't found.
302 */
303int countProbes(HashTable* pHashTable, unsigned int itemHash, const void* item,
304 HashCompareFunc cmpFunc)
305{
306 HashEntry* pEntry;
307 HashEntry* pEnd;
308 int count = 0;
309
310 assert(pHashTable->tableSize > 0);
311 assert(item != HASH_TOMBSTONE);
312 assert(item != NULL);
313
314 /* jump to the first entry and probe for a match */
315 pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)];
316 pEnd = &pHashTable->pEntries[pHashTable->tableSize];
317 while (pEntry->data != NULL) {
318 if (pEntry->data != HASH_TOMBSTONE &&
319 pEntry->hashValue == itemHash &&
320 (*cmpFunc)(pEntry->data, item) == 0)
321 {
322 /* match */
323 break;
324 }
325
326 pEntry++;
327 if (pEntry == pEnd) { /* wrap around to start */
328 if (pHashTable->tableSize == 1)
329 break; /* edge case - single-entry table */
330 pEntry = pHashTable->pEntries;
331 }
332
333 count++;
334 }
335 if (pEntry->data == NULL)
336 return -1;
337
338 return count;
339}
340
341/*
342 * Evaluate the amount of probing required for the specified hash table.
343 *
344 * We do this by running through all entries in the hash table, computing
345 * the hash value and then doing a lookup.
346 *
347 * The caller should lock the table before calling here.
348 */
349void mzHashTableProbeCount(HashTable* pHashTable, HashCalcFunc calcFunc,
350 HashCompareFunc cmpFunc)
351{
352 int numEntries, minProbe, maxProbe, totalProbe;
353 HashIter iter;
354
355 numEntries = maxProbe = totalProbe = 0;
356 minProbe = 65536*32767;
357
358 for (mzHashIterBegin(pHashTable, &iter); !mzHashIterDone(&iter);
359 mzHashIterNext(&iter))
360 {
361 const void* data = (const void*)mzHashIterData(&iter);
362 int count;
Tao Baod7d0f752015-07-15 14:13:06 -0700363
The Android Open Source Projectc24a8e62009-03-03 19:28:42 -0800364 count = countProbes(pHashTable, (*calcFunc)(data), data, cmpFunc);
365
366 numEntries++;
367
368 if (count < minProbe)
369 minProbe = count;
370 if (count > maxProbe)
371 maxProbe = count;
372 totalProbe += count;
373 }
374
Tianjie Xu74778142016-08-05 18:00:04 -0700375 LOG(VERBOSE) << "Probe: min=" << minProbe << ", max=" << maxProbe << ", total="
376 << totalProbe <<" in " << numEntries << " (" << pHashTable->tableSize
377 << "), avg=" << (float) totalProbe / (float) numEntries;
The Android Open Source Projectc24a8e62009-03-03 19:28:42 -0800378}