vm/Hash.c

   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\n", 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\n", 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...\n", 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\n");
 224                     dvmAbort();
 225                 }
 226                 /* note "pEntry" is now invalid */
 227             } else {
 228                 //LOGW("okay %d/%d/%d\n",
 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\n", 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...\n", 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\n",
 416         minProbe, maxProbe, totalProbe, numEntries, pHashTable->tableSize,
 417         (float) totalProbe / (float) numEntries);
 418 }