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