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
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
|
/*************************************************************************/ /*!
@Title Self scaling hash tables
@Copyright Copyright (c) Imagination Technologies Ltd. All Rights Reserved
@Description Implements simple self scaling hash tables.
@License Dual MIT/GPLv2
The contents of this file are subject to the MIT license as set out below.
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
Alternatively, the contents of this file may be used under the terms of
the GNU General Public License Version 2 ("GPL") in which case the provisions
of GPL are applicable instead of those above.
If you wish to allow use of your version of this file only under the terms of
GPL, and not to allow others to use your version of this file under the terms
of the MIT license, indicate your decision by deleting the provisions above
and replace them with the notice and other provisions required by GPL as set
out in the file called "GPL-COPYING" included in this distribution. If you do
not delete the provisions above, a recipient may use your version of this file
under the terms of either the MIT license or GPL.
This License is also included in this distribution in the file called
"MIT-COPYING".
EXCEPT AS OTHERWISE STATED IN A NEGOTIATED AGREEMENT: (A) THE SOFTWARE IS
PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
PURPOSE AND NONINFRINGEMENT; AND (B) IN NO EVENT SHALL THE AUTHORS OR
COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/ /**************************************************************************/
#ifndef _HASH_H_
#define _HASH_H_
#include "img_types.h"
#include "osfunc.h"
#if defined (__cplusplus)
extern "C" {
#endif
/*
* Keys passed to the comparsion function are only guaranteed to
* be aligned on an IMG_UINTPTR_T boundary.
*/
typedef IMG_UINT32 HASH_FUNC(IMG_SIZE_T uKeySize, IMG_VOID *pKey, IMG_UINT32 uHashTabLen);
typedef IMG_BOOL HASH_KEY_COMP(IMG_SIZE_T uKeySize, IMG_VOID *pKey1, IMG_VOID *pKey2);
typedef struct _HASH_TABLE_ HASH_TABLE;
typedef PVRSRV_ERROR (*HASH_pfnCallback) (
IMG_UINTPTR_T k,
IMG_UINTPTR_T v
);
/*!
******************************************************************************
@Function HASH_Func_Default
@Description Hash function intended for hashing keys composed of
IMG_UINTPTR_T arrays.
@Input uKeySize - the size of the hash key, in bytes.
@Input pKey - a pointer to the key to hash.
@Input uHashTabLen - the length of the hash table.
@Return The hash value.
******************************************************************************/
IMG_UINT32 HASH_Func_Default (IMG_SIZE_T uKeySize, IMG_VOID *pKey, IMG_UINT32 uHashTabLen);
/*!
******************************************************************************
@Function HASH_Key_Comp_Default
@Description Compares keys composed of IMG_UINTPTR_T arrays.
@Input uKeySize - the size of the hash key, in bytes.
@Input pKey1 - pointer to first hash key to compare.
@Input pKey2 - pointer to second hash key to compare.
@Return IMG_TRUE - the keys match.
IMG_FALSE - the keys don't match.
******************************************************************************/
IMG_BOOL HASH_Key_Comp_Default (IMG_SIZE_T uKeySize, IMG_VOID *pKey1, IMG_VOID *pKey2);
/*!
******************************************************************************
@Function HASH_Create_Extended
@Description Create a self scaling hash table, using the supplied
key size, and the supllied hash and key comparsion
functions.
@Input uInitialLen - initial and minimum length of the
hash table, where the length refers to the number
of entries in the hash table, not its size in
bytes.
@Input uKeySize - the size of the key, in bytes.
@Input pfnHashFunc - pointer to hash function.
@Input pfnKeyComp - pointer to key comparsion function.
@Return IMG_NULL or hash table handle.
******************************************************************************/
HASH_TABLE * HASH_Create_Extended (IMG_UINT32 uInitialLen, IMG_SIZE_T uKeySize, HASH_FUNC *pfnHashFunc, HASH_KEY_COMP *pfnKeyComp);
/*!
******************************************************************************
@Function HASH_Create
@Description Create a self scaling hash table with a key
consisting of a single IMG_UINTPTR_T, and using
the default hash and key comparison functions.
@Input uInitialLen - initial and minimum length of the
hash table, where the length refers to the
number of entries in the hash table, not its size
in bytes.
@Return IMG_NULL or hash table handle.
******************************************************************************/
HASH_TABLE * HASH_Create (IMG_UINT32 uInitialLen);
/*!
******************************************************************************
@Function HASH_Delete
@Description Delete a hash table created by HASH_Create_Extended or
HASH_Create. All entries in the table must have been
removed before calling this function.
@Input pHash - hash table
@Return None
******************************************************************************/
IMG_VOID HASH_Delete (HASH_TABLE *pHash);
/*!
******************************************************************************
@Function HASH_Insert_Extended
@Description Insert a key value pair into a hash table created
with HASH_Create_Extended.
@Input pHash - the hash table.
@Input pKey - pointer to the key.
@Input v - the value associated with the key.
@Return IMG_TRUE - success.
IMG_FALSE - failure.
******************************************************************************/
IMG_BOOL HASH_Insert_Extended (HASH_TABLE *pHash, IMG_VOID *pKey, IMG_UINTPTR_T v);
/*!
******************************************************************************
@Function HASH_Insert
@Description Insert a key value pair into a hash table created with
HASH_Create.
@Input pHash - the hash table.
@Input k - the key value.
@Input v - the value associated with the key.
@Return IMG_TRUE - success.
IMG_FALSE - failure.
******************************************************************************/
IMG_BOOL HASH_Insert (HASH_TABLE *pHash, IMG_UINTPTR_T k, IMG_UINTPTR_T v);
/*!
******************************************************************************
@Function HASH_Remove_Extended
@Description Remove a key from a hash table created with
HASH_Create_Extended.
@Input pHash - the hash table.
@Input pKey - pointer to key.
@Return 0 if the key is missing, or the value associated
with the key.
******************************************************************************/
IMG_UINTPTR_T HASH_Remove_Extended(HASH_TABLE *pHash, IMG_VOID *pKey);
/*!
******************************************************************************
@Function HASH_Remove
@Description Remove a key value pair from a hash table created
with HASH_Create.
@Input pHash - the hash table
@Input k - the key
@Return 0 if the key is missing, or the value associated
with the key.
******************************************************************************/
IMG_UINTPTR_T HASH_Remove (HASH_TABLE *pHash, IMG_UINTPTR_T k);
/*!
******************************************************************************
@Function HASH_Retrieve_Extended
@Description Retrieve a value from a hash table created with
HASH_Create_Extended.
@Input pHash - the hash table.
@Input pKey - pointer to the key.
@Return 0 if the key is missing, or the value associated with
the key.
******************************************************************************/
IMG_UINTPTR_T HASH_Retrieve_Extended (HASH_TABLE *pHash, IMG_VOID *pKey);
/*!
******************************************************************************
@Function HASH_Retrieve
@Description Retrieve a value from a hash table created with
HASH_Create.
@Input pHash - the hash table
@Input k - the key
@Return 0 if the key is missing, or the value associated with
the key.
******************************************************************************/
IMG_UINTPTR_T HASH_Retrieve (HASH_TABLE *pHash, IMG_UINTPTR_T k);
/*!
******************************************************************************
@Function HASH_Interate
@Description Iterate over every entry in the hash table
@Input pHash - the old hash table
@Input HASH_pfnCallback - the size of the old hash table
@Return Callback error if any, otherwise PVRSRV_OK
******************************************************************************/
PVRSRV_ERROR HASH_Iterate(HASH_TABLE *pHash, HASH_pfnCallback pfnCallback);
#ifdef HASH_TRACE
/*!
******************************************************************************
@Function HASH_Dump
@Description Dump out some information about a hash table.
@Input pHash - the hash table
@Return None
******************************************************************************/
IMG_VOID HASH_Dump (HASH_TABLE *pHash);
#endif
#if defined (__cplusplus)
}
#endif
#endif /* _HASH_H_ */
/******************************************************************************
End of file (hash.h)
******************************************************************************/
|