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