vm/Hash.h

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