drivers/gpu/drm/img-rogue/hash.c - chromiumos/third_party/kernel - Git at Google

 /*************************************************************************/ /*!
 @File
 @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/ */
 #include "img_defs.h"
 #include "img_types.h"
 #include "pvr_debug.h"
 #include "pvrsrv_error.h"

 /* services/shared/include/ */
 #include "hash.h"

 /* services/client/include/ or services/server/include/ */
 #include "osfunc.h"
 #include "allocmem.h"

 #if defined(__KERNEL__)
 #include "pvrsrv.h"
 #endif

 #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 */
 	uintptr_t v;

 	/* entry key */
 #if defined (WIN32)
 	uintptr_t k[1];
 #else
 	uintptr_t k[];		/* PRQA S 0642 */ /* override dynamic array declaration warning */
 #endif
 };
 typedef struct _BUCKET_ BUCKET;

 struct _HASH_TABLE_
 {
 	/* 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;

 	/* the hash table array */
 	BUCKET **ppBucketTable;
 };

 /*************************************************************************/ /*!
 @Function       HASH_Func_Default
 @Description    Hash function intended for hashing keys composed of
                 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_INTERNAL IMG_UINT32
 HASH_Func_Default (size_t uKeySize, void *pKey, IMG_UINT32 uHashTabLen)
 {
 	uintptr_t *p = (uintptr_t *)pKey;
 	IMG_UINT32 uKeyLen = uKeySize / sizeof(uintptr_t);
 	IMG_UINT32 ui;
 	IMG_UINT32 uHashKey = 0;

 	PVR_UNREFERENCED_PARAMETER(uHashTabLen);

 	PVR_ASSERT((uKeySize % sizeof(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 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_INTERNAL IMG_BOOL
 HASH_Key_Comp_Default (size_t uKeySize, void *pKey1, void *pKey2)
 {
 	uintptr_t *p1 = (uintptr_t *)pKey1;
 	uintptr_t *p2 = (uintptr_t *)pKey2;
 	IMG_UINT32 uKeyLen = uKeySize / sizeof(uintptr_t);
 	IMG_UINT32 ui;

 	PVR_ASSERT((uKeySize % sizeof(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 void
 _ChainInsert (HASH_TABLE *pHash, BUCKET *pBucket, BUCKET **ppBucketTable, IMG_UINT32 uSize)
 {
 	IMG_UINT32 uIndex;

 	/* We assume that all parameters passed by the caller are valid. */
 	PVR_ASSERT (pBucket != NULL);
 	PVR_ASSERT (ppBucketTable != NULL);
 	PVR_ASSERT (uSize != 0);

 	uIndex = KEY_TO_INDEX(pHash, pBucket->k, uSize);	/* PRQA S 0432,0541 */ /* ignore dynamic array warning */
 	pBucket->pNext = ppBucketTable[uIndex];
 	ppBucketTable[uIndex] = pBucket;
 }

 /*************************************************************************/ /*!
 @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 void
 _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 != NULL)
 		{
 			BUCKET *pNextBucket = pBucket->pNext;
 			_ChainInsert (pHash, pBucket, ppNewTable, uNewSize);
 			pBucket = pNextBucket;
 		}
     }
 }

 /*************************************************************************/ /*!
 @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;

 #if defined(__linux__) && defined(__KERNEL__)
 		ppNewTable = OSAllocMemNoStats(sizeof (BUCKET *) * uNewSize);
 #else
 		ppNewTable = OSAllocMem(sizeof (BUCKET *) * uNewSize);
 #endif
 		if (ppNewTable == NULL)
         {
             return IMG_FALSE;
         }

         for (uIndex=0; uIndex<uNewSize; uIndex++)
             ppNewTable[uIndex] = NULL;

         _Rehash(pHash, pHash->ppBucketTable, pHash->uSize, ppNewTable, uNewSize);

 #if defined(__linux__) && defined(__KERNEL__)
         OSFreeMemNoStats(pHash->ppBucketTable);
 #else
         OSFreeMem(pHash->ppBucketTable);
 #endif
         /*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         NULL or hash table handle.
 */ /**************************************************************************/
 IMG_INTERNAL
 HASH_TABLE * HASH_Create_Extended (IMG_UINT32 uInitialLen, size_t uKeySize, HASH_FUNC *pfnHashFunc, HASH_KEY_COMP *pfnKeyComp)
 {
 	HASH_TABLE *pHash;
 	IMG_UINT32 uIndex;

 	if (uInitialLen == 0 || uKeySize == 0 || pfnHashFunc == NULL || pfnKeyComp == NULL)
 	{
 		PVR_DPF((PVR_DBG_ERROR, "HASH_Create_Extended: invalid input parameters"));
 		return NULL;
 	}

 	PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Create_Extended: InitialSize=0x%x", uInitialLen));

 #if defined(__linux__) && defined(__KERNEL__)
 	pHash = OSAllocMemNoStats(sizeof(HASH_TABLE));
 #else
 	pHash = OSAllocMem(sizeof(HASH_TABLE));
 #endif
     if (pHash == NULL)
 	{
 		return NULL;
 	}

 	pHash->uCount = 0;
 	pHash->uSize = uInitialLen;
 	pHash->uMinimumSize = uInitialLen;
 	pHash->uKeySize = uKeySize;
 	pHash->pfnHashFunc = pfnHashFunc;
 	pHash->pfnKeyComp = pfnKeyComp;

 #if defined(__linux__) && defined(__KERNEL__)
     pHash->ppBucketTable = OSAllocMemNoStats(sizeof (BUCKET *) * pHash->uSize);
 #else
     pHash->ppBucketTable = OSAllocMem(sizeof (BUCKET *) * pHash->uSize);
 #endif
     if (pHash->ppBucketTable == NULL)
     {
 #if defined(__linux__) && defined(__KERNEL__)
 		OSFreeMemNoStats(pHash);
 #else
 		OSFreeMem(pHash);
 #endif
 		/*not nulling pointer, out of scope*/
 		return NULL;
     }

 	for (uIndex=0; uIndex<pHash->uSize; uIndex++)
 		pHash->ppBucketTable[uIndex] = NULL;
 	return pHash;
 }

 /*************************************************************************/ /*!
 @Function       HASH_Create
 @Description    Create a self scaling hash table with a key
                 consisting of a single 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         NULL or hash table handle.
 */ /**************************************************************************/
 IMG_INTERNAL
 HASH_TABLE * HASH_Create (IMG_UINT32 uInitialLen)
 {
 	return HASH_Create_Extended(uInitialLen, sizeof(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_INTERNAL void
 HASH_Delete (HASH_TABLE *pHash)
 {
 	IMG_BOOL bDoCheck = IMG_TRUE;
 #if defined(__KERNEL__) && !defined(__QNXNTO__)
 	PVRSRV_DATA *psPVRSRVData = PVRSRVGetPVRSRVData();

 	if (psPVRSRVData != NULL)
 	{
 		if (psPVRSRVData->eServicesState != PVRSRV_SERVICES_STATE_OK)
 		{
 			bDoCheck = IMG_FALSE;
 		}
 	}
 #if defined(PVRSRV_FORCE_UNLOAD_IF_BAD_STATE)
 	else
 	{
 		bDoCheck = IMG_FALSE;
 	}
 #endif
 #endif
 	if (pHash != NULL)
     {
 		PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Delete"));

 		if (bDoCheck)
 		{
 			PVR_ASSERT (pHash->uCount==0);
 		}
 		if(pHash->uCount != 0)
 		{
 			IMG_UINT32 uiEntriesLeft = pHash->uCount;
 			IMG_UINT32 i;
 			PVR_DPF ((PVR_DBG_ERROR, "%s: Leak detected in hash table!", __func__));
 			PVR_DPF ((PVR_DBG_ERROR, "%s: Likely Cause: client drivers not freeing allocations before destroying devmemcontext", __func__));
 			PVR_DPF ((PVR_DBG_ERROR, "%s: Removing remaining %u hash entries.", __func__, uiEntriesLeft));

 			for (i = 0; i < uiEntriesLeft; i++)
 			{
 #if defined(__linux__) && defined(__KERNEL__)
 				OSFreeMemNoStats(pHash->ppBucketTable[i]);
 #else
 				OSFreeMem(pHash->ppBucketTable[i]);
 #endif
 			}
 		}
 #if defined(__linux__) && defined(__KERNEL__)
 		OSFreeMemNoStats(pHash->ppBucketTable);
 #else
 		OSFreeMem(pHash->ppBucketTable);
 #endif
 		pHash->ppBucketTable = NULL;
 #if defined(__linux__) && defined(__KERNEL__)
 		OSFreeMemNoStats(pHash);
 #else
 		OSFreeMem(pHash);
 #endif
 		/*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     Hash table
 @Input          pKey      Pointer to the key.
 @Input          v         The value associated with the key.
 @Return         IMG_TRUE  - success
                 IMG_FALSE  - failure
 */ /**************************************************************************/
 IMG_INTERNAL IMG_BOOL
 HASH_Insert_Extended (HASH_TABLE *pHash, void *pKey, uintptr_t v)
 {
 	BUCKET *pBucket;

 	PVR_ASSERT (pHash != NULL);

 	if (pHash == NULL)
 	{
 		PVR_DPF((PVR_DBG_ERROR, "HASH_Insert_Extended: invalid parameter"));
 		return IMG_FALSE;
 	}

 #if defined(__linux__) && defined(__KERNEL__)
 	pBucket = OSAllocMemNoStats(sizeof(BUCKET) + pHash->uKeySize);
 #else
 	pBucket = OSAllocMem(sizeof(BUCKET) + pHash->uKeySize);
 #endif
     if (pBucket == NULL)
 	{
 		return IMG_FALSE;
 	}

 	pBucket->v = v;
 	/* PRQA S 0432,0541 1 */ /* ignore warning about dynamic array k (linux)*/
 	OSCachedMemCopy(pBucket->k, pKey, pHash->uKeySize);

 	_ChainInsert (pHash, pBucket, pHash->ppBucketTable, pHash->uSize);

 	pHash->uCount++;

 	/* check if we need to think about re-balancing */
 	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     Hash table
 @Input          k         The key value.
 @Input          v         The value associated with the key.
 @Return         IMG_TRUE - success.
                 IMG_FALSE - failure.
 */ /**************************************************************************/
 IMG_INTERNAL IMG_BOOL
 HASH_Insert (HASH_TABLE *pHash, uintptr_t k, uintptr_t 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     Hash table
 @Input          pKey      Pointer to key.
 @Return         0 if the key is missing, or the value associated with the key.
 */ /**************************************************************************/
 IMG_INTERNAL uintptr_t
 HASH_Remove_Extended(HASH_TABLE *pHash, void *pKey)
 {
 	BUCKET **ppBucket;
 	IMG_UINT32 uIndex;

 	PVR_ASSERT (pHash != NULL);

 	if (pHash == 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 != 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;
 			uintptr_t v = pBucket->v;
 			(*ppBucket) = pBucket->pNext;

 #if defined(__linux__) && defined(__KERNEL__)
 			OSFreeMemNoStats(pBucket);
 #else
 			OSFreeMem(pBucket);
 #endif
 			/*not nulling original pointer, already overwritten*/

 			pHash->uCount--;

 			/* check if we need to think about re-balancing */
 			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));
             }

 			return v;
 		}
 	}
 	return 0;
 }

 /*************************************************************************/ /*!
 @Function       HASH_Remove
 @Description    Remove a key value pair from a hash table created
                 with HASH_Create.
 @Input          pHash     Hash table
 @Input          k         The key
 @Return         0 if the key is missing, or the value associated with the key.
 */ /**************************************************************************/
 IMG_INTERNAL uintptr_t
 HASH_Remove (HASH_TABLE *pHash, uintptr_t 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     Hash table
 @Input          pKey      Pointer to the key.
 @Return         0 if the key is missing, or the value associated with the key.
 */ /**************************************************************************/
 IMG_INTERNAL uintptr_t
 HASH_Retrieve_Extended (HASH_TABLE *pHash, void *pKey)
 {
 	BUCKET **ppBucket;
 	IMG_UINT32 uIndex;

 	PVR_ASSERT (pHash != NULL);

 	if (pHash == 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 != 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;
 			uintptr_t v = pBucket->v;

 			return v;
 		}
 	}
 	return 0;
 }

 /*************************************************************************/ /*!
 @Function       HASH_Retrieve
 @Description    Retrieve a value from a hash table created with
                 HASH_Create.
 @Input          pHash     Hash table
 @Input          k         The key
 @Return         0 if the key is missing, or the value associated with the key.
 */ /**************************************************************************/
 IMG_INTERNAL uintptr_t
 HASH_Retrieve (HASH_TABLE *pHash, uintptr_t k)
 {
 	return HASH_Retrieve_Extended(pHash, &k);
 }

 /*************************************************************************/ /*!
 @Function       HASH_Iterate
 @Description    Iterate over every entry in the hash table
 @Input          pHash - Hash table to iterate
 @Input          pfnCallback - Callback to call with the key and data for each
 							  entry in the hash table
 @Return         Callback error if any, otherwise PVRSRV_OK
 */ /**************************************************************************/
 IMG_INTERNAL 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 != NULL)
         {
             PVRSRV_ERROR eError;
             BUCKET *pNextBucket = pBucket->pNext;

             eError = pfnCallback((uintptr_t) ((void *) *(pBucket->k)), (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     Hash table
 */ /**************************************************************************/
 void
 HASH_Dump (HASH_TABLE *pHash)
 {
 	IMG_UINT32 uIndex;
 	IMG_UINT32 uMaxLength=0;
 	IMG_UINT32 uEmptyCount=0;

 	PVR_ASSERT (pHash != NULL);
 	for (uIndex=0; uIndex<pHash->uSize; uIndex++)
 	{
 		BUCKET *pBucket;
 		IMG_UINT32 uLength = 0;
 		if (pHash->ppBucketTable[uIndex] == NULL)
 		{
 			uEmptyCount++;
 		}
 		for (pBucket=pHash->ppBucketTable[uIndex];
 				pBucket != 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
	/************************************************************************/ /!
	@File
	@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/ */
	#include "img_defs.h"
	#include "img_types.h"
	#include "pvr_debug.h"
	#include "pvrsrv_error.h"

	/* services/shared/include/ */
	#include "hash.h"

	/* services/client/include/ or services/server/include/ */
	#include "osfunc.h"
	#include "allocmem.h"

	#if defined(__KERNEL__)
	#include "pvrsrv.h"
	#endif

	#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 */
	uintptr_t v;

	/* entry key */
	#if defined (WIN32)
	uintptr_t k[1];
	#else
	uintptr_t k[]; /* PRQA S 0642 / / override dynamic array declaration warning */
	#endif
	};
	typedef struct _BUCKET_ BUCKET;

	struct _HASH_TABLE_
	{
	/* 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;

	/* the hash table array */
	BUCKET **ppBucketTable;
	};

	/************************************************************************/ /!
	@Function HASH_Func_Default
	@Description Hash function intended for hashing keys composed of
	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_INTERNAL IMG_UINT32
	HASH_Func_Default (size_t uKeySize, void *pKey, IMG_UINT32 uHashTabLen)
	{
	uintptr_t p = (uintptr_t )pKey;
	IMG_UINT32 uKeyLen = uKeySize / sizeof(uintptr_t);
	IMG_UINT32 ui;
	IMG_UINT32 uHashKey = 0;

	PVR_UNREFERENCED_PARAMETER(uHashTabLen);

	PVR_ASSERT((uKeySize % sizeof(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 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_INTERNAL IMG_BOOL
	HASH_Key_Comp_Default (size_t uKeySize, void pKey1, void pKey2)
	{
	uintptr_t p1 = (uintptr_t )pKey1;
	uintptr_t p2 = (uintptr_t )pKey2;
	IMG_UINT32 uKeyLen = uKeySize / sizeof(uintptr_t);
	IMG_UINT32 ui;

	PVR_ASSERT((uKeySize % sizeof(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 void
	_ChainInsert (HASH_TABLE pHash, BUCKET pBucket, BUCKET **ppBucketTable, IMG_UINT32 uSize)
	{
	IMG_UINT32 uIndex;

	/* We assume that all parameters passed by the caller are valid. */
	PVR_ASSERT (pBucket != NULL);
	PVR_ASSERT (ppBucketTable != NULL);
	PVR_ASSERT (uSize != 0);

	uIndex = KEY_TO_INDEX(pHash, pBucket->k, uSize); /* PRQA S 0432,0541 / / ignore dynamic array warning */
	pBucket->pNext = ppBucketTable[uIndex];
	ppBucketTable[uIndex] = pBucket;
	}

	/************************************************************************/ /!
	@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 void
	_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 != NULL)
	{
	BUCKET *pNextBucket = pBucket->pNext;
	_ChainInsert (pHash, pBucket, ppNewTable, uNewSize);
	pBucket = pNextBucket;
	}
	}
	}

	/************************************************************************/ /!
	@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;

	#if defined(__linux__) && defined(__KERNEL__)
	ppNewTable = OSAllocMemNoStats(sizeof (BUCKET ) uNewSize);
	#else
	ppNewTable = OSAllocMem(sizeof (BUCKET ) uNewSize);
	#endif
	if (ppNewTable == NULL)
	{
	return IMG_FALSE;
	}

	for (uIndex=0; uIndex<uNewSize; uIndex++)
	ppNewTable[uIndex] = NULL;

	_Rehash(pHash, pHash->ppBucketTable, pHash->uSize, ppNewTable, uNewSize);

	#if defined(__linux__) && defined(__KERNEL__)
	OSFreeMemNoStats(pHash->ppBucketTable);
	#else
	OSFreeMem(pHash->ppBucketTable);
	#endif
	/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 NULL or hash table handle.
	/ /*************************************************************************/
	IMG_INTERNAL
	HASH_TABLE * HASH_Create_Extended (IMG_UINT32 uInitialLen, size_t uKeySize, HASH_FUNC pfnHashFunc, HASH_KEY_COMP pfnKeyComp)
	{
	HASH_TABLE *pHash;
	IMG_UINT32 uIndex;

	if (uInitialLen == 0 \|\| uKeySize == 0 \|\| pfnHashFunc == NULL \|\| pfnKeyComp == NULL)
	{
	PVR_DPF((PVR_DBG_ERROR, "HASH_Create_Extended: invalid input parameters"));
	return NULL;
	}

	PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Create_Extended: InitialSize=0x%x", uInitialLen));

	#if defined(__linux__) && defined(__KERNEL__)
	pHash = OSAllocMemNoStats(sizeof(HASH_TABLE));
	#else
	pHash = OSAllocMem(sizeof(HASH_TABLE));
	#endif
	if (pHash == NULL)
	{
	return NULL;
	}

	pHash->uCount = 0;
	pHash->uSize = uInitialLen;
	pHash->uMinimumSize = uInitialLen;
	pHash->uKeySize = uKeySize;
	pHash->pfnHashFunc = pfnHashFunc;
	pHash->pfnKeyComp = pfnKeyComp;

	#if defined(__linux__) && defined(__KERNEL__)
	pHash->ppBucketTable = OSAllocMemNoStats(sizeof (BUCKET ) pHash->uSize);
	#else
	pHash->ppBucketTable = OSAllocMem(sizeof (BUCKET ) pHash->uSize);
	#endif
	if (pHash->ppBucketTable == NULL)
	{
	#if defined(__linux__) && defined(__KERNEL__)
	OSFreeMemNoStats(pHash);
	#else
	OSFreeMem(pHash);
	#endif
	/not nulling pointer, out of scope/
	return NULL;
	}

	for (uIndex=0; uIndex<pHash->uSize; uIndex++)
	pHash->ppBucketTable[uIndex] = NULL;
	return pHash;
	}

	/************************************************************************/ /!
	@Function HASH_Create
	@Description Create a self scaling hash table with a key
	consisting of a single 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 NULL or hash table handle.
	/ /*************************************************************************/
	IMG_INTERNAL
	HASH_TABLE * HASH_Create (IMG_UINT32 uInitialLen)
	{
	return HASH_Create_Extended(uInitialLen, sizeof(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_INTERNAL void
	HASH_Delete (HASH_TABLE *pHash)
	{
	IMG_BOOL bDoCheck = IMG_TRUE;
	#if defined(__KERNEL__) && !defined(__QNXNTO__)
	PVRSRV_DATA *psPVRSRVData = PVRSRVGetPVRSRVData();

	if (psPVRSRVData != NULL)
	{
	if (psPVRSRVData->eServicesState != PVRSRV_SERVICES_STATE_OK)
	{
	bDoCheck = IMG_FALSE;
	}
	}
	#if defined(PVRSRV_FORCE_UNLOAD_IF_BAD_STATE)
	else
	{
	bDoCheck = IMG_FALSE;
	}
	#endif
	#endif
	if (pHash != NULL)
	{
	PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Delete"));

	if (bDoCheck)
	{
	PVR_ASSERT (pHash->uCount==0);
	}
	if(pHash->uCount != 0)
	{
	IMG_UINT32 uiEntriesLeft = pHash->uCount;
	IMG_UINT32 i;
	PVR_DPF ((PVR_DBG_ERROR, "%s: Leak detected in hash table!", __func__));
	PVR_DPF ((PVR_DBG_ERROR, "%s: Likely Cause: client drivers not freeing allocations before destroying devmemcontext", __func__));
	PVR_DPF ((PVR_DBG_ERROR, "%s: Removing remaining %u hash entries.", __func__, uiEntriesLeft));

	for (i = 0; i < uiEntriesLeft; i++)
	{
	#if defined(__linux__) && defined(__KERNEL__)
	OSFreeMemNoStats(pHash->ppBucketTable[i]);
	#else
	OSFreeMem(pHash->ppBucketTable[i]);
	#endif
	}
	}
	#if defined(__linux__) && defined(__KERNEL__)
	OSFreeMemNoStats(pHash->ppBucketTable);
	#else
	OSFreeMem(pHash->ppBucketTable);
	#endif
	pHash->ppBucketTable = NULL;
	#if defined(__linux__) && defined(__KERNEL__)
	OSFreeMemNoStats(pHash);
	#else
	OSFreeMem(pHash);
	#endif
	/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 Hash table
	@Input pKey Pointer to the key.
	@Input v The value associated with the key.
	@Return IMG_TRUE - success
	IMG_FALSE - failure
	/ /*************************************************************************/
	IMG_INTERNAL IMG_BOOL
	HASH_Insert_Extended (HASH_TABLE pHash, void pKey, uintptr_t v)
	{
	BUCKET *pBucket;

	PVR_ASSERT (pHash != NULL);

	if (pHash == NULL)
	{
	PVR_DPF((PVR_DBG_ERROR, "HASH_Insert_Extended: invalid parameter"));
	return IMG_FALSE;
	}

	#if defined(__linux__) && defined(__KERNEL__)
	pBucket = OSAllocMemNoStats(sizeof(BUCKET) + pHash->uKeySize);
	#else
	pBucket = OSAllocMem(sizeof(BUCKET) + pHash->uKeySize);
	#endif
	if (pBucket == NULL)
	{
	return IMG_FALSE;
	}

	pBucket->v = v;
	/* PRQA S 0432,0541 1 / / ignore warning about dynamic array k (linux)*/
	OSCachedMemCopy(pBucket->k, pKey, pHash->uKeySize);

	_ChainInsert (pHash, pBucket, pHash->ppBucketTable, pHash->uSize);

	pHash->uCount++;

	/* check if we need to think about re-balancing */
	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 Hash table
	@Input k The key value.
	@Input v The value associated with the key.
	@Return IMG_TRUE - success.
	IMG_FALSE - failure.
	/ /*************************************************************************/
	IMG_INTERNAL IMG_BOOL
	HASH_Insert (HASH_TABLE *pHash, uintptr_t k, uintptr_t 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 Hash table
	@Input pKey Pointer to key.
	@Return 0 if the key is missing, or the value associated with the key.
	/ /*************************************************************************/
	IMG_INTERNAL uintptr_t
	HASH_Remove_Extended(HASH_TABLE pHash, void pKey)
	{
	BUCKET **ppBucket;
	IMG_UINT32 uIndex;

	PVR_ASSERT (pHash != NULL);

	if (pHash == 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 != 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;
	uintptr_t v = pBucket->v;
	(*ppBucket) = pBucket->pNext;

	#if defined(__linux__) && defined(__KERNEL__)
	OSFreeMemNoStats(pBucket);
	#else
	OSFreeMem(pBucket);
	#endif
	/not nulling original pointer, already overwritten/

	pHash->uCount--;

	/* check if we need to think about re-balancing */
	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));
	}

	return v;
	}
	}
	return 0;
	}

	/************************************************************************/ /!
	@Function HASH_Remove
	@Description Remove a key value pair from a hash table created
	with HASH_Create.
	@Input pHash Hash table
	@Input k The key
	@Return 0 if the key is missing, or the value associated with the key.
	/ /*************************************************************************/
	IMG_INTERNAL uintptr_t
	HASH_Remove (HASH_TABLE *pHash, uintptr_t 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 Hash table
	@Input pKey Pointer to the key.
	@Return 0 if the key is missing, or the value associated with the key.
	/ /*************************************************************************/
	IMG_INTERNAL uintptr_t
	HASH_Retrieve_Extended (HASH_TABLE pHash, void pKey)
	{
	BUCKET **ppBucket;
	IMG_UINT32 uIndex;

	PVR_ASSERT (pHash != NULL);

	if (pHash == 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 != 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;
	uintptr_t v = pBucket->v;

	return v;
	}
	}
	return 0;
	}

	/************************************************************************/ /!
	@Function HASH_Retrieve
	@Description Retrieve a value from a hash table created with
	HASH_Create.
	@Input pHash Hash table
	@Input k The key
	@Return 0 if the key is missing, or the value associated with the key.
	/ /*************************************************************************/
	IMG_INTERNAL uintptr_t
	HASH_Retrieve (HASH_TABLE *pHash, uintptr_t k)
	{
	return HASH_Retrieve_Extended(pHash, &k);
	}

	/************************************************************************/ /!
	@Function HASH_Iterate
	@Description Iterate over every entry in the hash table
	@Input pHash - Hash table to iterate
	@Input pfnCallback - Callback to call with the key and data for each
	entry in the hash table
	@Return Callback error if any, otherwise PVRSRV_OK
	/ /*************************************************************************/
	IMG_INTERNAL 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 != NULL)
	{
	PVRSRV_ERROR eError;
	BUCKET *pNextBucket = pBucket->pNext;

	eError = pfnCallback((uintptr_t) ((void ) (pBucket->k)), (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 Hash table
	/ /*************************************************************************/
	void
	HASH_Dump (HASH_TABLE *pHash)
	{
	IMG_UINT32 uIndex;
	IMG_UINT32 uMaxLength=0;
	IMG_UINT32 uEmptyCount=0;

	PVR_ASSERT (pHash != NULL);
	for (uIndex=0; uIndex<pHash->uSize; uIndex++)
	{
	BUCKET *pBucket;
	IMG_UINT32 uLength = 0;
	if (pHash->ppBucketTable[uIndex] == NULL)
	{
	uEmptyCount++;
	}
	for (pBucket=pHash->ppBucketTable[uIndex];
	pBucket != 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