1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2008 The Android Open Source Project 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License. 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License. 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Hash table. The dominant calls are add and lookup, with removals 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * happening very infrequently. We use probing, and don't worry much 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * about tombstone removal. 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#include "Dalvik.h" 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#include <stdlib.h> 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* table load factor, i.e. how full can it get before we resize */ 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project//#define LOAD_NUMER 3 // 75% 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project//#define LOAD_DENOM 4 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#define LOAD_NUMER 5 // 62.5% 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#define LOAD_DENOM 8 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project//#define LOAD_NUMER 1 // 50% 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project//#define LOAD_DENOM 2 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Compute the capacity needed for a table to hold "size" elements. 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectsize_t dvmHashSize(size_t size) { 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (size * LOAD_DENOM) / LOAD_NUMER +1; 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Create and initialize a hash table. 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source ProjectHashTable* dvmHashTableCreate(size_t initialSize, HashFreeFunc freeFunc) 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashTable* pHashTable; 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(initialSize > 0); 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable = (HashTable*) malloc(sizeof(*pHashTable)); 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pHashTable == NULL) 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return NULL; 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmInitMutex(&pHashTable->lock); 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable->tableSize = dexRoundUpPower2(initialSize); 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable->numEntries = pHashTable->numDeadEntries = 0; 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable->freeFunc = freeFunc; 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable->pEntries = 60b74e7190e86d559712747e5cdb31a0d390b7af7dIliyan Malchev (HashEntry*) calloc(pHashTable->tableSize, sizeof(HashEntry)); 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pHashTable->pEntries == NULL) { 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project free(pHashTable); 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return NULL; 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return pHashTable; 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Clear out all entries. 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmHashTableClear(HashTable* pHashTable) 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashEntry* pEnt; 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i; 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEnt = pHashTable->pEntries; 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (i = 0; i < pHashTable->tableSize; i++, pEnt++) { 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pEnt->data == HASH_TOMBSTONE) { 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // nuke entry 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEnt->data = NULL; 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (pEnt->data != NULL) { 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // call free func then nuke entry 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pHashTable->freeFunc != NULL) 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (*pHashTable->freeFunc)(pEnt->data); 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEnt->data = NULL; 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable->numEntries = 0; 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable->numDeadEntries = 0; 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Free the table. 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmHashTableFree(HashTable* pHashTable) 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pHashTable == NULL) 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmHashTableClear(pHashTable); 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project free(pHashTable->pEntries); 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project free(pHashTable); 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#ifndef NDEBUG 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Count up the number of tombstone entries in the hash table. 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectstatic int countTombStones(HashTable* pHashTable) 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i, count; 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (count = i = 0; i < pHashTable->tableSize; i++) { 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pHashTable->pEntries[i].data == HASH_TOMBSTONE) 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project count++; 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return count; 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#endif 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Resize a hash table. We do this when adding an entry increased the 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * size of the table beyond its comfy limit. 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This essentially requires re-inserting all elements into the new storage. 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If multiple threads can access the hash table, the table's lock should 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * have been grabbed before issuing the "lookup+add" call that led to the 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * resize, so we don't have a synchronization problem here. 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectstatic bool resizeHash(HashTable* pHashTable, int newSize) 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashEntry* pNewEntries; 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i; 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(countTombStones(pHashTable) == pHashTable->numDeadEntries); 1384308417beec548c2b2c06ecec4f7f4a965b09fb2Steve Block //ALOGI("before: dead=%d", pHashTable->numDeadEntries); 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pNewEntries = (HashEntry*) calloc(newSize, sizeof(HashEntry)); 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pNewEntries == NULL) 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (i = 0; i < pHashTable->tableSize; i++) { 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void* data = pHashTable->pEntries[i].data; 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (data != NULL && data != HASH_TOMBSTONE) { 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int hashValue = pHashTable->pEntries[i].hashValue; 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newIdx; 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* probe for new spot, wrapping around */ 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newIdx = hashValue & (newSize-1); 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (pNewEntries[newIdx].data != NULL) 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newIdx = (newIdx + 1) & (newSize-1); 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pNewEntries[newIdx].hashValue = hashValue; 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pNewEntries[newIdx].data = data; 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project free(pHashTable->pEntries); 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable->pEntries = pNewEntries; 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable->tableSize = newSize; 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable->numDeadEntries = 0; 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(countTombStones(pHashTable) == 0); 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Look up an entry. 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We probe on collisions, wrapping around the table. 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid* dvmHashTableLookup(HashTable* pHashTable, u4 itemHash, void* item, 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashCompareFunc cmpFunc, bool doAdd) 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashEntry* pEntry; 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashEntry* pEnd; 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project void* result = NULL; 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(pHashTable->tableSize > 0); 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(item != HASH_TOMBSTONE); 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(item != NULL); 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* jump to the first entry and probe for a match */ 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)]; 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEnd = &pHashTable->pEntries[pHashTable->tableSize]; 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (pEntry->data != NULL) { 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pEntry->data != HASH_TOMBSTONE && 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry->hashValue == itemHash && 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (*cmpFunc)(pEntry->data, item) == 0) 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project { 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* match */ 194062bf509a77fce9dfcb7e7b2e401cf2a124d83d5Steve Block //ALOGD("+++ match on entry %d", pEntry - pHashTable->pEntries); 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry++; 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pEntry == pEnd) { /* wrap around to start */ 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pHashTable->tableSize == 1) 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; /* edge case - single-entry table */ 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry = pHashTable->pEntries; 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2054308417beec548c2b2c06ecec4f7f4a965b09fb2Steve Block //ALOGI("+++ look probing %d...", pEntry - pHashTable->pEntries); 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pEntry->data == NULL) { 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (doAdd) { 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry->hashValue = itemHash; 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry->data = item; 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable->numEntries++; 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We've added an entry. See if this brings us too close to full. 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((pHashTable->numEntries+pHashTable->numDeadEntries) * LOAD_DENOM 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project > pHashTable->tableSize * LOAD_NUMER) 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project { 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!resizeHash(pHashTable, pHashTable->tableSize * 2)) { 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* don't really have a way to indicate failure */ 222c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE("Dalvik hash resize failure"); 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmAbort(); 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* note "pEntry" is now invalid */ 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 227e8e1ddccd616e8226b7cc1e4e9fdb327429249e8Steve Block //ALOGW("okay %d/%d/%d", 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // pHashTable->numEntries, pHashTable->tableSize, 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // (pHashTable->tableSize * LOAD_NUMER) / LOAD_DENOM); 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* full table is bad -- search for nonexistent never halts */ 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(pHashTable->numEntries < pHashTable->tableSize); 234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result = item; 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(result == NULL); 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result = pEntry->data; 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Remove an entry from the table. 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Does NOT invoke the "free" function on the item. 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectbool dvmHashTableRemove(HashTable* pHashTable, u4 itemHash, void* item) 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashEntry* pEntry; 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashEntry* pEnd; 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(pHashTable->tableSize > 0); 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* jump to the first entry and probe for a match */ 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)]; 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEnd = &pHashTable->pEntries[pHashTable->tableSize]; 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (pEntry->data != NULL) { 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pEntry->data == item) { 2624308417beec548c2b2c06ecec4f7f4a965b09fb2Steve Block //ALOGI("+++ stepping on entry %d", pEntry - pHashTable->pEntries); 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry->data = HASH_TOMBSTONE; 264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable->numEntries--; 265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable->numDeadEntries++; 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry++; 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pEntry == pEnd) { /* wrap around to start */ 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pHashTable->tableSize == 1) 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; /* edge case - single-entry table */ 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry = pHashTable->pEntries; 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2764308417beec548c2b2c06ecec4f7f4a965b09fb2Steve Block //ALOGI("+++ del probing %d...", pEntry - pHashTable->pEntries); 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 279f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Scan every entry in the hash table and evaluate it with the specified 284de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * indirect function call. If the function returns 1, remove the entry from 285de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * the table. 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Does NOT invoke the "free" function on the item. 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returning values other than 0 or 1 will abort the routine. 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectint dvmHashForeachRemove(HashTable* pHashTable, HashForeachRemoveFunc func) 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i, val; 294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (i = 0; i < pHashTable->tableSize; i++) { 296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashEntry* pEnt = &pHashTable->pEntries[i]; 297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pEnt->data != NULL && pEnt->data != HASH_TOMBSTONE) { 299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project val = (*func)(pEnt->data); 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (val == 1) { 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEnt->data = HASH_TOMBSTONE; 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable->numEntries--; 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pHashTable->numDeadEntries++; 304f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project else if (val != 0) { 306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return val; 307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 310f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return 0; 311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Execute a function on every entry in the hash table. 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If "func" returns a nonzero value, terminate early and return the value. 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectint dvmHashForeach(HashTable* pHashTable, HashForeachFunc func, void* arg) 320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int i, val; 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (i = 0; i < pHashTable->tableSize; i++) { 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashEntry* pEnt = &pHashTable->pEntries[i]; 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pEnt->data != NULL && pEnt->data != HASH_TOMBSTONE) { 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project val = (*func)(pEnt->data, arg); 328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (val != 0) 329f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return val; 330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return 0; 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Look up an entry, counting the number of times we have to probe. 339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 340f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns -1 if the entry wasn't found. 341f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectstatic int countProbes(HashTable* pHashTable, u4 itemHash, const void* item, 343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashCompareFunc cmpFunc) 344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashEntry* pEntry; 346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashEntry* pEnd; 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int count = 0; 348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(pHashTable->tableSize > 0); 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(item != HASH_TOMBSTONE); 351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(item != NULL); 352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* jump to the first entry and probe for a match */ 354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry = &pHashTable->pEntries[itemHash & (pHashTable->tableSize-1)]; 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEnd = &pHashTable->pEntries[pHashTable->tableSize]; 356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (pEntry->data != NULL) { 357f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pEntry->data != HASH_TOMBSTONE && 358f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry->hashValue == itemHash && 359f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (*cmpFunc)(pEntry->data, item) == 0) 360f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project { 361f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* match */ 362f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry++; 366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pEntry == pEnd) { /* wrap around to start */ 367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pHashTable->tableSize == 1) 368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; /* edge case - single-entry table */ 369f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry = pHashTable->pEntries; 370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 371f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 372f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project count++; 373f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pEntry->data == NULL) 375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return -1; 376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return count; 378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Evaluate the amount of probing required for the specified hash table. 382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We do this by running through all entries in the hash table, computing 384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the hash value and then doing a lookup. 385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The caller should lock the table before calling here. 387f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmHashTableProbeCount(HashTable* pHashTable, HashCalcFunc calcFunc, 389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashCompareFunc cmpFunc) 390f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int numEntries, minProbe, maxProbe, totalProbe; 392f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashIter iter; 393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project numEntries = maxProbe = totalProbe = 0; 395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project minProbe = 65536*32767; 396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (dvmHashIterBegin(pHashTable, &iter); !dvmHashIterDone(&iter); 398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmHashIterNext(&iter)) 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project { 400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project const void* data = (const void*)dvmHashIterData(&iter); 401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int count; 402de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 403f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project count = countProbes(pHashTable, (*calcFunc)(data), data, cmpFunc); 404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project numEntries++; 406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (count < minProbe) 408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project minProbe = count; 409f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (count > maxProbe) 410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project maxProbe = count; 411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project totalProbe += count; 412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 4144308417beec548c2b2c06ecec4f7f4a965b09fb2Steve Block ALOGI("Probe: min=%d max=%d, total=%d in %d (%d), avg=%.3f", 415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project minProbe, maxProbe, totalProbe, numEntries, pHashTable->tableSize, 416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (float) totalProbe / (float) numEntries); 417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 418