hash.c

Lido PXA270平台开发板的最新BSP,包括源代码

/* -*- c-file-style: "img" -*-
<module>
 * Name         : hash.c
 * Title        : Self scaling hash tables.
 * Author       : Marcus Shawcroft
 * Created      : 14 May 2003
 *
 * Copyright    : 2003 by Imagination Technologies Limited.
 *                All rights reserved.  No part of this software, either
 *                material or conceptual may be copied or distributed,
 *                transmitted, transcribed, stored in a retrieval system
 *                or translated into any human or computer language in any
 *                form by any means, electronic, mechanical, manual or
 *                other-wise, or disclosed to third parties without the
 *                express written permission of Imagination Technologies
 *                Limited, Unit 8, HomePark Industrial Estate,
 *                King's Langley, Hertfordshire, WD4 8LZ, U.K.
 *
 * 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.
 * 
 * Platform     : ALL
 *
</module>
 */

#include "pvr_debug.h"
#include "img_defs.h"
#include "services.h"
#include "hash.h"
#include "hostfunc.h"
#include "pool.h"

#define PRIVATE_MAX(a,b) ((a)>(b)?(a):(b))

struct _HASH_STATE_
{
	/* pool of struct hash objects */
	POOL *pHashPool;

    /* pool of struct _BUCKET_ objects */
	POOL *pBucketPool;
};

/* Each entry in a hash table is placed into a bucket */
struct _BUCKET_
{
	/* the next bucket on the same chain */
	struct _BUCKET_ *pNext;

	/* entry key */
	IMG_UINTPTR_T k;

	/* entry value */
	IMG_UINTPTR_T v;
};
typedef struct _BUCKET_ BUCKET;

struct _HASH_TABLE_ 
{
	/* the hash table array */
	BUCKET **ppBucketTable;
	
	/* current size of the hash table */
	IMG_UINT32 uSize;	

	/* number of entries currently in the hash table */
	IMG_UINT32 uCount;

	/* the minimum size that the hash table should be re-sized to */
	IMG_UINT32 uMinimumSize;

	HASH_STATE *pHashState;
};

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   HASH_Func

	PURPOSE:    Hash function intended for hashing addresses.
	                	
	PARAMETERS:	In:  p - the key to hash.
	            In:  uSize - the size of the hash table.
	RETURNS:	the hash value.
</function>
------------------------------------------------------------------------------*/
static IMG_UINT32
HASH_Func (IMG_UINTPTR_T p, IMG_UINT32 uSize)
{ 
	IMG_UINT32 uHashKey = (IMG_UINT32) p;
	uHashKey += (uHashKey << 12);
	uHashKey ^= (uHashKey >> 22);
	uHashKey += (uHashKey << 4);
	uHashKey ^= (uHashKey >> 9);
	uHashKey += (uHashKey << 10);
	uHashKey ^= (uHashKey >> 2);
	uHashKey += (uHashKey << 7);
	uHashKey ^= (uHashKey >> 12);
	uHashKey &= (uSize-1);
	return uHashKey;
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   _ChainInsert

	PURPOSE:    Insert a bucket into the appropriate hash table chain.
	                	
	PARAMETERS:	In:  pBucket - the bucket
	            In:  ppBucketTable - the hash table
	            In:  uSize - the size of the hash table
	RETURNS:	None
</function>
-----------------------------------------------------------------------------*/
static void
_ChainInsert (BUCKET *pBucket, BUCKET **ppBucketTable, IMG_UINT32 uSize)
{
	IMG_UINT32 uIndex;

	PVR_ASSERT (pBucket != IMG_NULL);
	PVR_ASSERT (ppBucketTable != IMG_NULL);
	PVR_ASSERT (uSize != 0);

	uIndex = HASH_Func (pBucket->k, uSize);
	pBucket->pNext = ppBucketTable[uIndex];
	ppBucketTable[uIndex] = pBucket;
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   _Rehash

	PURPOSE:    Iterate over every entry in an old hash table and rehash into
	            the new table.
	                	
	PARAMETERS:	In:  ppOldTable - the old hash table
	            In:  uOldSize - the size of the old hash table
	            In:  ppNewTable - the new hash table
	            In:  uNewSize - the size of the new hash table
	RETURNS:	None
</function>
-----------------------------------------------------------------------------*/
static void
_Rehash (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)
		{
			BUCKET *pNextBucket = pBucket->pNext;
			_ChainInsert (pBucket, ppNewTable, uNewSize);
			pBucket = pNextBucket;
		}
    }
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   _Resize

	PURPOSE:    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.
	                	
	PARAMETERS:	In:  pHash - Hash table to resize.
	            In:  uNewSize - Required table size.
	RETURNS:	IMG_TRUE Success
	            IMG_FALSE Failed
</function>
-----------------------------------------------------------------------------*/
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=%d  newsize=%d  count=%d",
				pHash->uSize, uNewSize, pHash->uCount));

		HostAllocMem (PVRSRV_HOST_PAGEABLE_HEAP, 
                      sizeof (BUCKET *) * uNewSize, 
                      (IMG_PVOID*)&ppNewTable, 0);
		if (ppNewTable == IMG_NULL)
            return IMG_FALSE;
        
        for (uIndex=0; uIndex<uNewSize; uIndex++)
            ppNewTable[uIndex] = IMG_NULL;
        _Rehash (pHash->ppBucketTable, pHash->uSize, ppNewTable, uNewSize);
        HostFreeMem (PVRSRV_HOST_PAGEABLE_HEAP, pHash->ppBucketTable);
        pHash->ppBucketTable = ppNewTable;
        pHash->uSize = uNewSize;
    }
    return IMG_TRUE;
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   HASH_Initialise

	PURPOSE:    To initialise the hash module.
	                	
	PARAMETERS:	Out:  pHashState - receives hash state pointer.
	RETURNS:	IMG_TRUE Success
	            IMG_FALSE Failed
</function>
-----------------------------------------------------------------------------*/
IMG_BOOL
HASH_Initialise (HASH_STATE **ppState)
{
	HASH_STATE *pHashState;
	
	PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Initialise ()"));
	PVR_ASSERT (ppState != IMG_NULL);

	HostAllocMem (PVRSRV_HOST_PAGEABLE_HEAP, 
                  sizeof (*pHashState), 
                  (IMG_VOID **)&pHashState, 0);

    if (pHashState==IMG_NULL)
    {
		PVR_DPF ((PVR_DBG_ERROR, "HASH_Initialise ERROR allocating Hash struct"));
    	goto alloc_fail;
	}

    pHashState->pHashPool = POOL_Create ("img-hash", sizeof (HASH_TABLE));
	if (pHashState->pHashPool==IMG_NULL)
	{
		PVR_DPF ((PVR_DBG_ERROR, "HASH_Initialise ERROR allocating Hash pool"));
		goto hash_fail;
	}
	pHashState->pBucketPool = POOL_Create ("img-bucket", sizeof (BUCKET));
	if (pHashState->pBucketPool==IMG_NULL)
	{
		PVR_DPF ((PVR_DBG_ERROR, "HASH_Initialise ERROR allocating Hash bucket"));
		goto bucket_fail;
	}

    *ppState = pHashState;
	return IMG_TRUE;

  bucket_fail:
	POOL_Delete (pHashState->pHashPool);
  hash_fail:
    HostFreeMem (PVRSRV_HOST_PAGEABLE_HEAP, pHashState);
  alloc_fail:
	return IMG_FALSE;
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   HASH_Finalise

	PURPOSE:    To finalise the hash module. All allocated hash tables should
	            be deleted before calling this function.
	                	
	PARAMETERS:	None
	RETURNS:	None
</function>
------------------------------------------------------------------------------*/
void
HASH_Finalise (HASH_STATE *pHashState)
{
	PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Finalise ()"));

	PVR_ASSERT (pHashState != IMG_NULL);
	
	if (pHashState != IMG_NULL)
	{
		POOL_Delete (pHashState->pHashPool);
		POOL_Delete (pHashState->pBucketPool);
		HostFreeMem (PVRSRV_HOST_PAGEABLE_HEAP, pHashState);
	}
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   HASH_Create

	PURPOSE:    Create a self scaling hash table.
	                	
	PARAMETERS:	In:  pHashState - hash module state (from HASH_Initialise)
	            In:  uInitialSize - initial and minimum size of the hash table.
	RETURNS:	IMG_NULL or hash table handle.
</function>
-----------------------------------------------------------------------------*/
HASH_TABLE *
HASH_Create (HASH_STATE *pHashState, IMG_UINT32 uInitialSize)
{
	HASH_TABLE *pHash;
	IMG_UINT32 uIndex;

	PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Create (%d)", uInitialSize));

	PVR_ASSERT (pHashState != IMG_NULL);
	
	pHash = POOL_Alloc (pHashState->pHashPool);
	if (pHash == IMG_NULL)
		return IMG_NULL;
	pHash->pHashState = pHashState;
	pHash->uCount = 0;
	pHash->uSize = uInitialSize;
	pHash->uMinimumSize = uInitialSize;
	HostAllocMem (PVRSRV_HOST_PAGEABLE_HEAP, 
                  sizeof (BUCKET *) * pHash->uSize, 
                  (IMG_PVOID*)&pHash->ppBucketTable, 0);	
	if (pHash->ppBucketTable == IMG_NULL)
    {
		POOL_Free (pHashState->pHashPool, pHash);
		return IMG_NULL;
    }

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

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   HASH_Delete

	PURPOSE:    To delete a hash table, all entries in the table should be
	            removed before calling this function.
	                	
	PARAMETERS:	In:  pHash - hash table
	RETURNS:	None
</function>
-----------------------------------------------------------------------------*/
void
HASH_Delete (HASH_TABLE *pHash)
{
	if (pHash != IMG_NULL)
    {
		PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Delete ()"));
		
		PVR_ASSERT (pHash->uCount==0);
		HostFreeMem(PVRSRV_HOST_PAGEABLE_HEAP, pHash->ppBucketTable);
		POOL_Free (pHash->pHashState->pHashPool, pHash);
    }
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   HASH_Insert

	PURPOSE:    To insert a key value pair into a hash table.
	                	
	PARAMETERS:	In:  pHash - the hash table.
	            In:  k - the key value.
	            In:  v - the value associated with the key.
	RETURNS:	IMG_TRUE Success
	            IMG_FALSE Failed
</function>
-----------------------------------------------------------------------------*/
IMG_BOOL
HASH_Insert (HASH_TABLE *pHash, IMG_UINTPTR_T k, IMG_UINTPTR_T v)
{
	BUCKET *pBucket;

	PVR_DPF ((PVR_DBG_MESSAGE,
              "HASH_Insert (hash=0x%x, k=0x%lx, v=0x%lx", pHash, k, v));

	PVR_ASSERT (pHash != IMG_NULL);
	PVR_ASSERT (pHash->pHashState != IMG_NULL);
	
	pBucket = POOL_Alloc (pHash->pHashState->pBucketPool);
	if (pBucket==IMG_NULL)
		return IMG_FALSE;
	pBucket->k = k;
	pBucket->v = v;
	_ChainInsert (pBucket, pHash->ppBucketTable, pHash->uSize);
	pHash->uCount++;

	/* check if we need to think about re-balencing */
	if (pHash->uCount << 1 > pHash->uSize)
    {
        /* Ignore the return code from _Resize because the hash table is
           still in a valid state and although not ideally sized, it is still
           functional */
        _Resize (pHash, pHash->uSize << 1);
    }
    
	
	return IMG_TRUE;
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   HASH_Remove

	PURPOSE:    To remove a key value pair from a hash table.
	                	
	PARAMETERS:	In:  pHash - the hash table
	            In:  k - the key
	RETURNS:	0 if the key is missing or the value associated with the key.
</function>
-----------------------------------------------------------------------------*/
IMG_UINTPTR_T
HASH_Remove (HASH_TABLE *pHash, IMG_UINTPTR_T k)
{
	BUCKET **ppBucket;
	IMG_UINT32 uIndex;

	PVR_DPF ((PVR_DBG_MESSAGE, "HASH_Remove (hash=<>, k=0x%lx", k));

	PVR_ASSERT (pHash != IMG_NULL);
	PVR_ASSERT (pHash->pHashState != IMG_NULL);
	
	uIndex = HASH_Func (k, pHash->uSize);
  
	for (ppBucket = &(pHash->ppBucketTable[uIndex]);
         *ppBucket != IMG_NULL;
         ppBucket = &((*ppBucket)->pNext))
		if ((*ppBucket)->k == k)
		{
			BUCKET *pBucket = *ppBucket;
			IMG_UINTPTR_T v = pBucket->v;
			(*ppBucket) = pBucket->pNext;
			POOL_Free (pHash->pHashState->pBucketPool, pBucket);
			pHash->uCount--;

			/* check if we need to think about re-balencing */
			if (pHash->uSize > (pHash->uCount << 2) &&
                pHash->uSize > pHash->uMinimumSize)
            {
                /* Ignore the return code from _Resize because the
                   hash table is still in a valid state and although
                   not ideally sized, it is still functional */
				_Resize (pHash,
                         PRIVATE_MAX (pHash->uSize >> 1,
                                      pHash->uMinimumSize));
            }
            
			PVR_DPF ((PVR_DBG_MESSAGE,
                      "  HASH_Remove (hash=0x%x, k=0x%lx) = 0x%lx",
                      pHash, k, v));
			return v;
		}
	PVR_DPF ((PVR_DBG_MESSAGE,
              "  HASH_Remove (hash=0x%x, k=0x%lx) = 0x0 !!!!", pHash, k));
	return 0;
}

#ifdef HASH_TRACE
/*----------------------------------------------------------------------------
<function>
	FUNCTION:   HASH_Dump

	PURPOSE:    To dump the contents of a hash table in human readable form.
	                	
	PARAMETERS:	In:  pHash - the hash table
	RETURNS:	None
</function>
-----------------------------------------------------------------------------*/
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);
    }

	printf ("hash table: uMinimumSize=%d  size=%d  count=%d",
			pHash->uMinimumSize, pHash->uSize, pHash->uCount);
	printf ("  empty=%d  max=%d", uEmptyCount, uMaxLength);
}
#endif