1 /*************************************************************************/ /*!
3 @Title Self scaling hash tables
4 @Copyright Copyright (c) Imagination Technologies Ltd. All Rights Reserved
5 @Description Implements simple self scaling hash tables.
6 @License Dual MIT/GPLv2
8 The contents of this file are subject to the MIT license as set out below.
10 Permission is hereby granted, free of charge, to any person obtaining a copy
11 of this software and associated documentation files (the "Software"), to deal
12 in the Software without restriction, including without limitation the rights
13 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
14 copies of the Software, and to permit persons to whom the Software is
15 furnished to do so, subject to the following conditions:
17 The above copyright notice and this permission notice shall be included in
18 all copies or substantial portions of the Software.
20 Alternatively, the contents of this file may be used under the terms of
21 the GNU General Public License Version 2 ("GPL") in which case the provisions
22 of GPL are applicable instead of those above.
24 If you wish to allow use of your version of this file only under the terms of
25 GPL, and not to allow others to use your version of this file under the terms
26 of the MIT license, indicate your decision by deleting the provisions above
27 and replace them with the notice and other provisions required by GPL as set
28 out in the file called "GPL-COPYING" included in this distribution. If you do
29 not delete the provisions above, a recipient may use your version of this file
30 under the terms of either the MIT license or GPL.
32 This License is also included in this distribution in the file called
35 EXCEPT AS OTHERWISE STATED IN A NEGOTIATED AGREEMENT: (A) THE SOFTWARE IS
36 PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING
37 BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
38 PURPOSE AND NONINFRINGEMENT; AND (B) IN NO EVENT SHALL THE AUTHORS OR
39 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
40 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
41 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
42 */ /**************************************************************************/
48 #include "img_types.h"
50 /* services/client/include/ or services/server/include/ */
53 #if defined (__cplusplus)
58 * Keys passed to the comparsion function are only guaranteed to
59 * be aligned on an IMG_UINTPTR_T boundary.
61 typedef IMG_UINT32 HASH_FUNC(IMG_SIZE_T uKeySize, IMG_VOID *pKey, IMG_UINT32 uHashTabLen);
62 typedef IMG_BOOL HASH_KEY_COMP(IMG_SIZE_T uKeySize, IMG_VOID *pKey1, IMG_VOID *pKey2);
64 typedef struct _HASH_TABLE_ HASH_TABLE;
66 typedef PVRSRV_ERROR (*HASH_pfnCallback) (
71 /*************************************************************************/ /*!
72 @Function HASH_Func_Default
73 @Description Hash function intended for hashing keys composed of
75 @Input uKeySize The size of the hash key, in bytes.
76 @Input pKey A pointer to the key to hash.
77 @Input uHashTabLen The length of the hash table.
78 @Return The hash value.
79 */ /**************************************************************************/
80 IMG_UINT32 HASH_Func_Default (IMG_SIZE_T uKeySize, IMG_VOID *pKey, IMG_UINT32 uHashTabLen);
82 /*************************************************************************/ /*!
83 @Function HASH_Key_Comp_Default
84 @Description Compares keys composed of IMG_UINTPTR_T arrays.
85 @Input uKeySize The size of the hash key, in bytes.
86 @Input pKey1 Pointer to first hash key to compare.
87 @Input pKey2 Pointer to second hash key to compare.
88 @Return IMG_TRUE - the keys match.
89 IMG_FALSE - the keys don't match.
90 */ /**************************************************************************/
91 IMG_BOOL HASH_Key_Comp_Default (IMG_SIZE_T uKeySize, IMG_VOID *pKey1, IMG_VOID *pKey2);
93 /*************************************************************************/ /*!
94 @Function HASH_Create_Extended
95 @Description Create a self scaling hash table, using the supplied
96 key size, and the supllied hash and key comparsion
98 @Input uInitialLen Initial and minimum length of the
99 hash table, where the length refers to the number
100 of entries in the hash table, not its size in
102 @Input uKeySize The size of the key, in bytes.
103 @Input pfnHashFunc Pointer to hash function.
104 @Input pfnKeyComp Pointer to key comparsion function.
105 @Return IMG_NULL or hash table handle.
106 */ /**************************************************************************/
107 HASH_TABLE * HASH_Create_Extended (IMG_UINT32 uInitialLen, IMG_SIZE_T uKeySize, HASH_FUNC *pfnHashFunc, HASH_KEY_COMP *pfnKeyComp);
109 /*************************************************************************/ /*!
110 @Function HASH_Create
111 @Description Create a self scaling hash table with a key
112 consisting of a single IMG_UINTPTR_T, and using
113 the default hash and key comparison functions.
114 @Input uInitialLen Initial and minimum length of the
115 hash table, where the length refers to the
116 number of entries in the hash table, not its size
118 @Return IMG_NULL or hash table handle.
119 */ /**************************************************************************/
120 HASH_TABLE * HASH_Create (IMG_UINT32 uInitialLen);
122 /*************************************************************************/ /*!
123 @Function HASH_Delete
124 @Description Delete a hash table created by HASH_Create_Extended or
125 HASH_Create. All entries in the table must have been
126 removed before calling this function.
127 @Input pHash Hash table
128 */ /**************************************************************************/
129 IMG_VOID HASH_Delete (HASH_TABLE *pHash);
131 /*************************************************************************/ /*!
132 @Function HASH_Insert_Extended
133 @Description Insert a key value pair into a hash table created
134 with HASH_Create_Extended.
135 @Input pHash The hash table.
136 @Input pKey Pointer to the key.
137 @Input v The value associated with the key.
138 @Return IMG_TRUE - success
140 */ /**************************************************************************/
141 IMG_BOOL HASH_Insert_Extended (HASH_TABLE *pHash, IMG_VOID *pKey, IMG_UINTPTR_T v);
143 /*************************************************************************/ /*!
144 @Function HASH_Insert
146 @Description Insert a key value pair into a hash table created with
148 @Input pHash The hash table.
149 @Input k The key value.
150 @Input v The value associated with the key.
151 @Return IMG_TRUE - success.
153 */ /**************************************************************************/
154 IMG_BOOL HASH_Insert (HASH_TABLE *pHash, IMG_UINTPTR_T k, IMG_UINTPTR_T v);
156 /*************************************************************************/ /*!
157 @Function HASH_Remove_Extended
158 @Description Remove a key from a hash table created with
159 HASH_Create_Extended.
160 @Input pHash The hash table.
161 @Input pKey Pointer to key.
162 @Return 0 if the key is missing, or the value associated
164 */ /**************************************************************************/
165 IMG_UINTPTR_T HASH_Remove_Extended(HASH_TABLE *pHash, IMG_VOID *pKey);
167 /*************************************************************************/ /*!
168 @Function HASH_Remove
169 @Description Remove a key value pair from a hash table created
171 @Input pHash The hash table.
172 @Input pKey Pointer to key.
173 @Return 0 if the key is missing, or the value associated
175 */ /**************************************************************************/
176 IMG_UINTPTR_T HASH_Remove (HASH_TABLE *pHash, IMG_UINTPTR_T k);
178 /*************************************************************************/ /*!
179 @Function HASH_Retrieve_Extended
180 @Description Retrieve a value from a hash table created with
181 HASH_Create_Extended.
182 @Input pHash The hash table.
183 @Input pKey Pointer to key.
184 @Return 0 if the key is missing, or the value associated with
186 */ /**************************************************************************/
187 IMG_UINTPTR_T HASH_Retrieve_Extended (HASH_TABLE *pHash, IMG_VOID *pKey);
189 /*************************************************************************/ /*!
190 @Function HASH_Retrieve
191 @Description Retrieve a value from a hash table created with
193 @Input pHash The hash table.
194 @Input pKey Pointer to key.
195 @Return 0 if the key is missing, or the value associated with
197 */ /**************************************************************************/
198 IMG_UINTPTR_T HASH_Retrieve (HASH_TABLE *pHash, IMG_UINTPTR_T k);
200 /*************************************************************************/ /*!
201 @Function HASH_Iterate
202 @Description Iterate over every entry in the hash table
203 @Input pHash Hash table to iterate
204 @Input pfnCallback Callback to call with the key and data for
205 each entry in the hash table
206 @Return Callback error if any, otherwise PVRSRV_OK
207 */ /**************************************************************************/
208 PVRSRV_ERROR HASH_Iterate(HASH_TABLE *pHash, HASH_pfnCallback pfnCallback);
211 /*************************************************************************/ /*!
213 @Description Dump out some information about a hash table.
214 @Input pHash The hash table.
215 */ /**************************************************************************/
216 IMG_VOID HASH_Dump (HASH_TABLE *pHash);
219 #if defined (__cplusplus)
223 #endif /* _HASH_H_ */
225 /******************************************************************************
227 ******************************************************************************/