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
12 The contents of this file are subject to the MIT license as set out below.
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:
21 The above copyright notice and this permission notice shall be included in
22 all copies or substantial portions of the Software.
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.
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.
36 This License is also included in this distribution in the file called
37 "MIT-COPYING".
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 */ /**************************************************************************/
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"
55 #define PRIVATE_MAX(a,b) ((a)>(b)?(a):(b))
57 #define KEY_TO_INDEX(pHash, key, uSize) \
58 ((pHash)->pfnHashFunc((pHash)->uKeySize, (key), (uSize)) % (uSize))
60 #define KEY_COMPARE(pHash, pKey1, pKey2) \
61 ((pHash)->pfnKeyComp((pHash)->uKeySize, (pKey1), (pKey2)))
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;
69 /* entry value */
70 IMG_UINTPTR_T v;
72 /* entry key */
73 IMG_UINTPTR_T k[]; /* PRQA S 0642 */ /* override dynamic array declaration warning */
74 };
75 typedef struct _BUCKET_ BUCKET;
77 struct _HASH_TABLE_
78 {
79 /* the hash table array */
80 BUCKET **ppBucketTable;
82 /* current size of the hash table */
83 IMG_UINT32 uSize;
85 /* number of entries currently in the hash table */
86 IMG_UINT32 uCount;
88 /* the minimum size that the hash table should be re-sized to */
89 IMG_UINT32 uMinimumSize;
91 /* size of key in bytes */
92 IMG_UINT32 uKeySize;
94 /* hash function */
95 HASH_FUNC *pfnHashFunc;
97 /* key comparison function */
98 HASH_KEY_COMP *pfnKeyComp;
99 };
101 /*!
102 ******************************************************************************
103 @Function HASH_Func_Default
105 @Description Hash function intended for hashing keys composed of
106 IMG_UINTPTR_T arrays.
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.
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;
122 PVR_UNREFERENCED_PARAMETER(uHashTabLen);
124 PVR_ASSERT((uKeySize % sizeof(IMG_UINTPTR_T)) == 0);
126 for (ui = 0; ui < uKeyLen; ui++)
127 {
128 IMG_UINT32 uHashPart = (IMG_UINT32)*p++;
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);
139 uHashKey += uHashPart;
140 }
142 return uHashKey;
143 }
145 /*!
146 ******************************************************************************
147 @Function HASH_Key_Comp_Default
149 @Description Compares keys composed of IMG_UINTPTR_T arrays.
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;
165 PVR_ASSERT((uKeySize % sizeof(IMG_UINTPTR_T)) == 0);
167 for (ui = 0; ui < uKeyLen; ui++)
168 {
169 if (*p1++ != *p2++)
170 return IMG_FALSE;
171 }
173 return IMG_TRUE;
174 }
176 /*!
177 ******************************************************************************
178 @Function _ChainInsert
180 @Description Insert a bucket into the appropriate hash table chain.
182 @Input pBucket - the bucket
183 @Input ppBucketTable - the hash table
184 @Input uSize - the size of the hash table
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;
193 PVR_ASSERT (pBucket != IMG_NULL);
194 PVR_ASSERT (ppBucketTable != IMG_NULL);
195 PVR_ASSERT (uSize != 0);
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 }
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;
207 return PVRSRV_OK;
208 }
210 /*!
211 ******************************************************************************
212 @Function _Rehash
214 @Description Iterate over every entry in an old hash table and
215 rehash into the new table.
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
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 }
250 /*!
251 ******************************************************************************
252 @Function _Resize
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.
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;
272 PVR_DPF ((PVR_DBG_MESSAGE,
273 "HASH_Resize: oldsize=0x%x newsize=0x%x count=0x%x",
274 pHash->uSize, uNewSize, pHash->uCount));
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;
283 for (uIndex=0; uIndex<uNewSize; uIndex++)
284 ppNewTable[uIndex] = IMG_NULL;
286 if (_Rehash (pHash, pHash->ppBucketTable, pHash->uSize, ppNewTable, uNewSize) != PVRSRV_OK)
287 {
288 OSFreeMem (PVRSRV_PAGEABLE_SELECT, sizeof(BUCKET *) * uNewSize, ppNewTable, IMG_NULL);
289 return IMG_FALSE;
290 }
292 OSFreeMem (PVRSRV_PAGEABLE_SELECT, sizeof(BUCKET *)*pHash->uSize, pHash->ppBucketTable, IMG_NULL);
293 /*not nulling pointer, being reassigned just below*/
294 pHash->ppBucketTable = ppNewTable;
295 pHash->uSize = uNewSize;
296 }
297 return IMG_TRUE;
298 }
301 /*!
302 ******************************************************************************
303 @Function HASH_Create_Extended
305 @Description Create a self scaling hash table, using the supplied
306 key size, and the supplied hash and key comparsion
307 functions.
309 @Input uInitialLen - initial and minimum length of the
310 hash table, where the length refers to the number
311 of entries in the hash table, not its size in
312 bytes.
313 @Input uKeySize - the size of the key, in bytes.
314 @Input pfnHashFunc - pointer to hash function.
315 @Input pfnKeyComp - pointer to key comparsion function.
316 @Return IMG_NULL or hash table handle.
317 ******************************************************************************/
318 HASH_TABLE * HASH_Create_Extended (IMG_UINT32 uInitialLen, IMG_SIZE_T uKeySize, HASH_FUNC *pfnHashFunc, HASH_KEY_COMP *pfnKeyComp)
319 {
320 HASH_TABLE *pHash;
321 IMG_UINT32 uIndex;
323 PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Create_Extended: InitialSize=0x%x", uInitialLen));
325 if(OSAllocMem(PVRSRV_PAGEABLE_SELECT,
326 sizeof(HASH_TABLE),
327 (IMG_VOID **)&pHash, IMG_NULL,
328 "Hash Table") != PVRSRV_OK)
329 {
330 return IMG_NULL;
331 }
333 pHash->uCount = 0;
334 pHash->uSize = uInitialLen;
335 pHash->uMinimumSize = uInitialLen;
336 pHash->uKeySize = (IMG_UINT32)uKeySize;
337 pHash->pfnHashFunc = pfnHashFunc;
338 pHash->pfnKeyComp = pfnKeyComp;
340 OSAllocMem(PVRSRV_PAGEABLE_SELECT,
341 sizeof (BUCKET *) * pHash->uSize,
342 (IMG_PVOID*)&pHash->ppBucketTable, IMG_NULL,
343 "Hash Table Buckets");
345 if (pHash->ppBucketTable == IMG_NULL)
346 {
347 OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(HASH_TABLE), pHash, IMG_NULL);
348 /*not nulling pointer, out of scope*/
349 return IMG_NULL;
350 }
352 for (uIndex=0; uIndex<pHash->uSize; uIndex++)
353 pHash->ppBucketTable[uIndex] = IMG_NULL;
354 return pHash;
355 }
357 /*!
358 ******************************************************************************
359 @Function HASH_Create
361 @Description Create a self scaling hash table with a key
362 consisting of a single IMG_UINTPTR_T, and using
363 the default hash and key comparison functions.
365 @Input uInitialLen - initial and minimum length of the
366 hash table, where the length refers to the
367 number of entries in the hash table, not its size
368 in bytes.
369 @Return IMG_NULL or hash table handle.
370 ******************************************************************************/
371 HASH_TABLE * HASH_Create (IMG_UINT32 uInitialLen)
372 {
373 return HASH_Create_Extended(uInitialLen, sizeof(IMG_UINTPTR_T),
374 &HASH_Func_Default, &HASH_Key_Comp_Default);
375 }
377 /*!
378 ******************************************************************************
379 @Function HASH_Delete
381 @Description Delete a hash table created by HASH_Create_Extended or
382 HASH_Create. All entries in the table must have been
383 removed before calling this function.
385 @Input pHash - hash table
387 @Return None
388 ******************************************************************************/
389 IMG_VOID
390 HASH_Delete (HASH_TABLE *pHash)
391 {
392 if (pHash != IMG_NULL)
393 {
394 PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Delete"));
396 PVR_ASSERT (pHash->uCount==0);
397 if(pHash->uCount != 0)
398 {
399 PVR_DPF ((PVR_DBG_ERROR, "HASH_Delete: leak detected in hash table!"));
400 PVR_DPF ((PVR_DBG_ERROR, "Likely Cause: client drivers not freeing allocations before destroying devmemcontext"));
401 }
402 OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(BUCKET *)*pHash->uSize, pHash->ppBucketTable, IMG_NULL);
403 pHash->ppBucketTable = IMG_NULL;
404 OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(HASH_TABLE), pHash, IMG_NULL);
405 /*not nulling pointer, copy on stack*/
406 }
407 }
409 /*!
410 ******************************************************************************
411 @Function HASH_Insert_Extended
413 @Description Insert a key value pair into a hash table created
414 with HASH_Create_Extended.
416 @Input pHash - the hash table.
417 @Input pKey - pointer to the key.
418 @Input v - the value associated with the key.
420 @Return IMG_TRUE - success
421 IMG_FALSE - failure
422 ******************************************************************************/
423 IMG_BOOL
424 HASH_Insert_Extended (HASH_TABLE *pHash, IMG_VOID *pKey, IMG_UINTPTR_T v)
425 {
426 BUCKET *pBucket;
428 PVR_DPF ((PVR_DBG_MESSAGE,
429 "HASH_Insert_Extended: Hash=0x%p, pKey=0x%p, v=0x" UINTPTR_FMT,
430 pHash, pKey, v));
432 PVR_ASSERT (pHash != IMG_NULL);
434 if (pHash == IMG_NULL)
435 {
436 PVR_DPF((PVR_DBG_ERROR, "HASH_Insert_Extended: invalid parameter"));
437 return IMG_FALSE;
438 }
440 if(OSAllocMem(PVRSRV_PAGEABLE_SELECT,
441 sizeof(BUCKET) + pHash->uKeySize,
442 (IMG_VOID **)&pBucket, IMG_NULL,
443 "Hash Table entry") != PVRSRV_OK)
444 {
445 return IMG_FALSE;
446 }
448 pBucket->v = v;
449 /* PRQA S 0432,0541 1 */ /* ignore warning about dynamic array k (linux)*/
450 OSMemCopy(pBucket->k, pKey, pHash->uKeySize);
451 if (_ChainInsert (pHash, pBucket, pHash->ppBucketTable, pHash->uSize) != PVRSRV_OK)
452 {
453 OSFreeMem(PVRSRV_PAGEABLE_SELECT,
454 sizeof(BUCKET) + pHash->uKeySize,
455 pBucket, IMG_NULL);
456 return IMG_FALSE;
457 }
459 pHash->uCount++;
461 /* check if we need to think about re-balencing */
462 if (pHash->uCount << 1 > pHash->uSize)
463 {
464 /* Ignore the return code from _Resize because the hash table is
465 still in a valid state and although not ideally sized, it is still
466 functional */
467 _Resize (pHash, pHash->uSize << 1);
468 }
471 return IMG_TRUE;
472 }
474 /*!
475 ******************************************************************************
476 @Function HASH_Insert
478 @Description Insert a key value pair into a hash table created with
479 HASH_Create.
481 @Input pHash - the hash table.
482 @Input k - the key value.
483 @Input v - the value associated with the key.
485 @Return IMG_TRUE - success.
486 IMG_FALSE - failure.
487 ******************************************************************************/
488 IMG_BOOL
489 HASH_Insert (HASH_TABLE *pHash, IMG_UINTPTR_T k, IMG_UINTPTR_T v)
490 {
491 PVR_DPF ((PVR_DBG_MESSAGE,
492 "HASH_Insert: Hash=0x%p, k=0x" UINTPTR_FMT ", v=0x" UINTPTR_FMT,
493 pHash, k, v));
495 return HASH_Insert_Extended(pHash, &k, v);
496 }
498 /*!
499 ******************************************************************************
500 @Function HASH_Remove_Extended
502 @Description Remove a key from a hash table created with
503 HASH_Create_Extended.
505 @Input pHash - the hash table.
506 @Input pKey - pointer to key.
508 @Return 0 if the key is missing, or the value associated
509 with the key.
510 ******************************************************************************/
511 IMG_UINTPTR_T
512 HASH_Remove_Extended(HASH_TABLE *pHash, IMG_VOID *pKey)
513 {
514 BUCKET **ppBucket;
515 IMG_UINT32 uIndex;
517 PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Remove_Extended: Hash=0x%p, pKey=0x%p",
518 pHash, pKey));
520 PVR_ASSERT (pHash != IMG_NULL);
522 if (pHash == IMG_NULL)
523 {
524 PVR_DPF((PVR_DBG_ERROR, "HASH_Remove_Extended: Null hash table"));
525 return 0;
526 }
528 uIndex = KEY_TO_INDEX(pHash, pKey, pHash->uSize);
530 for (ppBucket = &(pHash->ppBucketTable[uIndex]); *ppBucket != IMG_NULL; ppBucket = &((*ppBucket)->pNext))
531 {
532 /* PRQA S 0432,0541 1 */ /* ignore warning about dynamic array k */
533 if (KEY_COMPARE(pHash, (*ppBucket)->k, pKey))
534 {
535 BUCKET *pBucket = *ppBucket;
536 IMG_UINTPTR_T v = pBucket->v;
537 (*ppBucket) = pBucket->pNext;
539 OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(BUCKET) + pHash->uKeySize, pBucket, IMG_NULL);
540 /*not nulling original pointer, already overwritten*/
542 pHash->uCount--;
544 /* check if we need to think about re-balencing */
545 if (pHash->uSize > (pHash->uCount << 2) &&
546 pHash->uSize > pHash->uMinimumSize)
547 {
548 /* Ignore the return code from _Resize because the
549 hash table is still in a valid state and although
550 not ideally sized, it is still functional */
551 _Resize (pHash,
552 PRIVATE_MAX (pHash->uSize >> 1,
553 pHash->uMinimumSize));
554 }
556 PVR_DPF ((PVR_DBG_MESSAGE,
557 "HASH_Remove_Extended: Hash=0x%p, pKey=0x%p = 0x" UINTPTR_FMT,
558 pHash, pKey, v));
559 return v;
560 }
561 }
562 PVR_DPF ((PVR_DBG_MESSAGE,
563 "HASH_Remove_Extended: Hash=0x%p, pKey=0x%p = 0x0 !!!!",
564 pHash, pKey));
565 return 0;
566 }
568 /*!
569 ******************************************************************************
570 @Function HASH_Remove
572 @Description Remove a key value pair from a hash table created
573 with HASH_Create.
575 @Input pHash - the hash table
576 @Input k - the key
578 @Return 0 if the key is missing, or the value associated
579 with the key.
580 ******************************************************************************/
581 IMG_UINTPTR_T
582 HASH_Remove (HASH_TABLE *pHash, IMG_UINTPTR_T k)
583 {
584 PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Remove: Hash=0x%p, k=0x" UINTPTR_FMT,
585 pHash, k));
587 return HASH_Remove_Extended(pHash, &k);
588 }
590 /*!
591 ******************************************************************************
592 @Function HASH_Retrieve_Extended
594 @Description Retrieve a value from a hash table created with
595 HASH_Create_Extended.
597 @Input pHash - the hash table.
598 @Input pKey - pointer to the key.
600 @Return 0 if the key is missing, or the value associated with
601 the key.
602 ******************************************************************************/
603 IMG_UINTPTR_T
604 HASH_Retrieve_Extended (HASH_TABLE *pHash, IMG_VOID *pKey)
605 {
606 BUCKET **ppBucket;
607 IMG_UINT32 uIndex;
609 PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Retrieve_Extended: Hash=0x%p, pKey=0x%p",
610 pHash, pKey));
612 PVR_ASSERT (pHash != IMG_NULL);
614 if (pHash == IMG_NULL)
615 {
616 PVR_DPF((PVR_DBG_ERROR, "HASH_Retrieve_Extended: Null hash table"));
617 return 0;
618 }
620 uIndex = KEY_TO_INDEX(pHash, pKey, pHash->uSize);
622 for (ppBucket = &(pHash->ppBucketTable[uIndex]); *ppBucket != IMG_NULL; ppBucket = &((*ppBucket)->pNext))
623 {
624 /* PRQA S 0432,0541 1 */ /* ignore warning about dynamic array k */
625 if (KEY_COMPARE(pHash, (*ppBucket)->k, pKey))
626 {
627 BUCKET *pBucket = *ppBucket;
628 IMG_UINTPTR_T v = pBucket->v;
630 PVR_DPF ((PVR_DBG_MESSAGE,
631 "HASH_Retrieve: Hash=0x%p, pKey=0x%p = 0x" UINTPTR_FMT,
632 pHash, pKey, v));
633 return v;
634 }
635 }
636 PVR_DPF ((PVR_DBG_MESSAGE,
637 "HASH_Retrieve: Hash=0x%p, pKey=0x%p = 0x0 !!!!",
638 pHash, pKey));
639 return 0;
640 }
642 /*!
643 ******************************************************************************
644 @Function HASH_Retrieve
646 @Description Retrieve a value from a hash table created with
647 HASH_Create.
649 @Input pHash - the hash table
650 @Input k - the key
651 @Return 0 if the key is missing, or the value associated with
652 the key.
653 ******************************************************************************/
654 IMG_UINTPTR_T
655 HASH_Retrieve (HASH_TABLE *pHash, IMG_UINTPTR_T k)
656 {
657 PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Retrieve: Hash=0x%p, k=0x" UINTPTR_FMT,
658 pHash, k));
659 return HASH_Retrieve_Extended(pHash, &k);
660 }
662 /*!
663 ******************************************************************************
664 @Function HASH_Iterate
666 @Description Iterate over every entry in the hash table
668 @Input pHash - the old hash table
669 @Input pfnCallback - the size of the old hash table
671 @Return Callback error if any, otherwise PVRSRV_OK
672 ******************************************************************************/
673 PVRSRV_ERROR
674 HASH_Iterate(HASH_TABLE *pHash, HASH_pfnCallback pfnCallback)
675 {
676 IMG_UINT32 uIndex;
677 for (uIndex=0; uIndex < pHash->uSize; uIndex++)
678 {
679 BUCKET *pBucket;
680 pBucket = pHash->ppBucketTable[uIndex];
681 while (pBucket != IMG_NULL)
682 {
683 PVRSRV_ERROR eError;
684 BUCKET *pNextBucket = pBucket->pNext;
686 eError = pfnCallback((IMG_UINTPTR_T) ((IMG_VOID *) *(pBucket->k)), (IMG_UINTPTR_T) pBucket->v);
688 /* The callback might want us to break out early */
689 if (eError != PVRSRV_OK)
690 return eError;
692 pBucket = pNextBucket;
693 }
694 }
695 return PVRSRV_OK;
696 }
698 #ifdef HASH_TRACE
699 /*!
700 ******************************************************************************
701 @Function HASH_Dump
703 @Description To dump the contents of a hash table in human readable
704 form.
706 @Input pHash - the hash table
708 @Return None
709 ******************************************************************************/
710 IMG_VOID
711 HASH_Dump (HASH_TABLE *pHash)
712 {
713 IMG_UINT32 uIndex;
714 IMG_UINT32 uMaxLength=0;
715 IMG_UINT32 uEmptyCount=0;
717 PVR_ASSERT (pHash != IMG_NULL);
718 for (uIndex=0; uIndex<pHash->uSize; uIndex++)
719 {
720 BUCKET *pBucket;
721 IMG_UINT32 uLength = 0;
722 if (pHash->ppBucketTable[uIndex] == IMG_NULL)
723 {
724 uEmptyCount++;
725 }
726 for (pBucket=pHash->ppBucketTable[uIndex];
727 pBucket != IMG_NULL;
728 pBucket = pBucket->pNext)
729 {
730 uLength++;
731 }
732 uMaxLength = PRIVATE_MAX (uMaxLength, uLength);
733 }
735 PVR_TRACE(("hash table: uMinimumSize=%d size=%d count=%d",
736 pHash->uMinimumSize, pHash->uSize, pHash->uCount));
737 PVR_TRACE((" empty=%d max=%d", uEmptyCount, uMaxLength));
738 }
739 #endif