1 files changed, 506 insertions, 0 deletions
diff --git a/drivers/staging/cdv/pvr/services4/srvkm/common/hash.c b/drivers/staging/cdv/pvr/services4/srvkm/common/hash.c
new file mode 100644
index 000000000000..e5dd7815b49e
--- /dev/null
+++ b/drivers/staging/cdv/pvr/services4/srvkm/common/hash.c
@@ -0,0 +1,506 @@
+/**********************************************************************
+ *
+ * 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)
+		{
+			OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(BUCKET*) * uNewSize, ppNewTable, IMG_NULL);
+			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 && *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