drivers/staging/imgtec/rogue/hash.c

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