1 /* 2 * Copyright 2007 The Android Open Source Project 3 * 4 * General purpose hash table, used for finding classes, methods, etc. 5 * 6 * When the number of elements reaches 3/4 of the table's capacity, the 7 * table will be resized. 8 */ 9 #ifndef _MINZIP_HASH 10 #define _MINZIP_HASH 11 12 #include "inline_magic.h" 13 14 #include <stdlib.h> 15 #include <stdbool.h> 16 #include <assert.h> 17 18 /* compute the hash of an item with a specific type */ 19 typedef unsigned int (*HashCompute)(const void* item); 20 21 /* 22 * Compare a hash entry with a "loose" item after their hash values match. 23 * Returns { <0, 0, >0 } depending on ordering of items (same semantics 24 * as strcmp()). 25 */ 26 typedef int (*HashCompareFunc)(const void* tableItem, const void* looseItem); 27 28 /* 29 * This function will be used to free entries in the table. This can be 30 * NULL if no free is required, free(), or a custom function. 31 */ 32 typedef void (*HashFreeFunc)(void* ptr); 33 34 /* 35 * Used by mzHashForeach(). 36 */ 37 typedef int (*HashForeachFunc)(void* data, void* arg); 38 39 /* 40 * One entry in the hash table. "data" values are expected to be (or have 41 * the same characteristics as) valid pointers. In particular, a NULL 42 * value for "data" indicates an empty slot, and HASH_TOMBSTONE indicates 43 * a no-longer-used slot that must be stepped over during probing. 44 * 45 * Attempting to add a NULL or tombstone value is an error. 46 * 47 * When an entry is released, we will call (HashFreeFunc)(entry->data). 48 */ 49 typedef struct HashEntry { 50 unsigned int hashValue; 51 void* data; 52 } HashEntry; 53 54 #define HASH_TOMBSTONE ((void*) 0xcbcacccd) // invalid ptr value 55 56 /* 57 * Expandable hash table. 58 * 59 * This structure should be considered opaque. 60 */ 61 typedef struct HashTable { 62 int tableSize; /* must be power of 2 */ 63 int numEntries; /* current #of "live" entries */ 64 int numDeadEntries; /* current #of tombstone entries */ 65 HashEntry* pEntries; /* array on heap */ 66 HashFreeFunc freeFunc; 67 } HashTable; 68 69 /* 70 * Create and initialize a HashTable structure, using "initialSize" as 71 * a basis for the initial capacity of the table. (The actual initial 72 * table size may be adjusted upward.) If you know exactly how many 73 * elements the table will hold, pass the result from mzHashSize() in.) 74 * 75 * Returns "false" if unable to allocate the table. 76 */ 77 HashTable* mzHashTableCreate(size_t initialSize, HashFreeFunc freeFunc); 78 79 /* 80 * Compute the capacity needed for a table to hold "size" elements. Use 81 * this when you know ahead of time how many elements the table will hold. 82 * Pass this value into mzHashTableCreate() to ensure that you can add 83 * all elements without needing to reallocate the table. 84 */ 85 size_t mzHashSize(size_t size); 86 87 /* 88 * Clear out a hash table, freeing the contents of any used entries. 89 */ 90 void mzHashTableClear(HashTable* pHashTable); 91 92 /* 93 * Free a hash table. 94 */ 95 void mzHashTableFree(HashTable* pHashTable); 96 97 /* 98 * Get #of entries in hash table. 99 */ 100 INLINE int mzHashTableNumEntries(HashTable* pHashTable) { 101 return pHashTable->numEntries; 102 } 103 104 /* 105 * Get total size of hash table (for memory usage calculations). 106 */ 107 INLINE int mzHashTableMemUsage(HashTable* pHashTable) { 108 return sizeof(HashTable) + pHashTable->tableSize * sizeof(HashEntry); 109 } 110 111 /* 112 * Look up an entry in the table, possibly adding it if it's not there. 113 * 114 * If "item" is not found, and "doAdd" is false, NULL is returned. 115 * Otherwise, a pointer to the found or added item is returned. (You can 116 * tell the difference by seeing if return value == item.) 117 * 118 * An "add" operation may cause the entire table to be reallocated. 119 */ 120 void* mzHashTableLookup(HashTable* pHashTable, unsigned int itemHash, void* item, 121 HashCompareFunc cmpFunc, bool doAdd); 122 123 /* 124 * Remove an item from the hash table, given its "data" pointer. Does not 125 * invoke the "free" function; just detaches it from the table. 126 */ 127 bool mzHashTableRemove(HashTable* pHashTable, unsigned int hash, void* item); 128 129 /* 130 * Execute "func" on every entry in the hash table. 131 * 132 * If "func" returns a nonzero value, terminate early and return the value. 133 */ 134 int mzHashForeach(HashTable* pHashTable, HashForeachFunc func, void* arg); 135 136 /* 137 * An alternative to mzHashForeach(), using an iterator. 138 * 139 * Use like this: 140 * HashIter iter; 141 * for (mzHashIterBegin(hashTable, &iter); !mzHashIterDone(&iter); 142 * mzHashIterNext(&iter)) 143 * { 144 * MyData* data = (MyData*)mzHashIterData(&iter); 145 * } 146 */ 147 typedef struct HashIter { 148 void* data; 149 HashTable* pHashTable; 150 int idx; 151 } HashIter; 152 INLINE void mzHashIterNext(HashIter* pIter) { 153 int i = pIter->idx +1; 154 int lim = pIter->pHashTable->tableSize; 155 for ( ; i < lim; i++) { 156 void* data = pIter->pHashTable->pEntries[i].data; 157 if (data != NULL && data != HASH_TOMBSTONE) 158 break; 159 } 160 pIter->idx = i; 161 } 162 INLINE void mzHashIterBegin(HashTable* pHashTable, HashIter* pIter) { 163 pIter->pHashTable = pHashTable; 164 pIter->idx = -1; 165 mzHashIterNext(pIter); 166 } 167 INLINE bool mzHashIterDone(HashIter* pIter) { 168 return (pIter->idx >= pIter->pHashTable->tableSize); 169 } 170 INLINE void* mzHashIterData(HashIter* pIter) { 171 assert(pIter->idx >= 0 && pIter->idx < pIter->pHashTable->tableSize); 172 return pIter->pHashTable->pEntries[pIter->idx].data; 173 } 174 175 176 /* 177 * Evaluate hash table performance by examining the number of times we 178 * have to probe for an entry. 179 * 180 * The caller should lock the table beforehand. 181 */ 182 typedef unsigned int (*HashCalcFunc)(const void* item); 183 void mzHashTableProbeCount(HashTable* pHashTable, HashCalcFunc calcFunc, 184 HashCompareFunc cmpFunc); 185 186 #endif /*_MINZIP_HASH*/ 187
