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