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*) 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 */
dvmHashTableClear(HashTable * pHashTable)73 void 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 */
dvmHashTableFree(HashTable * pHashTable)98 void 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 */
countTombStones(HashTable * pHashTable)111 static 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 */
resizeHash(HashTable * pHashTable,int newSize)133 static bool resizeHash(HashTable* pHashTable, int newSize)
134 {
135 HashEntry* pNewEntries;
136 int i;
137
138 assert(countTombStones(pHashTable) == pHashTable->numDeadEntries);
139 //LOGI("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 */
dvmHashTableLookup(HashTable * pHashTable,u4 itemHash,void * item,HashCompareFunc cmpFunc,bool doAdd)175 void* 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 //LOGD("+++ 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 //LOGI("+++ 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 //LOGW("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 */
dvmHashTableRemove(HashTable * pHashTable,u4 itemHash,void * item)251 bool 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 //LOGI("+++ 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 //LOGI("+++ 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 */
dvmHashForeachRemove(HashTable * pHashTable,HashForeachRemoveFunc func)292 int 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 */
dvmHashForeach(HashTable * pHashTable,HashForeachFunc func,void * arg)320 int 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 */
countProbes(HashTable * pHashTable,u4 itemHash,const void * item,HashCompareFunc cmpFunc)343 static 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 */
dvmHashTableProbeCount(HashTable * pHashTable,HashCalcFunc calcFunc,HashCompareFunc cmpFunc)389 void 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 LOGI("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