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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
|
/*
* Copyright (C) 2008 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/*
* General purpose hash table, used for finding classes, methods, etc.
*
* When the number of elements reaches a certain percentage of the table's
* capacity, the table will be resized.
*/
#ifndef _DALVIK_HASH
#define _DALVIK_HASH
/* compute the hash of an item with a specific type */
typedef u4 (*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 dvmHashForeach().
*/
typedef int (*HashForeachFunc)(void* data, void* arg);
/*
* Used by dvmHashForeachRemove().
*/
typedef int (*HashForeachRemoveFunc)(void* data);
/*
* 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 {
u4 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;
pthread_mutex_t lock;
} 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 dvmHashSize() in.)
*
* Returns "false" if unable to allocate the table.
*/
HashTable* dvmHashTableCreate(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 dvmHashTableCreate() to ensure that you can add
* all elements without needing to reallocate the table.
*/
size_t dvmHashSize(size_t size);
/*
* Clear out a hash table, freeing the contents of any used entries.
*/
void dvmHashTableClear(HashTable* pHashTable);
/*
* Free a hash table. Performs a "clear" first.
*/
void dvmHashTableFree(HashTable* pHashTable);
/*
* Exclusive access. Important when adding items to a table, or when
* doing any operations on a table that could be added to by another thread.
*/
INLINE void dvmHashTableLock(HashTable* pHashTable) {
dvmLockMutex(&pHashTable->lock);
}
INLINE void dvmHashTableUnlock(HashTable* pHashTable) {
dvmUnlockMutex(&pHashTable->lock);
}
/*
* Get #of entries in hash table.
*/
INLINE int dvmHashTableNumEntries(HashTable* pHashTable) {
return pHashTable->numEntries;
}
/*
* Get total size of hash table (for memory usage calculations).
*/
INLINE int dvmHashTableMemUsage(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. Don't
* forget to lock the table before calling this.
*/
void* dvmHashTableLookup(HashTable* pHashTable, u4 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 dvmHashTableRemove(HashTable* pHashTable, u4 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 dvmHashForeach(HashTable* pHashTable, HashForeachFunc func, void* arg);
/*
* Execute "func" on every entry in the hash table.
*
* If "func" returns 1 detach the entry from the hash table. Does not invoke
* the "free" function.
*
* Returning values other than 0 or 1 from "func" will abort the routine.
*/
int dvmHashForeachRemove(HashTable* pHashTable, HashForeachRemoveFunc func);
/*
* An alternative to dvmHashForeach(), using an iterator.
*
* Use like this:
* HashIter iter;
* for (dvmHashIterBegin(hashTable, &iter); !dvmHashIterDone(&iter);
* dvmHashIterNext(&iter))
* {
* MyData* data = (MyData*)dvmHashIterData(&iter);
* }
*/
typedef struct HashIter {
void* data;
HashTable* pHashTable;
int idx;
} HashIter;
INLINE void dvmHashIterNext(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 dvmHashIterBegin(HashTable* pHashTable, HashIter* pIter) {
pIter->pHashTable = pHashTable;
pIter->idx = -1;
dvmHashIterNext(pIter);
}
INLINE bool dvmHashIterDone(HashIter* pIter) {
return (pIter->idx >= pIter->pHashTable->tableSize);
}
INLINE void* dvmHashIterData(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 u4 (*HashCalcFunc)(const void* item);
void dvmHashTableProbeCount(HashTable* pHashTable, HashCalcFunc calcFunc,
HashCompareFunc cmpFunc);
#endif /*_DALVIK_HASH*/
|
