diff options
Diffstat (limited to 'mp/src/public/tier1/utlhash.h')
| -rw-r--r-- | mp/src/public/tier1/utlhash.h | 936 |
1 files changed, 936 insertions, 0 deletions
diff --git a/mp/src/public/tier1/utlhash.h b/mp/src/public/tier1/utlhash.h new file mode 100644 index 00000000..72751ffc --- /dev/null +++ b/mp/src/public/tier1/utlhash.h @@ -0,0 +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
|