drivers/gpu/pvr/hash.c - kernel/panda - Git at Google

 /**********************************************************************
  *
  * Copyright (C) Imagination Technologies Ltd. All rights reserved.
  *
  * This program is free software; you can redistribute it and/or modify it
  * under the terms and conditions of the GNU General Public License,
  * version 2, as published by the Free Software Foundation.
  *
  * This program is distributed in the hope it will be useful but, except
  * as otherwise stated in writing, without any warranty; without even the
  * implied warranty of merchantability or fitness for a particular purpose.
  * See the GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License along with
  * this program; if not, write to the Free Software Foundation, Inc.,
  * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * The full GNU General Public License is included in this distribution in
  * the file called "COPYING".
  *
  * Contact Information:
  * Imagination Technologies Ltd. <gpl-support@imgtec.com>
  * Home Park Estate, Kings Langley, Herts, WD4 8LZ, UK
  *
  ******************************************************************************/

 #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)))

 struct _BUCKET_
 {

 	struct _BUCKET_ *pNext;


 	IMG_UINTPTR_T v;


 	IMG_UINTPTR_T k[];
 };
 typedef struct _BUCKET_ BUCKET;

 struct _HASH_TABLE_
 {

 	BUCKET **ppBucketTable;


 	IMG_UINT32 uSize;


 	IMG_UINT32 uCount;


 	IMG_UINT32 uMinimumSize;


 	IMG_UINT32 uKeySize;


 	HASH_FUNC *pfnHashFunc;


 	HASH_KEY_COMP *pfnKeyComp;
 };

 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;
 }

 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;
 }

 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);
 	pBucket->pNext = ppBucketTable[uIndex];
 	ppBucketTable[uIndex] = pBucket;

 	return PVRSRV_OK;
 }

 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;
 }

 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);

         pHash->ppBucketTable = ppNewTable;
         pHash->uSize = uNewSize;
     }
     return IMG_TRUE;
 }


 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);

 		return IMG_NULL;
     }

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

 HASH_TABLE * HASH_Create (IMG_UINT32 uInitialLen)
 {
 	return HASH_Create_Extended(uInitialLen, sizeof(IMG_UINTPTR_T),
 		&HASH_Func_Default, &HASH_Key_Comp_Default);
 }

 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);

     }
 }

 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;

 	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++;


 	if (pHash->uCount << 1 > pHash->uSize)
     {


         _Resize (pHash, pHash->uSize << 1);
     }


 	return IMG_TRUE;
 }

 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);
 }

 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))
 	{

 		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);


 			pHash->uCount--;


 			if (pHash->uSize > (pHash->uCount << 2) &&
                 pHash->uSize > pHash->uMinimumSize)
             {


 				_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;
 }

 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);
 }

 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))
 	{

 		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;
 }

 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);
 }

 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);


 			if (eError != PVRSRV_OK)
 				return eError;

 			pBucket = pNextBucket;
 		}
 	}
 	return PVRSRV_OK;
 }

 #ifdef HASH_TRACE
 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
	/**********************************************************************
	*
	* Copyright (C) Imagination Technologies Ltd. All rights reserved.
	*
	* This program is free software; you can redistribute it and/or modify it
	* under the terms and conditions of the GNU General Public License,
	* version 2, as published by the Free Software Foundation.
	*
	* This program is distributed in the hope it will be useful but, except
	* as otherwise stated in writing, without any warranty; without even the
	* implied warranty of merchantability or fitness for a particular purpose.
	* See the GNU General Public License for more details.
	*
	* You should have received a copy of the GNU General Public License along with
	* this program; if not, write to the Free Software Foundation, Inc.,
	* 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* The full GNU General Public License is included in this distribution in
	* the file called "COPYING".
	*
	* Contact Information:
	* Imagination Technologies Ltd. <gpl-support@imgtec.com>
	* Home Park Estate, Kings Langley, Herts, WD4 8LZ, UK
	*
	******************************************************************************/

	#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)))

	struct _BUCKET_
	{

	struct _BUCKET_ *pNext;


	IMG_UINTPTR_T v;


	IMG_UINTPTR_T k[];
	};
	typedef struct _BUCKET_ BUCKET;

	struct _HASH_TABLE_
	{

	BUCKET **ppBucketTable;


	IMG_UINT32 uSize;


	IMG_UINT32 uCount;


	IMG_UINT32 uMinimumSize;


	IMG_UINT32 uKeySize;


	HASH_FUNC *pfnHashFunc;


	HASH_KEY_COMP *pfnKeyComp;
	};

	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;
	}

	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;
	}

	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);
	pBucket->pNext = ppBucketTable[uIndex];
	ppBucketTable[uIndex] = pBucket;

	return PVRSRV_OK;
	}

	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;
	}

	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);

	pHash->ppBucketTable = ppNewTable;
	pHash->uSize = uNewSize;
	}
	return IMG_TRUE;
	}


	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);

	return IMG_NULL;
	}

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

	HASH_TABLE * HASH_Create (IMG_UINT32 uInitialLen)
	{
	return HASH_Create_Extended(uInitialLen, sizeof(IMG_UINTPTR_T),
	&HASH_Func_Default, &HASH_Key_Comp_Default);
	}

	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);

	}
	}

	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;

	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++;


	if (pHash->uCount << 1 > pHash->uSize)
	{


	_Resize (pHash, pHash->uSize << 1);
	}


	return IMG_TRUE;
	}

	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);
	}

	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))
	{

	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);


	pHash->uCount--;


	if (pHash->uSize > (pHash->uCount << 2) &&
	pHash->uSize > pHash->uMinimumSize)
	{


	_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;
	}

	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);
	}

	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))
	{

	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;
	}

	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);
	}

	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);


	if (eError != PVRSRV_OK)
	return eError;

	pBucket = pNextBucket;
	}
	}
	return PVRSRV_OK;
	}

	#ifdef HASH_TRACE
	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