summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
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.c738
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
12The contents of this file are subject to the MIT license as set out below.
13
14Permission is hereby granted, free of charge, to any person obtaining a copy
15of this software and associated documentation files (the "Software"), to deal
16in the Software without restriction, including without limitation the rights
17to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
18copies of the Software, and to permit persons to whom the Software is
19furnished to do so, subject to the following conditions:
20
21The above copyright notice and this permission notice shall be included in
22all copies or substantial portions of the Software.
23
24Alternatively, the contents of this file may be used under the terms of
25the GNU General Public License Version 2 ("GPL") in which case the provisions
26of GPL are applicable instead of those above.
27
28If you wish to allow use of your version of this file only under the terms of
29GPL, and not to allow others to use your version of this file under the terms
30of the MIT license, indicate your decision by deleting the provisions above
31and replace them with the notice and other provisions required by GPL as set
32out in the file called "GPL-COPYING" included in this distribution. If you do
33not delete the provisions above, a recipient may use your version of this file
34under the terms of either the MIT license or GPL.
35
36This License is also included in this distribution in the file called
37"MIT-COPYING".
38
39EXCEPT AS OTHERWISE STATED IN A NEGOTIATED AGREEMENT: (A) THE SOFTWARE IS
40PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING
41BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
42PURPOSE AND NONINFRINGEMENT; AND (B) IN NO EVENT SHALL THE AUTHORS OR
43COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
44IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
45CONNECTION 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 */
64struct _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};
75typedef struct _BUCKET_ BUCKET;
76
77struct _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******************************************************************************/
114IMG_UINT32
115HASH_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******************************************************************************/
157IMG_BOOL
158HASH_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******************************************************************************/
188static 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******************************************************************************/
224static 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******************************************************************************/
264static 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******************************************************************************/
317HASH_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******************************************************************************/
370HASH_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******************************************************************************/
388IMG_VOID
389HASH_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******************************************************************************/
422IMG_BOOL
423HASH_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******************************************************************************/
487IMG_BOOL
488HASH_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******************************************************************************/
510IMG_UINTPTR_T
511HASH_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******************************************************************************/
580IMG_UINTPTR_T
581HASH_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******************************************************************************/
602IMG_UINTPTR_T
603HASH_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******************************************************************************/
653IMG_UINTPTR_T
654HASH_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******************************************************************************/
672PVRSRV_ERROR
673HASH_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******************************************************************************/
709IMG_VOID
710HASH_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