blob: 8194537f34bf5af5c3f2dae918b492e90449248e [file] [log] [blame]
Dees Troyb7ae0982013-09-10 20:47:35 +00001/*
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 */
19typedef 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 */
26typedef 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 */
32typedef void (*HashFreeFunc)(void* ptr);
33
34/*
35 * Used by mzHashForeach().
36 */
37typedef 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 */
49typedef 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 */
61typedef 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 */
77HashTable* 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 */
85size_t mzHashSize(size_t size);
86
87/*
88 * Clear out a hash table, freeing the contents of any used entries.
89 */
90void mzHashTableClear(HashTable* pHashTable);
91
92/*
93 * Free a hash table.
94 */
95void mzHashTableFree(HashTable* pHashTable);
96
97/*
98 * Get #of entries in hash table.
99 */
100INLINE int mzHashTableNumEntries(HashTable* pHashTable) {
101 return pHashTable->numEntries;
102}
103
104/*
105 * Get total size of hash table (for memory usage calculations).
106 */
107INLINE 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 */
120void* 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 */
127bool 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 */
134int 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 */
147typedef struct HashIter {
148 void* data;
149 HashTable* pHashTable;
150 int idx;
151} HashIter;
152INLINE 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}
162INLINE void mzHashIterBegin(HashTable* pHashTable, HashIter* pIter) {
163 pIter->pHashTable = pHashTable;
164 pIter->idx = -1;
165 mzHashIterNext(pIter);
166}
167INLINE bool mzHashIterDone(HashIter* pIter) {
168 return (pIter->idx >= pIter->pHashTable->tableSize);
169}
170INLINE 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 */
182typedef unsigned int (*HashCalcFunc)(const void* item);
183void mzHashTableProbeCount(HashTable* pHashTable, HashCalcFunc calcFunc,
184 HashCompareFunc cmpFunc);
185
186#endif /*_MINZIP_HASH*/