diff options
| author | Joe Ludwig <[email protected]> | 2013-06-26 15:22:04 -0700 |
|---|---|---|
| committer | Joe Ludwig <[email protected]> | 2013-06-26 15:22:04 -0700 |
| commit | 39ed87570bdb2f86969d4be821c94b722dc71179 (patch) | |
| tree | abc53757f75f40c80278e87650ea92808274aa59 /sp/src/public/tier1/utlhashdict.h | |
| download | source-sdk-2013-39ed87570bdb2f86969d4be821c94b722dc71179.tar.xz source-sdk-2013-39ed87570bdb2f86969d4be821c94b722dc71179.zip | |
First version of the SOurce SDK 2013
Diffstat (limited to 'sp/src/public/tier1/utlhashdict.h')
| -rw-r--r-- | sp/src/public/tier1/utlhashdict.h | 342 |
1 files changed, 342 insertions, 0 deletions
diff --git a/sp/src/public/tier1/utlhashdict.h b/sp/src/public/tier1/utlhashdict.h new file mode 100644 index 00000000..b1ba7ecd --- /dev/null +++ b/sp/src/public/tier1/utlhashdict.h @@ -0,0 +1,342 @@ +//========= Copyright Valve Corporation, All rights reserved. ============//
+//
+// Purpose:
+//
+//=============================================================================
+
+#ifndef UTLHASHDICT_H
+#define UTLHASHDICT_H
+
+#if defined( _WIN32 )
+#pragma once
+#endif
+
+#include "tier1/utlhash.h"
+#include "tier1/generichash.h"
+#include "mathlib/mathlib.h"
+
+//-----------------------------------------------------------------------------
+//
+//-----------------------------------------------------------------------------
+template <typename T, bool bCaseInsensitive = true, bool bDupeStrings = true>
+class CUtlHashDict
+{
+public:
+ // constructor, destructor
+ CUtlHashDict( int bucketCount = 16, int growCount = 0, int initCount = 0 );
+ ~CUtlHashDict( );
+
+ // gets particular elements
+ T& Element( unsigned i );
+ const T& Element( unsigned i ) const;
+ T& operator[]( unsigned i );
+ const T& operator[]( unsigned i ) const;
+
+ // gets element names
+ char const *GetElementName( unsigned i ) const;
+
+ // Number of elements
+ int Count() const;
+
+ // Checks if a node is valid and in the tree
+ bool IsValidIndex( unsigned i ) const;
+
+ // Invalid index
+ static unsigned InvalidHandle();
+
+ // Insert method (inserts in order)
+ unsigned Insert( const char *pName, const T &element );
+ unsigned Insert( const char *pName );
+
+ // Find method
+ unsigned Find( const char *pName ) const;
+
+ // Remove methods
+ void RemoveAt( unsigned i );
+ void Remove( const char *pName );
+ void RemoveAll( );
+
+ // Purge memory
+ void Purge();
+ void PurgeAndDeleteElements(); // Call delete on each element.
+
+ // Iteration methods
+ unsigned First() const;
+ unsigned Next( unsigned i ) const;
+
+protected:
+ struct Entry_t
+ {
+ const char *pszSymbol;
+ T value;
+ };
+
+ template <bool bCaseInsensitive>
+ class CCompare
+ {
+ public:
+ CCompare( int ignored ) {}
+
+ bool operator()( const Entry_t &entry1, const Entry_t &entry2 ) const
+ {
+ return !( ( bCaseInsensitive ) ? stricmp( entry1.pszSymbol, entry2.pszSymbol ) : strcmp( entry1.pszSymbol, entry2.pszSymbol ) );
+ }
+ };
+
+ template <bool bCaseInsensitive>
+ class CHash
+ {
+ public:
+ CHash( int ignored ) {}
+
+ unsigned operator()( const Entry_t &entry ) const
+ {
+ return !( ( bCaseInsensitive ) ? HashStringCaseless( entry.pszSymbol ) : HashString( entry.pszSymbol ) );
+ }
+ };
+
+ typedef CUtlHash<Entry_t, CCompare<bCaseInsensitive>, CHash<bCaseInsensitive> > CHashTable;
+ CHashTable m_Elements;
+ int m_nCount;
+};
+
+//-----------------------------------------------------------------------------
+// constructor, destructor
+//-----------------------------------------------------------------------------
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::CUtlHashDict( int bucketCount = 16, int growCount = 0, int initCount = 0 ) :
+ m_Elements( SmallestPowerOfTwoGreaterOrEqual(bucketCount), growCount, initCount )
+{
+ Assert( SmallestPowerOfTwoGreaterOrEqual(bucketCount) <= 0xffff );
+}
+
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::~CUtlHashDict()
+{
+ Purge();
+}
+
+//-----------------------------------------------------------------------------
+// gets particular elements
+//-----------------------------------------------------------------------------
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+inline T& CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Element( unsigned i )
+{
+ return m_Elements[i].value;
+}
+
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+inline const T& CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Element( unsigned i ) const
+{
+ return m_Elements[i].value;
+}
+
+//-----------------------------------------------------------------------------
+// gets element names
+//-----------------------------------------------------------------------------
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+inline char const *CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::GetElementName( unsigned i ) const
+{
+ return m_Elements[i].pszSymbol;
+}
+
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+inline T& CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::operator[]( unsigned i )
+{
+ return m_Elements[i].value;
+}
+
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+inline const T & CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::operator[]( unsigned i ) const
+{
+ return m_Elements[i].value;
+}
+
+//-----------------------------------------------------------------------------
+// Num elements
+//-----------------------------------------------------------------------------
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+inline int CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Count() const
+{
+ Assert( m_nCount == m_Elements.Count() );
+ return m_nCount;
+}
+
+
+//-----------------------------------------------------------------------------
+// Checks if a node is valid and in the tree
+//-----------------------------------------------------------------------------
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+inline bool CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::IsValidIndex( unsigned i ) const
+{
+ return m_Elements.IsValidHandle(i);
+}
+
+
+//-----------------------------------------------------------------------------
+// Invalid index
+//-----------------------------------------------------------------------------
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+inline unsigned CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::InvalidHandle()
+{
+ return CHashTable::InvalidHandle();
+}
+
+
+//-----------------------------------------------------------------------------
+// Delete a node from the tree
+//-----------------------------------------------------------------------------
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+void CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::RemoveAt(unsigned elem)
+{
+ if ( bDupeStrings )
+ {
+ free( (void *)m_Elements[elem].pszSymbol );
+ }
+ m_Elements.Remove(elem);
+ m_nCount--;
+}
+
+
+//-----------------------------------------------------------------------------
+// remove a node in the tree
+//-----------------------------------------------------------------------------
+template <typename T, bool bCaseInsensitive, bool bDupeStrings> void CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Remove( const char *search )
+{
+ unsigned node = Find( search );
+ if (node != InvalidHandle())
+ {
+ RemoveAt(node);
+ }
+}
+
+
+//-----------------------------------------------------------------------------
+// Removes all nodes from the tree
+//-----------------------------------------------------------------------------
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+void CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::RemoveAll()
+{
+ if ( bDupeStrings )
+ {
+ typename UtlHashHandle_t index = m_Elements.GetFirstHandle();
+ while ( index != m_Elements.InvalidHandle() )
+ {
+ free( (void *)m_Elements[index].pszSymbol );
+ index = m_Elements.GetNextHandle( index );
+ }
+ }
+
+ m_Elements.RemoveAll();
+ m_nCount = 0;
+}
+
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+void CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Purge()
+{
+ if ( bDupeStrings )
+ {
+ typename UtlHashHandle_t index = m_Elements.GetFirstHandle();
+ while ( index != m_Elements.InvalidHandle() )
+ {
+ free( (void *)m_Elements[index].pszSymbol );
+ index = m_Elements.GetNextHandle( index );
+ }
+ }
+
+ m_Elements.Purge();
+ m_nCount = 0;
+}
+
+
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+void CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::PurgeAndDeleteElements()
+{
+ // Delete all the elements.
+ unsigned index = m_Elements.GetFirstHandle();
+ while ( index != m_Elements.InvalidHandle() )
+ {
+ if ( bDupeStrings )
+ {
+ free( (void *)m_Elements[index].pszSymbol );
+ }
+ delete m_Elements[index].value;
+ index = m_Elements.GetNextHandle( index );
+ }
+
+ m_Elements.RemoveAll();
+ m_nCount = 0;
+}
+
+
+//-----------------------------------------------------------------------------
+// inserts a node into the tree
+//-----------------------------------------------------------------------------
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+unsigned CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Insert( const char *pName, const T &element )
+{
+ MEM_ALLOC_CREDIT_CLASS();
+ m_nCount++;
+ Entry_t entry =
+ {
+ (bDupeStrings) ? strdup( pName ) : pName,
+ element
+ };
+ bool bInserted;
+ unsigned result = m_Elements.Insert( entry, &bInserted );
+ if ( bDupeStrings && !bInserted )
+ {
+ free( (void *)entry.pszSymbol );
+ }
+ return result;
+}
+
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+unsigned CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Insert( const char *pName )
+{
+ MEM_ALLOC_CREDIT_CLASS();
+ m_nCount++;
+ Entry_t entry =
+ {
+ (bDupeStrings) ? strdup( pName ) : pName
+ };
+ bool bInserted;
+ unsigned result = m_Elements.Insert( entry, &bInserted );
+ if ( bDupeStrings && !bInserted )
+ {
+ free( (void *)entry.pszSymbol );
+ }
+ return result;
+}
+
+
+//-----------------------------------------------------------------------------
+// finds a node in the tree
+//-----------------------------------------------------------------------------
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+unsigned CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Find( const char *pName ) const
+{
+ MEM_ALLOC_CREDIT_CLASS();
+ if ( pName )
+ return m_Elements.Find( *((Entry_t *)&pName) );
+ else
+ return InvalidHandle();
+}
+
+
+//-----------------------------------------------------------------------------
+// Iteration methods
+//-----------------------------------------------------------------------------
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+unsigned CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::First() const
+{
+ return m_Elements.GetFirstHandle();
+}
+
+template <typename T, bool bCaseInsensitive, bool bDupeStrings>
+unsigned CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Next( unsigned i ) const
+{
+ return m_Elements.GetNextHandle(i);
+}
+
+#endif // UTLHASHDICT_H
|