diff options
Diffstat (limited to 'sgx_km/eurasia_km/services4/srvkm/common/hash.c')
-rw-r--r-- | sgx_km/eurasia_km/services4/srvkm/common/hash.c | 739 |
1 files changed, 739 insertions, 0 deletions
diff --git a/sgx_km/eurasia_km/services4/srvkm/common/hash.c b/sgx_km/eurasia_km/services4/srvkm/common/hash.c new file mode 100644 index 0000000..8dcedf9 --- /dev/null +++ b/sgx_km/eurasia_km/services4/srvkm/common/hash.c | |||
@@ -0,0 +1,739 @@ | |||
1 | /*************************************************************************/ /*! | ||
2 | @Title Self scaling hash tables. | ||
3 | @Copyright Copyright (c) Imagination Technologies Ltd. All Rights Reserved | ||
4 | @Description | ||
5 | Implements simple self scaling hash tables. Hash collisions are | ||
6 | handled by chaining entries together. Hash tables are increased in | ||
7 | size when they become more than (50%?) full and decreased in size | ||
8 | when less than (25%?) full. Hash tables are never decreased below | ||
9 | their initial size. | ||
10 | @License Dual MIT/GPLv2 | ||
11 | |||
12 | The contents of this file are subject to the MIT license as set out below. | ||
13 | |||
14 | Permission is hereby granted, free of charge, to any person obtaining a copy | ||
15 | of this software and associated documentation files (the "Software"), to deal | ||
16 | in the Software without restriction, including without limitation the rights | ||
17 | to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | ||
18 | copies of the Software, and to permit persons to whom the Software is | ||
19 | furnished to do so, subject to the following conditions: | ||
20 | |||
21 | The above copyright notice and this permission notice shall be included in | ||
22 | all copies or substantial portions of the Software. | ||
23 | |||
24 | Alternatively, the contents of this file may be used under the terms of | ||
25 | the GNU General Public License Version 2 ("GPL") in which case the provisions | ||
26 | of GPL are applicable instead of those above. | ||
27 | |||
28 | If you wish to allow use of your version of this file only under the terms of | ||
29 | GPL, and not to allow others to use your version of this file under the terms | ||
30 | of the MIT license, indicate your decision by deleting the provisions above | ||
31 | and replace them with the notice and other provisions required by GPL as set | ||
32 | out in the file called "GPL-COPYING" included in this distribution. If you do | ||
33 | not delete the provisions above, a recipient may use your version of this file | ||
34 | under the terms of either the MIT license or GPL. | ||
35 | |||
36 | This License is also included in this distribution in the file called | ||
37 | "MIT-COPYING". | ||
38 | |||
39 | EXCEPT AS OTHERWISE STATED IN A NEGOTIATED AGREEMENT: (A) THE SOFTWARE IS | ||
40 | PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING | ||
41 | BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR | ||
42 | PURPOSE AND NONINFRINGEMENT; AND (B) IN NO EVENT SHALL THE AUTHORS OR | ||
43 | COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER | ||
44 | IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN | ||
45 | CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. | ||
46 | */ /**************************************************************************/ | ||
47 | |||
48 | #include "pvr_debug.h" | ||
49 | #include "img_defs.h" | ||
50 | #include "services.h" | ||
51 | #include "servicesint.h" | ||
52 | #include "hash.h" | ||
53 | #include "osfunc.h" | ||
54 | |||
55 | #define PRIVATE_MAX(a,b) ((a)>(b)?(a):(b)) | ||
56 | |||
57 | #define KEY_TO_INDEX(pHash, key, uSize) \ | ||
58 | ((pHash)->pfnHashFunc((pHash)->uKeySize, (key), (uSize)) % (uSize)) | ||
59 | |||
60 | #define KEY_COMPARE(pHash, pKey1, pKey2) \ | ||
61 | ((pHash)->pfnKeyComp((pHash)->uKeySize, (pKey1), (pKey2))) | ||
62 | |||
63 | /* Each entry in a hash table is placed into a bucket */ | ||
64 | struct _BUCKET_ | ||
65 | { | ||
66 | /* the next bucket on the same chain */ | ||
67 | struct _BUCKET_ *pNext; | ||
68 | |||
69 | /* entry value */ | ||
70 | IMG_UINTPTR_T v; | ||
71 | |||
72 | /* entry key */ | ||
73 | IMG_UINTPTR_T k[]; /* PRQA S 0642 */ /* override dynamic array declaration warning */ | ||
74 | }; | ||
75 | typedef struct _BUCKET_ BUCKET; | ||
76 | |||
77 | struct _HASH_TABLE_ | ||
78 | { | ||
79 | /* the hash table array */ | ||
80 | BUCKET **ppBucketTable; | ||
81 | |||
82 | /* current size of the hash table */ | ||
83 | IMG_UINT32 uSize; | ||
84 | |||
85 | /* number of entries currently in the hash table */ | ||
86 | IMG_UINT32 uCount; | ||
87 | |||
88 | /* the minimum size that the hash table should be re-sized to */ | ||
89 | IMG_UINT32 uMinimumSize; | ||
90 | |||
91 | /* size of key in bytes */ | ||
92 | IMG_UINT32 uKeySize; | ||
93 | |||
94 | /* hash function */ | ||
95 | HASH_FUNC *pfnHashFunc; | ||
96 | |||
97 | /* key comparison function */ | ||
98 | HASH_KEY_COMP *pfnKeyComp; | ||
99 | }; | ||
100 | |||
101 | /*! | ||
102 | ****************************************************************************** | ||
103 | @Function HASH_Func_Default | ||
104 | |||
105 | @Description Hash function intended for hashing keys composed of | ||
106 | IMG_UINTPTR_T arrays. | ||
107 | |||
108 | @Input uKeySize - the size of the hash key, in bytes. | ||
109 | @Input pKey - a pointer to the key to hash. | ||
110 | @Input uHashTabLen - the length of the hash table. | ||
111 | |||
112 | @Return the hash value. | ||
113 | ******************************************************************************/ | ||
114 | IMG_UINT32 | ||
115 | HASH_Func_Default (IMG_SIZE_T uKeySize, IMG_VOID *pKey, IMG_UINT32 uHashTabLen) | ||
116 | { | ||
117 | IMG_UINTPTR_T *p = (IMG_UINTPTR_T *)pKey; | ||
118 | IMG_UINT32 uKeyLen = (IMG_UINT32)(uKeySize / sizeof(IMG_UINTPTR_T)); | ||
119 | IMG_UINT32 ui; | ||
120 | IMG_UINT32 uHashKey = 0; | ||
121 | |||
122 | PVR_UNREFERENCED_PARAMETER(uHashTabLen); | ||
123 | |||
124 | PVR_ASSERT((uKeySize % sizeof(IMG_UINTPTR_T)) == 0); | ||
125 | |||
126 | for (ui = 0; ui < uKeyLen; ui++) | ||
127 | { | ||
128 | IMG_UINT32 uHashPart = (IMG_UINT32)*p++; | ||
129 | |||
130 | uHashPart += (uHashPart << 12); | ||
131 | uHashPart ^= (uHashPart >> 22); | ||
132 | uHashPart += (uHashPart << 4); | ||
133 | uHashPart ^= (uHashPart >> 9); | ||
134 | uHashPart += (uHashPart << 10); | ||
135 | uHashPart ^= (uHashPart >> 2); | ||
136 | uHashPart += (uHashPart << 7); | ||
137 | uHashPart ^= (uHashPart >> 12); | ||
138 | |||
139 | uHashKey += uHashPart; | ||
140 | } | ||
141 | |||
142 | return uHashKey; | ||
143 | } | ||
144 | |||
145 | /*! | ||
146 | ****************************************************************************** | ||
147 | @Function HASH_Key_Comp_Default | ||
148 | |||
149 | @Description Compares keys composed of IMG_UINTPTR_T arrays. | ||
150 | |||
151 | @Input uKeySize - the size of the hash key, in bytes. | ||
152 | @Input pKey1 - pointer to first hash key to compare. | ||
153 | @Input pKey2 - pointer to second hash key to compare. | ||
154 | @Return IMG_TRUE - the keys match. | ||
155 | IMG_FALSE - the keys don't match. | ||
156 | ******************************************************************************/ | ||
157 | IMG_BOOL | ||
158 | HASH_Key_Comp_Default (IMG_SIZE_T uKeySize, IMG_VOID *pKey1, IMG_VOID *pKey2) | ||
159 | { | ||
160 | IMG_UINTPTR_T *p1 = (IMG_UINTPTR_T *)pKey1; | ||
161 | IMG_UINTPTR_T *p2 = (IMG_UINTPTR_T *)pKey2; | ||
162 | IMG_UINT32 uKeyLen = (IMG_UINT32)(uKeySize / sizeof(IMG_UINTPTR_T)); | ||
163 | IMG_UINT32 ui; | ||
164 | |||
165 | PVR_ASSERT((uKeySize % sizeof(IMG_UINTPTR_T)) == 0); | ||
166 | |||
167 | for (ui = 0; ui < uKeyLen; ui++) | ||
168 | { | ||
169 | if (*p1++ != *p2++) | ||
170 | return IMG_FALSE; | ||
171 | } | ||
172 | |||
173 | return IMG_TRUE; | ||
174 | } | ||
175 | |||
176 | /*! | ||
177 | ****************************************************************************** | ||
178 | @Function _ChainInsert | ||
179 | |||
180 | @Description Insert a bucket into the appropriate hash table chain. | ||
181 | |||
182 | @Input pBucket - the bucket | ||
183 | @Input ppBucketTable - the hash table | ||
184 | @Input uSize - the size of the hash table | ||
185 | |||
186 | @Return PVRSRV_ERROR | ||
187 | ******************************************************************************/ | ||
188 | static PVRSRV_ERROR | ||
189 | _ChainInsert (HASH_TABLE *pHash, BUCKET *pBucket, BUCKET **ppBucketTable, IMG_UINT32 uSize) | ||
190 | { | ||
191 | IMG_UINT32 uIndex; | ||
192 | |||
193 | PVR_ASSERT (pBucket != IMG_NULL); | ||
194 | PVR_ASSERT (ppBucketTable != IMG_NULL); | ||
195 | PVR_ASSERT (uSize != 0); | ||
196 | |||
197 | if ((pBucket == IMG_NULL) || (ppBucketTable == IMG_NULL) || (uSize == 0)) | ||
198 | { | ||
199 | PVR_DPF((PVR_DBG_ERROR, "_ChainInsert: invalid parameter")); | ||
200 | return PVRSRV_ERROR_INVALID_PARAMS; | ||
201 | } | ||
202 | |||
203 | uIndex = KEY_TO_INDEX(pHash, pBucket->k, uSize); /* PRQA S 0432,0541 */ /* ignore dynamic array warning */ | ||
204 | pBucket->pNext = ppBucketTable[uIndex]; | ||
205 | ppBucketTable[uIndex] = pBucket; | ||
206 | |||
207 | return PVRSRV_OK; | ||
208 | } | ||
209 | |||
210 | /*! | ||
211 | ****************************************************************************** | ||
212 | @Function _Rehash | ||
213 | |||
214 | @Description Iterate over every entry in an old hash table and | ||
215 | rehash into the new table. | ||
216 | |||
217 | @Input ppOldTable - the old hash table | ||
218 | @Input uOldSize - the size of the old hash table | ||
219 | @Input ppNewTable - the new hash table | ||
220 | @Input uNewSize - the size of the new hash table | ||
221 | |||
222 | @Return None | ||
223 | ******************************************************************************/ | ||
224 | static PVRSRV_ERROR | ||
225 | _Rehash (HASH_TABLE *pHash, | ||
226 | BUCKET **ppOldTable, IMG_UINT32 uOldSize, | ||
227 | BUCKET **ppNewTable, IMG_UINT32 uNewSize) | ||
228 | { | ||
229 | IMG_UINT32 uIndex; | ||
230 | for (uIndex=0; uIndex< uOldSize; uIndex++) | ||
231 | { | ||
232 | BUCKET *pBucket; | ||
233 | pBucket = ppOldTable[uIndex]; | ||
234 | while (pBucket != IMG_NULL) | ||
235 | { | ||
236 | PVRSRV_ERROR eError; | ||
237 | BUCKET *pNextBucket = pBucket->pNext; | ||
238 | eError = _ChainInsert (pHash, pBucket, ppNewTable, uNewSize); | ||
239 | if (eError != PVRSRV_OK) | ||
240 | { | ||
241 | PVR_DPF((PVR_DBG_ERROR, "_Rehash: call to _ChainInsert failed")); | ||
242 | return eError; | ||
243 | } | ||
244 | pBucket = pNextBucket; | ||
245 | } | ||
246 | } | ||
247 | return PVRSRV_OK; | ||
248 | } | ||
249 | |||
250 | /*! | ||
251 | ****************************************************************************** | ||
252 | @Function _Resize | ||
253 | |||
254 | @Description Attempt to resize a hash table, failure to allocate a | ||
255 | new larger hash table is not considered a hard failure. | ||
256 | We simply continue and allow the table to fill up, the | ||
257 | effect is to allow hash chains to become longer. | ||
258 | |||
259 | @Input pHash - Hash table to resize. | ||
260 | @Input uNewSize - Required table size. | ||
261 | @Return IMG_TRUE Success | ||
262 | IMG_FALSE Failed | ||
263 | ******************************************************************************/ | ||
264 | static IMG_BOOL | ||
265 | _Resize (HASH_TABLE *pHash, IMG_UINT32 uNewSize) | ||
266 | { | ||
267 | if (uNewSize != pHash->uSize) | ||
268 | { | ||
269 | BUCKET **ppNewTable; | ||
270 | IMG_UINT32 uIndex; | ||
271 | |||
272 | PVR_DPF ((PVR_DBG_MESSAGE, | ||
273 | "HASH_Resize: oldsize=0x%x newsize=0x%x count=0x%x", | ||
274 | pHash->uSize, uNewSize, pHash->uCount)); | ||
275 | |||
276 | OSAllocMem(PVRSRV_PAGEABLE_SELECT, | ||
277 | sizeof (BUCKET *) * uNewSize, | ||
278 | (IMG_PVOID*)&ppNewTable, IMG_NULL, | ||
279 | "Hash Table Buckets"); | ||
280 | if (ppNewTable == IMG_NULL) | ||
281 | return IMG_FALSE; | ||
282 | |||
283 | for (uIndex=0; uIndex<uNewSize; uIndex++) | ||
284 | ppNewTable[uIndex] = IMG_NULL; | ||
285 | |||
286 | if (_Rehash (pHash, pHash->ppBucketTable, pHash->uSize, ppNewTable, uNewSize) != PVRSRV_OK) | ||
287 | { | ||
288 | OSFreeMem (PVRSRV_PAGEABLE_SELECT, sizeof(BUCKET *) * uNewSize, ppNewTable, IMG_NULL); | ||
289 | return IMG_FALSE; | ||
290 | } | ||
291 | |||
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 | } | ||
299 | |||
300 | |||
301 | /*! | ||
302 | ****************************************************************************** | ||
303 | @Function HASH_Create_Extended | ||
304 | |||
305 | @Description Create a self scaling hash table, using the supplied | ||
306 | key size, and the supplied hash and key comparsion | ||
307 | functions. | ||
308 | |||
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; | ||
322 | |||
323 | PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Create_Extended: InitialSize=0x%x", uInitialLen)); | ||
324 | |||
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 | } | ||
332 | |||
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; | ||
339 | |||
340 | OSAllocMem(PVRSRV_PAGEABLE_SELECT, | ||
341 | sizeof (BUCKET *) * pHash->uSize, | ||
342 | (IMG_PVOID*)&pHash->ppBucketTable, IMG_NULL, | ||
343 | "Hash Table Buckets"); | ||
344 | |||
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 | } | ||
351 | |||
352 | for (uIndex=0; uIndex<pHash->uSize; uIndex++) | ||
353 | pHash->ppBucketTable[uIndex] = IMG_NULL; | ||
354 | return pHash; | ||
355 | } | ||
356 | |||
357 | /*! | ||
358 | ****************************************************************************** | ||
359 | @Function HASH_Create | ||
360 | |||
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. | ||
364 | |||
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 | } | ||
376 | |||
377 | /*! | ||
378 | ****************************************************************************** | ||
379 | @Function HASH_Delete | ||
380 | |||
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. | ||
384 | |||
385 | @Input pHash - hash table | ||
386 | |||
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")); | ||
395 | |||
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 | } | ||
408 | |||
409 | /*! | ||
410 | ****************************************************************************** | ||
411 | @Function HASH_Insert_Extended | ||
412 | |||
413 | @Description Insert a key value pair into a hash table created | ||
414 | with HASH_Create_Extended. | ||
415 | |||
416 | @Input pHash - the hash table. | ||
417 | @Input pKey - pointer to the key. | ||
418 | @Input v - the value associated with the key. | ||
419 | |||
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; | ||
427 | |||
428 | PVR_DPF ((PVR_DBG_MESSAGE, | ||
429 | "HASH_Insert_Extended: Hash=0x%p, pKey=0x%p, v=0x" UINTPTR_FMT, | ||
430 | pHash, pKey, v)); | ||
431 | |||
432 | PVR_ASSERT (pHash != IMG_NULL); | ||
433 | |||
434 | if (pHash == IMG_NULL) | ||
435 | { | ||
436 | PVR_DPF((PVR_DBG_ERROR, "HASH_Insert_Extended: invalid parameter")); | ||
437 | return IMG_FALSE; | ||
438 | } | ||
439 | |||
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 | } | ||
447 | |||
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 | } | ||
458 | |||
459 | pHash->uCount++; | ||
460 | |||
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 | } | ||
469 | |||
470 | |||
471 | return IMG_TRUE; | ||
472 | } | ||
473 | |||
474 | /*! | ||
475 | ****************************************************************************** | ||
476 | @Function HASH_Insert | ||
477 | |||
478 | @Description Insert a key value pair into a hash table created with | ||
479 | HASH_Create. | ||
480 | |||
481 | @Input pHash - the hash table. | ||
482 | @Input k - the key value. | ||
483 | @Input v - the value associated with the key. | ||
484 | |||
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)); | ||
494 | |||
495 | return HASH_Insert_Extended(pHash, &k, v); | ||
496 | } | ||
497 | |||
498 | /*! | ||
499 | ****************************************************************************** | ||
500 | @Function HASH_Remove_Extended | ||
501 | |||
502 | @Description Remove a key from a hash table created with | ||
503 | HASH_Create_Extended. | ||
504 | |||
505 | @Input pHash - the hash table. | ||
506 | @Input pKey - pointer to key. | ||
507 | |||
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; | ||
516 | |||
517 | PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Remove_Extended: Hash=0x%p, pKey=0x%p", | ||
518 | pHash, pKey)); | ||
519 | |||
520 | PVR_ASSERT (pHash != IMG_NULL); | ||
521 | |||
522 | if (pHash == IMG_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 != 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; | ||
538 | |||
539 | OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(BUCKET) + pHash->uKeySize, pBucket, IMG_NULL); | ||
540 | /*not nulling original pointer, already overwritten*/ | ||
541 | |||
542 | pHash->uCount--; | ||
543 | |||
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 | } | ||
555 | |||
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 | } | ||
567 | |||
568 | /*! | ||
569 | ****************************************************************************** | ||
570 | @Function HASH_Remove | ||
571 | |||
572 | @Description Remove a key value pair from a hash table created | ||
573 | with HASH_Create. | ||
574 | |||
575 | @Input pHash - the hash table | ||
576 | @Input k - the key | ||
577 | |||
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)); | ||
586 | |||
587 | return HASH_Remove_Extended(pHash, &k); | ||
588 | } | ||
589 | |||
590 | /*! | ||
591 | ****************************************************************************** | ||
592 | @Function HASH_Retrieve_Extended | ||
593 | |||
594 | @Description Retrieve a value from a hash table created with | ||
595 | HASH_Create_Extended. | ||
596 | |||
597 | @Input pHash - the hash table. | ||
598 | @Input pKey - pointer to the key. | ||
599 | |||
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; | ||
608 | |||
609 | PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Retrieve_Extended: Hash=0x%p, pKey=0x%p", | ||
610 | pHash, pKey)); | ||
611 | |||
612 | PVR_ASSERT (pHash != IMG_NULL); | ||
613 | |||
614 | if (pHash == IMG_NULL) | ||
615 | { | ||
616 | PVR_DPF((PVR_DBG_ERROR, "HASH_Retrieve_Extended: Null hash table")); | ||
617 | return 0; | ||
618 | } | ||
619 | |||
620 | uIndex = KEY_TO_INDEX(pHash, pKey, pHash->uSize); | ||
621 | |||
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; | ||
629 | |||
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 | } | ||
641 | |||
642 | /*! | ||
643 | ****************************************************************************** | ||
644 | @Function HASH_Retrieve | ||
645 | |||
646 | @Description Retrieve a value from a hash table created with | ||
647 | HASH_Create. | ||
648 | |||
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 | } | ||
661 | |||
662 | /*! | ||
663 | ****************************************************************************** | ||
664 | @Function HASH_Iterate | ||
665 | |||
666 | @Description Iterate over every entry in the hash table | ||
667 | |||
668 | @Input pHash - the old hash table | ||
669 | @Input pfnCallback - the size of the old hash table | ||
670 | |||
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; | ||
685 | |||
686 | eError = pfnCallback((IMG_UINTPTR_T) ((IMG_VOID *) *(pBucket->k)), (IMG_UINTPTR_T) pBucket->v); | ||
687 | |||
688 | /* The callback might want us to break out early */ | ||
689 | if (eError != PVRSRV_OK) | ||
690 | return eError; | ||
691 | |||
692 | pBucket = pNextBucket; | ||
693 | } | ||
694 | } | ||
695 | return PVRSRV_OK; | ||
696 | } | ||
697 | |||
698 | #ifdef HASH_TRACE | ||
699 | /*! | ||
700 | ****************************************************************************** | ||
701 | @Function HASH_Dump | ||
702 | |||
703 | @Description To dump the contents of a hash table in human readable | ||
704 | form. | ||
705 | |||
706 | @Input pHash - the hash table | ||
707 | |||
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; | ||
716 | |||
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 | } | ||
734 | |||
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 | ||