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 /mp/src/tier1/stringpool.cpp | |
| download | source-sdk-2013-39ed87570bdb2f86969d4be821c94b722dc71179.tar.xz source-sdk-2013-39ed87570bdb2f86969d4be821c94b722dc71179.zip | |
First version of the SOurce SDK 2013
Diffstat (limited to 'mp/src/tier1/stringpool.cpp')
| -rw-r--r-- | mp/src/tier1/stringpool.cpp | 334 |
1 files changed, 334 insertions, 0 deletions
diff --git a/mp/src/tier1/stringpool.cpp b/mp/src/tier1/stringpool.cpp new file mode 100644 index 00000000..f891ed49 --- /dev/null +++ b/mp/src/tier1/stringpool.cpp @@ -0,0 +1,334 @@ +//========= Copyright Valve Corporation, All rights reserved. ============//
+//
+// Purpose:
+//
+// $NoKeywords: $
+//===========================================================================//
+
+#include "convar.h"
+#include "tier0/dbg.h"
+#include "stringpool.h"
+#include "tier1/strtools.h"
+#include "generichash.h"
+
+// memdbgon must be the last include file in a .cpp file!!!
+#include "tier0/memdbgon.h"
+
+//-----------------------------------------------------------------------------
+// Purpose: Comparison function for string sorted associative data structures
+//-----------------------------------------------------------------------------
+
+bool StrLess( const char * const &pszLeft, const char * const &pszRight )
+{
+ return ( Q_stricmp( pszLeft, pszRight) < 0 );
+}
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+
+CStringPool::CStringPool()
+ : m_Strings( 32, 256, StrLess )
+{
+}
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+
+CStringPool::~CStringPool()
+{
+ FreeAll();
+}
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+
+unsigned int CStringPool::Count() const
+{
+ return m_Strings.Count();
+}
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+const char * CStringPool::Find( const char *pszValue )
+{
+ unsigned short i = m_Strings.Find(pszValue);
+ if ( m_Strings.IsValidIndex(i) )
+ return m_Strings[i];
+
+ return NULL;
+}
+
+const char * CStringPool::Allocate( const char *pszValue )
+{
+ char *pszNew;
+
+ unsigned short i = m_Strings.Find(pszValue);
+ bool bNew = (i == m_Strings.InvalidIndex());
+
+ if ( !bNew )
+ return m_Strings[i];
+
+ pszNew = strdup( pszValue );
+
+ if ( bNew )
+ m_Strings.Insert( pszNew );
+
+ return pszNew;
+}
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+
+void CStringPool::FreeAll()
+{
+ unsigned short i = m_Strings.FirstInorder();
+ while ( i != m_Strings.InvalidIndex() )
+ {
+ free( (void *)m_Strings[i] );
+ i = m_Strings.NextInorder(i);
+ }
+ m_Strings.RemoveAll();
+}
+
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+
+
+CCountedStringPool::CCountedStringPool()
+{
+ MEM_ALLOC_CREDIT();
+ m_HashTable.EnsureCount(HASH_TABLE_SIZE);
+
+ for( int i = 0; i < m_HashTable.Count(); i++ )
+ {
+ m_HashTable[i] = INVALID_ELEMENT;
+ }
+
+ m_FreeListStart = INVALID_ELEMENT;
+ m_Elements.AddToTail();
+ m_Elements[0].pString = NULL;
+ m_Elements[0].nReferenceCount = 0;
+ m_Elements[0].nNextElement = INVALID_ELEMENT;
+}
+
+CCountedStringPool::~CCountedStringPool()
+{
+ FreeAll();
+}
+
+void CCountedStringPool::FreeAll()
+{
+ int i;
+
+ // Reset the hash table:
+ for( i = 0; i < m_HashTable.Count(); i++ )
+ {
+ m_HashTable[i] = INVALID_ELEMENT;
+ }
+
+ // Blow away the free list:
+ m_FreeListStart = INVALID_ELEMENT;
+
+ for( i = 0; i < m_Elements.Count(); i++ )
+ {
+ if( m_Elements[i].pString )
+ {
+ delete [] m_Elements[i].pString;
+ m_Elements[i].pString = NULL;
+ m_Elements[i].nReferenceCount = 0;
+ m_Elements[i].nNextElement = INVALID_ELEMENT;
+ }
+ }
+
+ // Remove all but the invalid element:
+ m_Elements.RemoveAll();
+ m_Elements.AddToTail();
+ m_Elements[0].pString = NULL;
+ m_Elements[0].nReferenceCount = 0;
+ m_Elements[0].nNextElement = INVALID_ELEMENT;
+}
+
+
+unsigned short CCountedStringPool::FindStringHandle( const char* pIntrinsic )
+{
+ if( pIntrinsic == NULL )
+ return INVALID_ELEMENT;
+
+ unsigned short nHashBucketIndex = (HashStringCaseless(pIntrinsic ) %HASH_TABLE_SIZE);
+ unsigned short nCurrentBucket = m_HashTable[ nHashBucketIndex ];
+
+ // Does the bucket already exist?
+ if( nCurrentBucket != INVALID_ELEMENT )
+ {
+ for( ; nCurrentBucket != INVALID_ELEMENT ; nCurrentBucket = m_Elements[nCurrentBucket].nNextElement )
+ {
+ if( !Q_stricmp( pIntrinsic, m_Elements[nCurrentBucket].pString ) )
+ {
+ return nCurrentBucket;
+ }
+ }
+ }
+
+ return 0;
+
+}
+
+char* CCountedStringPool::FindString( const char* pIntrinsic )
+{
+ if( pIntrinsic == NULL )
+ return NULL;
+
+ // Yes, this will be NULL on failure.
+ return m_Elements[FindStringHandle(pIntrinsic)].pString;
+}
+
+unsigned short CCountedStringPool::ReferenceStringHandle( const char* pIntrinsic )
+{
+ if( pIntrinsic == NULL )
+ return INVALID_ELEMENT;
+
+ unsigned short nHashBucketIndex = (HashStringCaseless( pIntrinsic ) % HASH_TABLE_SIZE);
+ unsigned short nCurrentBucket = m_HashTable[ nHashBucketIndex ];
+
+ // Does the bucket already exist?
+ if( nCurrentBucket != INVALID_ELEMENT )
+ {
+ for( ; nCurrentBucket != INVALID_ELEMENT ; nCurrentBucket = m_Elements[nCurrentBucket].nNextElement )
+ {
+ if( !Q_stricmp( pIntrinsic, m_Elements[nCurrentBucket].pString ) )
+ {
+ // Anyone who hits 65k references is permanant
+ if( m_Elements[nCurrentBucket].nReferenceCount < MAX_REFERENCE )
+ {
+ m_Elements[nCurrentBucket].nReferenceCount ++ ;
+ }
+ return nCurrentBucket;
+ }
+ }
+ }
+
+ if( m_FreeListStart != INVALID_ELEMENT )
+ {
+ nCurrentBucket = m_FreeListStart;
+ m_FreeListStart = m_Elements[nCurrentBucket].nNextElement;
+ }
+ else
+ {
+ nCurrentBucket = m_Elements.AddToTail();
+ }
+
+ m_Elements[nCurrentBucket].nReferenceCount = 1;
+
+ // Insert at the beginning of the bucket:
+ m_Elements[nCurrentBucket].nNextElement = m_HashTable[ nHashBucketIndex ];
+ m_HashTable[ nHashBucketIndex ] = nCurrentBucket;
+
+ m_Elements[nCurrentBucket].pString = new char[Q_strlen( pIntrinsic ) + 1];
+ Q_strcpy( m_Elements[nCurrentBucket].pString, pIntrinsic );
+
+ return nCurrentBucket;
+}
+
+
+char* CCountedStringPool::ReferenceString( const char* pIntrinsic )
+{
+ if(!pIntrinsic)
+ return NULL;
+
+ return m_Elements[ReferenceStringHandle( pIntrinsic)].pString;
+}
+
+void CCountedStringPool::DereferenceString( const char* pIntrinsic )
+{
+ // If we get a NULL pointer, just return
+ if (!pIntrinsic)
+ return;
+
+ unsigned short nHashBucketIndex = (HashStringCaseless( pIntrinsic ) % m_HashTable.Count());
+ unsigned short nCurrentBucket = m_HashTable[ nHashBucketIndex ];
+
+ // If there isn't anything in the bucket, just return.
+ if ( nCurrentBucket == INVALID_ELEMENT )
+ return;
+
+ for( unsigned short previous = INVALID_ELEMENT; nCurrentBucket != INVALID_ELEMENT ; nCurrentBucket = m_Elements[nCurrentBucket].nNextElement )
+ {
+ if( !Q_stricmp( pIntrinsic, m_Elements[nCurrentBucket].pString ) )
+ {
+ // Anyone who hits 65k references is permanant
+ if( m_Elements[nCurrentBucket].nReferenceCount < MAX_REFERENCE )
+ {
+ m_Elements[nCurrentBucket].nReferenceCount --;
+ }
+
+ if( m_Elements[nCurrentBucket].nReferenceCount == 0 )
+ {
+ if( previous == INVALID_ELEMENT )
+ {
+ m_HashTable[nHashBucketIndex] = m_Elements[nCurrentBucket].nNextElement;
+ }
+ else
+ {
+ m_Elements[previous].nNextElement = m_Elements[nCurrentBucket].nNextElement;
+ }
+
+ delete [] m_Elements[nCurrentBucket].pString;
+ m_Elements[nCurrentBucket].pString = NULL;
+ m_Elements[nCurrentBucket].nReferenceCount = 0;
+
+ m_Elements[nCurrentBucket].nNextElement = m_FreeListStart;
+ m_FreeListStart = nCurrentBucket;
+ break;
+
+ }
+ }
+
+ previous = nCurrentBucket;
+ }
+}
+
+char* CCountedStringPool::HandleToString( unsigned short handle )
+{
+ return m_Elements[handle].pString;
+}
+
+void CCountedStringPool::SpewStrings()
+{
+ int i;
+ for ( i = 0; i < m_Elements.Count(); i++ )
+ {
+ char* string = m_Elements[i].pString;
+
+ Msg("String %d: ref:%d %s", i, m_Elements[i].nReferenceCount, string == NULL? "EMPTY - ok for slot zero only!" : string);
+ }
+
+ Msg("\n%d total counted strings.", m_Elements.Count());
+}
+
+#ifdef _DEBUG
+CON_COMMAND( test_stringpool, "Tests the class CStringPool" )
+{
+ CStringPool pool;
+
+ Assert(pool.Count() == 0);
+
+ pool.Allocate("test");
+ Assert(pool.Count() == 1);
+
+ pool.Allocate("test");
+ Assert(pool.Count() == 1);
+
+ pool.Allocate("test2");
+ Assert(pool.Count() == 2);
+
+ Assert( pool.Find("test2") != NULL );
+ Assert( pool.Find("TEST") != NULL );
+ Assert( pool.Find("Test2") != NULL );
+ Assert( pool.Find("test") != NULL );
+
+ pool.FreeAll();
+ Assert(pool.Count() == 0);
+
+ Msg("Pass.");
+}
+#endif
|