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