vm/Hash.cpp

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