//========= Copyright © 1996-2005, Valve Corporation, All rights reserved. ============//
//
// Purpose: 
//
// $NoKeywords: $
//
//=============================================================================//

#ifndef UTLHASH_H
#define UTLHASH_H
#pragma once

#include <assert.h>
#include "utlmemory.h"
#include "utlvector.h"
#include "utlfixedlinkedlist.h"
#include "commonmacros.h"

typedef unsigned int UtlHashHandle_t;

template<class Data>
class CUtlHash
{
public:

	// compare and key functions - implemented by the 
	typedef bool (*CompareFunc_t)( Data const&, Data const& );
	typedef unsigned int (*KeyFunc_t)( Data const& );
	
	// constructor/deconstructor
	CUtlHash( int bucketCount = 0, int growCount = 0, int initCount = 0,
		      CompareFunc_t compareFunc = 0, KeyFunc_t keyFunc = 0 );
	~CUtlHash();

	// invalid handle
	static UtlHashHandle_t InvalidHandle( void )  { return ( UtlHashHandle_t )~0; }
	bool IsValidHandle( UtlHashHandle_t handle ) const;

	// size
	int Count( void );

	// memory
	void Purge( void );

	// insertion methods
	UtlHashHandle_t Insert( Data const &src );
	UtlHashHandle_t AllocEntryFromKey( Data const &src );

	// removal methods
	void Remove( UtlHashHandle_t handle );
	void RemoveAll( void );

	// retrieval methods
	UtlHashHandle_t Find( Data const &src );

	Data &Element( UtlHashHandle_t handle );
	Data const &Element( UtlHashHandle_t handle ) const;
	Data &operator[]( UtlHashHandle_t handle );
	Data const &operator[]( UtlHashHandle_t handle ) const;

	// debugging!!
	void Log( const char *filename );

protected:

	int GetBucketIndex( UtlHashHandle_t handle ) const;
	int GetKeyDataIndex( UtlHashHandle_t handle ) const;
	UtlHashHandle_t BuildHandle( int ndxBucket, int ndxKeyData );

protected:

	// handle upper 16 bits = bucket index (bucket heads)
	// handle lower 16 bits = key index (bucket list)
	typedef CUtlVector<Data> HashBucketList_t;
	CUtlVector<HashBucketList_t>	m_Buckets;
	
	CompareFunc_t					m_CompareFunc;			// function used to handle unique compares on data
	KeyFunc_t						m_KeyFunc;				// function used to generate the key value

	bool							m_bPowerOfTwo;			// if the bucket value is a power of two, 
	unsigned int					m_ModMask;				// use the mod mask to "mod"	
};


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
CUtlHash<Data>::CUtlHash( int bucketCount, int growCount, int initCount,
						  CompareFunc_t compareFunc, KeyFunc_t keyFunc ) :
	m_CompareFunc( compareFunc ),
	m_KeyFunc( keyFunc )
{
	m_Buckets.SetSize( bucketCount );
	for( int ndxBucket = 0; ndxBucket < bucketCount; ndxBucket++ )
	{
		m_Buckets[ndxBucket].SetSize( initCount );
		m_Buckets[ndxBucket].SetGrowSize( growCount );
	}

	// check to see if the bucket count is a power of 2 and set up
	// optimizations appropriately
	m_bPowerOfTwo = IsPowerOfTwo( bucketCount );
	m_ModMask = m_bPowerOfTwo ? (bucketCount-1) : 0;
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
CUtlHash<Data>::~CUtlHash()
{
	Purge();
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline bool CUtlHash<Data>::IsValidHandle( UtlHashHandle_t handle ) const
{
	int ndxBucket = GetBucketIndex( handle );
	int ndxKeyData = GetKeyDataIndex( handle );

	if( ( ndxBucket >= 0 ) && ( ndxBucket < 65536 ) )
	{
		if( ( ndxKeyData >= 0 ) &&  ( ndxKeyData < 65536 ) )
			return true;
	}
	
	return false;
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline int CUtlHash<Data>::Count( void )
{
	int count = 0;

	int bucketCount = m_Buckets.Count();
	for( int ndxBucket = 0; ndxBucket < bucketCount; ndxBucket++ )
	{
		count += m_Buckets[ndxBucket].Count();
	}

	return count;
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline int CUtlHash<Data>::GetBucketIndex( UtlHashHandle_t handle ) const
{
	return ( ( ( handle >> 16 ) & 0x0000ffff ) );
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline int CUtlHash<Data>::GetKeyDataIndex( UtlHashHandle_t handle ) const
{
	return ( handle & 0x0000ffff );
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline UtlHashHandle_t CUtlHash<Data>::BuildHandle( int ndxBucket, int ndxKeyData )
{
	assert( ( ndxBucket >= 0 ) && ( ndxBucket < 65536 ) );
	assert( ( ndxKeyData >= 0 ) && ( ndxKeyData < 65536 ) );

	UtlHashHandle_t handle = ndxKeyData;
	handle |= ( ndxBucket << 16 );

	return handle;
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline void CUtlHash<Data>::Purge( void )
{
	int bucketCount = m_Buckets.Count();
	for( int ndxBucket = 0; ndxBucket < bucketCount; ndxBucket++ )
	{
		m_Buckets[ndxBucket].Purge();
	}

	m_Buckets.Purge();

	m_CompareFunc = 0;
	m_KeyFunc = 0;
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline UtlHashHandle_t CUtlHash<Data>::Insert( Data const &src )
{
	// check to see if that "key" already exists in the "bucket"
	// as "keys" are unique
	UtlHashHandle_t handle = Find( src );
	if( handle != InvalidHandle() )
		return handle;

	// generate the data "key"
	unsigned int key = m_KeyFunc( src );

	// hash the "key" - get the correct hash table "bucket"
	int bucketCount = m_Buckets.Count();
	unsigned int ndxBucket;
	if( m_bPowerOfTwo )
	{
		ndxBucket = ( key & m_ModMask );
	}
	else
	{
		ndxBucket = key % bucketCount;
	}

	// add the key/data pair to the "bucket"
	int	ndx = m_Buckets[ndxBucket].AddToTail( src );

	return ( BuildHandle( ndxBucket, ndx ) );
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline UtlHashHandle_t CUtlHash<Data>::AllocEntryFromKey( Data const &src )
{
	// check to see if that "key" already exists in the "bucket"
	// as "keys" are unique
	UtlHashHandle_t handle = Find( src );
	if( handle != InvalidHandle() )
		return handle;

	// generate the data "key"
	unsigned int key = m_KeyFunc( src );

	// hash the "key" - get the correct hash table "bucket"
	int bucketCount = m_Buckets.Count();
	unsigned int ndxBucket;
	if( m_bPowerOfTwo )
	{
		ndxBucket = ( key & m_ModMask );
	}
	else
	{
		ndxBucket = key % bucketCount;
	}

	// add the key/data pair to the "bucket"
	int	ndx = m_Buckets[ndxBucket].AddToTail();

	return ( BuildHandle( ndxBucket, ndx ) );
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline void CUtlHash<Data>::Remove( UtlHashHandle_t handle )
{
	assert( IsValidHandle( handle ) );

	// check to see if the bucket exists
	int ndxBucket = GetBucketIndex( handle );
	int ndxKeyData = GetKeyDataIndex( handle );

	if( m_Buckets[ndxBucket].IsValidIndex( ndxKeyData ) )
	{
		m_Buckets[ndxBucket].Remove( ndxKeyData );
	}
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline void CUtlHash<Data>::RemoveAll( void )
{
	int bucketCount = m_Buckets.Count();
	for( int ndxBucket = 0; ndxBucket < bucketCount; ndxBucket++ )
	{
		m_Buckets[ndxBucket].RemoveAll();
	}

	m_Buckets.RemoveAll();
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline UtlHashHandle_t CUtlHash<Data>::Find( Data const &src )
{
	// sanity check(s)
	assert( m_KeyFunc );
	assert( m_CompareFunc );

	// generate the data "key"
	unsigned int key = m_KeyFunc( src );

	// hash the "key" - get the correct hash table "bucket"
	int bucketCount = m_Buckets.Count();
	unsigned int ndxBucket;
	if( m_bPowerOfTwo )
	{
		ndxBucket = ( key & m_ModMask );
	}
	else
	{
		ndxBucket = key % bucketCount;
	}

	int ndxKeyData;
	int keyDataCount = m_Buckets[ndxBucket].Count();
	for( ndxKeyData = 0; ndxKeyData < keyDataCount; ndxKeyData++ )
	{
		if( m_CompareFunc( m_Buckets[ndxBucket].Element( ndxKeyData ), src ) )
			break;
	}
	
	if( ndxKeyData == keyDataCount )
		return ( InvalidHandle() );

	return ( BuildHandle( ndxBucket, ndxKeyData ) );
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline Data &CUtlHash<Data>::Element( UtlHashHandle_t handle )
{
	int ndxBucket = GetBucketIndex( handle );
	int ndxKeyData = GetKeyDataIndex( handle );

	return ( m_Buckets[ndxBucket].Element( ndxKeyData ) );
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline Data const &CUtlHash<Data>::Element( UtlHashHandle_t handle ) const
{
	int ndxBucket = GetBucketIndex( handle );
	int ndxKeyData = GetKeyDataIndex( handle );

	return ( m_Buckets[ndxBucket].Element( ndxKeyData ) );
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline Data &CUtlHash<Data>::operator[]( UtlHashHandle_t handle )
{
	int ndxBucket = GetBucketIndex( handle );
	int ndxKeyData = GetKeyDataIndex( handle );

	return ( m_Buckets[ndxBucket].Element( ndxKeyData ) );
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline Data const &CUtlHash<Data>::operator[]( UtlHashHandle_t handle ) const
{
	int ndxBucket = GetBucketIndex( handle );
	int ndxKeyData = GetKeyDataIndex( handle );

	return ( m_Buckets[ndxBucket].Element( ndxKeyData ) );
}


//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data>
inline void CUtlHash<Data>::Log( const char *filename )
{
	FILE *pDebugFp;
	pDebugFp = fopen( filename, "w" );
	if( !pDebugFp )
		return;

	int maxBucketSize = 0;
	int numBucketsEmpty = 0;

	int bucketCount = m_Buckets.Count();
	fprintf( pDebugFp, "\n%d Buckets\n", bucketCount ); 

	for( int ndxBucket = 0; ndxBucket < bucketCount; ndxBucket++ )
	{
		int count = m_Buckets[ndxBucket].Count();
		
		if( count > maxBucketSize ) { maxBucketSize = count; }
		if( count == 0 )
			numBucketsEmpty++;

		fprintf( pDebugFp, "Bucket %d: %d\n", ndxBucket, count );
	}

	fprintf( pDebugFp, "\nBucketHeads Used: %d\n", bucketCount - numBucketsEmpty );
	fprintf( pDebugFp, "Max Bucket Size: %d\n", maxBucketSize );

	fclose( pDebugFp );
}

//=============================================================================
// 
// Fast Hash
//
// Number of buckets must be a power of 2.
// Key must be 32-bits (unsigned int).
//
typedef int UtlHashFastHandle_t;

#define UTLHASH_POOL_SCALAR		2

template<class Data> class CUtlHashFast
{
public:

	// Constructor/Deconstructor.
	CUtlHashFast();
	~CUtlHashFast();

	// Memory.
	void Purge( void );

	// Invalid handle.
	static UtlHashFastHandle_t InvalidHandle( void )	{ return ( UtlHashFastHandle_t )~0; }

	// Initialize.
	bool Init( int nBucketCount );

	// Size.
	int Count( void );

	// Insertion.
	UtlHashFastHandle_t Insert( unsigned int uiKey, const Data &data );
	UtlHashFastHandle_t FastInsert( unsigned int uiKey, const Data &data );

	// Removal.
	void Remove( UtlHashFastHandle_t hHash );
	void RemoveAll( void );

	// Retrieval.
	UtlHashFastHandle_t Find( unsigned int uiKey );

	Data &Element( UtlHashFastHandle_t hHash );
	Data const &Element( UtlHashFastHandle_t hHash ) const;
	Data &operator[]( UtlHashFastHandle_t hHash );
	Data const &operator[]( UtlHashFastHandle_t hHash ) const;

//protected:

	struct HashFastData_t
	{
		unsigned int	m_uiKey;
		Data			m_Data;
	};

	unsigned int							m_uiBucketMask;	
	CUtlVector<UtlHashFastHandle_t>			m_aBuckets;
	CUtlFixedLinkedList<HashFastData_t>		m_aDataPool;
};

//-----------------------------------------------------------------------------
// Purpose: Constructor
//-----------------------------------------------------------------------------
template<class Data> CUtlHashFast<Data>::CUtlHashFast()
{
	Purge();
}

//-----------------------------------------------------------------------------
// Purpose: Deconstructor
//-----------------------------------------------------------------------------
template<class Data> CUtlHashFast<Data>::~CUtlHashFast()
{
	Purge();
}

//-----------------------------------------------------------------------------
// Purpose: Destroy dynamically allocated hash data.
//-----------------------------------------------------------------------------
template<class Data> inline void CUtlHashFast<Data>::Purge( void )
{
	m_aBuckets.Purge();
	m_aDataPool.Purge();
}

//-----------------------------------------------------------------------------
// Purpose: Initialize the hash - set bucket count and hash grow amount.
//-----------------------------------------------------------------------------
template<class Data> bool CUtlHashFast<Data>::Init( int nBucketCount )
{
	// Verify the bucket count is power of 2.
	if ( !IsPowerOfTwo( nBucketCount ) )
		return false;

	// Set the bucket size.
	m_aBuckets.SetSize( nBucketCount );
	for ( int iBucket = 0; iBucket < nBucketCount; ++iBucket )
	{
		m_aBuckets[iBucket] = m_aDataPool.InvalidIndex();
	}

	// Set the mod mask.
	m_uiBucketMask = nBucketCount - 1;

	// Calculate the grow size.
	int nGrowSize = UTLHASH_POOL_SCALAR * nBucketCount;
	m_aDataPool.SetGrowSize( nGrowSize );

	return true;
}

//-----------------------------------------------------------------------------
// Purpose: Return the number of elements in the hash.
//-----------------------------------------------------------------------------
template<class Data> inline int CUtlHashFast<Data>::Count( void )
{
	return m_aDataPool.Count();
}

//-----------------------------------------------------------------------------
// Purpose: Insert data into the hash table given its key (unsigned int), with
//          a check to see if the element already exists within the tree.
//-----------------------------------------------------------------------------
template<class Data> inline UtlHashFastHandle_t CUtlHashFast<Data>::Insert( unsigned int uiKey, const Data &data )
{
	// Check to see if that key already exists in the buckets (should be unique).
	UtlHashFastHandle_t hHash = Find( uiKey );
	if( hHash != InvalidHandle() )
		return hHash;

	return FastInsert( uiKey, data );
}

//-----------------------------------------------------------------------------
// Purpose: Insert data into the hash table given its key (unsigned int),
//          without a check to see if the element already exists within the tree.
//-----------------------------------------------------------------------------
template<class Data> inline UtlHashFastHandle_t CUtlHashFast<Data>::FastInsert( unsigned int uiKey, const Data &data )
{
	// Get a new element from the pool.
	int iHashData = m_aDataPool.Alloc( true );
	HashFastData_t *pHashData = &m_aDataPool[iHashData];
	if ( !pHashData )
		return InvalidHandle();

	// Add data to new element.
	pHashData->m_uiKey = uiKey;
	pHashData->m_Data = data;
				
	// Link element.
	int iBucket = ( uiKey & m_uiBucketMask );
	m_aDataPool.LinkBefore( m_aBuckets[iBucket], iHashData );
	m_aBuckets[iBucket] = iHashData;
	
	return iHashData;	
}

//-----------------------------------------------------------------------------
// Purpose: Remove a given element from the hash.
//-----------------------------------------------------------------------------
template<class Data> inline void CUtlHashFast<Data>::Remove( UtlHashFastHandle_t hHash )
{
	int iBucket = ( m_aDataPool[hHash].m_uiKey & m_uiBucketMask );
	if ( m_aBuckets[iBucket] == hHash )
	{
		// It is a bucket head.
		m_aBuckets[iBucket] = m_aDataPool.Next( hHash );
	}
	else
	{
		// Not a bucket head.
		m_aDataPool.Unlink( hHash );
	}

	// Remove the element.
	m_aDataPool.Remove( hHash );
}

//-----------------------------------------------------------------------------
// Purpose: Remove all elements from the hash
//-----------------------------------------------------------------------------
template<class Data> inline void CUtlHashFast<Data>::RemoveAll( void )
{
	m_aBuckets.RemoveAll();
	m_aDataPool.RemoveAll();
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template<class Data> inline UtlHashFastHandle_t CUtlHashFast<Data>::Find( unsigned int uiKey )
{
	// hash the "key" - get the correct hash table "bucket"
	int iBucket = ( uiKey & m_uiBucketMask );
	if ( m_aBuckets[iBucket] == m_aDataPool.InvalidIndex() )
		return InvalidHandle();

	for ( int iElement = m_aBuckets[iBucket]; iElement != m_aDataPool.InvalidIndex(); iElement = m_aDataPool.Next( iElement ) )
	{
		if ( m_aDataPool[iElement].m_uiKey == uiKey )
			return iElement;
	}

	return InvalidHandle();
}

//-----------------------------------------------------------------------------
// Purpose: Return data given a hash handle.
//-----------------------------------------------------------------------------
template<class Data> inline Data &CUtlHashFast<Data>::Element( UtlHashFastHandle_t hHash )
{
	return ( m_aDataPool[hHash].m_Data );
}

//-----------------------------------------------------------------------------
// Purpose: Return data given a hash handle.
//-----------------------------------------------------------------------------
template<class Data> inline Data const &CUtlHashFast<Data>::Element( UtlHashFastHandle_t hHash ) const
{
	return ( m_aDataPool[hHash].m_Data );
}

//-----------------------------------------------------------------------------
// Purpose: Return data given a hash handle.
//-----------------------------------------------------------------------------
template<class Data> inline Data &CUtlHashFast<Data>::operator[]( UtlHashFastHandle_t hHash )
{
	return ( m_aDataPool[hHash].m_Data );
}

//-----------------------------------------------------------------------------
// Purpose: Return data given a hash handle.
//-----------------------------------------------------------------------------
template<class Data> inline Data const &CUtlHashFast<Data>::operator[]( UtlHashFastHandle_t hHash ) const
{
	return ( m_aDataPool[hHash].m_Data );
}

#endif // UTLHASH_H
