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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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