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 * General purpose hash table, used for finding classes, methods, etc. 18 * 19 * When the number of elements reaches a certain percentage of the table's 20 * capacity, the table will be resized. 21 */ 22 #ifndef DALVIK_HASH_H_ 23 #define DALVIK_HASH_H_ 24 25 /* compute the hash of an item with a specific type */ 26 typedef u4 (*HashCompute)(const void* item); 27 28 /* 29 * Compare a hash entry with a "loose" item after their hash values match. 30 * Returns { <0, 0, >0 } depending on ordering of items (same semantics 31 * as strcmp()). 32 */ 33 typedef int (*HashCompareFunc)(const void* tableItem, const void* looseItem); 34 35 /* 36 * This function will be used to free entries in the table. This can be 37 * NULL if no free is required, free(), or a custom function. 38 */ 39 typedef void (*HashFreeFunc)(void* ptr); 40 41 /* 42 * Used by dvmHashForeach(). 43 */ 44 typedef int (*HashForeachFunc)(void* data, void* arg); 45 46 /* 47 * Used by dvmHashForeachRemove(). 48 */ 49 typedef int (*HashForeachRemoveFunc)(void* data); 50 51 /* 52 * One entry in the hash table. "data" values are expected to be (or have 53 * the same characteristics as) valid pointers. In particular, a NULL 54 * value for "data" indicates an empty slot, and HASH_TOMBSTONE indicates 55 * a no-longer-used slot that must be stepped over during probing. 56 * 57 * Attempting to add a NULL or tombstone value is an error. 58 * 59 * When an entry is released, we will call (HashFreeFunc)(entry->data). 60 */ 61 struct HashEntry { 62 u4 hashValue; 63 void* data; 64 }; 65 66 #define HASH_TOMBSTONE ((void*) 0xcbcacccd) // invalid ptr value 67 68 /* 69 * Expandable hash table. 70 * 71 * This structure should be considered opaque. 72 */ 73 struct HashTable { 74 int tableSize; /* must be power of 2 */ 75 int numEntries; /* current #of "live" entries */ 76 int numDeadEntries; /* current #of tombstone entries */ 77 HashEntry* pEntries; /* array on heap */ 78 HashFreeFunc freeFunc; 79 pthread_mutex_t lock; 80 }; 81 82 /* 83 * Create and initialize a HashTable structure, using "initialSize" as 84 * a basis for the initial capacity of the table. (The actual initial 85 * table size may be adjusted upward.) If you know exactly how many 86 * elements the table will hold, pass the result from dvmHashSize() in.) 87 * 88 * Returns "false" if unable to allocate the table. 89 */ 90 HashTable* dvmHashTableCreate(size_t initialSize, HashFreeFunc freeFunc); 91 92 /* 93 * Compute the capacity needed for a table to hold "size" elements. Use 94 * this when you know ahead of time how many elements the table will hold. 95 * Pass this value into dvmHashTableCreate() to ensure that you can add 96 * all elements without needing to reallocate the table. 97 */ 98 size_t dvmHashSize(size_t size); 99 100 /* 101 * Clear out a hash table, freeing the contents of any used entries. 102 */ 103 void dvmHashTableClear(HashTable* pHashTable); 104 105 /* 106 * Free a hash table. Performs a "clear" first. 107 */ 108 void dvmHashTableFree(HashTable* pHashTable); 109 110 /* 111 * Exclusive access. Important when adding items to a table, or when 112 * doing any operations on a table that could be added to by another thread. 113 */ 114 INLINE void dvmHashTableLock(HashTable* pHashTable) { 115 dvmLockMutex(&pHashTable->lock); 116 } 117 INLINE void dvmHashTableUnlock(HashTable* pHashTable) { 118 dvmUnlockMutex(&pHashTable->lock); 119 } 120 121 /* 122 * Get #of entries in hash table. 123 */ 124 INLINE int dvmHashTableNumEntries(HashTable* pHashTable) { 125 return pHashTable->numEntries; 126 } 127 128 /* 129 * Get total size of hash table (for memory usage calculations). 130 */ 131 INLINE int dvmHashTableMemUsage(HashTable* pHashTable) { 132 return sizeof(HashTable) + pHashTable->tableSize * sizeof(HashEntry); 133 } 134 135 /* 136 * Look up an entry in the table, possibly adding it if it's not there. 137 * 138 * If "item" is not found, and "doAdd" is false, NULL is returned. 139 * Otherwise, a pointer to the found or added item is returned. (You can 140 * tell the difference by seeing if return value == item.) 141 * 142 * An "add" operation may cause the entire table to be reallocated. Don't 143 * forget to lock the table before calling this. 144 */ 145 void* dvmHashTableLookup(HashTable* pHashTable, u4 itemHash, void* item, 146 HashCompareFunc cmpFunc, bool doAdd); 147 148 /* 149 * Remove an item from the hash table, given its "data" pointer. Does not 150 * invoke the "free" function; just detaches it from the table. 151 */ 152 bool dvmHashTableRemove(HashTable* pHashTable, u4 hash, void* item); 153 154 /* 155 * Execute "func" on every entry in the hash table. 156 * 157 * If "func" returns a nonzero value, terminate early and return the value. 158 */ 159 int dvmHashForeach(HashTable* pHashTable, HashForeachFunc func, void* arg); 160 161 /* 162 * Execute "func" on every entry in the hash table. 163 * 164 * If "func" returns 1 detach the entry from the hash table. Does not invoke 165 * the "free" function. 166 * 167 * Returning values other than 0 or 1 from "func" will abort the routine. 168 */ 169 int dvmHashForeachRemove(HashTable* pHashTable, HashForeachRemoveFunc func); 170 171 /* 172 * An alternative to dvmHashForeach(), using an iterator. 173 * 174 * Use like this: 175 * HashIter iter; 176 * for (dvmHashIterBegin(hashTable, &iter); !dvmHashIterDone(&iter); 177 * dvmHashIterNext(&iter)) 178 * { 179 * MyData* data = (MyData*)dvmHashIterData(&iter); 180 * } 181 */ 182 struct HashIter { 183 void* data; 184 HashTable* pHashTable; 185 int idx; 186 }; 187 INLINE void dvmHashIterNext(HashIter* pIter) { 188 int i = pIter->idx +1; 189 int lim = pIter->pHashTable->tableSize; 190 for ( ; i < lim; i++) { 191 void* data = pIter->pHashTable->pEntries[i].data; 192 if (data != NULL && data != HASH_TOMBSTONE) 193 break; 194 } 195 pIter->idx = i; 196 } 197 INLINE void dvmHashIterBegin(HashTable* pHashTable, HashIter* pIter) { 198 pIter->pHashTable = pHashTable; 199 pIter->idx = -1; 200 dvmHashIterNext(pIter); 201 } 202 INLINE bool dvmHashIterDone(HashIter* pIter) { 203 return (pIter->idx >= pIter->pHashTable->tableSize); 204 } 205 INLINE void* dvmHashIterData(HashIter* pIter) { 206 assert(pIter->idx >= 0 && pIter->idx < pIter->pHashTable->tableSize); 207 return pIter->pHashTable->pEntries[pIter->idx].data; 208 } 209 210 211 /* 212 * Evaluate hash table performance by examining the number of times we 213 * have to probe for an entry. 214 * 215 * The caller should lock the table beforehand. 216 */ 217 typedef u4 (*HashCalcFunc)(const void* item); 218 void dvmHashTableProbeCount(HashTable* pHashTable, HashCalcFunc calcFunc, 219 HashCompareFunc cmpFunc); 220 221 #endif // DALVIK_HASH_H_ 222
