source-engine/public/tier1/utlsymbollarge.h

//========= Copyright Valve Corporation, All rights reserved. ============//
//
// Purpose: Defines a large symbol table (intp sized handles, can store more than 64k strings)
//
// $Header: $
// $NoKeywords: $
//===========================================================================//

#ifndef UTLSYMBOLLARGE_H
#define UTLSYMBOLLARGE_H

#ifdef _WIN32
#pragma once
#endif

#include "tier0/threadtools.h"
#include "tier1/utltshash.h"
#include "tier1/stringpool.h"
#include "tier0/vprof.h"
#include "tier1/utltshash.h"

//-----------------------------------------------------------------------------
// CUtlSymbolTableLarge:
// description:
//    This class defines a symbol table, which allows us to perform mappings
//    of strings to symbols and back. 
// 
//    This class stores the strings in a series of string pools. The returned CUtlSymbolLarge is just a pointer
//     to the string data, the hash precedes it in memory and is used to speed up searching, etc.
//-----------------------------------------------------------------------------

typedef intp UtlSymLargeId_t;

#define UTL_INVAL_SYMBOL_LARGE  ((UtlSymLargeId_t)~0)

class CUtlSymbolLarge
{
public:
	// constructor, destructor
	CUtlSymbolLarge() 
	{
		u.m_Id = UTL_INVAL_SYMBOL_LARGE;
	}

	CUtlSymbolLarge( UtlSymLargeId_t id )
	{
		u.m_Id = id;
	}
	CUtlSymbolLarge( CUtlSymbolLarge const& sym )
	{
		u.m_Id = sym.u.m_Id; 
	}

	// operator=
	CUtlSymbolLarge& operator=( CUtlSymbolLarge const& src ) 
	{ 
		u.m_Id = src.u.m_Id; 
		return *this; 
	}

	// operator==
	bool operator==( CUtlSymbolLarge const& src ) const 
	{ 
		return u.m_Id == src.u.m_Id; 
	}

	// operator==
	bool operator==( UtlSymLargeId_t const& src ) const 
	{ 
		return u.m_Id == src; 
	}

	// operator==
	bool operator!=( CUtlSymbolLarge const& src ) const 
	{ 
		return u.m_Id != src.u.m_Id; 
	}

	// operator==
	bool operator!=( UtlSymLargeId_t const& src ) const 
	{ 
		return u.m_Id != src; 
	}

	// Gets at the symbol
	operator UtlSymLargeId_t const() const 
	{ 
		return u.m_Id; 
	}

	// Gets the string associated with the symbol
	inline const char* String( ) const
	{
		if ( u.m_Id == UTL_INVAL_SYMBOL_LARGE )
			return "";
		return u.m_pAsString;
	}

	inline bool IsValid() const
	{
		return u.m_Id != UTL_INVAL_SYMBOL_LARGE ? true : false;
	}

private:
	// Disallowed
	CUtlSymbolLarge( const char* pStr );       // they need to go through the table to assign the ptr
	bool operator==( const char* pStr ) const; // disallow since we don't know if the table this is from was case sensitive or not... maybe we don't care

	union
	{
		UtlSymLargeId_t m_Id;
		char const *m_pAsString;
	} u;
};

#define MIN_STRING_POOL_SIZE	2048

inline uint32 CUtlSymbolLarge_Hash( bool CASEINSENSITIVE, const char *pString, int len )
{
	return ( CASEINSENSITIVE ? HashStringCaseless( pString ) : HashString( pString ) ); 
}

typedef uint32 LargeSymbolTableHashDecoration_t; 

// The structure consists of the hash immediately followed by the string data
struct CUtlSymbolTableLargeBaseTreeEntry_t
{
	LargeSymbolTableHashDecoration_t	m_Hash;
	// Variable length string data
	char								m_String[1];

	bool IsEmpty() const
	{
		return ( ( m_Hash == 0 ) && ( 0 == m_String[0] ) );
	}

	char const *String() const
	{
		return (const char *)&m_String[ 0 ];
	}

	CUtlSymbolLarge ToSymbol() const
	{
		return reinterpret_cast< UtlSymLargeId_t >( String() );
	}
	
	LargeSymbolTableHashDecoration_t HashValue() const
	{
		return m_Hash;
	}
};
	
template< class TreeType, bool CASEINSENSITIVE >
class CTreeEntryLess
{
public:
	CTreeEntryLess( int ignored = 0 ) {} // permits default initialization to NULL in CUtlRBTree
	bool operator!() const { return false; }
	bool operator()( CUtlSymbolTableLargeBaseTreeEntry_t * const &left, CUtlSymbolTableLargeBaseTreeEntry_t * const &right ) const
	{
		// compare the hashes
		if ( left->m_Hash == right->m_Hash )
		{
			// if the hashes match compare the strings
			if ( !CASEINSENSITIVE )
				return strcmp( left->String(), right->String() ) < 0;
			else
				return V_stricmp( left->String(), right->String() ) < 0;
		}
		else
		{
			return left->m_Hash < right->m_Hash;
		}
	}
};
	
// For non-threaded versions, simply index into CUtlRBTree
template< bool CASEINSENSITIVE >
class CNonThreadsafeTree : public CUtlRBTree<CUtlSymbolTableLargeBaseTreeEntry_t *, intp, CTreeEntryLess< CNonThreadsafeTree< CASEINSENSITIVE >, CASEINSENSITIVE > >
{
public:
	typedef CUtlRBTree<CUtlSymbolTableLargeBaseTreeEntry_t *, intp, CTreeEntryLess< CNonThreadsafeTree, CASEINSENSITIVE > > CNonThreadsafeTreeType;

	CNonThreadsafeTree() : 
		CNonThreadsafeTreeType( 0, 16 ) 
	{
	}
	inline void Commit() 
	{
		// Nothing, only matters for thread-safe tables
	}
	inline int Insert( CUtlSymbolTableLargeBaseTreeEntry_t *entry )
	{
		return CNonThreadsafeTreeType::Insert( entry );
	}
	inline int Find( CUtlSymbolTableLargeBaseTreeEntry_t *entry ) const
	{
		return CNonThreadsafeTreeType::Find( entry );
	}
	inline int InvalidIndex() const
	{
		return CNonThreadsafeTreeType::InvalidIndex();
	}
	inline int GetElements( int nFirstElement, int nCount, CUtlSymbolLarge *pElements ) const
	{
		CUtlVector< CUtlSymbolTableLargeBaseTreeEntry_t * > list;
		list.EnsureCount( nCount );
		for ( int i = 0; i < nCount; ++i )
		{
			pElements[ i ] = CNonThreadsafeTreeType::Element( i )->ToSymbol();
		}

		return nCount;
	}
};

// Since CUtlSymbolTableLargeBaseTreeEntry_t already has the hash 
//  contained inside of it, don't need to recompute a hash here
template < int BUCKET_COUNT, class KEYTYPE, bool CASEINSENSITIVE >
class CCThreadsafeTreeHashMethod
{
public:
	static int Hash( const KEYTYPE &key, int nBucketMask )
	{
		uint32 nHash = key->HashValue();
		return ( nHash & nBucketMask );
	}

	static bool Compare( CUtlSymbolTableLargeBaseTreeEntry_t * const &lhs, CUtlSymbolTableLargeBaseTreeEntry_t * const &rhs )
	{
		if ( lhs->m_Hash != rhs->m_Hash )
			return false;
		if ( !CASEINSENSITIVE )
		{
			return ( !Q_strcmp( lhs->String(), rhs->String() ) ? true : false );
		}

		return ( !Q_stricmp( lhs->String(), rhs->String() ) ? true : false );
	}
};

/*
  NOTE:  So the only crappy thing about using a CUtlTSHash here is that the KEYTYPE is a CUtlSymbolTableLargeBaseTreeEntry_t ptr which has both the 
   hash and the string since with strings there is a good chance of hash collision after you have a fair number of strings so we have to implement
   a Compare method (above) which falls back to strcmp/stricmp if the hashes are equal.  This means that all of the data is in the KEYTYPE of the hash and the 
   payload doesn't matter.  So I made the payload also be a pointer to a CUtlSymbolTableLargeBaseTreeEntry_t since that makes using the API more convenient

  TODO:  If we have a CUtlTSHash that was all about the existence of the KEYTYPE and didn't require a payload (or template on 'void') then we could eliminate
   50% of the pointer overhead used for this data structure.
*/

// Thread safe version is based on the 
template < bool CASEINSENSITIVE >
class CThreadsafeTree : public CUtlTSHash< CUtlSymbolTableLargeBaseTreeEntry_t *, 2048, CUtlSymbolTableLargeBaseTreeEntry_t *, CCThreadsafeTreeHashMethod< 2048, CUtlSymbolTableLargeBaseTreeEntry_t *, CASEINSENSITIVE > >
{
public:
	typedef CUtlTSHash< CUtlSymbolTableLargeBaseTreeEntry_t *, 2048, CUtlSymbolTableLargeBaseTreeEntry_t *, CCThreadsafeTreeHashMethod< 2048, CUtlSymbolTableLargeBaseTreeEntry_t *, CASEINSENSITIVE > > CThreadsafeTreeType;

	CThreadsafeTree() : 
		CThreadsafeTreeType( 32 ) 
	{
	}
	inline void Commit() 
	{
		CThreadsafeTreeType::Commit();
	}
	inline int Insert( CUtlSymbolTableLargeBaseTreeEntry_t *entry )
	{
		return CThreadsafeTreeType::Insert( entry, entry );
	}
	inline int Find( CUtlSymbolTableLargeBaseTreeEntry_t *entry )
	{
		return CThreadsafeTreeType::Find( entry );
	}
	inline int InvalidIndex() const
	{
		return CThreadsafeTreeType::InvalidHandle();
	}
	inline int GetElements( int nFirstElement, int nCount, CUtlSymbolLarge *pElements ) const
	{
		CUtlVector< UtlTSHashHandle_t > list;
		list.EnsureCount( nCount );
		int c = CThreadsafeTreeType::GetElements( nFirstElement, nCount, list.Base() );
		for ( int i = 0; i < c; ++i )
		{
			pElements[ i ] = CThreadsafeTreeType::Element( list[ i ] )->ToSymbol();
		}
		
		return c;
	}
};

// Base Class for threaded and non-threaded types
template < class TreeType, bool CASEINSENSITIVE, size_t POOL_SIZE = MIN_STRING_POOL_SIZE >
class CUtlSymbolTableLargeBase
{
public:
	// constructor, destructor
	CUtlSymbolTableLargeBase();
	~CUtlSymbolTableLargeBase();
	
	// Finds and/or creates a symbol based on the string
	CUtlSymbolLarge AddString( const char* pString );

	// Finds the symbol for pString
	CUtlSymbolLarge Find( const char* pString ) const;
	
	// Remove all symbols in the table.
	void  RemoveAll();

	int GetNumStrings( void ) const
	{
		return m_Lookup.Count();
	}

	void Commit()
	{
		m_Lookup.Commit();
	}

	// Returns elements in the table
	int GetElements( int nFirstElement, int nCount, CUtlSymbolLarge *pElements ) const
	{
		return m_Lookup.GetElements( nFirstElement, nCount, pElements );
	}

	uint64 GetMemoryUsage() const
	{
		uint64 unBytesUsed = 0u;

		for ( int i=0; i < m_StringPools.Count(); i++ )
		{
			StringPool_t *pPool = m_StringPools[i];

			unBytesUsed += (uint64)pPool->m_TotalLen;
		}
		return unBytesUsed;
	}


protected:

	struct StringPool_t
	{	
		int m_TotalLen;		// How large is 
		int m_SpaceUsed;
		char m_Data[1];
	};

	TreeType m_Lookup;

	// stores the string data
	CUtlVector< StringPool_t * > m_StringPools;

private:
	int FindPoolWithSpace( int len ) const;
};

//-----------------------------------------------------------------------------
// constructor, destructor
//-----------------------------------------------------------------------------
template < class TreeType, bool CASEINSENSITIVE, size_t POOL_SIZE >
inline CUtlSymbolTableLargeBase<TreeType, CASEINSENSITIVE, POOL_SIZE >::CUtlSymbolTableLargeBase() : 
	m_StringPools( 8 )
{
}

template < class TreeType, bool CASEINSENSITIVE, size_t POOL_SIZE >
inline CUtlSymbolTableLargeBase<TreeType, CASEINSENSITIVE, POOL_SIZE>::~CUtlSymbolTableLargeBase()
{
	// Release the stringpool string data
	RemoveAll();
}

template < class TreeType, bool CASEINSENSITIVE, size_t POOL_SIZE >
inline CUtlSymbolLarge CUtlSymbolTableLargeBase<TreeType, CASEINSENSITIVE, POOL_SIZE>::Find( const char* pString ) const
{	
	VPROF( "CUtlSymbolLarge::Find" );
	if (!pString)
		return CUtlSymbolLarge();

	// Passing this special invalid symbol makes the comparison function
	// use the string passed in the context
	int len = Q_strlen( pString ) + 1;

	CUtlSymbolTableLargeBaseTreeEntry_t *search = (CUtlSymbolTableLargeBaseTreeEntry_t *)_alloca( len + sizeof( LargeSymbolTableHashDecoration_t ) );
	search->m_Hash = CUtlSymbolLarge_Hash( CASEINSENSITIVE, pString, len );
	Q_memcpy( (char *)&search->m_String[ 0 ], pString, len );

	int idx = const_cast< TreeType & >(m_Lookup).Find( search );

	if ( idx == m_Lookup.InvalidIndex() )
		return UTL_INVAL_SYMBOL_LARGE;

	const CUtlSymbolTableLargeBaseTreeEntry_t *entry = m_Lookup[ idx ];
	return entry->ToSymbol();
}

template < class TreeType, bool CASEINSENSITIVE, size_t POOL_SIZE >
inline int CUtlSymbolTableLargeBase<TreeType, CASEINSENSITIVE, POOL_SIZE>::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
//-----------------------------------------------------------------------------
template < class TreeType, bool CASEINSENSITIVE, size_t POOL_SIZE >
inline CUtlSymbolLarge CUtlSymbolTableLargeBase<TreeType, CASEINSENSITIVE, POOL_SIZE>::AddString( const char* pString )
{
	VPROF("CUtlSymbolLarge::AddString");
	if (!pString) 
		return UTL_INVAL_SYMBOL_LARGE;

	CUtlSymbolLarge id = Find( pString );
	if ( id != UTL_INVAL_SYMBOL_LARGE )
		return id;

	int lenString = Q_strlen(pString) + 1; // length of just the string
	int lenDecorated = lenString + sizeof(LargeSymbolTableHashDecoration_t); // and with its hash decoration
	// make sure that all strings are aligned on 2-byte boundaries so the hashes will read correctly
	// This assert seems to be invalid because LargeSymbolTableHashDecoration_t is always
	// a uint32, by design.
	//COMPILE_TIME_ASSERT(sizeof(LargeSymbolTableHashDecoration_t) == sizeof(intp));
	lenDecorated = ALIGN_VALUE(lenDecorated, sizeof( intp ) );

	// 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 ), 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
	LargeSymbolTableHashDecoration_t hash = CUtlSymbolLarge_Hash( CASEINSENSITIVE, pString, lenString );

	// Copy the string in.
	StringPool_t *pPool = m_StringPools[iPool];
	// Assert( pPool->m_SpaceUsed < 0xFFFF );	// Pool could be bigger than 2k
	// This should never happen, because if we had a string > 64k, it
	// would have been given its entire own pool.
	
	CUtlSymbolTableLargeBaseTreeEntry_t *entry = ( CUtlSymbolTableLargeBaseTreeEntry_t * )&pPool->m_Data[ pPool->m_SpaceUsed ];
	
	pPool->m_SpaceUsed += lenDecorated;

	entry->m_Hash = hash;
	char *pText = (char *)&entry->m_String [ 0 ];
	Q_memcpy( pText, pString, lenString );

	// insert the string into the database
	MEM_ALLOC_CREDIT();
	int idx = m_Lookup.Insert( entry );
	return m_Lookup.Element( idx )->ToSymbol();
}

//-----------------------------------------------------------------------------
// Remove all symbols in the table.
//-----------------------------------------------------------------------------
template < class TreeType, bool CASEINSENSITIVE, size_t POOL_SIZE >
inline void CUtlSymbolTableLargeBase<TreeType, CASEINSENSITIVE, POOL_SIZE>::RemoveAll()
{
	m_Lookup.Purge();

	for ( int i=0; i < m_StringPools.Count(); i++ )
	{
		StringPool_t * pString = m_StringPools[i];
		free( pString );
	}

	m_StringPools.RemoveAll();
}

// Case-sensitive
typedef CUtlSymbolTableLargeBase< CNonThreadsafeTree< false >, false > CUtlSymbolTableLarge;
// Case-insensitive
typedef CUtlSymbolTableLargeBase< CNonThreadsafeTree< true >, true > CUtlSymbolTableLarge_CI;
// Multi-threaded case-sensitive
typedef CUtlSymbolTableLargeBase< CThreadsafeTree< false >, false > CUtlSymbolTableLargeMT;
// Multi-threaded case-insensitive
typedef CUtlSymbolTableLargeBase< CThreadsafeTree< true >, true > CUtlSymbolTableLargeMT_CI;

#endif // UTLSYMBOLLARGE_H