diff options
Diffstat (limited to 'public/tier1/utltshash.h')
| -rw-r--r-- | public/tier1/utltshash.h | 625 |
1 files changed, 625 insertions, 0 deletions
diff --git a/public/tier1/utltshash.h b/public/tier1/utltshash.h new file mode 100644 index 0000000..9ff4e83 --- /dev/null +++ b/public/tier1/utltshash.h @@ -0,0 +1,625 @@ +//========= Copyright Valve Corporation, All rights reserved. ============// +// +// Purpose: +// +// $NoKeywords: $ +// +// Thread-safe hash class +//===========================================================================// + +#ifndef UTLTSHASH_H +#define UTLTSHASH_H + +#ifdef _WIN32 +#pragma once +#endif + +#include <limits.h> +#include "tier0/threadtools.h" +#include "tier1/mempool.h" +#include "generichash.h" + + +//============================================================================= +// +// Threadsafe Hash +// +// Number of buckets must be a power of 2. +// Key must be intp sized (32-bits on x32, 64-bits on x64) +// Designed for a usage pattern where the data is semi-static, and there +// is a well-defined point where we are guaranteed no queries are occurring. +// +// Insertions are added into a thread-safe list, and when Commit() is called, +// the insertions are moved into a lock-free list +// +// Elements are never individually removed; clears must occur at a time +// where we and guaranteed no queries are occurring +// +typedef intp UtlTSHashHandle_t; + +template < class T > +abstract_class ITSHashConstructor +{ +public: + virtual void Construct( T* pElement ) = 0; +}; + +template < class T > +class CDefaultTSHashConstructor : public ITSHashConstructor< T > +{ +public: + virtual void Construct( T* pElement ) + { + ::Construct( pElement ); + } +}; + +template < int BUCKET_COUNT, class KEYTYPE = intp > +class CUtlTSHashGenericHash +{ +public: + static int Hash( const KEYTYPE &key, int nBucketMask ) + { + int nHash = HashIntConventional( (intp)key ); + if ( BUCKET_COUNT <= USHRT_MAX ) + { + nHash ^= ( nHash >> 16 ); + } + if ( BUCKET_COUNT <= UCHAR_MAX ) + { + nHash ^= ( nHash >> 8 ); + } + return ( nHash & nBucketMask ); + } + + static bool Compare( const KEYTYPE &lhs, const KEYTYPE &rhs ) + { + return lhs == rhs; + } +}; + +template < int BUCKET_COUNT, class KEYTYPE > +class CUtlTSHashUseKeyHashMethod +{ +public: + static int Hash( const KEYTYPE &key, int nBucketMask ) + { + uint32 nHash = key.HashValue(); + return ( nHash & nBucketMask ); + } + + static bool Compare( const KEYTYPE &lhs, const KEYTYPE &rhs ) + { + return lhs == rhs; + } +}; + +template< class T, int BUCKET_COUNT, class KEYTYPE = intp, class HashFuncs = CUtlTSHashGenericHash< BUCKET_COUNT, KEYTYPE >, int nAlignment = 0 > +class CUtlTSHash +{ +public: + // Constructor/Deconstructor. + CUtlTSHash( int nAllocationCount ); + ~CUtlTSHash(); + + // Invalid handle. + static UtlTSHashHandle_t InvalidHandle( void ) { return ( UtlTSHashHandle_t )0; } + + // Retrieval. Super fast, is thread-safe + UtlTSHashHandle_t Find( KEYTYPE uiKey ); + + // Insertion ( find or add ). + UtlTSHashHandle_t Insert( KEYTYPE uiKey, const T &data, bool *pDidInsert = NULL ); + UtlTSHashHandle_t Insert( KEYTYPE uiKey, ITSHashConstructor<T> *pConstructor, bool *pDidInsert = NULL ); + + // This insertion method assumes the element is not in the hash table, skips + UtlTSHashHandle_t FastInsert( KEYTYPE uiKey, const T &data ); + UtlTSHashHandle_t FastInsert( KEYTYPE uiKey, ITSHashConstructor<T> *pConstructor ); + + // Commit recent insertions, making finding them faster. + // Only call when you're certain no threads are accessing the hash table + void Commit( ); + + // Removal. Only call when you're certain no threads are accessing the hash table + void FindAndRemove( KEYTYPE uiKey ); + void Remove( UtlTSHashHandle_t hHash ) { FindAndRemove( GetID( hHash ) ); } + void RemoveAll( void ); + void Purge( void ); + + // Returns the number of elements in the hash table + int Count() const; + + // Returns elements in the table + int GetElements( int nFirstElement, int nCount, UtlTSHashHandle_t *pHandles ) const; + + // Element access + T &Element( UtlTSHashHandle_t hHash ); + T const &Element( UtlTSHashHandle_t hHash ) const; + T &operator[]( UtlTSHashHandle_t hHash ); + T const &operator[]( UtlTSHashHandle_t hHash ) const; + KEYTYPE GetID( UtlTSHashHandle_t hHash ) const; + + // Convert element * to hashHandle + UtlTSHashHandle_t ElementPtrToHandle( T* pElement ) const; + +private: + // Templatized for memory tracking purposes + template < typename Data_t > + struct HashFixedDataInternal_t + { + KEYTYPE m_uiKey; + HashFixedDataInternal_t< Data_t >* m_pNext; + Data_t m_Data; + }; + + typedef HashFixedDataInternal_t<T> HashFixedData_t; + + enum + { + BUCKET_MASK = BUCKET_COUNT - 1 + }; + + struct HashBucket_t + { + HashFixedData_t *m_pFirst; + HashFixedData_t *m_pFirstUncommitted; + CThreadSpinRWLock m_AddLock; + }; + + UtlTSHashHandle_t Find( KEYTYPE uiKey, HashFixedData_t *pFirstElement, HashFixedData_t *pLastElement ); + UtlTSHashHandle_t InsertUncommitted( KEYTYPE uiKey, HashBucket_t &bucket ); + CMemoryPoolMT m_EntryMemory; + HashBucket_t m_aBuckets[BUCKET_COUNT]; + bool m_bNeedsCommit; + +#ifdef _DEBUG + CInterlockedInt m_ContentionCheck; +#endif +}; + + +//----------------------------------------------------------------------------- +// Purpose: Constructor +//----------------------------------------------------------------------------- +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::CUtlTSHash( int nAllocationCount ) : + m_EntryMemory( sizeof( HashFixedData_t ), nAllocationCount, CUtlMemoryPool::GROW_SLOW, MEM_ALLOC_CLASSNAME( HashFixedData_t ), nAlignment ) +{ +#ifdef _DEBUG + m_ContentionCheck = 0; +#endif + m_bNeedsCommit = false; + for ( int i = 0; i < BUCKET_COUNT; i++ ) + { + HashBucket_t &bucket = m_aBuckets[ i ]; + bucket.m_pFirst = NULL; + bucket.m_pFirstUncommitted = NULL; + } +} + + +//----------------------------------------------------------------------------- +// Purpose: Deconstructor +//----------------------------------------------------------------------------- +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::~CUtlTSHash() +{ +#ifdef _DEBUG + if ( m_ContentionCheck != 0 ) + { + DebuggerBreak(); + } +#endif + Purge(); +} + +//----------------------------------------------------------------------------- +// Purpose: Destroy dynamically allocated hash data. +//----------------------------------------------------------------------------- +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline void CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::Purge( void ) +{ + RemoveAll(); +} + + +//----------------------------------------------------------------------------- +// Returns the number of elements in the hash table +//----------------------------------------------------------------------------- +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline int CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::Count() const +{ + return m_EntryMemory.Count(); +} + + +//----------------------------------------------------------------------------- +// Returns elements in the table +//----------------------------------------------------------------------------- +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +int CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::GetElements( int nFirstElement, int nCount, UtlTSHashHandle_t *pHandles ) const +{ + int nIndex = 0; + for ( int i = 0; i < BUCKET_COUNT; i++ ) + { + const HashBucket_t &bucket = m_aBuckets[ i ]; + bucket.m_AddLock.LockForRead( ); + for ( HashFixedData_t *pElement = bucket.m_pFirstUncommitted; pElement; pElement = pElement->m_pNext ) + { + if ( --nFirstElement >= 0 ) + continue; + + pHandles[ nIndex++ ] = (UtlTSHashHandle_t)pElement; + if ( nIndex >= nCount ) + { + bucket.m_AddLock.UnlockRead( ); + return nIndex; + } + } + bucket.m_AddLock.UnlockRead( ); + } + return nIndex; +} + + +//----------------------------------------------------------------------------- +// Purpose: Insert data into the hash table given its key (KEYTYPE), +// without a check to see if the element already exists within the tree. +//----------------------------------------------------------------------------- +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline UtlTSHashHandle_t CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::InsertUncommitted( KEYTYPE uiKey, HashBucket_t &bucket ) +{ + m_bNeedsCommit = true; + HashFixedData_t *pNewElement = static_cast< HashFixedData_t * >( m_EntryMemory.Alloc() ); + pNewElement->m_pNext = bucket.m_pFirstUncommitted; + bucket.m_pFirstUncommitted = pNewElement; + pNewElement->m_uiKey = uiKey; + return (UtlTSHashHandle_t)pNewElement; +} + + +//----------------------------------------------------------------------------- +// Purpose: Insert data into the hash table given its key, with +// a check to see if the element already exists within the tree. +//----------------------------------------------------------------------------- +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline UtlTSHashHandle_t CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::Insert( KEYTYPE uiKey, const T &data, bool *pDidInsert ) +{ +#ifdef _DEBUG + if ( m_ContentionCheck != 0 ) + { + DebuggerBreak(); + } +#endif + + if ( pDidInsert ) + { + *pDidInsert = false; + } + + int iBucket = HashFuncs::Hash( uiKey, BUCKET_MASK ); + HashBucket_t &bucket = m_aBuckets[ iBucket ]; + + // First try lock-free + UtlTSHashHandle_t h = Find( uiKey ); + if ( h != InvalidHandle() ) + return h; + + // Now, try again, but only look in uncommitted elements + bucket.m_AddLock.LockForWrite( ); + + h = Find( uiKey, bucket.m_pFirstUncommitted, bucket.m_pFirst ); + if ( h == InvalidHandle() ) + { + h = InsertUncommitted( uiKey, bucket ); + CopyConstruct( &Element(h), data ); + if ( pDidInsert ) + { + *pDidInsert = true; + } + } + + bucket.m_AddLock.UnlockWrite( ); + return h; +} + +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline UtlTSHashHandle_t CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::Insert( KEYTYPE uiKey, ITSHashConstructor<T> *pConstructor, bool *pDidInsert ) +{ +#ifdef _DEBUG + if ( m_ContentionCheck != 0 ) + { + DebuggerBreak(); + } +#endif + + if ( pDidInsert ) + { + *pDidInsert = false; + } + + // First try lock-free + UtlTSHashHandle_t h = Find( uiKey ); + if ( h != InvalidHandle() ) + return h; + + // Now, try again, but only look in uncommitted elements + int iBucket = HashFuncs::Hash( uiKey, BUCKET_MASK ); + HashBucket_t &bucket = m_aBuckets[ iBucket ]; + bucket.m_AddLock.LockForWrite( ); + + h = Find( uiKey, bucket.m_pFirstUncommitted, bucket.m_pFirst ); + if ( h == InvalidHandle() ) + { + // Useful if non-trivial work needs to happen to make data; don't want to + // do it and then have to undo it if it turns out we don't need to add it + h = InsertUncommitted( uiKey, bucket ); + pConstructor->Construct( &Element(h) ); + if ( pDidInsert ) + { + *pDidInsert = true; + } + } + + bucket.m_AddLock.UnlockWrite( ); + return h; +} + + +//----------------------------------------------------------------------------- +// Purpose: Insert data into the hash table given its key +// without a check to see if the element already exists within the tree. +//----------------------------------------------------------------------------- +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline UtlTSHashHandle_t CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::FastInsert( KEYTYPE uiKey, const T &data ) +{ +#ifdef _DEBUG + if ( m_ContentionCheck != 0 ) + { + DebuggerBreak(); + } +#endif + int iBucket = HashFuncs::Hash( uiKey, BUCKET_MASK ); + HashBucket_t &bucket = m_aBuckets[ iBucket ]; + bucket.m_AddLock.LockForWrite( ); + UtlTSHashHandle_t h = InsertUncommitted( uiKey, bucket ); + CopyConstruct( &Element(h), data ); + bucket.m_AddLock.UnlockWrite( ); + return h; +} + +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline UtlTSHashHandle_t CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::FastInsert( KEYTYPE uiKey, ITSHashConstructor<T> *pConstructor ) +{ +#ifdef _DEBUG + if ( m_ContentionCheck != 0 ) + { + DebuggerBreak(); + } +#endif + int iBucket = HashFuncs::Hash( uiKey, BUCKET_MASK ); + HashBucket_t &bucket = m_aBuckets[ iBucket ]; + bucket.m_AddLock.LockForWrite( ); + UtlTSHashHandle_t h = InsertUncommitted( uiKey, bucket ); + pConstructor->Construct( &Element(h) ); + bucket.m_AddLock.UnlockWrite( ); + return h; +} + + +//----------------------------------------------------------------------------- +// Purpose: Commits all uncommitted insertions +//----------------------------------------------------------------------------- +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline void CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::Commit( ) +{ + // FIXME: Is this legal? Want this to be lock-free + if ( !m_bNeedsCommit ) + return; + + // This must occur when no queries are occurring +#ifdef _DEBUG + m_ContentionCheck++; +#endif + + for ( int i = 0; i < BUCKET_COUNT; i++ ) + { + HashBucket_t &bucket = m_aBuckets[ i ]; + bucket.m_AddLock.LockForRead( ); + bucket.m_pFirst = bucket.m_pFirstUncommitted; + bucket.m_AddLock.UnlockRead( ); + } + + m_bNeedsCommit = false; + +#ifdef _DEBUG + m_ContentionCheck--; +#endif +} + + +//----------------------------------------------------------------------------- +// Purpose: Remove a single element from the hash +//----------------------------------------------------------------------------- +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline void CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::FindAndRemove( KEYTYPE uiKey ) +{ + if ( m_EntryMemory.Count() == 0 ) + return; + + // This must occur when no queries are occurring +#ifdef _DEBUG + m_ContentionCheck++; +#endif + + int iBucket = HashFuncs::Hash( uiKey, BUCKET_MASK ); + HashBucket_t &bucket = m_aBuckets[ iBucket ]; + bucket.m_AddLock.LockForWrite( ); + + HashFixedData_t *pPrev = NULL; + for ( HashFixedData_t *pElement = bucket.m_pFirstUncommitted; pElement; pPrev = pElement, pElement = pElement->m_pNext ) + { + if ( !HashFuncs::Compare( pElement->m_uiKey, uiKey ) ) + continue; + + if ( pPrev ) + { + pPrev->m_pNext = pElement->m_pNext; + } + else + { + bucket.m_pFirstUncommitted = pElement->m_pNext; + } + + if ( bucket.m_pFirst == pElement ) + { + bucket.m_pFirst = bucket.m_pFirst->m_pNext; + } + + Destruct( &pElement->m_Data ); + +#ifdef _DEBUG + memset( pElement, 0xDD, sizeof(HashFixedData_t) ); +#endif + + m_EntryMemory.Free( pElement ); + + break; + } + + bucket.m_AddLock.UnlockWrite( ); + +#ifdef _DEBUG + m_ContentionCheck--; +#endif +} + + +//----------------------------------------------------------------------------- +// Purpose: Remove all elements from the hash +//----------------------------------------------------------------------------- +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline void CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::RemoveAll( void ) +{ + m_bNeedsCommit = false; + if ( m_EntryMemory.Count() == 0 ) + return; + + // This must occur when no queries are occurring +#ifdef _DEBUG + m_ContentionCheck++; +#endif + + for ( int i = 0; i < BUCKET_COUNT; i++ ) + { + HashBucket_t &bucket = m_aBuckets[ i ]; + + bucket.m_AddLock.LockForWrite( ); + + for ( HashFixedData_t *pElement = bucket.m_pFirstUncommitted; pElement; pElement = pElement->m_pNext ) + { + Destruct( &pElement->m_Data ); + } + + bucket.m_pFirst = NULL; + bucket.m_pFirstUncommitted = NULL; + bucket.m_AddLock.UnlockWrite( ); + } + + m_EntryMemory.Clear(); + +#ifdef _DEBUG + m_ContentionCheck--; +#endif +} + +//----------------------------------------------------------------------------- +// Finds an element, but only in the committed elements +//----------------------------------------------------------------------------- +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline UtlTSHashHandle_t CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::Find( KEYTYPE uiKey, HashFixedData_t *pFirstElement, HashFixedData_t *pLastElement ) +{ +#ifdef _DEBUG + if ( m_ContentionCheck != 0 ) + { + DebuggerBreak(); + } +#endif + + for ( HashFixedData_t *pElement = pFirstElement; pElement != pLastElement; pElement = pElement->m_pNext ) + { + if ( HashFuncs::Compare( pElement->m_uiKey, uiKey ) ) + return (UtlTSHashHandle_t)pElement; + } + return InvalidHandle(); +} + + +//----------------------------------------------------------------------------- +// Finds an element, but only in the committed elements +//----------------------------------------------------------------------------- +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline UtlTSHashHandle_t CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::Find( KEYTYPE uiKey ) +{ + int iBucket = HashFuncs::Hash( uiKey, BUCKET_MASK ); + const HashBucket_t &bucket = m_aBuckets[iBucket]; + UtlTSHashHandle_t h = Find( uiKey, bucket.m_pFirst, NULL ); + if ( h != InvalidHandle() ) + return h; + + // Didn't find it in the fast ( committed ) list. Let's try the slow ( uncommitted ) one + bucket.m_AddLock.LockForRead( ); + h = Find( uiKey, bucket.m_pFirstUncommitted, bucket.m_pFirst ); + bucket.m_AddLock.UnlockRead( ); + + return h; +} + + +//----------------------------------------------------------------------------- +// Purpose: Return data given a hash handle. +//----------------------------------------------------------------------------- +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline T &CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::Element( UtlTSHashHandle_t hHash ) +{ + return ((HashFixedData_t *)hHash)->m_Data; +} + +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline T const &CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::Element( UtlTSHashHandle_t hHash ) const +{ + return ((HashFixedData_t *)hHash)->m_Data; +} + +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline T &CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::operator[]( UtlTSHashHandle_t hHash ) +{ + return ((HashFixedData_t *)hHash)->m_Data; +} + +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline T const &CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::operator[]( UtlTSHashHandle_t hHash ) const +{ + return ((HashFixedData_t *)hHash)->m_Data; +} + + +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline KEYTYPE CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::GetID( UtlTSHashHandle_t hHash ) const +{ + return ((HashFixedData_t *)hHash)->m_uiKey; +} + + +// Convert element * to hashHandle +template<class T, int BUCKET_COUNT, class KEYTYPE, class HashFuncs, int nAlignment> +inline UtlTSHashHandle_t CUtlTSHash<T,BUCKET_COUNT,KEYTYPE,HashFuncs,nAlignment>::ElementPtrToHandle( T* pElement ) const +{ + Assert( pElement ); + HashFixedData_t *pFixedData = (HashFixedData_t*)( (uint8*)pElement - offsetof( HashFixedData_t, m_Data ) ); + Assert( m_EntryMemory.IsAllocationWithinPool( pFixedData ) ); + return (UtlTSHashHandle_t)pFixedData; +} + + +#endif // UTLTSHASH_H |