diff options
Diffstat (limited to 'jacinto6/sgx_src/eurasia_km/services4/srvkm/common/hash.c')
-rw-r--r-- | jacinto6/sgx_src/eurasia_km/services4/srvkm/common/hash.c | 738 |
1 files changed, 738 insertions, 0 deletions
diff --git a/jacinto6/sgx_src/eurasia_km/services4/srvkm/common/hash.c b/jacinto6/sgx_src/eurasia_km/services4/srvkm/common/hash.c new file mode 100644 index 0000000..1569425 --- /dev/null +++ b/jacinto6/sgx_src/eurasia_km/services4/srvkm/common/hash.c | |||
@@ -0,0 +1,738 @@ | |||
1 | /*************************************************************************/ /*! | ||
2 | @Title Self scaling hash tables. | ||
3 | @Copyright Copyright (c) Imagination Technologies Ltd. All Rights Reserved | ||
4 | @Description | ||
5 | Implements simple self scaling hash tables. Hash collisions are | ||
6 | handled by chaining entries together. Hash tables are increased in | ||
7 | size when they become more than (50%?) full and decreased in size | ||
8 | when less than (25%?) full. Hash tables are never decreased below | ||
9 | their initial size. | ||
10 | @License Dual MIT/GPLv2 | ||
11 | |||
12 | The contents of this file are subject to the MIT license as set out below. | ||
13 | |||
14 | Permission is hereby granted, free of charge, to any person obtaining a copy | ||
15 | of this software and associated documentation files (the "Software"), to deal | ||
16 | in the Software without restriction, including without limitation the rights | ||
17 | to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | ||
18 | copies of the Software, and to permit persons to whom the Software is | ||
19 | furnished to do so, subject to the following conditions: | ||
20 | |||
21 | The above copyright notice and this permission notice shall be included in | ||
22 | all copies or substantial portions of the Software. | ||
23 | |||
24 | Alternatively, the contents of this file may be used under the terms of | ||
25 | the GNU General Public License Version 2 ("GPL") in which case the provisions | ||
26 | of GPL are applicable instead of those above. | ||
27 | |||
28 | If you wish to allow use of your version of this file only under the terms of | ||
29 | GPL, and not to allow others to use your version of this file under the terms | ||
30 | of the MIT license, indicate your decision by deleting the provisions above | ||
31 | and replace them with the notice and other provisions required by GPL as set | ||
32 | out in the file called "GPL-COPYING" included in this distribution. If you do | ||
33 | not delete the provisions above, a recipient may use your version of this file | ||
34 | under the terms of either the MIT license or GPL. | ||
35 | |||
36 | This License is also included in this distribution in the file called | ||
37 | "MIT-COPYING". | ||
38 | |||
39 | EXCEPT AS OTHERWISE STATED IN A NEGOTIATED AGREEMENT: (A) THE SOFTWARE IS | ||
40 | PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING | ||
41 | BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR | ||
42 | PURPOSE AND NONINFRINGEMENT; AND (B) IN NO EVENT SHALL THE AUTHORS OR | ||
43 | COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER | ||
44 | IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN | ||
45 | CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. | ||
46 | */ /**************************************************************************/ | ||
47 | |||
48 | #include "pvr_debug.h" | ||
49 | #include "img_defs.h" | ||
50 | #include "services.h" | ||
51 | #include "servicesint.h" | ||
52 | #include "hash.h" | ||
53 | #include "osfunc.h" | ||
54 | |||
55 | #define PRIVATE_MAX(a,b) ((a)>(b)?(a):(b)) | ||
56 | |||
57 | #define KEY_TO_INDEX(pHash, key, uSize) \ | ||
58 | ((pHash)->pfnHashFunc((pHash)->uKeySize, (key), (uSize)) % (uSize)) | ||
59 | |||
60 | #define KEY_COMPARE(pHash, pKey1, pKey2) \ | ||
61 | ((pHash)->pfnKeyComp((pHash)->uKeySize, (pKey1), (pKey2))) | ||
62 | |||
63 | /* Each entry in a hash table is placed into a bucket */ | ||
64 | struct _BUCKET_ | ||
65 | { | ||
66 | /* the next bucket on the same chain */ | ||
67 | struct _BUCKET_ *pNext; | ||
68 | |||
69 | /* entry value */ | ||
70 | IMG_UINTPTR_T v; | ||
71 | |||
72 | /* entry key */ | ||
73 | IMG_UINTPTR_T k[]; /* PRQA S 0642 */ /* override dynamic array declaration warning */ | ||
74 | }; | ||
75 | typedef struct _BUCKET_ BUCKET; | ||
76 | |||
77 | struct _HASH_TABLE_ | ||
78 | { | ||
79 | /* the hash table array */ | ||
80 | BUCKET **ppBucketTable; | ||
81 | |||
82 | /* current size of the hash table */ | ||
83 | IMG_UINT32 uSize; | ||
84 | |||
85 | /* number of entries currently in the hash table */ | ||
86 | IMG_UINT32 uCount; | ||
87 | |||
88 | /* the minimum size that the hash table should be re-sized to */ | ||
89 | IMG_UINT32 uMinimumSize; | ||
90 | |||
91 | /* size of key in bytes */ | ||
92 | IMG_UINT32 uKeySize; | ||
93 | |||
94 | /* hash function */ | ||
95 | HASH_FUNC *pfnHashFunc; | ||
96 | |||
97 | /* key comparison function */ | ||
98 | HASH_KEY_COMP *pfnKeyComp; | ||
99 | }; | ||
100 | |||
101 | /*! | ||
102 | ****************************************************************************** | ||
103 | @Function HASH_Func_Default | ||
104 | |||
105 | @Description Hash function intended for hashing keys composed of | ||
106 | IMG_UINTPTR_T arrays. | ||
107 | |||
108 | @Input uKeySize - the size of the hash key, in bytes. | ||
109 | @Input pKey - a pointer to the key to hash. | ||
110 | @Input uHashTabLen - the length of the hash table. | ||
111 | |||
112 | @Return the hash value. | ||
113 | ******************************************************************************/ | ||
114 | IMG_UINT32 | ||
115 | HASH_Func_Default (IMG_SIZE_T uKeySize, IMG_VOID *pKey, IMG_UINT32 uHashTabLen) | ||
116 | { | ||
117 | IMG_UINTPTR_T *p = (IMG_UINTPTR_T *)pKey; | ||
118 | IMG_UINT32 uKeyLen = (IMG_UINT32)(uKeySize / sizeof(IMG_UINTPTR_T)); | ||
119 | IMG_UINT32 ui; | ||
120 | IMG_UINT32 uHashKey = 0; | ||
121 | |||
122 | PVR_UNREFERENCED_PARAMETER(uHashTabLen); | ||
123 | |||
124 | PVR_ASSERT((uKeySize % sizeof(IMG_UINTPTR_T)) == 0); | ||
125 | |||
126 | for (ui = 0; ui < uKeyLen; ui++) | ||
127 | { | ||
128 | IMG_UINT32 uHashPart = (IMG_UINT32)*p++; | ||
129 | |||
130 | uHashPart += (uHashPart << 12); | ||
131 | uHashPart ^= (uHashPart >> 22); | ||
132 | uHashPart += (uHashPart << 4); | ||
133 | uHashPart ^= (uHashPart >> 9); | ||
134 | uHashPart += (uHashPart << 10); | ||
135 | uHashPart ^= (uHashPart >> 2); | ||
136 | uHashPart += (uHashPart << 7); | ||
137 | uHashPart ^= (uHashPart >> 12); | ||
138 | |||
139 | uHashKey += uHashPart; | ||
140 | } | ||
141 | |||
142 | return uHashKey; | ||
143 | } | ||
144 | |||
145 | /*! | ||
146 | ****************************************************************************** | ||
147 | @Function HASH_Key_Comp_Default | ||
148 | |||
149 | @Description Compares keys composed of IMG_UINTPTR_T arrays. | ||
150 | |||
151 | @Input uKeySize - the size of the hash key, in bytes. | ||
152 | @Input pKey1 - pointer to first hash key to compare. | ||
153 | @Input pKey2 - pointer to second hash key to compare. | ||
154 | @Return IMG_TRUE - the keys match. | ||
155 | IMG_FALSE - the keys don't match. | ||
156 | ******************************************************************************/ | ||
157 | IMG_BOOL | ||
158 | HASH_Key_Comp_Default (IMG_SIZE_T uKeySize, IMG_VOID *pKey1, IMG_VOID *pKey2) | ||
159 | { | ||
160 | IMG_UINTPTR_T *p1 = (IMG_UINTPTR_T *)pKey1; | ||
161 | IMG_UINTPTR_T *p2 = (IMG_UINTPTR_T *)pKey2; | ||
162 | IMG_UINT32 uKeyLen = (IMG_UINT32)(uKeySize / sizeof(IMG_UINTPTR_T)); | ||
163 | IMG_UINT32 ui; | ||
164 | |||
165 | PVR_ASSERT((uKeySize % sizeof(IMG_UINTPTR_T)) == 0); | ||
166 | |||
167 | for (ui = 0; ui < uKeyLen; ui++) | ||
168 | { | ||
169 | if (*p1++ != *p2++) | ||
170 | return IMG_FALSE; | ||
171 | } | ||
172 | |||
173 | return IMG_TRUE; | ||
174 | } | ||
175 | |||
176 | /*! | ||
177 | ****************************************************************************** | ||
178 | @Function _ChainInsert | ||
179 | |||
180 | @Description Insert a bucket into the appropriate hash table chain. | ||
181 | |||
182 | @Input pBucket - the bucket | ||
183 | @Input ppBucketTable - the hash table | ||
184 | @Input uSize - the size of the hash table | ||
185 | |||
186 | @Return PVRSRV_ERROR | ||
187 | ******************************************************************************/ | ||
188 | static PVRSRV_ERROR | ||
189 | _ChainInsert (HASH_TABLE *pHash, BUCKET *pBucket, BUCKET **ppBucketTable, IMG_UINT32 uSize) | ||
190 | { | ||
191 | IMG_UINT32 uIndex; | ||
192 | |||
193 | PVR_ASSERT (pBucket != IMG_NULL); | ||
194 | PVR_ASSERT (ppBucketTable != IMG_NULL); | ||
195 | PVR_ASSERT (uSize != 0); | ||
196 | |||
197 | if ((pBucket == IMG_NULL) || (ppBucketTable == IMG_NULL) || (uSize == 0)) | ||
198 | { | ||
199 | PVR_DPF((PVR_DBG_ERROR, "_ChainInsert: invalid parameter")); | ||
200 | return PVRSRV_ERROR_INVALID_PARAMS; | ||
201 | } | ||
202 | |||
203 | uIndex = KEY_TO_INDEX(pHash, pBucket->k, uSize); /* PRQA S 0432,0541 */ /* ignore dynamic array warning */ | ||
204 | pBucket->pNext = ppBucketTable[uIndex]; | ||
205 | ppBucketTable[uIndex] = pBucket; | ||
206 | |||
207 | return PVRSRV_OK; | ||
208 | } | ||
209 | |||
210 | /*! | ||
211 | ****************************************************************************** | ||
212 | @Function _Rehash | ||
213 | |||
214 | @Description Iterate over every entry in an old hash table and | ||
215 | rehash into the new table. | ||
216 | |||
217 | @Input ppOldTable - the old hash table | ||
218 | @Input uOldSize - the size of the old hash table | ||
219 | @Input ppNewTable - the new hash table | ||
220 | @Input uNewSize - the size of the new hash table | ||
221 | |||
222 | @Return None | ||
223 | ******************************************************************************/ | ||
224 | static PVRSRV_ERROR | ||
225 | _Rehash (HASH_TABLE *pHash, | ||
226 | BUCKET **ppOldTable, IMG_UINT32 uOldSize, | ||
227 | BUCKET **ppNewTable, IMG_UINT32 uNewSize) | ||
228 | { | ||
229 | IMG_UINT32 uIndex; | ||
230 | for (uIndex=0; uIndex< uOldSize; uIndex++) | ||
231 | { | ||
232 | BUCKET *pBucket; | ||
233 | pBucket = ppOldTable[uIndex]; | ||
234 | while (pBucket != IMG_NULL) | ||
235 | { | ||
236 | PVRSRV_ERROR eError; | ||
237 | BUCKET *pNextBucket = pBucket->pNext; | ||
238 | eError = _ChainInsert (pHash, pBucket, ppNewTable, uNewSize); | ||
239 | if (eError != PVRSRV_OK) | ||
240 | { | ||
241 | PVR_DPF((PVR_DBG_ERROR, "_Rehash: call to _ChainInsert failed")); | ||
242 | return eError; | ||
243 | } | ||
244 | pBucket = pNextBucket; | ||
245 | } | ||
246 | } | ||
247 | return PVRSRV_OK; | ||
248 | } | ||
249 | |||
250 | /*! | ||
251 | ****************************************************************************** | ||
252 | @Function _Resize | ||
253 | |||
254 | @Description Attempt to resize a hash table, failure to allocate a | ||
255 | new larger hash table is not considered a hard failure. | ||
256 | We simply continue and allow the table to fill up, the | ||
257 | effect is to allow hash chains to become longer. | ||
258 | |||
259 | @Input pHash - Hash table to resize. | ||
260 | @Input uNewSize - Required table size. | ||
261 | @Return IMG_TRUE Success | ||
262 | IMG_FALSE Failed | ||
263 | ******************************************************************************/ | ||
264 | static IMG_BOOL | ||
265 | _Resize (HASH_TABLE *pHash, IMG_UINT32 uNewSize) | ||
266 | { | ||
267 | if (uNewSize != pHash->uSize) | ||
268 | { | ||
269 | BUCKET **ppNewTable; | ||
270 | IMG_UINT32 uIndex; | ||
271 | |||
272 | PVR_DPF ((PVR_DBG_MESSAGE, | ||
273 | "HASH_Resize: oldsize=0x%x newsize=0x%x count=0x%x", | ||
274 | pHash->uSize, uNewSize, pHash->uCount)); | ||
275 | |||
276 | OSAllocMem(PVRSRV_PAGEABLE_SELECT, | ||
277 | sizeof (BUCKET *) * uNewSize, | ||
278 | (IMG_PVOID*)&ppNewTable, IMG_NULL, | ||
279 | "Hash Table Buckets"); | ||
280 | if (ppNewTable == IMG_NULL) | ||
281 | return IMG_FALSE; | ||
282 | |||
283 | for (uIndex=0; uIndex<uNewSize; uIndex++) | ||
284 | ppNewTable[uIndex] = IMG_NULL; | ||
285 | |||
286 | if (_Rehash (pHash, pHash->ppBucketTable, pHash->uSize, ppNewTable, uNewSize) != PVRSRV_OK) | ||
287 | { | ||
288 | return IMG_FALSE; | ||
289 | } | ||
290 | |||
291 | OSFreeMem (PVRSRV_PAGEABLE_SELECT, sizeof(BUCKET *)*pHash->uSize, pHash->ppBucketTable, IMG_NULL); | ||
292 | /*not nulling pointer, being reassigned just below*/ | ||
293 | pHash->ppBucketTable = ppNewTable; | ||
294 | pHash->uSize = uNewSize; | ||
295 | } | ||
296 | return IMG_TRUE; | ||
297 | } | ||
298 | |||
299 | |||
300 | /*! | ||
301 | ****************************************************************************** | ||
302 | @Function HASH_Create_Extended | ||
303 | |||
304 | @Description Create a self scaling hash table, using the supplied | ||
305 | key size, and the supplied hash and key comparsion | ||
306 | functions. | ||
307 | |||
308 | @Input uInitialLen - initial and minimum length of the | ||
309 | hash table, where the length refers to the number | ||
310 | of entries in the hash table, not its size in | ||
311 | bytes. | ||
312 | @Input uKeySize - the size of the key, in bytes. | ||
313 | @Input pfnHashFunc - pointer to hash function. | ||
314 | @Input pfnKeyComp - pointer to key comparsion function. | ||
315 | @Return IMG_NULL or hash table handle. | ||
316 | ******************************************************************************/ | ||
317 | HASH_TABLE * HASH_Create_Extended (IMG_UINT32 uInitialLen, IMG_SIZE_T uKeySize, HASH_FUNC *pfnHashFunc, HASH_KEY_COMP *pfnKeyComp) | ||
318 | { | ||
319 | HASH_TABLE *pHash; | ||
320 | IMG_UINT32 uIndex; | ||
321 | |||
322 | PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Create_Extended: InitialSize=0x%x", uInitialLen)); | ||
323 | |||
324 | if(OSAllocMem(PVRSRV_PAGEABLE_SELECT, | ||
325 | sizeof(HASH_TABLE), | ||
326 | (IMG_VOID **)&pHash, IMG_NULL, | ||
327 | "Hash Table") != PVRSRV_OK) | ||
328 | { | ||
329 | return IMG_NULL; | ||
330 | } | ||
331 | |||
332 | pHash->uCount = 0; | ||
333 | pHash->uSize = uInitialLen; | ||
334 | pHash->uMinimumSize = uInitialLen; | ||
335 | pHash->uKeySize = (IMG_UINT32)uKeySize; | ||
336 | pHash->pfnHashFunc = pfnHashFunc; | ||
337 | pHash->pfnKeyComp = pfnKeyComp; | ||
338 | |||
339 | OSAllocMem(PVRSRV_PAGEABLE_SELECT, | ||
340 | sizeof (BUCKET *) * pHash->uSize, | ||
341 | (IMG_PVOID*)&pHash->ppBucketTable, IMG_NULL, | ||
342 | "Hash Table Buckets"); | ||
343 | |||
344 | if (pHash->ppBucketTable == IMG_NULL) | ||
345 | { | ||
346 | OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(HASH_TABLE), pHash, IMG_NULL); | ||
347 | /*not nulling pointer, out of scope*/ | ||
348 | return IMG_NULL; | ||
349 | } | ||
350 | |||
351 | for (uIndex=0; uIndex<pHash->uSize; uIndex++) | ||
352 | pHash->ppBucketTable[uIndex] = IMG_NULL; | ||
353 | return pHash; | ||
354 | } | ||
355 | |||
356 | /*! | ||
357 | ****************************************************************************** | ||
358 | @Function HASH_Create | ||
359 | |||
360 | @Description Create a self scaling hash table with a key | ||
361 | consisting of a single IMG_UINTPTR_T, and using | ||
362 | the default hash and key comparison functions. | ||
363 | |||
364 | @Input uInitialLen - initial and minimum length of the | ||
365 | hash table, where the length refers to the | ||
366 | number of entries in the hash table, not its size | ||
367 | in bytes. | ||
368 | @Return IMG_NULL or hash table handle. | ||
369 | ******************************************************************************/ | ||
370 | HASH_TABLE * HASH_Create (IMG_UINT32 uInitialLen) | ||
371 | { | ||
372 | return HASH_Create_Extended(uInitialLen, sizeof(IMG_UINTPTR_T), | ||
373 | &HASH_Func_Default, &HASH_Key_Comp_Default); | ||
374 | } | ||
375 | |||
376 | /*! | ||
377 | ****************************************************************************** | ||
378 | @Function HASH_Delete | ||
379 | |||
380 | @Description Delete a hash table created by HASH_Create_Extended or | ||
381 | HASH_Create. All entries in the table must have been | ||
382 | removed before calling this function. | ||
383 | |||
384 | @Input pHash - hash table | ||
385 | |||
386 | @Return None | ||
387 | ******************************************************************************/ | ||
388 | IMG_VOID | ||
389 | HASH_Delete (HASH_TABLE *pHash) | ||
390 | { | ||
391 | if (pHash != IMG_NULL) | ||
392 | { | ||
393 | PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Delete")); | ||
394 | |||
395 | PVR_ASSERT (pHash->uCount==0); | ||
396 | if(pHash->uCount != 0) | ||
397 | { | ||
398 | PVR_DPF ((PVR_DBG_ERROR, "HASH_Delete: leak detected in hash table!")); | ||
399 | PVR_DPF ((PVR_DBG_ERROR, "Likely Cause: client drivers not freeing alocations before destroying devmemcontext")); | ||
400 | } | ||
401 | OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(BUCKET *)*pHash->uSize, pHash->ppBucketTable, IMG_NULL); | ||
402 | pHash->ppBucketTable = IMG_NULL; | ||
403 | OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(HASH_TABLE), pHash, IMG_NULL); | ||
404 | /*not nulling pointer, copy on stack*/ | ||
405 | } | ||
406 | } | ||
407 | |||
408 | /*! | ||
409 | ****************************************************************************** | ||
410 | @Function HASH_Insert_Extended | ||
411 | |||
412 | @Description Insert a key value pair into a hash table created | ||
413 | with HASH_Create_Extended. | ||
414 | |||
415 | @Input pHash - the hash table. | ||
416 | @Input pKey - pointer to the key. | ||
417 | @Input v - the value associated with the key. | ||
418 | |||
419 | @Return IMG_TRUE - success | ||
420 | IMG_FALSE - failure | ||
421 | ******************************************************************************/ | ||
422 | IMG_BOOL | ||
423 | HASH_Insert_Extended (HASH_TABLE *pHash, IMG_VOID *pKey, IMG_UINTPTR_T v) | ||
424 | { | ||
425 | BUCKET *pBucket; | ||
426 | |||
427 | PVR_DPF ((PVR_DBG_MESSAGE, | ||
428 | "HASH_Insert_Extended: Hash=0x%08x, pKey=0x%08x, v=0x%x", | ||
429 | (IMG_UINTPTR_T)pHash, (IMG_UINTPTR_T)pKey, v)); | ||
430 | |||
431 | PVR_ASSERT (pHash != IMG_NULL); | ||
432 | |||
433 | if (pHash == IMG_NULL) | ||
434 | { | ||
435 | PVR_DPF((PVR_DBG_ERROR, "HASH_Insert_Extended: invalid parameter")); | ||
436 | return IMG_FALSE; | ||
437 | } | ||
438 | |||
439 | if(OSAllocMem(PVRSRV_PAGEABLE_SELECT, | ||
440 | sizeof(BUCKET) + pHash->uKeySize, | ||
441 | (IMG_VOID **)&pBucket, IMG_NULL, | ||
442 | "Hash Table entry") != PVRSRV_OK) | ||
443 | { | ||
444 | return IMG_FALSE; | ||
445 | } | ||
446 | |||
447 | pBucket->v = v; | ||
448 | /* PRQA S 0432,0541 1 */ /* ignore warning about dynamic array k (linux)*/ | ||
449 | OSMemCopy(pBucket->k, pKey, pHash->uKeySize); | ||
450 | if (_ChainInsert (pHash, pBucket, pHash->ppBucketTable, pHash->uSize) != PVRSRV_OK) | ||
451 | { | ||
452 | OSFreeMem(PVRSRV_PAGEABLE_SELECT, | ||
453 | sizeof(BUCKET) + pHash->uKeySize, | ||
454 | pBucket, IMG_NULL); | ||
455 | return IMG_FALSE; | ||
456 | } | ||
457 | |||
458 | pHash->uCount++; | ||
459 | |||
460 | /* check if we need to think about re-balencing */ | ||
461 | if (pHash->uCount << 1 > pHash->uSize) | ||
462 | { | ||
463 | /* Ignore the return code from _Resize because the hash table is | ||
464 | still in a valid state and although not ideally sized, it is still | ||
465 | functional */ | ||
466 | _Resize (pHash, pHash->uSize << 1); | ||
467 | } | ||
468 | |||
469 | |||
470 | return IMG_TRUE; | ||
471 | } | ||
472 | |||
473 | /*! | ||
474 | ****************************************************************************** | ||
475 | @Function HASH_Insert | ||
476 | |||
477 | @Description Insert a key value pair into a hash table created with | ||
478 | HASH_Create. | ||
479 | |||
480 | @Input pHash - the hash table. | ||
481 | @Input k - the key value. | ||
482 | @Input v - the value associated with the key. | ||
483 | |||
484 | @Return IMG_TRUE - success. | ||
485 | IMG_FALSE - failure. | ||
486 | ******************************************************************************/ | ||
487 | IMG_BOOL | ||
488 | HASH_Insert (HASH_TABLE *pHash, IMG_UINTPTR_T k, IMG_UINTPTR_T v) | ||
489 | { | ||
490 | PVR_DPF ((PVR_DBG_MESSAGE, | ||
491 | "HASH_Insert: Hash=0x%x, k=0x%x, v=0x%x", | ||
492 | (IMG_UINTPTR_T)pHash, k, v)); | ||
493 | |||
494 | return HASH_Insert_Extended(pHash, &k, v); | ||
495 | } | ||
496 | |||
497 | /*! | ||
498 | ****************************************************************************** | ||
499 | @Function HASH_Remove_Extended | ||
500 | |||
501 | @Description Remove a key from a hash table created with | ||
502 | HASH_Create_Extended. | ||
503 | |||
504 | @Input pHash - the hash table. | ||
505 | @Input pKey - pointer to key. | ||
506 | |||
507 | @Return 0 if the key is missing, or the value associated | ||
508 | with the key. | ||
509 | ******************************************************************************/ | ||
510 | IMG_UINTPTR_T | ||
511 | HASH_Remove_Extended(HASH_TABLE *pHash, IMG_VOID *pKey) | ||
512 | { | ||
513 | BUCKET **ppBucket; | ||
514 | IMG_UINT32 uIndex; | ||
515 | |||
516 | PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Remove_Extended: Hash=0x%x, pKey=0x%x", | ||
517 | (IMG_UINTPTR_T)pHash, (IMG_UINTPTR_T)pKey)); | ||
518 | |||
519 | PVR_ASSERT (pHash != IMG_NULL); | ||
520 | |||
521 | if (pHash == IMG_NULL) | ||
522 | { | ||
523 | PVR_DPF((PVR_DBG_ERROR, "HASH_Remove_Extended: Null hash table")); | ||
524 | return 0; | ||
525 | } | ||
526 | |||
527 | uIndex = KEY_TO_INDEX(pHash, pKey, pHash->uSize); | ||
528 | |||
529 | for (ppBucket = &(pHash->ppBucketTable[uIndex]); *ppBucket != IMG_NULL; ppBucket = &((*ppBucket)->pNext)) | ||
530 | { | ||
531 | /* PRQA S 0432,0541 1 */ /* ignore warning about dynamic array k */ | ||
532 | if (KEY_COMPARE(pHash, (*ppBucket)->k, pKey)) | ||
533 | { | ||
534 | BUCKET *pBucket = *ppBucket; | ||
535 | IMG_UINTPTR_T v = pBucket->v; | ||
536 | (*ppBucket) = pBucket->pNext; | ||
537 | |||
538 | OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(BUCKET) + pHash->uKeySize, pBucket, IMG_NULL); | ||
539 | /*not nulling original pointer, already overwritten*/ | ||
540 | |||
541 | pHash->uCount--; | ||
542 | |||
543 | /* check if we need to think about re-balencing */ | ||
544 | if (pHash->uSize > (pHash->uCount << 2) && | ||
545 | pHash->uSize > pHash->uMinimumSize) | ||
546 | { | ||
547 | /* Ignore the return code from _Resize because the | ||
548 | hash table is still in a valid state and although | ||
549 | not ideally sized, it is still functional */ | ||
550 | _Resize (pHash, | ||
551 | PRIVATE_MAX (pHash->uSize >> 1, | ||
552 | pHash->uMinimumSize)); | ||
553 | } | ||
554 | |||
555 | PVR_DPF ((PVR_DBG_MESSAGE, | ||
556 | "HASH_Remove_Extended: Hash=0x%x, pKey=0x%x = 0x%x", | ||
557 | (IMG_UINTPTR_T)pHash, (IMG_UINTPTR_T)pKey, v)); | ||
558 | return v; | ||
559 | } | ||
560 | } | ||
561 | PVR_DPF ((PVR_DBG_MESSAGE, | ||
562 | "HASH_Remove_Extended: Hash=0x%x, pKey=0x%x = 0x0 !!!!", | ||
563 | (IMG_UINTPTR_T)pHash, (IMG_UINTPTR_T)pKey)); | ||
564 | return 0; | ||
565 | } | ||
566 | |||
567 | /*! | ||
568 | ****************************************************************************** | ||
569 | @Function HASH_Remove | ||
570 | |||
571 | @Description Remove a key value pair from a hash table created | ||
572 | with HASH_Create. | ||
573 | |||
574 | @Input pHash - the hash table | ||
575 | @Input k - the key | ||
576 | |||
577 | @Return 0 if the key is missing, or the value associated | ||
578 | with the key. | ||
579 | ******************************************************************************/ | ||
580 | IMG_UINTPTR_T | ||
581 | HASH_Remove (HASH_TABLE *pHash, IMG_UINTPTR_T k) | ||
582 | { | ||
583 | PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Remove: Hash=0x%x, k=0x%x", | ||
584 | (IMG_UINTPTR_T)pHash, k)); | ||
585 | |||
586 | return HASH_Remove_Extended(pHash, &k); | ||
587 | } | ||
588 | |||
589 | /*! | ||
590 | ****************************************************************************** | ||
591 | @Function HASH_Retrieve_Extended | ||
592 | |||
593 | @Description Retrieve a value from a hash table created with | ||
594 | HASH_Create_Extended. | ||
595 | |||
596 | @Input pHash - the hash table. | ||
597 | @Input pKey - pointer to the key. | ||
598 | |||
599 | @Return 0 if the key is missing, or the value associated with | ||
600 | the key. | ||
601 | ******************************************************************************/ | ||
602 | IMG_UINTPTR_T | ||
603 | HASH_Retrieve_Extended (HASH_TABLE *pHash, IMG_VOID *pKey) | ||
604 | { | ||
605 | BUCKET **ppBucket; | ||
606 | IMG_UINT32 uIndex; | ||
607 | |||
608 | PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Retrieve_Extended: Hash=0x%x, pKey=0x%x", | ||
609 | (IMG_UINTPTR_T)pHash, (IMG_UINTPTR_T)pKey)); | ||
610 | |||
611 | PVR_ASSERT (pHash != IMG_NULL); | ||
612 | |||
613 | if (pHash == IMG_NULL) | ||
614 | { | ||
615 | PVR_DPF((PVR_DBG_ERROR, "HASH_Retrieve_Extended: Null hash table")); | ||
616 | return 0; | ||
617 | } | ||
618 | |||
619 | uIndex = KEY_TO_INDEX(pHash, pKey, pHash->uSize); | ||
620 | |||
621 | for (ppBucket = &(pHash->ppBucketTable[uIndex]); *ppBucket != IMG_NULL; ppBucket = &((*ppBucket)->pNext)) | ||
622 | { | ||
623 | /* PRQA S 0432,0541 1 */ /* ignore warning about dynamic array k */ | ||
624 | if (KEY_COMPARE(pHash, (*ppBucket)->k, pKey)) | ||
625 | { | ||
626 | BUCKET *pBucket = *ppBucket; | ||
627 | IMG_UINTPTR_T v = pBucket->v; | ||
628 | |||
629 | PVR_DPF ((PVR_DBG_MESSAGE, | ||
630 | "HASH_Retrieve: Hash=0x%x, pKey=0x%x = 0x%x", | ||
631 | (IMG_UINTPTR_T)pHash, (IMG_UINTPTR_T)pKey, v)); | ||
632 | return v; | ||
633 | } | ||
634 | } | ||
635 | PVR_DPF ((PVR_DBG_MESSAGE, | ||
636 | "HASH_Retrieve: Hash=0x%x, pKey=0x%x = 0x0 !!!!", | ||
637 | (IMG_UINTPTR_T)pHash, (IMG_UINTPTR_T)pKey)); | ||
638 | return 0; | ||
639 | } | ||
640 | |||
641 | /*! | ||
642 | ****************************************************************************** | ||
643 | @Function HASH_Retrieve | ||
644 | |||
645 | @Description Retrieve a value from a hash table created with | ||
646 | HASH_Create. | ||
647 | |||
648 | @Input pHash - the hash table | ||
649 | @Input k - the key | ||
650 | @Return 0 if the key is missing, or the value associated with | ||
651 | the key. | ||
652 | ******************************************************************************/ | ||
653 | IMG_UINTPTR_T | ||
654 | HASH_Retrieve (HASH_TABLE *pHash, IMG_UINTPTR_T k) | ||
655 | { | ||
656 | PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Retrieve: Hash=0x%x, k=0x%x", | ||
657 | (IMG_UINTPTR_T)pHash, k)); | ||
658 | return HASH_Retrieve_Extended(pHash, &k); | ||
659 | } | ||
660 | |||
661 | /*! | ||
662 | ****************************************************************************** | ||
663 | @Function HASH_Iterate | ||
664 | |||
665 | @Description Iterate over every entry in the hash table | ||
666 | |||
667 | @Input pHash - the old hash table | ||
668 | @Input pfnCallback - the size of the old hash table | ||
669 | |||
670 | @Return Callback error if any, otherwise PVRSRV_OK | ||
671 | ******************************************************************************/ | ||
672 | PVRSRV_ERROR | ||
673 | HASH_Iterate(HASH_TABLE *pHash, HASH_pfnCallback pfnCallback) | ||
674 | { | ||
675 | IMG_UINT32 uIndex; | ||
676 | for (uIndex=0; uIndex < pHash->uSize; uIndex++) | ||
677 | { | ||
678 | BUCKET *pBucket; | ||
679 | pBucket = pHash->ppBucketTable[uIndex]; | ||
680 | while (pBucket != IMG_NULL) | ||
681 | { | ||
682 | PVRSRV_ERROR eError; | ||
683 | BUCKET *pNextBucket = pBucket->pNext; | ||
684 | |||
685 | eError = pfnCallback((IMG_UINTPTR_T) ((IMG_VOID *) *(pBucket->k)), (IMG_UINTPTR_T) pBucket->v); | ||
686 | |||
687 | /* The callback might want us to break out early */ | ||
688 | if (eError != PVRSRV_OK) | ||
689 | return eError; | ||
690 | |||
691 | pBucket = pNextBucket; | ||
692 | } | ||
693 | } | ||
694 | return PVRSRV_OK; | ||
695 | } | ||
696 | |||
697 | #ifdef HASH_TRACE | ||
698 | /*! | ||
699 | ****************************************************************************** | ||
700 | @Function HASH_Dump | ||
701 | |||
702 | @Description To dump the contents of a hash table in human readable | ||
703 | form. | ||
704 | |||
705 | @Input pHash - the hash table | ||
706 | |||
707 | @Return None | ||
708 | ******************************************************************************/ | ||
709 | IMG_VOID | ||
710 | HASH_Dump (HASH_TABLE *pHash) | ||
711 | { | ||
712 | IMG_UINT32 uIndex; | ||
713 | IMG_UINT32 uMaxLength=0; | ||
714 | IMG_UINT32 uEmptyCount=0; | ||
715 | |||
716 | PVR_ASSERT (pHash != IMG_NULL); | ||
717 | for (uIndex=0; uIndex<pHash->uSize; uIndex++) | ||
718 | { | ||
719 | BUCKET *pBucket; | ||
720 | IMG_UINT32 uLength = 0; | ||
721 | if (pHash->ppBucketTable[uIndex] == IMG_NULL) | ||
722 | { | ||
723 | uEmptyCount++; | ||
724 | } | ||
725 | for (pBucket=pHash->ppBucketTable[uIndex]; | ||
726 | pBucket != IMG_NULL; | ||
727 | pBucket = pBucket->pNext) | ||
728 | { | ||
729 | uLength++; | ||
730 | } | ||
731 | uMaxLength = PRIVATE_MAX (uMaxLength, uLength); | ||
732 | } | ||
733 | |||
734 | PVR_TRACE(("hash table: uMinimumSize=%d size=%d count=%d", | ||
735 | pHash->uMinimumSize, pHash->uSize, pHash->uCount)); | ||
736 | PVR_TRACE((" empty=%d max=%d", uEmptyCount, uMaxLength)); | ||
737 | } | ||
738 | #endif | ||