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