Fix line endings. WHAMMY.

1 files changed, 936 insertions, 936 deletions

diff --git a/sp/src/public/tier1/utlhash.h b/sp/src/public/tier1/utlhash.h
index 72751ffc..7207b597 100644
--- a/sp/src/public/tier1/utlhash.h
+++ b/sp/src/public/tier1/utlhash.h
@@ -1,936 +1,936 @@
-//========= Copyright Valve Corporation, All rights reserved. ============//

-//

-// Purpose: 

-//

-// $NoKeywords: $

-//

-// Serialization/unserialization buffer

-//=============================================================================//

-

-#ifndef UTLHASH_H

-#define UTLHASH_H

-#pragma once

-

-#include <assert.h>

-#include <limits.h>

-#include "utlmemory.h"

-#include "utlvector.h"

-#include "utllinkedlist.h"

-#include "utllinkedlist.h"

-#include "commonmacros.h"

-#include "generichash.h"

-

-typedef unsigned int UtlHashHandle_t;

-

-template<class Data, typename C = bool (*)( Data const&, Data const& ), typename K = unsigned int (*)( Data const& ) >

-class CUtlHash

-{

-public:

-	// compare and key functions - implemented by the 

-	typedef C CompareFunc_t;

-	typedef K KeyFunc_t;

-	

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

-

-	// memory

-	void Purge( void );

-

-	// insertion methods

-	UtlHashHandle_t Insert( Data const &src );

-	UtlHashHandle_t Insert( Data const &src, bool *pDidInsert );

-	UtlHashHandle_t AllocEntryFromKey( Data const &src );

-

-	// removal methods

-	void Remove( UtlHashHandle_t handle );

-	void RemoveAll();

-

-	// retrieval methods

-	UtlHashHandle_t Find( Data const &src ) const;

-

-	Data &Element( UtlHashHandle_t handle );

-	Data const &Element( UtlHashHandle_t handle ) const;

-	Data &operator[]( UtlHashHandle_t handle );

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

-

-	UtlHashHandle_t GetFirstHandle() const;

-	UtlHashHandle_t GetNextHandle( UtlHashHandle_t h ) 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 ) const;

-

-	bool DoFind( Data const &src, unsigned int *pBucket, int *pIndex ) const;

-

-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, typename C, typename K>

-CUtlHash<Data, C, K>::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, typename C, typename K>

-CUtlHash<Data, C, K>::~CUtlHash()

-{

-	Purge();

-}

-

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline bool CUtlHash<Data, C, K>::IsValidHandle( UtlHashHandle_t handle ) const

-{

-	int ndxBucket = GetBucketIndex( handle );

-	int ndxKeyData = GetKeyDataIndex( handle );

-

-	// ndxBucket and ndxKeyData can't possibly be less than zero -- take a 

-	// look at the definition of the Get..Index functions for why. However,

-	// if you override those functions, you will need to override this one

-	// as well. 

-	if( /*( ndxBucket >= 0 ) && */      ( ndxBucket < m_Buckets.Count() ) )

-	{

-		if( /*( ndxKeyData >= 0 ) && */ ( ndxKeyData < m_Buckets[ndxBucket].Count() ) )

-			return true;

-	}

-	

-	return false;

-}

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline int CUtlHash<Data, C, K>::Count( void ) const

-{

-	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, typename C, typename K>

-inline int CUtlHash<Data, C, K>::GetBucketIndex( UtlHashHandle_t handle ) const

-{

-	return ( ( ( handle >> 16 ) & 0x0000ffff ) );

-}

-

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline int CUtlHash<Data, C, K>::GetKeyDataIndex( UtlHashHandle_t handle ) const

-{

-	return ( handle & 0x0000ffff );

-}

-

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline UtlHashHandle_t CUtlHash<Data, C, K>::BuildHandle( int ndxBucket, int ndxKeyData ) const

-{

-	assert( ( ndxBucket >= 0 ) && ( ndxBucket < 65536 ) );

-	assert( ( ndxKeyData >= 0 ) && ( ndxKeyData < 65536 ) );

-

-	UtlHashHandle_t handle = ndxKeyData;

-	handle |= ( ndxBucket << 16 );

-

-	return handle;

-}

-

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline void CUtlHash<Data, C, K>::Purge( void )

-{

-	int bucketCount = m_Buckets.Count();

-	for( int ndxBucket = 0; ndxBucket < bucketCount; ndxBucket++ )

-	{

-		m_Buckets[ndxBucket].Purge();

-	}

-}

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline bool CUtlHash<Data, C, K>::DoFind( Data const &src, unsigned int *pBucket, int *pIndex ) const

-{

-	// generate the data "key"

-	unsigned int key = m_KeyFunc( src );

-

-	// hash the "key" - get the correct hash table "bucket"

-	unsigned int ndxBucket;

-	if( m_bPowerOfTwo )

-	{

-		*pBucket = ndxBucket = ( key & m_ModMask );

-	}

-	else

-	{

-		int bucketCount = m_Buckets.Count();

-		*pBucket = ndxBucket = key % bucketCount;

-	}

-

-	int ndxKeyData;

-	const CUtlVector<Data> &bucket = m_Buckets[ndxBucket];

-	int keyDataCount = bucket.Count();

-	for( ndxKeyData = 0; ndxKeyData < keyDataCount; ndxKeyData++ )

-	{

-		if( m_CompareFunc( bucket.Element( ndxKeyData ), src ) )

-			break;

-	}

-

-	if( ndxKeyData == keyDataCount )

-		return false;

-

-	*pIndex = ndxKeyData;

-	return true;

-}

-

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline UtlHashHandle_t CUtlHash<Data, C, K>::Find( Data const &src ) const

-{

-	unsigned int ndxBucket;

-	int ndxKeyData;

-

-	if ( DoFind( src, &ndxBucket, &ndxKeyData ) )

-	{

-		return ( BuildHandle( ndxBucket, ndxKeyData ) );

-	}

-	return ( InvalidHandle() );

-}

-

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline UtlHashHandle_t CUtlHash<Data, C, K>::Insert( Data const &src )

-{

-	unsigned int ndxBucket;

-	int ndxKeyData;

-

-	if ( DoFind( src, &ndxBucket, &ndxKeyData ) )

-	{

-		return ( BuildHandle( ndxBucket, ndxKeyData ) );

-	}

-

-	ndxKeyData = m_Buckets[ndxBucket].AddToTail( src );

-

-	return ( BuildHandle( ndxBucket, ndxKeyData ) );

-}

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline UtlHashHandle_t CUtlHash<Data, C, K>::Insert( Data const &src, bool *pDidInsert )

-{

-	unsigned int ndxBucket;

-	int ndxKeyData;

-

-	if ( DoFind( src, &ndxBucket, &ndxKeyData ) )

-	{

-		*pDidInsert = false;

-		return ( BuildHandle( ndxBucket, ndxKeyData ) );

-	}

-

-	*pDidInsert = true;

-	ndxKeyData = m_Buckets[ndxBucket].AddToTail( src );

-

-	return ( BuildHandle( ndxBucket, ndxKeyData ) );

-}

-

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline UtlHashHandle_t CUtlHash<Data, C, K>::AllocEntryFromKey( Data const &src )

-{

-	unsigned int ndxBucket;

-	int ndxKeyData;

-

-	if ( DoFind( src, &ndxBucket, &ndxKeyData ) )

-	{

-		return ( BuildHandle( ndxBucket, ndxKeyData ) );

-	}

-

-	ndxKeyData = m_Buckets[ndxBucket].AddToTail();

-

-	return ( BuildHandle( ndxBucket, ndxKeyData ) );

-}

-

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline void CUtlHash<Data, C, K>::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].FastRemove( ndxKeyData );

-	}

-}

-

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline void CUtlHash<Data, C, K>::RemoveAll()

-{

-	int bucketCount = m_Buckets.Count();

-	for( int ndxBucket = 0; ndxBucket < bucketCount; ndxBucket++ )

-	{

-		m_Buckets[ndxBucket].RemoveAll();

-	}

-}

-

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline Data &CUtlHash<Data, C, K>::Element( UtlHashHandle_t handle )

-{

-	int ndxBucket = GetBucketIndex( handle );

-	int ndxKeyData = GetKeyDataIndex( handle );

-

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

-}

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline Data const &CUtlHash<Data, C, K>::Element( UtlHashHandle_t handle ) const

-{

-	int ndxBucket = GetBucketIndex( handle );

-	int ndxKeyData = GetKeyDataIndex( handle );

-

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

-}

-

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline Data &CUtlHash<Data, C, K>::operator[]( UtlHashHandle_t handle )

-{

-	int ndxBucket = GetBucketIndex( handle );

-	int ndxKeyData = GetKeyDataIndex( handle );

-

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

-}

-

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline Data const &CUtlHash<Data, C, K>::operator[]( UtlHashHandle_t handle ) const

-{

-	int ndxBucket = GetBucketIndex( handle );

-	int ndxKeyData = GetKeyDataIndex( handle );

-

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

-}

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline UtlHashHandle_t CUtlHash<Data, C, K>::GetFirstHandle() const

-{

-	return GetNextHandle( ( UtlHashHandle_t )-1 );

-}

-

-template<class Data, typename C, typename K>

-inline UtlHashHandle_t CUtlHash<Data, C, K>::GetNextHandle( UtlHashHandle_t handle ) const

-{

-	++handle; // start at the first possible handle after the one given

-

-	int bi = GetBucketIndex( handle );

-	int ki =  GetKeyDataIndex( handle );

-

-	int nBuckets = m_Buckets.Count();

-	for ( ; bi < nBuckets; ++bi )

-	{

-		if ( ki < m_Buckets[ bi ].Count() )

-			return BuildHandle( bi, ki );

-

-		ki = 0;

-	}

-

-	return InvalidHandle();

-}

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, typename C, typename K>

-inline void CUtlHash<Data, C, K>::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

-

-class CUtlHashFastNoHash

-{

-public:

-	static int Hash( int key, int bucketMask )

-	{

-		return ( key & bucketMask );

-	}

-};

-

-class CUtlHashFastGenericHash

-{

-public:

-	static int Hash( int key, int bucketMask )

-	{

-		return ( HashIntConventional( key ) & bucketMask );

-	}

-};

-

-template<class Data, class HashFuncs = CUtlHashFastNoHash > 

-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:

-

-	// Templatized for memory tracking purposes

-	template <typename HashData>

-	struct HashFastData_t_

-	{

-		unsigned int	m_uiKey;

-		HashData	m_Data;

-	};

-

-	typedef HashFastData_t_<Data> HashFastData_t;

-

-	unsigned int						m_uiBucketMask;	

-	CUtlVector<UtlHashFastHandle_t>		m_aBuckets;

-	CUtlFixedLinkedList<HashFastData_t>	m_aDataPool;

-};

-

-//-----------------------------------------------------------------------------

-// Purpose: Constructor

-//-----------------------------------------------------------------------------

-template<class Data, class HashFuncs> CUtlHashFast<Data,HashFuncs>::CUtlHashFast()

-{

-	Purge();

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Deconstructor

-//-----------------------------------------------------------------------------

-template<class Data, class HashFuncs> CUtlHashFast<Data,HashFuncs>::~CUtlHashFast()

-{

-	Purge();

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Destroy dynamically allocated hash data.

-//-----------------------------------------------------------------------------

-template<class Data, class HashFuncs> inline void CUtlHashFast<Data,HashFuncs>::Purge( void )

-{

-	m_aBuckets.Purge();

-	m_aDataPool.Purge();

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Initialize the hash - set bucket count and hash grow amount.

-//-----------------------------------------------------------------------------

-template<class Data, class HashFuncs> bool CUtlHashFast<Data,HashFuncs>::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, class HashFuncs> inline int CUtlHashFast<Data,HashFuncs>::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, class HashFuncs> inline UtlHashFastHandle_t CUtlHashFast<Data,HashFuncs>::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, class HashFuncs> inline UtlHashFastHandle_t CUtlHashFast<Data,HashFuncs>::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 = HashFuncs::Hash( 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, class HashFuncs> inline void CUtlHashFast<Data,HashFuncs>::Remove( UtlHashFastHandle_t hHash )

-{

-	int iBucket = HashFuncs::Hash( 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, class HashFuncs> inline void CUtlHashFast<Data,HashFuncs>::RemoveAll( void )

-{

-	m_aBuckets.RemoveAll();

-	m_aDataPool.RemoveAll();

-}

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, class HashFuncs> inline UtlHashFastHandle_t CUtlHashFast<Data,HashFuncs>::Find( unsigned int uiKey )

-{

-	// hash the "key" - get the correct hash table "bucket"

-	int iBucket = HashFuncs::Hash( uiKey, m_uiBucketMask );

-

-	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, class HashFuncs> inline Data &CUtlHashFast<Data,HashFuncs>::Element( UtlHashFastHandle_t hHash )

-{

-	return ( m_aDataPool[hHash].m_Data );

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Return data given a hash handle.

-//-----------------------------------------------------------------------------

-template<class Data, class HashFuncs> inline Data const &CUtlHashFast<Data,HashFuncs>::Element( UtlHashFastHandle_t hHash ) const

-{

-	return ( m_aDataPool[hHash].m_Data );

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Return data given a hash handle.

-//-----------------------------------------------------------------------------

-template<class Data, class HashFuncs> inline Data &CUtlHashFast<Data,HashFuncs>::operator[]( UtlHashFastHandle_t hHash )

-{

-	return ( m_aDataPool[hHash].m_Data );

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Return data given a hash handle.

-//-----------------------------------------------------------------------------

-template<class Data, class HashFuncs> inline Data const &CUtlHashFast<Data,HashFuncs>::operator[]( UtlHashFastHandle_t hHash ) const

-{

-	return ( m_aDataPool[hHash].m_Data );

-}

-

-//=============================================================================

-// 

-// Fixed Hash

-//

-// Number of buckets must be a power of 2.

-// Key must be 32-bits (unsigned int).

-//

-typedef int UtlHashFixedHandle_t;

-

-template <int NUM_BUCKETS>

-class CUtlHashFixedGenericHash

-{

-public:

-	static int Hash( int key, int bucketMask )

-	{

-		int hash = HashIntConventional( key );

-		if ( NUM_BUCKETS <= USHRT_MAX )

-		{

-			hash ^= ( hash >> 16 );

-		}

-		if ( NUM_BUCKETS <= UCHAR_MAX )

-		{

-			hash ^= ( hash >> 8 );

-		}

-		return ( hash & bucketMask );

-	}

-};

-

-template<class Data, int NUM_BUCKETS, class CHashFuncs = CUtlHashFastNoHash > 

-class CUtlHashFixed

-{

-public:

-

-	// Constructor/Deconstructor.

-	CUtlHashFixed();

-	~CUtlHashFixed();

-

-	// Memory.

-	void Purge( void );

-

-	// Invalid handle.

-	static UtlHashFixedHandle_t InvalidHandle( void )	{ return ( UtlHashFixedHandle_t )~0; }

-

-	// Size.

-	int Count( void );

-

-	// Insertion.

-	UtlHashFixedHandle_t Insert( unsigned int uiKey, const Data &data );

-	UtlHashFixedHandle_t FastInsert( unsigned int uiKey, const Data &data );

-

-	// Removal.

-	void Remove( UtlHashFixedHandle_t hHash );

-	void RemoveAll( void );

-

-	// Retrieval.

-	UtlHashFixedHandle_t Find( unsigned int uiKey );

-

-	Data &Element( UtlHashFixedHandle_t hHash );

-	Data const &Element( UtlHashFixedHandle_t hHash ) const;

-	Data &operator[]( UtlHashFixedHandle_t hHash );

-	Data const &operator[]( UtlHashFixedHandle_t hHash ) const;

-

-	//protected:

-

-	// Templatized for memory tracking purposes

-	template <typename Data_t>

-	struct HashFixedData_t_

-	{

-		unsigned int	m_uiKey;

-		Data_t			m_Data;

-	};

-

-	typedef HashFixedData_t_<Data> HashFixedData_t;

-

-	enum

-	{

-		BUCKET_MASK = NUM_BUCKETS - 1

-	};

-	CUtlPtrLinkedList<HashFixedData_t> m_aBuckets[NUM_BUCKETS];

-	int m_nElements;

-};

-

-//-----------------------------------------------------------------------------

-// Purpose: Constructor

-//-----------------------------------------------------------------------------

-template<class Data, int NUM_BUCKETS, class HashFuncs> CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::CUtlHashFixed()

-{

-	Purge();

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Deconstructor

-//-----------------------------------------------------------------------------

-template<class Data, int NUM_BUCKETS, class HashFuncs> CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::~CUtlHashFixed()

-{

-	Purge();

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Destroy dynamically allocated hash data.

-//-----------------------------------------------------------------------------

-template<class Data, int NUM_BUCKETS, class HashFuncs> inline void CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::Purge( void )

-{

-	RemoveAll();

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Return the number of elements in the hash.

-//-----------------------------------------------------------------------------

-template<class Data, int NUM_BUCKETS, class HashFuncs> inline int CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::Count( void )

-{

-	return m_nElements;

-}

-

-//-----------------------------------------------------------------------------

-// 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, int NUM_BUCKETS, class HashFuncs> inline UtlHashFixedHandle_t CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::Insert( unsigned int uiKey, const Data &data )

-{

-	// Check to see if that key already exists in the buckets (should be unique).

-	UtlHashFixedHandle_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, int NUM_BUCKETS, class HashFuncs> inline UtlHashFixedHandle_t CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::FastInsert( unsigned int uiKey, const Data &data )

-{

-	int iBucket = HashFuncs::Hash( uiKey, NUM_BUCKETS - 1 );

-	UtlPtrLinkedListIndex_t iElem = m_aBuckets[iBucket].AddToHead();

-

-	HashFixedData_t *pHashData = &m_aBuckets[iBucket][iElem];

-

-	Assert( (UtlPtrLinkedListIndex_t)pHashData == iElem );

-

-	// Add data to new element.

-	pHashData->m_uiKey = uiKey;

-	pHashData->m_Data = data;

-

-	m_nElements++;

-	return (UtlHashFixedHandle_t)pHashData;	

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Remove a given element from the hash.

-//-----------------------------------------------------------------------------

-template<class Data, int NUM_BUCKETS, class HashFuncs> inline void CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::Remove( UtlHashFixedHandle_t hHash )

-{

-	HashFixedData_t *pHashData = (HashFixedData_t *)hHash;

-	Assert( Find(pHashData->m_uiKey) != InvalidHandle() );

-	int iBucket = HashFuncs::Hash( pHashData->m_uiKey, NUM_BUCKETS - 1 );

-	m_aBuckets[iBucket].Remove( (UtlPtrLinkedListIndex_t)pHashData );

-	m_nElements--;

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Remove all elements from the hash

-//-----------------------------------------------------------------------------

-template<class Data, int NUM_BUCKETS, class HashFuncs> inline void CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::RemoveAll( void )

-{

-	for ( int i = 0; i < NUM_BUCKETS; i++ )

-	{

-		m_aBuckets[i].RemoveAll();

-	}

-	m_nElements = 0;

-}

-

-//-----------------------------------------------------------------------------

-//-----------------------------------------------------------------------------

-template<class Data, int NUM_BUCKETS, class HashFuncs> inline UtlHashFixedHandle_t CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::Find( unsigned int uiKey )

-{

-	int iBucket = HashFuncs::Hash( uiKey, NUM_BUCKETS - 1 );

-	CUtlPtrLinkedList<HashFixedData_t> &bucket = m_aBuckets[iBucket];

-

-	for ( UtlPtrLinkedListIndex_t iElement = bucket.Head(); iElement != bucket.InvalidIndex(); iElement = bucket.Next( iElement ) )

-	{

-		if ( bucket[iElement].m_uiKey == uiKey )

-			return (UtlHashFixedHandle_t)iElement;

-	}

-

-	return InvalidHandle();

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Return data given a hash handle.

-//-----------------------------------------------------------------------------

-template<class Data, int NUM_BUCKETS, class HashFuncs> inline Data &CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::Element( UtlHashFixedHandle_t hHash )

-{

-	return ((HashFixedData_t *)hHash)->m_Data;

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Return data given a hash handle.

-//-----------------------------------------------------------------------------

-template<class Data, int NUM_BUCKETS, class HashFuncs> inline Data const &CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::Element( UtlHashFixedHandle_t hHash ) const

-{

-	return ((HashFixedData_t *)hHash)->m_Data;

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Return data given a hash handle.

-//-----------------------------------------------------------------------------

-template<class Data, int NUM_BUCKETS, class HashFuncs> inline Data &CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::operator[]( UtlHashFixedHandle_t hHash )

-{

-	return ((HashFixedData_t *)hHash)->m_Data;

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Return data given a hash handle.

-//-----------------------------------------------------------------------------

-template<class Data, int NUM_BUCKETS, class HashFuncs> inline Data const &CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::operator[]( UtlHashFixedHandle_t hHash ) const

-{

-	return ((HashFixedData_t *)hHash)->m_Data;

-}

-

-#endif // UTLHASH_H

+//========= Copyright Valve Corporation, All rights reserved. ============//
+//
+// Purpose: 
+//
+// $NoKeywords: $
+//
+// Serialization/unserialization buffer
+//=============================================================================//
+
+#ifndef UTLHASH_H
+#define UTLHASH_H
+#pragma once
+
+#include <assert.h>
+#include <limits.h>
+#include "utlmemory.h"
+#include "utlvector.h"
+#include "utllinkedlist.h"
+#include "utllinkedlist.h"
+#include "commonmacros.h"
+#include "generichash.h"
+
+typedef unsigned int UtlHashHandle_t;
+
+template<class Data, typename C = bool (*)( Data const&, Data const& ), typename K = unsigned int (*)( Data const& ) >
+class CUtlHash
+{
+public:
+	// compare and key functions - implemented by the 
+	typedef C CompareFunc_t;
+	typedef K KeyFunc_t;
+	
+	// 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 ) const;
+
+	// memory
+	void Purge( void );
+
+	// insertion methods
+	UtlHashHandle_t Insert( Data const &src );
+	UtlHashHandle_t Insert( Data const &src, bool *pDidInsert );
+	UtlHashHandle_t AllocEntryFromKey( Data const &src );
+
+	// removal methods
+	void Remove( UtlHashHandle_t handle );
+	void RemoveAll();
+
+	// retrieval methods
+	UtlHashHandle_t Find( Data const &src ) const;
+
+	Data &Element( UtlHashHandle_t handle );
+	Data const &Element( UtlHashHandle_t handle ) const;
+	Data &operator[]( UtlHashHandle_t handle );
+	Data const &operator[]( UtlHashHandle_t handle ) const;
+
+	UtlHashHandle_t GetFirstHandle() const;
+	UtlHashHandle_t GetNextHandle( UtlHashHandle_t h ) 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 ) const;
+
+	bool DoFind( Data const &src, unsigned int *pBucket, int *pIndex ) const;
+
+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, typename C, typename K>
+CUtlHash<Data, C, K>::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, typename C, typename K>
+CUtlHash<Data, C, K>::~CUtlHash()
+{
+	Purge();
+}
+
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline bool CUtlHash<Data, C, K>::IsValidHandle( UtlHashHandle_t handle ) const
+{
+	int ndxBucket = GetBucketIndex( handle );
+	int ndxKeyData = GetKeyDataIndex( handle );
+
+	// ndxBucket and ndxKeyData can't possibly be less than zero -- take a 
+	// look at the definition of the Get..Index functions for why. However,
+	// if you override those functions, you will need to override this one
+	// as well. 
+	if( /*( ndxBucket >= 0 ) && */      ( ndxBucket < m_Buckets.Count() ) )
+	{
+		if( /*( ndxKeyData >= 0 ) && */ ( ndxKeyData < m_Buckets[ndxBucket].Count() ) )
+			return true;
+	}
+	
+	return false;
+}
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline int CUtlHash<Data, C, K>::Count( void ) const
+{
+	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, typename C, typename K>
+inline int CUtlHash<Data, C, K>::GetBucketIndex( UtlHashHandle_t handle ) const
+{
+	return ( ( ( handle >> 16 ) & 0x0000ffff ) );
+}
+
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline int CUtlHash<Data, C, K>::GetKeyDataIndex( UtlHashHandle_t handle ) const
+{
+	return ( handle & 0x0000ffff );
+}
+
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline UtlHashHandle_t CUtlHash<Data, C, K>::BuildHandle( int ndxBucket, int ndxKeyData ) const
+{
+	assert( ( ndxBucket >= 0 ) && ( ndxBucket < 65536 ) );
+	assert( ( ndxKeyData >= 0 ) && ( ndxKeyData < 65536 ) );
+
+	UtlHashHandle_t handle = ndxKeyData;
+	handle |= ( ndxBucket << 16 );
+
+	return handle;
+}
+
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline void CUtlHash<Data, C, K>::Purge( void )
+{
+	int bucketCount = m_Buckets.Count();
+	for( int ndxBucket = 0; ndxBucket < bucketCount; ndxBucket++ )
+	{
+		m_Buckets[ndxBucket].Purge();
+	}
+}
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline bool CUtlHash<Data, C, K>::DoFind( Data const &src, unsigned int *pBucket, int *pIndex ) const
+{
+	// generate the data "key"
+	unsigned int key = m_KeyFunc( src );
+
+	// hash the "key" - get the correct hash table "bucket"
+	unsigned int ndxBucket;
+	if( m_bPowerOfTwo )
+	{
+		*pBucket = ndxBucket = ( key & m_ModMask );
+	}
+	else
+	{
+		int bucketCount = m_Buckets.Count();
+		*pBucket = ndxBucket = key % bucketCount;
+	}
+
+	int ndxKeyData;
+	const CUtlVector<Data> &bucket = m_Buckets[ndxBucket];
+	int keyDataCount = bucket.Count();
+	for( ndxKeyData = 0; ndxKeyData < keyDataCount; ndxKeyData++ )
+	{
+		if( m_CompareFunc( bucket.Element( ndxKeyData ), src ) )
+			break;
+	}
+
+	if( ndxKeyData == keyDataCount )
+		return false;
+
+	*pIndex = ndxKeyData;
+	return true;
+}
+
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline UtlHashHandle_t CUtlHash<Data, C, K>::Find( Data const &src ) const
+{
+	unsigned int ndxBucket;
+	int ndxKeyData;
+
+	if ( DoFind( src, &ndxBucket, &ndxKeyData ) )
+	{
+		return ( BuildHandle( ndxBucket, ndxKeyData ) );
+	}
+	return ( InvalidHandle() );
+}
+
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline UtlHashHandle_t CUtlHash<Data, C, K>::Insert( Data const &src )
+{
+	unsigned int ndxBucket;
+	int ndxKeyData;
+
+	if ( DoFind( src, &ndxBucket, &ndxKeyData ) )
+	{
+		return ( BuildHandle( ndxBucket, ndxKeyData ) );
+	}
+
+	ndxKeyData = m_Buckets[ndxBucket].AddToTail( src );
+
+	return ( BuildHandle( ndxBucket, ndxKeyData ) );
+}
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline UtlHashHandle_t CUtlHash<Data, C, K>::Insert( Data const &src, bool *pDidInsert )
+{
+	unsigned int ndxBucket;
+	int ndxKeyData;
+
+	if ( DoFind( src, &ndxBucket, &ndxKeyData ) )
+	{
+		*pDidInsert = false;
+		return ( BuildHandle( ndxBucket, ndxKeyData ) );
+	}
+
+	*pDidInsert = true;
+	ndxKeyData = m_Buckets[ndxBucket].AddToTail( src );
+
+	return ( BuildHandle( ndxBucket, ndxKeyData ) );
+}
+
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline UtlHashHandle_t CUtlHash<Data, C, K>::AllocEntryFromKey( Data const &src )
+{
+	unsigned int ndxBucket;
+	int ndxKeyData;
+
+	if ( DoFind( src, &ndxBucket, &ndxKeyData ) )
+	{
+		return ( BuildHandle( ndxBucket, ndxKeyData ) );
+	}
+
+	ndxKeyData = m_Buckets[ndxBucket].AddToTail();
+
+	return ( BuildHandle( ndxBucket, ndxKeyData ) );
+}
+
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline void CUtlHash<Data, C, K>::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].FastRemove( ndxKeyData );
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline void CUtlHash<Data, C, K>::RemoveAll()
+{
+	int bucketCount = m_Buckets.Count();
+	for( int ndxBucket = 0; ndxBucket < bucketCount; ndxBucket++ )
+	{
+		m_Buckets[ndxBucket].RemoveAll();
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline Data &CUtlHash<Data, C, K>::Element( UtlHashHandle_t handle )
+{
+	int ndxBucket = GetBucketIndex( handle );
+	int ndxKeyData = GetKeyDataIndex( handle );
+
+	return ( m_Buckets[ndxBucket].Element( ndxKeyData ) );
+}
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline Data const &CUtlHash<Data, C, K>::Element( UtlHashHandle_t handle ) const
+{
+	int ndxBucket = GetBucketIndex( handle );
+	int ndxKeyData = GetKeyDataIndex( handle );
+
+	return ( m_Buckets[ndxBucket].Element( ndxKeyData ) );
+}
+
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline Data &CUtlHash<Data, C, K>::operator[]( UtlHashHandle_t handle )
+{
+	int ndxBucket = GetBucketIndex( handle );
+	int ndxKeyData = GetKeyDataIndex( handle );
+
+	return ( m_Buckets[ndxBucket].Element( ndxKeyData ) );
+}
+
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline Data const &CUtlHash<Data, C, K>::operator[]( UtlHashHandle_t handle ) const
+{
+	int ndxBucket = GetBucketIndex( handle );
+	int ndxKeyData = GetKeyDataIndex( handle );
+
+	return ( m_Buckets[ndxBucket].Element( ndxKeyData ) );
+}
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline UtlHashHandle_t CUtlHash<Data, C, K>::GetFirstHandle() const
+{
+	return GetNextHandle( ( UtlHashHandle_t )-1 );
+}
+
+template<class Data, typename C, typename K>
+inline UtlHashHandle_t CUtlHash<Data, C, K>::GetNextHandle( UtlHashHandle_t handle ) const
+{
+	++handle; // start at the first possible handle after the one given
+
+	int bi = GetBucketIndex( handle );
+	int ki =  GetKeyDataIndex( handle );
+
+	int nBuckets = m_Buckets.Count();
+	for ( ; bi < nBuckets; ++bi )
+	{
+		if ( ki < m_Buckets[ bi ].Count() )
+			return BuildHandle( bi, ki );
+
+		ki = 0;
+	}
+
+	return InvalidHandle();
+}
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, typename C, typename K>
+inline void CUtlHash<Data, C, K>::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
+
+class CUtlHashFastNoHash
+{
+public:
+	static int Hash( int key, int bucketMask )
+	{
+		return ( key & bucketMask );
+	}
+};
+
+class CUtlHashFastGenericHash
+{
+public:
+	static int Hash( int key, int bucketMask )
+	{
+		return ( HashIntConventional( key ) & bucketMask );
+	}
+};
+
+template<class Data, class HashFuncs = CUtlHashFastNoHash > 
+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:
+
+	// Templatized for memory tracking purposes
+	template <typename HashData>
+	struct HashFastData_t_
+	{
+		unsigned int	m_uiKey;
+		HashData	m_Data;
+	};
+
+	typedef HashFastData_t_<Data> HashFastData_t;
+
+	unsigned int						m_uiBucketMask;	
+	CUtlVector<UtlHashFastHandle_t>		m_aBuckets;
+	CUtlFixedLinkedList<HashFastData_t>	m_aDataPool;
+};
+
+//-----------------------------------------------------------------------------
+// Purpose: Constructor
+//-----------------------------------------------------------------------------
+template<class Data, class HashFuncs> CUtlHashFast<Data,HashFuncs>::CUtlHashFast()
+{
+	Purge();
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Deconstructor
+//-----------------------------------------------------------------------------
+template<class Data, class HashFuncs> CUtlHashFast<Data,HashFuncs>::~CUtlHashFast()
+{
+	Purge();
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Destroy dynamically allocated hash data.
+//-----------------------------------------------------------------------------
+template<class Data, class HashFuncs> inline void CUtlHashFast<Data,HashFuncs>::Purge( void )
+{
+	m_aBuckets.Purge();
+	m_aDataPool.Purge();
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Initialize the hash - set bucket count and hash grow amount.
+//-----------------------------------------------------------------------------
+template<class Data, class HashFuncs> bool CUtlHashFast<Data,HashFuncs>::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, class HashFuncs> inline int CUtlHashFast<Data,HashFuncs>::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, class HashFuncs> inline UtlHashFastHandle_t CUtlHashFast<Data,HashFuncs>::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, class HashFuncs> inline UtlHashFastHandle_t CUtlHashFast<Data,HashFuncs>::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 = HashFuncs::Hash( 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, class HashFuncs> inline void CUtlHashFast<Data,HashFuncs>::Remove( UtlHashFastHandle_t hHash )
+{
+	int iBucket = HashFuncs::Hash( 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, class HashFuncs> inline void CUtlHashFast<Data,HashFuncs>::RemoveAll( void )
+{
+	m_aBuckets.RemoveAll();
+	m_aDataPool.RemoveAll();
+}
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, class HashFuncs> inline UtlHashFastHandle_t CUtlHashFast<Data,HashFuncs>::Find( unsigned int uiKey )
+{
+	// hash the "key" - get the correct hash table "bucket"
+	int iBucket = HashFuncs::Hash( uiKey, m_uiBucketMask );
+
+	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, class HashFuncs> inline Data &CUtlHashFast<Data,HashFuncs>::Element( UtlHashFastHandle_t hHash )
+{
+	return ( m_aDataPool[hHash].m_Data );
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Return data given a hash handle.
+//-----------------------------------------------------------------------------
+template<class Data, class HashFuncs> inline Data const &CUtlHashFast<Data,HashFuncs>::Element( UtlHashFastHandle_t hHash ) const
+{
+	return ( m_aDataPool[hHash].m_Data );
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Return data given a hash handle.
+//-----------------------------------------------------------------------------
+template<class Data, class HashFuncs> inline Data &CUtlHashFast<Data,HashFuncs>::operator[]( UtlHashFastHandle_t hHash )
+{
+	return ( m_aDataPool[hHash].m_Data );
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Return data given a hash handle.
+//-----------------------------------------------------------------------------
+template<class Data, class HashFuncs> inline Data const &CUtlHashFast<Data,HashFuncs>::operator[]( UtlHashFastHandle_t hHash ) const
+{
+	return ( m_aDataPool[hHash].m_Data );
+}
+
+//=============================================================================
+// 
+// Fixed Hash
+//
+// Number of buckets must be a power of 2.
+// Key must be 32-bits (unsigned int).
+//
+typedef int UtlHashFixedHandle_t;
+
+template <int NUM_BUCKETS>
+class CUtlHashFixedGenericHash
+{
+public:
+	static int Hash( int key, int bucketMask )
+	{
+		int hash = HashIntConventional( key );
+		if ( NUM_BUCKETS <= USHRT_MAX )
+		{
+			hash ^= ( hash >> 16 );
+		}
+		if ( NUM_BUCKETS <= UCHAR_MAX )
+		{
+			hash ^= ( hash >> 8 );
+		}
+		return ( hash & bucketMask );
+	}
+};
+
+template<class Data, int NUM_BUCKETS, class CHashFuncs = CUtlHashFastNoHash > 
+class CUtlHashFixed
+{
+public:
+
+	// Constructor/Deconstructor.
+	CUtlHashFixed();
+	~CUtlHashFixed();
+
+	// Memory.
+	void Purge( void );
+
+	// Invalid handle.
+	static UtlHashFixedHandle_t InvalidHandle( void )	{ return ( UtlHashFixedHandle_t )~0; }
+
+	// Size.
+	int Count( void );
+
+	// Insertion.
+	UtlHashFixedHandle_t Insert( unsigned int uiKey, const Data &data );
+	UtlHashFixedHandle_t FastInsert( unsigned int uiKey, const Data &data );
+
+	// Removal.
+	void Remove( UtlHashFixedHandle_t hHash );
+	void RemoveAll( void );
+
+	// Retrieval.
+	UtlHashFixedHandle_t Find( unsigned int uiKey );
+
+	Data &Element( UtlHashFixedHandle_t hHash );
+	Data const &Element( UtlHashFixedHandle_t hHash ) const;
+	Data &operator[]( UtlHashFixedHandle_t hHash );
+	Data const &operator[]( UtlHashFixedHandle_t hHash ) const;
+
+	//protected:
+
+	// Templatized for memory tracking purposes
+	template <typename Data_t>
+	struct HashFixedData_t_
+	{
+		unsigned int	m_uiKey;
+		Data_t			m_Data;
+	};
+
+	typedef HashFixedData_t_<Data> HashFixedData_t;
+
+	enum
+	{
+		BUCKET_MASK = NUM_BUCKETS - 1
+	};
+	CUtlPtrLinkedList<HashFixedData_t> m_aBuckets[NUM_BUCKETS];
+	int m_nElements;
+};
+
+//-----------------------------------------------------------------------------
+// Purpose: Constructor
+//-----------------------------------------------------------------------------
+template<class Data, int NUM_BUCKETS, class HashFuncs> CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::CUtlHashFixed()
+{
+	Purge();
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Deconstructor
+//-----------------------------------------------------------------------------
+template<class Data, int NUM_BUCKETS, class HashFuncs> CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::~CUtlHashFixed()
+{
+	Purge();
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Destroy dynamically allocated hash data.
+//-----------------------------------------------------------------------------
+template<class Data, int NUM_BUCKETS, class HashFuncs> inline void CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::Purge( void )
+{
+	RemoveAll();
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Return the number of elements in the hash.
+//-----------------------------------------------------------------------------
+template<class Data, int NUM_BUCKETS, class HashFuncs> inline int CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::Count( void )
+{
+	return m_nElements;
+}
+
+//-----------------------------------------------------------------------------
+// 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, int NUM_BUCKETS, class HashFuncs> inline UtlHashFixedHandle_t CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::Insert( unsigned int uiKey, const Data &data )
+{
+	// Check to see if that key already exists in the buckets (should be unique).
+	UtlHashFixedHandle_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, int NUM_BUCKETS, class HashFuncs> inline UtlHashFixedHandle_t CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::FastInsert( unsigned int uiKey, const Data &data )
+{
+	int iBucket = HashFuncs::Hash( uiKey, NUM_BUCKETS - 1 );
+	UtlPtrLinkedListIndex_t iElem = m_aBuckets[iBucket].AddToHead();
+
+	HashFixedData_t *pHashData = &m_aBuckets[iBucket][iElem];
+
+	Assert( (UtlPtrLinkedListIndex_t)pHashData == iElem );
+
+	// Add data to new element.
+	pHashData->m_uiKey = uiKey;
+	pHashData->m_Data = data;
+
+	m_nElements++;
+	return (UtlHashFixedHandle_t)pHashData;	
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Remove a given element from the hash.
+//-----------------------------------------------------------------------------
+template<class Data, int NUM_BUCKETS, class HashFuncs> inline void CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::Remove( UtlHashFixedHandle_t hHash )
+{
+	HashFixedData_t *pHashData = (HashFixedData_t *)hHash;
+	Assert( Find(pHashData->m_uiKey) != InvalidHandle() );
+	int iBucket = HashFuncs::Hash( pHashData->m_uiKey, NUM_BUCKETS - 1 );
+	m_aBuckets[iBucket].Remove( (UtlPtrLinkedListIndex_t)pHashData );
+	m_nElements--;
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Remove all elements from the hash
+//-----------------------------------------------------------------------------
+template<class Data, int NUM_BUCKETS, class HashFuncs> inline void CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::RemoveAll( void )
+{
+	for ( int i = 0; i < NUM_BUCKETS; i++ )
+	{
+		m_aBuckets[i].RemoveAll();
+	}
+	m_nElements = 0;
+}
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+template<class Data, int NUM_BUCKETS, class HashFuncs> inline UtlHashFixedHandle_t CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::Find( unsigned int uiKey )
+{
+	int iBucket = HashFuncs::Hash( uiKey, NUM_BUCKETS - 1 );
+	CUtlPtrLinkedList<HashFixedData_t> &bucket = m_aBuckets[iBucket];
+
+	for ( UtlPtrLinkedListIndex_t iElement = bucket.Head(); iElement != bucket.InvalidIndex(); iElement = bucket.Next( iElement ) )
+	{
+		if ( bucket[iElement].m_uiKey == uiKey )
+			return (UtlHashFixedHandle_t)iElement;
+	}
+
+	return InvalidHandle();
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Return data given a hash handle.
+//-----------------------------------------------------------------------------
+template<class Data, int NUM_BUCKETS, class HashFuncs> inline Data &CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::Element( UtlHashFixedHandle_t hHash )
+{
+	return ((HashFixedData_t *)hHash)->m_Data;
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Return data given a hash handle.
+//-----------------------------------------------------------------------------
+template<class Data, int NUM_BUCKETS, class HashFuncs> inline Data const &CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::Element( UtlHashFixedHandle_t hHash ) const
+{
+	return ((HashFixedData_t *)hHash)->m_Data;
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Return data given a hash handle.
+//-----------------------------------------------------------------------------
+template<class Data, int NUM_BUCKETS, class HashFuncs> inline Data &CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::operator[]( UtlHashFixedHandle_t hHash )
+{
+	return ((HashFixedData_t *)hHash)->m_Data;
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Return data given a hash handle.
+//-----------------------------------------------------------------------------
+template<class Data, int NUM_BUCKETS, class HashFuncs> inline Data const &CUtlHashFixed<Data,NUM_BUCKETS,HashFuncs>::operator[]( UtlHashFixedHandle_t hHash ) const
+{
+	return ((HashFixedData_t *)hHash)->m_Data;
+}
+
+#endif // UTLHASH_H