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_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_