//========= Copyright � 1996-2005, Valve Corporation, All rights reserved. ============// // // Purpose: Defines a symbol table // // $Header: $ // $NoKeywords: $ //=============================================================================// #pragma warning (disable:4514) #include "utlsymbol.h" #include "tier0/threadtools.h" #include "stringpool.h" #include "generichash.h" #include "tier0/vprof.h" #include // memdbgon must be the last include file in a .cpp file!!! #include "tier0/memdbgon.h" #define INVALID_STRING_INDEX CStringPoolIndex( 0xFFFF, 0xFFFF ) #define MIN_STRING_POOL_SIZE 2048 //----------------------------------------------------------------------------- // globals //----------------------------------------------------------------------------- CUtlSymbolTableMT* CUtlSymbol::s_pSymbolTable = 0; bool CUtlSymbol::s_bAllowStaticSymbolTable = true; //----------------------------------------------------------------------------- // symbol methods //----------------------------------------------------------------------------- void CUtlSymbol::Initialize() { // If this assert fails, then the module that this call is in has chosen to disallow // use of the static symbol table. Usually, it's to prevent confusion because it's easy // to accidentally use the global symbol table when you really want to use a specific one. Assert( s_bAllowStaticSymbolTable ); // necessary to allow us to create global symbols static bool symbolsInitialized = false; if (!symbolsInitialized) { s_pSymbolTable = new CUtlSymbolTableMT; symbolsInitialized = true; } } void CUtlSymbol::LockTableForRead() { Initialize(); s_pSymbolTable->LockForRead(); } void CUtlSymbol::UnlockTableForRead() { s_pSymbolTable->UnlockForRead(); } //----------------------------------------------------------------------------- // Purpose: Singleton to delete table on exit from module //----------------------------------------------------------------------------- class CCleanupUtlSymbolTable { public: ~CCleanupUtlSymbolTable() { delete CUtlSymbol::s_pSymbolTable; CUtlSymbol::s_pSymbolTable = NULL; } }; static CCleanupUtlSymbolTable g_CleanupSymbolTable; CUtlSymbolTableMT* CUtlSymbol::CurrTable() { Initialize(); return s_pSymbolTable; } //----------------------------------------------------------------------------- // string->symbol->string //----------------------------------------------------------------------------- CUtlSymbol::CUtlSymbol( const char* pStr ) { m_Id = CurrTable()->AddString( pStr ); } const char* CUtlSymbol::String( ) const { return CurrTable()->String(m_Id); } const char* CUtlSymbol::StringNoLock( ) const { return CurrTable()->StringNoLock(m_Id); } void CUtlSymbol::DisableStaticSymbolTable() { s_bAllowStaticSymbolTable = false; } //----------------------------------------------------------------------------- // checks if the symbol matches a string //----------------------------------------------------------------------------- bool CUtlSymbol::operator==( const char* pStr ) const { if (m_Id == UTL_INVAL_SYMBOL) return false; return strcmp( String(), pStr ) == 0; } //----------------------------------------------------------------------------- // symbol table stuff //----------------------------------------------------------------------------- inline const char* CUtlSymbolTable::DecoratedStringFromIndex( const CStringPoolIndex &index ) const { Assert( index.m_iPool < m_StringPools.Count() ); Assert( index.m_iOffset < m_StringPools[index.m_iPool]->m_TotalLen ); // step over the hash decorating the beginning of the string return (&m_StringPools[index.m_iPool]->m_Data[index.m_iOffset]); } inline const char* CUtlSymbolTable::StringFromIndex( const CStringPoolIndex &index ) const { // step over the hash decorating the beginning of the string return DecoratedStringFromIndex(index)+sizeof(hashDecoration_t); } // The first two bytes of each string in the pool are actually the hash for that string. // Thus we compare hashes rather than entire strings for a significant perf benefit. // However since there is a high rate of hash collision we must still compare strings // if the hashes match. bool CUtlSymbolTable::CLess::operator()( const CStringPoolIndex &i1, const CStringPoolIndex &i2 ) const { // Need to do pointer math because CUtlSymbolTable is used in CUtlVectors, and hence // can be arbitrarily moved in memory on a realloc. Yes, this is portable. In reality, // right now at least, because m_LessFunc is the first member of CUtlRBTree, and m_Lookup // is the first member of CUtlSymbolTabke, this == pTable CUtlSymbolTable *pTable = (CUtlSymbolTable *)( (byte *)this - offsetof(CUtlSymbolTable::CTree, m_LessFunc) ) - offsetof(CUtlSymbolTable, m_Lookup ); #if 1 // using the hashes const char *str1, *str2; hashDecoration_t hash1, hash2; if (i1 == INVALID_STRING_INDEX) { str1 = pTable->m_pUserSearchString; hash1 = pTable->m_nUserSearchStringHash; } else { str1 = pTable->DecoratedStringFromIndex( i1 ); hashDecoration_t storedHash = *reinterpret_cast(str1); str1 += sizeof(hashDecoration_t); AssertMsg2( storedHash == ( !pTable->m_bInsensitive ? HashString(str1) : HashStringCaseless(str1) ), "The stored hash (%d) for symbol %s is not correct.", storedHash, str1 ); hash1 = storedHash; } if (i2 == INVALID_STRING_INDEX) { str2 = pTable->m_pUserSearchString; hash2 = pTable->m_nUserSearchStringHash; } else { str2 = pTable->DecoratedStringFromIndex( i2 ); hashDecoration_t storedHash = *reinterpret_cast(str2); str2 += sizeof(hashDecoration_t); AssertMsg2( storedHash == ( !pTable->m_bInsensitive ? HashString(str2) : HashStringCaseless(str2) ), "The stored hash (%d) for symbol '%s' is not correct.", storedHash, str2 ); hash2 = storedHash; } // compare the hashes if ( hash1 == hash2 ) { if ( !str1 && str2 ) return 1; if ( !str2 && str1 ) return -1; if ( !str1 && !str2 ) return 0; // if the hashes match compare the strings if ( !pTable->m_bInsensitive ) return strcmp( str1, str2 ) < 0; else return V_stricmp( str1, str2 ) < 0; } else { return hash1 < hash2; } #else // not using the hashes, just comparing strings const char* str1 = (i1 == INVALID_STRING_INDEX) ? pTable->m_pUserSearchString : pTable->StringFromIndex( i1 ); const char* str2 = (i2 == INVALID_STRING_INDEX) ? pTable->m_pUserSearchString : pTable->StringFromIndex( i2 ); if ( !str1 && str2 ) return 1; if ( !str2 && str1 ) return -1; if ( !str1 && !str2 ) return 0; if ( !pTable->m_bInsensitive ) return strcmp( str1, str2 ) < 0; else return strcmpi( str1, str2 ) < 0; #endif } //----------------------------------------------------------------------------- // constructor, destructor //----------------------------------------------------------------------------- CUtlSymbolTable::CUtlSymbolTable( int growSize, int initSize, bool caseInsensitive ) : m_Lookup( growSize, initSize ), m_bInsensitive( caseInsensitive ), m_StringPools( 8 ) { } CUtlSymbolTable::~CUtlSymbolTable() { // Release the stringpool string data RemoveAll(); } CUtlSymbol CUtlSymbolTable::Find( const char* pString ) const { VPROF( "CUtlSymbol::Find" ); if (!pString) return CUtlSymbol(); // Store a special context used to help with insertion m_pUserSearchString = pString; m_nUserSearchStringHash = m_bInsensitive ? HashStringCaseless(pString) : HashString(pString) ; // Passing this special invalid symbol makes the comparison function // use the string passed in the context UtlSymId_t idx = m_Lookup.Find( INVALID_STRING_INDEX ); #ifdef _DEBUG m_pUserSearchString = NULL; m_nUserSearchStringHash = 0; #endif return CUtlSymbol( idx ); } int CUtlSymbolTable::FindPoolWithSpace( int len ) const { for ( int i=0; i < m_StringPools.Count(); i++ ) { StringPool_t *pPool = m_StringPools[i]; if ( (pPool->m_TotalLen - pPool->m_SpaceUsed) >= len ) { return i; } } return -1; } //----------------------------------------------------------------------------- // Finds and/or creates a symbol based on the string //----------------------------------------------------------------------------- CUtlSymbol CUtlSymbolTable::AddString( const char* pString ) { VPROF("CUtlSymbol::AddString"); if (!pString) return CUtlSymbol( UTL_INVAL_SYMBOL ); CUtlSymbol id = Find( pString ); if (id.IsValid()) return id; int lenString = strlen(pString) + 1; // length of just the string int lenDecorated = lenString + sizeof(hashDecoration_t); // and with its hash decoration // make sure that all strings are aligned on 2-byte boundaries so the hashes will read correctly COMPILE_TIME_ASSERT(sizeof(hashDecoration_t) == 2); lenDecorated = (lenDecorated + 1) & (~0x01); // round up to nearest multiple of 2 // Find a pool with space for this string, or allocate a new one. int iPool = FindPoolWithSpace( lenDecorated ); if ( iPool == -1 ) { // Add a new pool. int newPoolSize = MAX( lenDecorated + sizeof( StringPool_t ), MIN_STRING_POOL_SIZE ); StringPool_t *pPool = (StringPool_t*)malloc( newPoolSize ); pPool->m_TotalLen = newPoolSize - sizeof( StringPool_t ); pPool->m_SpaceUsed = 0; iPool = m_StringPools.AddToTail( pPool ); } // Compute a hash hashDecoration_t hash = m_bInsensitive ? HashStringCaseless(pString) : HashString(pString) ; // Copy the string in. StringPool_t *pPool = m_StringPools[iPool]; Assert( pPool->m_SpaceUsed < 0xFFFF ); // This should never happen, because if we had a string > 64k, it // would have been given its entire own pool. unsigned short iStringOffset = pPool->m_SpaceUsed; const char *startingAddr = &pPool->m_Data[pPool->m_SpaceUsed]; // store the hash at the head of the string *((hashDecoration_t *)(startingAddr)) = hash; // and then the string's data memcpy( (void *)(startingAddr + sizeof(hashDecoration_t)), pString, lenString ); pPool->m_SpaceUsed += lenDecorated; // insert the string into the vector. CStringPoolIndex index; index.m_iPool = iPool; index.m_iOffset = iStringOffset; MEM_ALLOC_CREDIT(); UtlSymId_t idx = m_Lookup.Insert( index ); return CUtlSymbol( idx ); } //----------------------------------------------------------------------------- // Look up the string associated with a particular symbol //----------------------------------------------------------------------------- const char* CUtlSymbolTable::String( CUtlSymbol id ) const { if (!id.IsValid()) return ""; Assert( m_Lookup.IsValidIndex((UtlSymId_t)id) ); return StringFromIndex( m_Lookup[id] ); } //----------------------------------------------------------------------------- // Remove all symbols in the table. //----------------------------------------------------------------------------- void CUtlSymbolTable::RemoveAll() { m_Lookup.Purge(); for ( int i=0; i < m_StringPools.Count(); i++ ) free( m_StringPools[i] ); m_StringPools.RemoveAll(); } //----------------------------------------------------------------------------- // Purpose: // Input : *pFileName - // Output : FileNameHandle_t //----------------------------------------------------------------------------- FileNameHandle_t CUtlFilenameSymbolTable::FindOrAddFileName( const char *pFileName ) { if ( !pFileName ) { return NULL; } // find first FileNameHandle_t hFileName = FindFileName( pFileName ); if ( hFileName ) { return hFileName; } // Fix slashes+dotslashes and make lower case first.. char fn[ MAX_PATH ]; Q_strncpy( fn, pFileName, sizeof( fn ) ); Q_RemoveDotSlashes( fn ); #ifdef _WIN32 strlwr( fn ); #endif // Split the filename into constituent parts char basepath[ MAX_PATH ]; Q_ExtractFilePath( fn, basepath, sizeof( basepath ) ); char filename[ MAX_PATH ]; Q_strncpy( filename, fn + Q_strlen( basepath ), sizeof( filename ) ); // not found, lock and look again FileNameHandleInternal_t handle; m_lock.LockForWrite(); handle.SetPath( m_PathStringPool.FindStringHandle( basepath ) ); handle.SetFile( m_FileStringPool.FindStringHandle( filename ) ); if ( handle.GetPath() && handle.GetFile() ) { // found m_lock.UnlockWrite(); return *( FileNameHandle_t * )( &handle ); } // safely add it handle.SetPath( m_PathStringPool.ReferenceStringHandle( basepath ) ); handle.SetFile( m_FileStringPool.ReferenceStringHandle( filename ) ); m_lock.UnlockWrite(); return *( FileNameHandle_t * )( &handle ); } FileNameHandle_t CUtlFilenameSymbolTable::FindFileName( const char *pFileName ) { if ( !pFileName ) { return NULL; } // Fix slashes+dotslashes and make lower case first.. char fn[ MAX_PATH ]; Q_strncpy( fn, pFileName, sizeof( fn ) ); Q_RemoveDotSlashes( fn ); #ifdef _WIN32 strlwr( fn ); #endif // Split the filename into constituent parts char basepath[ MAX_PATH ]; Q_ExtractFilePath( fn, basepath, sizeof( basepath ) ); char filename[ MAX_PATH ]; Q_strncpy( filename, fn + Q_strlen( basepath ), sizeof( filename ) ); FileNameHandleInternal_t handle; m_lock.LockForRead(); handle.SetPath( m_PathStringPool.FindStringHandle( basepath ) ); handle.SetFile( m_FileStringPool.FindStringHandle( filename ) ); m_lock.UnlockRead(); if ( ( handle.GetPath() == 0 ) || ( handle.GetFile() == 0 ) ) return NULL; return *( FileNameHandle_t * )( &handle ); } //----------------------------------------------------------------------------- // Purpose: // Input : handle - // Output : const char //----------------------------------------------------------------------------- bool CUtlFilenameSymbolTable::String( const FileNameHandle_t& handle, char *buf, int buflen ) { buf[ 0 ] = 0; FileNameHandleInternal_t *internalFileHandle = ( FileNameHandleInternal_t * )&handle; if ( !internalFileHandle ) { return false; } m_lock.LockForRead(); const char *path = m_PathStringPool.HandleToString( internalFileHandle->GetPath() ); const char *fn = m_FileStringPool.HandleToString( internalFileHandle->GetFile() ); m_lock.UnlockRead(); if ( !path || !fn ) { return false; } Q_strncpy( buf, path, buflen ); Q_strncat( buf, fn, buflen, COPY_ALL_CHARACTERS ); return true; } void CUtlFilenameSymbolTable::RemoveAll() { m_PathStringPool.FreeAll(); m_FileStringPool.FreeAll(); } void CUtlFilenameSymbolTable::SpewStrings() { m_lock.LockForRead(); m_PathStringPool.SpewStrings(); m_FileStringPool.SpewStrings(); m_lock.UnlockRead(); } bool CUtlFilenameSymbolTable::SaveToBuffer( CUtlBuffer &buffer ) { m_lock.LockForRead(); bool bResult = m_PathStringPool.SaveToBuffer( buffer ); bResult = bResult && m_FileStringPool.SaveToBuffer( buffer ); m_lock.UnlockRead(); return bResult; } bool CUtlFilenameSymbolTable::RestoreFromBuffer( CUtlBuffer &buffer ) { m_lock.LockForWrite(); bool bResult = m_PathStringPool.RestoreFromBuffer( buffer ); bResult = bResult && m_FileStringPool.RestoreFromBuffer( buffer ); m_lock.UnlockWrite(); return bResult; }