blob: e83eac41422fe229ac7d67fb10764e6476675e17 [file] [log] [blame]
The Android Open Source Projectc24a8e62009-03-03 19:28:42 -08001/*
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
Tao Baoba9a42a2015-06-23 23:23:33 -070018#ifdef __cplusplus
19extern "C" {
20#endif
21
The Android Open Source Projectc24a8e62009-03-03 19:28:42 -080022/* compute the hash of an item with a specific type */
23typedef 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 */
30typedef 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 */
36typedef void (*HashFreeFunc)(void* ptr);
37
38/*
39 * Used by mzHashForeach().
40 */
41typedef 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 */
53typedef 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 */
65typedef 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 */
81HashTable* 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 */
89size_t mzHashSize(size_t size);
90
91/*
92 * Clear out a hash table, freeing the contents of any used entries.
93 */
94void mzHashTableClear(HashTable* pHashTable);
95
96/*
97 * Free a hash table.
98 */
99void mzHashTableFree(HashTable* pHashTable);
100
101/*
102 * Get #of entries in hash table.
103 */
104INLINE int mzHashTableNumEntries(HashTable* pHashTable) {
105 return pHashTable->numEntries;
106}
107
108/*
109 * Get total size of hash table (for memory usage calculations).
110 */
111INLINE 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 */
124void* 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 */
131bool 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 */
138int 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 */
151typedef struct HashIter {
152 void* data;
153 HashTable* pHashTable;
154 int idx;
155} HashIter;
156INLINE 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}
166INLINE void mzHashIterBegin(HashTable* pHashTable, HashIter* pIter) {
167 pIter->pHashTable = pHashTable;
168 pIter->idx = -1;
169 mzHashIterNext(pIter);
170}
171INLINE bool mzHashIterDone(HashIter* pIter) {
172 return (pIter->idx >= pIter->pHashTable->tableSize);
173}
174INLINE 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 */
186typedef unsigned int (*HashCalcFunc)(const void* item);
187void mzHashTableProbeCount(HashTable* pHashTable, HashCalcFunc calcFunc,
188 HashCompareFunc cmpFunc);
189
Tao Baoba9a42a2015-06-23 23:23:33 -0700190#ifdef __cplusplus
191}
192#endif
193
The Android Open Source Projectc24a8e62009-03-03 19:28:42 -0800194#endif /*_MINZIP_HASH*/