Fix line endings. WHAMMY.

1 files changed, 698 insertions, 698 deletions

diff --git a/mp/src/public/tier1/thash.h b/mp/src/public/tier1/thash.h
index 453aebf0..51020749 100644
--- a/mp/src/public/tier1/thash.h
+++ b/mp/src/public/tier1/thash.h
@@ -1,698 +1,698 @@
-//========= Copyright Valve Corporation, All rights reserved. ============//

-//

-// Purpose:

-//

-// $NoKeywords: $

-//=============================================================================

-

-#ifndef THASH_H

-#define THASH_H

-#ifdef _WIN32

-#pragma once

-#endif

-

-#include <typeinfo>

-

-//#define DBGFLAG_THASH			// Perform extra sanity checks on the THash

-

-

-// THash

-// This is a heavyweight, templatized version of DHash.

-// It differs from DHash in the following ways:

-// - It's templetized, and automatically constructs and destructs its records as appropriate

-// - It provides a scheduling service, which can be used to touch every record in the table

-//		at a specified interval.  The scheduler is low-overhead, and provides a very smooth

-//		distribution of touches across frames.

-

-// Template arguments:

-//		Data: the class to be stored in the hash table

-//		I: the type of the primary key (uint32 by default)

-template<class Data, typename I=uint32>

-class CTHash

-{

-private:

-	// RecHdr

-	// We insert one of these at the beginning of every record.  It's used for

-	// keeping the records in a linked list.

-	typedef struct RecHdr_t

-	{

-		RecHdr_t *m_pRecHdrNext;		// Next item in our linked list

-		RecHdr_t *m_pRecHdrPrev;		// Previous item in our linked list

-		I m_unKey;						// Key of this item

-		int m_iBucket;					// The bucket we're in

-		int m_nRunRatio;				// We want to run 1 cycle out of every m_nRunRatio

-										// cycles (not at all if 0).

-#ifdef DBGFLAG_THASH

-		uint m_iCycleLast;				// Last cycle we were visited (whether or not we ran)

-#endif

-	} RecHdr_t;

-

-	// Bucket

-	// Each hash bucket is represented by a Bucket structure, which points to the 

-	// first record with the bucket's hash.

-	typedef struct Bucket_t

-	{

-		RecHdr_t *m_pRecHdrFirst;		// First record in our list

-	} Bucket_t;

-

-

-public:

-	// Constructors & destructors

-	CTHash( int cFramesPerCycle );

-	~CTHash();

-

-	// Initializer

-	void Init( int cRecordInit, int cBuckets );

-

-	// Insert a record into the table

-	Data *PvRecordInsert( I unKey );

-	// Insert a record into the table and set the allocated object's pointer as the hash key

-	Data *PvRecordInsertAutoKey();

-	// Changes the key for a previously inserted item

-	void ChangeKey( Data * pvRecord, I unOldKey, I unNewKey );

-

-	// Remove a record

-	void Remove( I unKey );

-	// Remove a record

-	void Remove( Data * pvRecord );

-	// Remove all records

-	void RemoveAll();

-	

-	// Find a record

-	Data *PvRecordFind( I unKey ) const;

-

-	// How many records do we have

-	int Count() const { return m_cRecordInUse; }

-

-	// Iterate through our members

-	Data *PvRecordFirst() const;

-	Data *PvRecordNext( Data *pvRecordCur ) const;

-

-	// We provide a scheduling service.  Call StartFrameSchedule when you want to start running

-	// records in a given frame, and repeatedly call PvRecordRun until it returns NULL (or you

-	// run our of time).

-	void SetRunRatio( Data *pvRecord, int nRunRatio );

-	void SetMicroSecPerCycle( int cMicroSecPerCycle, int cMicroSecPerFrame ) { m_cFramesPerCycle = cMicroSecPerCycle / cMicroSecPerFrame; }

-	void StartFrameSchedule( bool bNewFrame );

-	Data *PvRecordRun();

-

-	bool BCompletedPass();

-

-#ifdef DBGFLAG_VALIDATE

-	virtual void Validate( CValidator &validator, const char *pchName );

-#endif // DBGFLAG_VALIDATE

-

-

-private:

-	// Insert a record into the table

-	Data *PvRecordInsertInternal( RecHdr_t *pRecHdr, I unKey );

-

-	// Get the record associated with a THashHdr

-	Data *PvRecordFromPRecHdr( RecHdr_t *pRecHdr ) const { return ( Data * ) ( ( ( uint8 * ) pRecHdr + sizeof( RecHdr_t ) ) ); }

-

-	// Get the RecHdr preceding a PvRecord

-	RecHdr_t *PRecHdrFromPvRecord( Data *pvRecord ) const { return ( ( ( RecHdr_t * ) pvRecord ) - 1 ); }

-

-	// Get the hash bucket corresponding to a key

-	int IBucket( I unKey ) const;

-

-	void InsertIntoHash( RecHdr_t *pRecHdr, I unKey );

-	void RemoveFromHash( Data * pvRecord );

-

-	int m_cBucket;						// # of hash buckets we have

-	Bucket_t *m_pBucket;				// Big array of hash buckets

-

-	CUtlMemoryPool *m_pMemoryPoolRecord;	// All our data records

-

-	int m_cRecordInUse;					// # of records in use

-	RecHdr_t m_RecHdrHead;				// Head of our linked list

-	RecHdr_t m_RecHdrTail;				// Tail of our linked list

-

-	int m_cFramesPerCycle;				// Run each of our records once every m_cFramesPerCycle frames

-	RecHdr_t *m_pRecHdrRunNext;			// Next record to run (be careful-- this is more complicated than it sounds)

-	int m_iBucketRunMax;				// Stop running when we get to this bucket

-	uint m_iCycleCur;					// Current cycle (ie, how many times we've made a complete scheduler pass)

-	uint m_iCycleLast;					// Our previous cycle

-	uint m_iFrameCur;					// Our current frame (incremented once each StartFrameSchedule)

-	uint m_iCycleLastReported;			// Last cycle checked by BCompletedPass()

-};

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Constructor

-// Input:	cMicroSecRunInterval -		How often we want the scheduler to run each of our records

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-CTHash<Data,I>::CTHash( int cFramesPerCycle )

-{

-	m_cBucket = 0;

-	m_pBucket = NULL;

-	m_pMemoryPoolRecord = NULL;

-	m_cRecordInUse = 0;

-

-	m_cFramesPerCycle = cFramesPerCycle;

-	m_pRecHdrRunNext = &m_RecHdrTail;		// This will make us start at the beginning on our first frame

-	m_iBucketRunMax = 0;

-	m_iCycleCur = 0;

-	m_iCycleLast = 0;

-	m_iFrameCur = 0;

-	m_iCycleLastReported = 0;

-

-	m_RecHdrHead.m_pRecHdrPrev = NULL;

-	m_RecHdrHead.m_pRecHdrNext = &m_RecHdrTail;

-	m_RecHdrHead.m_iBucket = -1;

-

-	m_RecHdrTail.m_pRecHdrPrev = &m_RecHdrHead;

-	m_RecHdrTail.m_pRecHdrNext = NULL;

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Destructor

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-CTHash<Data,I>::~CTHash()

-{

-	RemoveAll();

-

-	if ( NULL != m_pBucket )

-		FreePv( m_pBucket );

-	m_pBucket = NULL;

-

-	if ( NULL != m_pMemoryPoolRecord )

-		delete( m_pMemoryPoolRecord );

-	m_pMemoryPoolRecord = NULL;

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Initializer.  Allocate our various arrays, and set up the free

-//			list.

-// Input:	cRecordInit -		Initial # of data records we can contain

-//			cBucket -			# of hash buckets we should use

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-void CTHash<Data,I>::Init( int cRecordInit, int cBucket )

-{

-	Assert( cRecordInit > 0 );	// need to init with non-zero value or memory pool will never grow

-

-	// Copy our parameters

-	m_cBucket = cBucket;

-

-	// Alloc our arrays

-	m_pBucket = ( Bucket_t * ) PvAlloc( sizeof( Bucket_t ) * m_cBucket );

-	m_pMemoryPoolRecord = new CUtlMemoryPool( sizeof( Data ) + sizeof( RecHdr_t ), cRecordInit,

-		CUtlMemoryPool::GROW_SLOW );

-

-	// Init the hash buckets

-	for ( int iBucket = 0; iBucket < m_cBucket; iBucket++ )

-		m_pBucket[iBucket].m_pRecHdrFirst = NULL;

-

-	// Make the tail have an illegally large bucket

-	m_RecHdrTail.m_iBucket = m_cBucket + 1;

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Inserts a new record into the table

-// Input:	unKey -			Primary key of the new record

-// Output:	Pointer to the new record

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-Data *CTHash<Data,I>::PvRecordInsert( I unKey )

-{

-	Assert( PvRecordFind( unKey ) == NULL );	// keys are unique; no record with this key may exist

-

-	// Find a free record

-	RecHdr_t *pRecHdr = ( RecHdr_t * ) m_pMemoryPoolRecord->Alloc();

-	

-	return PvRecordInsertInternal( pRecHdr, unKey );

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Inserts a new record into the table and sets its key to the pointer

-//			value of the record

-// Output:	Pointer to the new record

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-Data *CTHash<Data,I>::PvRecordInsertAutoKey()

-{

-	// Find a free record

-	RecHdr_t *pRecHdr = ( RecHdr_t * ) m_pMemoryPoolRecord->Alloc();

-	

-	return PvRecordInsertInternal( pRecHdr, (I) PvRecordFromPRecHdr( pRecHdr ) );

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Inserts an allocated record into the hash table with specified key

-//			and calls the constructor of the allocated object

-// Input:	pRecHdr - record to insert

-//			unKey - hash key to use for record

-// Output:	Pointer to the new record

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-Data *CTHash<Data,I>::PvRecordInsertInternal( RecHdr_t *pRecHdr, I unKey )

-{

-	InsertIntoHash( pRecHdr, unKey );

-

-	// assert that we don't have too many items per bucket

-	static bool s_bPerfWarning = false;

-	if ( !s_bPerfWarning && Count() >= ( 5 * m_cBucket ) )

-	{

-		s_bPerfWarning = true;

-		AssertMsg( false, "Performance warning: too many items, not enough buckets" );

-		Msg( "not enough buckets in thash class %s (%d records, %d buckets)\n",

-#ifdef _WIN32

-		 typeid(*this).raw_name(),

-#else

-		typeid(*this).name(),

-#endif

-		Count(), m_cBucket );

-	}

-

-	// Construct ourselves

-	Data *pData = PvRecordFromPRecHdr( pRecHdr );

-	Construct<Data>( pData );

-	return pData;

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Changes key on previously inserted item

-// Input:	pvRecord -		record to change key for

-//			unOldKey -		old key (not strictly needed, but helpful consistency check)

-//			unNewKey -		new key to use

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-void CTHash<Data,I>::ChangeKey( Data * pvRecord, I unOldKey, I unNewKey )

-{

-	Data * pvRecordFound = PvRecordFind( unOldKey );

-	Assert( pvRecordFound == pvRecord );

-	if ( pvRecordFound == pvRecord )

-	{

-		RemoveFromHash( pvRecord );

-		InsertIntoHash( PRecHdrFromPvRecord( pvRecord), unNewKey );

-	}

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Removes the entry with a specified key from the table

-// Input:	unKey -		Key of the entry to remove

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-void CTHash<Data,I>::Remove( I unKey )

-{

-	Data *pvRemove = ( Data * ) PvRecordFind( unKey );

-	Assert( pvRemove );

-	if ( !pvRemove )

-		return;

-	Remove( pvRemove );

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Removes the specified entry from the table

-// Input:	pvRemove -		Pointer to the entry to remove

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-void CTHash<Data,I>::Remove( Data * pvRemove )

-{

-	// Destruct the record we're removing

-	Destruct<Data>( pvRemove );

-

-	RemoveFromHash( pvRemove );

-	m_pMemoryPoolRecord->Free( PRecHdrFromPvRecord( pvRemove ) );

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Removes all entries from the table

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-void CTHash<Data,I>::RemoveAll()

-{

-	Data * pvRecord = PvRecordFirst();

-	while ( pvRecord )

-	{

-		Data *pvRecordNext = PvRecordNext( pvRecord );

-		Remove( pvRecord );

-		pvRecord = pvRecordNext;

-	}

-}

-

-//-----------------------------------------------------------------------------

-// Purpose: Finds the entry with a specified key

-// Input:	unKey -		Key to find

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-Data *CTHash<Data,I>::PvRecordFind( I unKey ) const

-{

-	// Find our hash bucket

-	int iBucket = IBucket( unKey );

-

-	// Walk the bucket's list looking for an exact match

-	for ( RecHdr_t *pRecHdr = m_pBucket[iBucket].m_pRecHdrFirst;

-		NULL != pRecHdr && pRecHdr->m_iBucket == iBucket;

-		pRecHdr = pRecHdr->m_pRecHdrNext )

-	{

-		if ( unKey == pRecHdr->m_unKey )

-			return PvRecordFromPRecHdr( pRecHdr );

-	}

-

-	// Didn't find a match

-	return NULL;

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Finds our first record

-// Output:	Pointer to our first record

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-Data *CTHash<Data,I>::PvRecordFirst() const

-{

-	if ( &m_RecHdrTail != m_RecHdrHead.m_pRecHdrNext )

-		return PvRecordFromPRecHdr( m_RecHdrHead.m_pRecHdrNext );

-	else

-		return NULL;

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Iterates to the record after a given record

-// Input:	Pointer to a current record

-// Output:	Pointer to the next record

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-Data *CTHash<Data,I>::PvRecordNext( Data *pvRecordCur ) const

-{

-	RecHdr_t *pRecHdr = PRecHdrFromPvRecord( pvRecordCur );

-	if ( &m_RecHdrTail == pRecHdr->m_pRecHdrNext )

-		return NULL;

-

-	return PvRecordFromPRecHdr( pRecHdr->m_pRecHdrNext );

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Sets the run ratio of a particular record in the hash table.

-//			The record will be run 1 cycle out of every nRunRatio cycles.

-// Input:	pvRecord -		The record we're setting

-//			nRunRatio -		The run ratio for this record

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-void CTHash<Data,I>::SetRunRatio( Data *pvRecord, int nRunRatio )

-{

-	PRecHdrFromPvRecord( pvRecord )->m_nRunRatio = nRunRatio;

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Prepares us to run all records that are due to be run this frame.

-//			Records are run at a particular time dependent on their hash bucket,

-//			regardless of when they were last run.

-// Input:	bNewFrame -		True if this is a new frame.  If false, we've run

-//							off the end of the list and are checking whether

-//							we need to keep going at the beginning.

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-void CTHash<Data,I>::StartFrameSchedule( bool bNewFrame )

-{

-	// Calculate our current frame and cycle cycle

-	if ( bNewFrame )

-	{

-		m_iCycleLast = m_iCycleCur;

-		m_iFrameCur++;

-		m_iCycleCur = m_iFrameCur / m_cFramesPerCycle;

-	}

-

-	// Calculate the last bucket to run

-	int iFrameInCycle = m_iFrameCur % m_cFramesPerCycle;

-	m_iBucketRunMax = ( int ) ( ( ( int64 ) ( iFrameInCycle + 1 ) * ( int64 ) m_cBucket )

-		/ ( int64 ) m_cFramesPerCycle );

-	AssertFatal( m_iBucketRunMax >= 0 && m_iBucketRunMax <= m_cBucket );

-

-	// Are we starting a new cycle?

-	if ( m_iCycleCur > m_iCycleLast )

-	{

-#ifdef DBGFLAG_THASH

-		Assert( m_iCycleCur == m_iCycleLast + 1 );

-#endif

-

-		// Did we finish the last cycle?

-		if ( &m_RecHdrTail == m_pRecHdrRunNext )

-		{

-			m_pRecHdrRunNext = m_RecHdrHead.m_pRecHdrNext;

-		}

-		// No-- finish it up before moving on

-		else

-		{

-			m_iBucketRunMax = m_cBucket + 1;

-		}

-	}

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Returns the next record to run, if any

-// Output:	Pointer to the next record that needs to run (NULL if we're done)

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-Data *CTHash<Data,I>::PvRecordRun()

-{

-	// Loop until we find a record to run, or until we pass m_iBucketRunMax

-	for ( ; ; )

-	{

-		// Are we past our stopping point?

-		if ( m_pRecHdrRunNext->m_iBucket >= m_iBucketRunMax )

-		{

-			// If this cycle ran to the very end, see if we need to start over

-			if ( m_iBucketRunMax > m_cBucket )

-			{

-				StartFrameSchedule( false );

-				continue;

-			}

-

-			return NULL;

-		}

-

-#ifdef DBGFLAG_THASH

-		Assert( m_pRecHdrRunNext->m_iBucket >= m_iBucketRunFirst );

-		if ( 0 != m_pRecHdrRunNext->m_iCycleLast )

-		{

-			if ( m_pRecHdrRunNext->m_iCycleLast == m_iCycleCur )

-			{

-				DMsg( SPEW_CONSOLE,  1, "Double cycle: hdr = 0x%x, last frame = %d, curFrame = %d, first = %d, last = %d, bucket = %d\n",

-					m_pRecHdrRunNext, m_pRecHdrRunNext->m_iFrameLast, m_iFrame,

-					m_iBucketRunFirst, m_iBucketRunMax, m_pRecHdrRunNext->m_iBucket );

-			}

-			else if ( m_pRecHdrRunNext->m_iCycleLast != m_iCycleCur - 1 )

-			{

-				DMsg( SPEW_CONSOLE,  1, "Skipped cycle: hdr = 0x%x, cycleLast = %u, cycleCur = %u (missed %u cycles)\n",

-					m_pRecHdrRunNext, m_pRecHdrRunNext->m_iCycleLast, m_iCycleCur,

-					m_iCycleCur - m_pRecHdrRunNext->m_iCycleLast );

-				Assert( false );

-			}

-		}

-		m_pRecHdrRunNext->m_iCycleLast = m_iCycleCur;

-		m_pRecHdrRunNext->m_iFrameLast = m_iFrame;

-#endif

-

-		// Set up the record to run next time

-		RecHdr_t *pRecHdrCur = m_pRecHdrRunNext;

-		m_pRecHdrRunNext = m_pRecHdrRunNext->m_pRecHdrNext;

-

-		// Does this record need to run?

-		if ( 0 == pRecHdrCur->m_nRunRatio )

-			continue;

-

-		if ( 0 == m_iCycleCur % pRecHdrCur->m_nRunRatio )

-			return PvRecordFromPRecHdr( pRecHdrCur );

-	}

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Return true if we've completed a scheduler pass since last called

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-bool CTHash<Data,I>::BCompletedPass()

-{

-	if ( m_iCycleCur != m_iCycleLastReported )

-	{

-		m_iCycleLastReported = m_iCycleCur;

-		return true;

-	}

-	return false;

-}

-

-

-extern const unsigned char g_CTHashRandomValues[256];  // definition lives in globals.cpp

-

-//-----------------------------------------------------------------------------

-// Purpose: Returns the index of the hash bucket corresponding to a particular key

-// Input:	unKey -		Key to find

-// Output:	Index of the hash bucket corresponding to unKey

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-int CTHash<Data,I>::IBucket( I unKey ) const

-{

-	AssertFatal( m_cBucket > 0 );

-

-	// This is a pearsons hash variant that returns a maximum of 32 bits

-	size_t size = sizeof(I);

-	const uint8 *	k    = (const uint8 *) &unKey;

-	uint32 byte_one = 0, byte_two = 0, byte_three = 0, byte_four = 0, n;

-

-	while (size)

-	{

-		--size;

-		n    = *k++;

-		byte_one = g_CTHashRandomValues[byte_one ^ n];

-		

-		if (size)

-		{

-			--size;

-			n   = *k++;

-			byte_two = g_CTHashRandomValues[byte_two ^ n];

-		}

-		else

-			break;

-		

-		if (size)

-		{

-			--size;

-			n   = *k++;

-			byte_three = g_CTHashRandomValues[byte_three ^ n];

-		}

-		else

-			break;

-		

-		if (size)

-		{

-			--size;

-			n   = *k++;

-			byte_four = g_CTHashRandomValues[byte_four ^ n];

-		}

-		else

-			break;

-	}

-

-	uint32 idx = ( byte_four << 24 ) | ( byte_three << 16 ) | ( byte_two << 8 ) | byte_one;

-	idx = idx % m_cBucket;

-	return ( (int) idx ); 

-}

-

-

-#ifdef DBGFLAG_VALIDATE

-//-----------------------------------------------------------------------------

-// Purpose: Run a global validation pass on all of our data structures and memory

-//			allocations.

-// Input:	validator -		Our global validator object

-//			pchName -		Our name (typically a member var in our container)

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-void CTHash<Data,I>::Validate( CValidator &validator, const char *pchName )

-{

-	VALIDATE_SCOPE();

-

-	validator.ClaimMemory( m_pBucket );

-	ValidatePtr( m_pMemoryPoolRecord );

-

-#if defined( _DEBUG )

-	// first verify m_cRecordInUse

-	Data * pvRecord = PvRecordFirst();

-	int cItems = 0;

-	while ( pvRecord )

-	{

-		Data *pvRecordNext = PvRecordNext( pvRecord );

-		cItems++;

-		pvRecord = pvRecordNext;

-	}

-	Assert( m_cRecordInUse == cItems );

-	// then ask the mempool to verify this

-	if ( m_pMemoryPoolRecord )

-		m_pMemoryPoolRecord->LeakCheck( cItems );

-#endif // _DEBUG

-}

-#endif // DBGFLAG_VALIDATE

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Inserts a new record into the table

-// Input:	unKey -			Primary key of the new record

-// Output:	Pointer to the new record

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-void CTHash<Data,I>::InsertIntoHash( RecHdr_t *pRecHdr, I unKey )

-{

-	m_cRecordInUse++;

-

-	// Init the RecHdr

-	pRecHdr->m_unKey = unKey;

-	pRecHdr->m_nRunRatio = 1;

-

-	// Find our hash bucket

-	int iBucket = IBucket( unKey );

-	pRecHdr->m_iBucket = iBucket;

-#ifdef DBGFLAG_THASH

-	pRecHdr->m_iCycleLast = 0;

-#endif

-

-	// Find where to insert ourselves in the linked list

-	RecHdr_t *pRecHdrInsertBefore = &m_RecHdrTail;

-	// Find the first bucket with anything in it that's at or after our bucket

-	for ( int iBucketT = iBucket; iBucketT < m_cBucket; iBucketT++ )

-	{

-		if ( NULL != m_pBucket[iBucketT].m_pRecHdrFirst )

-		{

-			pRecHdrInsertBefore = m_pBucket[iBucketT].m_pRecHdrFirst;

-			break;

-		}

-	}

-

-	// Insert ourselves

-	pRecHdr->m_pRecHdrNext = pRecHdrInsertBefore;

-	pRecHdr->m_pRecHdrPrev = pRecHdrInsertBefore->m_pRecHdrPrev;

-	pRecHdrInsertBefore->m_pRecHdrPrev = pRecHdr;

-	pRecHdr->m_pRecHdrPrev->m_pRecHdrNext = pRecHdr;

-

-	// Our bucket should point to us

-	m_pBucket[iBucket].m_pRecHdrFirst = pRecHdr;

-}

-

-

-//-----------------------------------------------------------------------------

-// Purpose: Removes the specified entry from the table

-// Input:	pvRemove -		Pointer to the entry to remove

-//-----------------------------------------------------------------------------

-template<class Data, class I>

-void CTHash<Data,I>::RemoveFromHash( Data * pvRemove )

-{

-	// Find our RecHdr

-	RecHdr_t *pRecHdr = PRecHdrFromPvRecord( pvRemove );

-

-	// If our bucket points to us, point it to the next record (or else NULL)

-	int iBucket = IBucket( pRecHdr->m_unKey );

-	if ( pRecHdr == m_pBucket[iBucket].m_pRecHdrFirst )

-	{

-		if ( pRecHdr->m_pRecHdrNext->m_iBucket == iBucket )

-			m_pBucket[iBucket].m_pRecHdrFirst = pRecHdr->m_pRecHdrNext;

-		else

-			m_pBucket[iBucket].m_pRecHdrFirst = NULL;

-	}

-

-	// Remove us from the linked list

-	pRecHdr->m_pRecHdrPrev->m_pRecHdrNext = pRecHdr->m_pRecHdrNext;

-	pRecHdr->m_pRecHdrNext->m_pRecHdrPrev = pRecHdr->m_pRecHdrPrev;

-

-	// Are we the next record to run?

-	if ( pRecHdr == m_pRecHdrRunNext )

-		m_pRecHdrRunNext = pRecHdr->m_pRecHdrNext;

-

-	m_cRecordInUse--;

-}

-

-#endif // THASH_H

+//========= Copyright Valve Corporation, All rights reserved. ============//
+//
+// Purpose:
+//
+// $NoKeywords: $
+//=============================================================================
+
+#ifndef THASH_H
+#define THASH_H
+#ifdef _WIN32
+#pragma once
+#endif
+
+#include <typeinfo>
+
+//#define DBGFLAG_THASH			// Perform extra sanity checks on the THash
+
+
+// THash
+// This is a heavyweight, templatized version of DHash.
+// It differs from DHash in the following ways:
+// - It's templetized, and automatically constructs and destructs its records as appropriate
+// - It provides a scheduling service, which can be used to touch every record in the table
+//		at a specified interval.  The scheduler is low-overhead, and provides a very smooth
+//		distribution of touches across frames.
+
+// Template arguments:
+//		Data: the class to be stored in the hash table
+//		I: the type of the primary key (uint32 by default)
+template<class Data, typename I=uint32>
+class CTHash
+{
+private:
+	// RecHdr
+	// We insert one of these at the beginning of every record.  It's used for
+	// keeping the records in a linked list.
+	typedef struct RecHdr_t
+	{
+		RecHdr_t *m_pRecHdrNext;		// Next item in our linked list
+		RecHdr_t *m_pRecHdrPrev;		// Previous item in our linked list
+		I m_unKey;						// Key of this item
+		int m_iBucket;					// The bucket we're in
+		int m_nRunRatio;				// We want to run 1 cycle out of every m_nRunRatio
+										// cycles (not at all if 0).
+#ifdef DBGFLAG_THASH
+		uint m_iCycleLast;				// Last cycle we were visited (whether or not we ran)
+#endif
+	} RecHdr_t;
+
+	// Bucket
+	// Each hash bucket is represented by a Bucket structure, which points to the 
+	// first record with the bucket's hash.
+	typedef struct Bucket_t
+	{
+		RecHdr_t *m_pRecHdrFirst;		// First record in our list
+	} Bucket_t;
+
+
+public:
+	// Constructors & destructors
+	CTHash( int cFramesPerCycle );
+	~CTHash();
+
+	// Initializer
+	void Init( int cRecordInit, int cBuckets );
+
+	// Insert a record into the table
+	Data *PvRecordInsert( I unKey );
+	// Insert a record into the table and set the allocated object's pointer as the hash key
+	Data *PvRecordInsertAutoKey();
+	// Changes the key for a previously inserted item
+	void ChangeKey( Data * pvRecord, I unOldKey, I unNewKey );
+
+	// Remove a record
+	void Remove( I unKey );
+	// Remove a record
+	void Remove( Data * pvRecord );
+	// Remove all records
+	void RemoveAll();
+	
+	// Find a record
+	Data *PvRecordFind( I unKey ) const;
+
+	// How many records do we have
+	int Count() const { return m_cRecordInUse; }
+
+	// Iterate through our members
+	Data *PvRecordFirst() const;
+	Data *PvRecordNext( Data *pvRecordCur ) const;
+
+	// We provide a scheduling service.  Call StartFrameSchedule when you want to start running
+	// records in a given frame, and repeatedly call PvRecordRun until it returns NULL (or you
+	// run our of time).
+	void SetRunRatio( Data *pvRecord, int nRunRatio );
+	void SetMicroSecPerCycle( int cMicroSecPerCycle, int cMicroSecPerFrame ) { m_cFramesPerCycle = cMicroSecPerCycle / cMicroSecPerFrame; }
+	void StartFrameSchedule( bool bNewFrame );
+	Data *PvRecordRun();
+
+	bool BCompletedPass();
+
+#ifdef DBGFLAG_VALIDATE
+	virtual void Validate( CValidator &validator, const char *pchName );
+#endif // DBGFLAG_VALIDATE
+
+
+private:
+	// Insert a record into the table
+	Data *PvRecordInsertInternal( RecHdr_t *pRecHdr, I unKey );
+
+	// Get the record associated with a THashHdr
+	Data *PvRecordFromPRecHdr( RecHdr_t *pRecHdr ) const { return ( Data * ) ( ( ( uint8 * ) pRecHdr + sizeof( RecHdr_t ) ) ); }
+
+	// Get the RecHdr preceding a PvRecord
+	RecHdr_t *PRecHdrFromPvRecord( Data *pvRecord ) const { return ( ( ( RecHdr_t * ) pvRecord ) - 1 ); }
+
+	// Get the hash bucket corresponding to a key
+	int IBucket( I unKey ) const;
+
+	void InsertIntoHash( RecHdr_t *pRecHdr, I unKey );
+	void RemoveFromHash( Data * pvRecord );
+
+	int m_cBucket;						// # of hash buckets we have
+	Bucket_t *m_pBucket;				// Big array of hash buckets
+
+	CUtlMemoryPool *m_pMemoryPoolRecord;	// All our data records
+
+	int m_cRecordInUse;					// # of records in use
+	RecHdr_t m_RecHdrHead;				// Head of our linked list
+	RecHdr_t m_RecHdrTail;				// Tail of our linked list
+
+	int m_cFramesPerCycle;				// Run each of our records once every m_cFramesPerCycle frames
+	RecHdr_t *m_pRecHdrRunNext;			// Next record to run (be careful-- this is more complicated than it sounds)
+	int m_iBucketRunMax;				// Stop running when we get to this bucket
+	uint m_iCycleCur;					// Current cycle (ie, how many times we've made a complete scheduler pass)
+	uint m_iCycleLast;					// Our previous cycle
+	uint m_iFrameCur;					// Our current frame (incremented once each StartFrameSchedule)
+	uint m_iCycleLastReported;			// Last cycle checked by BCompletedPass()
+};
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Constructor
+// Input:	cMicroSecRunInterval -		How often we want the scheduler to run each of our records
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+CTHash<Data,I>::CTHash( int cFramesPerCycle )
+{
+	m_cBucket = 0;
+	m_pBucket = NULL;
+	m_pMemoryPoolRecord = NULL;
+	m_cRecordInUse = 0;
+
+	m_cFramesPerCycle = cFramesPerCycle;
+	m_pRecHdrRunNext = &m_RecHdrTail;		// This will make us start at the beginning on our first frame
+	m_iBucketRunMax = 0;
+	m_iCycleCur = 0;
+	m_iCycleLast = 0;
+	m_iFrameCur = 0;
+	m_iCycleLastReported = 0;
+
+	m_RecHdrHead.m_pRecHdrPrev = NULL;
+	m_RecHdrHead.m_pRecHdrNext = &m_RecHdrTail;
+	m_RecHdrHead.m_iBucket = -1;
+
+	m_RecHdrTail.m_pRecHdrPrev = &m_RecHdrHead;
+	m_RecHdrTail.m_pRecHdrNext = NULL;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Destructor
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+CTHash<Data,I>::~CTHash()
+{
+	RemoveAll();
+
+	if ( NULL != m_pBucket )
+		FreePv( m_pBucket );
+	m_pBucket = NULL;
+
+	if ( NULL != m_pMemoryPoolRecord )
+		delete( m_pMemoryPoolRecord );
+	m_pMemoryPoolRecord = NULL;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Initializer.  Allocate our various arrays, and set up the free
+//			list.
+// Input:	cRecordInit -		Initial # of data records we can contain
+//			cBucket -			# of hash buckets we should use
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+void CTHash<Data,I>::Init( int cRecordInit, int cBucket )
+{
+	Assert( cRecordInit > 0 );	// need to init with non-zero value or memory pool will never grow
+
+	// Copy our parameters
+	m_cBucket = cBucket;
+
+	// Alloc our arrays
+	m_pBucket = ( Bucket_t * ) PvAlloc( sizeof( Bucket_t ) * m_cBucket );
+	m_pMemoryPoolRecord = new CUtlMemoryPool( sizeof( Data ) + sizeof( RecHdr_t ), cRecordInit,
+		CUtlMemoryPool::GROW_SLOW );
+
+	// Init the hash buckets
+	for ( int iBucket = 0; iBucket < m_cBucket; iBucket++ )
+		m_pBucket[iBucket].m_pRecHdrFirst = NULL;
+
+	// Make the tail have an illegally large bucket
+	m_RecHdrTail.m_iBucket = m_cBucket + 1;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Inserts a new record into the table
+// Input:	unKey -			Primary key of the new record
+// Output:	Pointer to the new record
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+Data *CTHash<Data,I>::PvRecordInsert( I unKey )
+{
+	Assert( PvRecordFind( unKey ) == NULL );	// keys are unique; no record with this key may exist
+
+	// Find a free record
+	RecHdr_t *pRecHdr = ( RecHdr_t * ) m_pMemoryPoolRecord->Alloc();
+	
+	return PvRecordInsertInternal( pRecHdr, unKey );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Inserts a new record into the table and sets its key to the pointer
+//			value of the record
+// Output:	Pointer to the new record
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+Data *CTHash<Data,I>::PvRecordInsertAutoKey()
+{
+	// Find a free record
+	RecHdr_t *pRecHdr = ( RecHdr_t * ) m_pMemoryPoolRecord->Alloc();
+	
+	return PvRecordInsertInternal( pRecHdr, (I) PvRecordFromPRecHdr( pRecHdr ) );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Inserts an allocated record into the hash table with specified key
+//			and calls the constructor of the allocated object
+// Input:	pRecHdr - record to insert
+//			unKey - hash key to use for record
+// Output:	Pointer to the new record
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+Data *CTHash<Data,I>::PvRecordInsertInternal( RecHdr_t *pRecHdr, I unKey )
+{
+	InsertIntoHash( pRecHdr, unKey );
+
+	// assert that we don't have too many items per bucket
+	static bool s_bPerfWarning = false;
+	if ( !s_bPerfWarning && Count() >= ( 5 * m_cBucket ) )
+	{
+		s_bPerfWarning = true;
+		AssertMsg( false, "Performance warning: too many items, not enough buckets" );
+		Msg( "not enough buckets in thash class %s (%d records, %d buckets)\n",
+#ifdef _WIN32
+		 typeid(*this).raw_name(),
+#else
+		typeid(*this).name(),
+#endif
+		Count(), m_cBucket );
+	}
+
+	// Construct ourselves
+	Data *pData = PvRecordFromPRecHdr( pRecHdr );
+	Construct<Data>( pData );
+	return pData;
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Changes key on previously inserted item
+// Input:	pvRecord -		record to change key for
+//			unOldKey -		old key (not strictly needed, but helpful consistency check)
+//			unNewKey -		new key to use
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+void CTHash<Data,I>::ChangeKey( Data * pvRecord, I unOldKey, I unNewKey )
+{
+	Data * pvRecordFound = PvRecordFind( unOldKey );
+	Assert( pvRecordFound == pvRecord );
+	if ( pvRecordFound == pvRecord )
+	{
+		RemoveFromHash( pvRecord );
+		InsertIntoHash( PRecHdrFromPvRecord( pvRecord), unNewKey );
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Removes the entry with a specified key from the table
+// Input:	unKey -		Key of the entry to remove
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+void CTHash<Data,I>::Remove( I unKey )
+{
+	Data *pvRemove = ( Data * ) PvRecordFind( unKey );
+	Assert( pvRemove );
+	if ( !pvRemove )
+		return;
+	Remove( pvRemove );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Removes the specified entry from the table
+// Input:	pvRemove -		Pointer to the entry to remove
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+void CTHash<Data,I>::Remove( Data * pvRemove )
+{
+	// Destruct the record we're removing
+	Destruct<Data>( pvRemove );
+
+	RemoveFromHash( pvRemove );
+	m_pMemoryPoolRecord->Free( PRecHdrFromPvRecord( pvRemove ) );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Removes all entries from the table
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+void CTHash<Data,I>::RemoveAll()
+{
+	Data * pvRecord = PvRecordFirst();
+	while ( pvRecord )
+	{
+		Data *pvRecordNext = PvRecordNext( pvRecord );
+		Remove( pvRecord );
+		pvRecord = pvRecordNext;
+	}
+}
+
+//-----------------------------------------------------------------------------
+// Purpose: Finds the entry with a specified key
+// Input:	unKey -		Key to find
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+Data *CTHash<Data,I>::PvRecordFind( I unKey ) const
+{
+	// Find our hash bucket
+	int iBucket = IBucket( unKey );
+
+	// Walk the bucket's list looking for an exact match
+	for ( RecHdr_t *pRecHdr = m_pBucket[iBucket].m_pRecHdrFirst;
+		NULL != pRecHdr && pRecHdr->m_iBucket == iBucket;
+		pRecHdr = pRecHdr->m_pRecHdrNext )
+	{
+		if ( unKey == pRecHdr->m_unKey )
+			return PvRecordFromPRecHdr( pRecHdr );
+	}
+
+	// Didn't find a match
+	return NULL;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Finds our first record
+// Output:	Pointer to our first record
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+Data *CTHash<Data,I>::PvRecordFirst() const
+{
+	if ( &m_RecHdrTail != m_RecHdrHead.m_pRecHdrNext )
+		return PvRecordFromPRecHdr( m_RecHdrHead.m_pRecHdrNext );
+	else
+		return NULL;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Iterates to the record after a given record
+// Input:	Pointer to a current record
+// Output:	Pointer to the next record
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+Data *CTHash<Data,I>::PvRecordNext( Data *pvRecordCur ) const
+{
+	RecHdr_t *pRecHdr = PRecHdrFromPvRecord( pvRecordCur );
+	if ( &m_RecHdrTail == pRecHdr->m_pRecHdrNext )
+		return NULL;
+
+	return PvRecordFromPRecHdr( pRecHdr->m_pRecHdrNext );
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Sets the run ratio of a particular record in the hash table.
+//			The record will be run 1 cycle out of every nRunRatio cycles.
+// Input:	pvRecord -		The record we're setting
+//			nRunRatio -		The run ratio for this record
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+void CTHash<Data,I>::SetRunRatio( Data *pvRecord, int nRunRatio )
+{
+	PRecHdrFromPvRecord( pvRecord )->m_nRunRatio = nRunRatio;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Prepares us to run all records that are due to be run this frame.
+//			Records are run at a particular time dependent on their hash bucket,
+//			regardless of when they were last run.
+// Input:	bNewFrame -		True if this is a new frame.  If false, we've run
+//							off the end of the list and are checking whether
+//							we need to keep going at the beginning.
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+void CTHash<Data,I>::StartFrameSchedule( bool bNewFrame )
+{
+	// Calculate our current frame and cycle cycle
+	if ( bNewFrame )
+	{
+		m_iCycleLast = m_iCycleCur;
+		m_iFrameCur++;
+		m_iCycleCur = m_iFrameCur / m_cFramesPerCycle;
+	}
+
+	// Calculate the last bucket to run
+	int iFrameInCycle = m_iFrameCur % m_cFramesPerCycle;
+	m_iBucketRunMax = ( int ) ( ( ( int64 ) ( iFrameInCycle + 1 ) * ( int64 ) m_cBucket )
+		/ ( int64 ) m_cFramesPerCycle );
+	AssertFatal( m_iBucketRunMax >= 0 && m_iBucketRunMax <= m_cBucket );
+
+	// Are we starting a new cycle?
+	if ( m_iCycleCur > m_iCycleLast )
+	{
+#ifdef DBGFLAG_THASH
+		Assert( m_iCycleCur == m_iCycleLast + 1 );
+#endif
+
+		// Did we finish the last cycle?
+		if ( &m_RecHdrTail == m_pRecHdrRunNext )
+		{
+			m_pRecHdrRunNext = m_RecHdrHead.m_pRecHdrNext;
+		}
+		// No-- finish it up before moving on
+		else
+		{
+			m_iBucketRunMax = m_cBucket + 1;
+		}
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Returns the next record to run, if any
+// Output:	Pointer to the next record that needs to run (NULL if we're done)
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+Data *CTHash<Data,I>::PvRecordRun()
+{
+	// Loop until we find a record to run, or until we pass m_iBucketRunMax
+	for ( ; ; )
+	{
+		// Are we past our stopping point?
+		if ( m_pRecHdrRunNext->m_iBucket >= m_iBucketRunMax )
+		{
+			// If this cycle ran to the very end, see if we need to start over
+			if ( m_iBucketRunMax > m_cBucket )
+			{
+				StartFrameSchedule( false );
+				continue;
+			}
+
+			return NULL;
+		}
+
+#ifdef DBGFLAG_THASH
+		Assert( m_pRecHdrRunNext->m_iBucket >= m_iBucketRunFirst );
+		if ( 0 != m_pRecHdrRunNext->m_iCycleLast )
+		{
+			if ( m_pRecHdrRunNext->m_iCycleLast == m_iCycleCur )
+			{
+				DMsg( SPEW_CONSOLE,  1, "Double cycle: hdr = 0x%x, last frame = %d, curFrame = %d, first = %d, last = %d, bucket = %d\n",
+					m_pRecHdrRunNext, m_pRecHdrRunNext->m_iFrameLast, m_iFrame,
+					m_iBucketRunFirst, m_iBucketRunMax, m_pRecHdrRunNext->m_iBucket );
+			}
+			else if ( m_pRecHdrRunNext->m_iCycleLast != m_iCycleCur - 1 )
+			{
+				DMsg( SPEW_CONSOLE,  1, "Skipped cycle: hdr = 0x%x, cycleLast = %u, cycleCur = %u (missed %u cycles)\n",
+					m_pRecHdrRunNext, m_pRecHdrRunNext->m_iCycleLast, m_iCycleCur,
+					m_iCycleCur - m_pRecHdrRunNext->m_iCycleLast );
+				Assert( false );
+			}
+		}
+		m_pRecHdrRunNext->m_iCycleLast = m_iCycleCur;
+		m_pRecHdrRunNext->m_iFrameLast = m_iFrame;
+#endif
+
+		// Set up the record to run next time
+		RecHdr_t *pRecHdrCur = m_pRecHdrRunNext;
+		m_pRecHdrRunNext = m_pRecHdrRunNext->m_pRecHdrNext;
+
+		// Does this record need to run?
+		if ( 0 == pRecHdrCur->m_nRunRatio )
+			continue;
+
+		if ( 0 == m_iCycleCur % pRecHdrCur->m_nRunRatio )
+			return PvRecordFromPRecHdr( pRecHdrCur );
+	}
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Return true if we've completed a scheduler pass since last called
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+bool CTHash<Data,I>::BCompletedPass()
+{
+	if ( m_iCycleCur != m_iCycleLastReported )
+	{
+		m_iCycleLastReported = m_iCycleCur;
+		return true;
+	}
+	return false;
+}
+
+
+extern const unsigned char g_CTHashRandomValues[256];  // definition lives in globals.cpp
+
+//-----------------------------------------------------------------------------
+// Purpose: Returns the index of the hash bucket corresponding to a particular key
+// Input:	unKey -		Key to find
+// Output:	Index of the hash bucket corresponding to unKey
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+int CTHash<Data,I>::IBucket( I unKey ) const
+{
+	AssertFatal( m_cBucket > 0 );
+
+	// This is a pearsons hash variant that returns a maximum of 32 bits
+	size_t size = sizeof(I);
+	const uint8 *	k    = (const uint8 *) &unKey;
+	uint32 byte_one = 0, byte_two = 0, byte_three = 0, byte_four = 0, n;
+
+	while (size)
+	{
+		--size;
+		n    = *k++;
+		byte_one = g_CTHashRandomValues[byte_one ^ n];
+		
+		if (size)
+		{
+			--size;
+			n   = *k++;
+			byte_two = g_CTHashRandomValues[byte_two ^ n];
+		}
+		else
+			break;
+		
+		if (size)
+		{
+			--size;
+			n   = *k++;
+			byte_three = g_CTHashRandomValues[byte_three ^ n];
+		}
+		else
+			break;
+		
+		if (size)
+		{
+			--size;
+			n   = *k++;
+			byte_four = g_CTHashRandomValues[byte_four ^ n];
+		}
+		else
+			break;
+	}
+
+	uint32 idx = ( byte_four << 24 ) | ( byte_three << 16 ) | ( byte_two << 8 ) | byte_one;
+	idx = idx % m_cBucket;
+	return ( (int) idx ); 
+}
+
+
+#ifdef DBGFLAG_VALIDATE
+//-----------------------------------------------------------------------------
+// Purpose: Run a global validation pass on all of our data structures and memory
+//			allocations.
+// Input:	validator -		Our global validator object
+//			pchName -		Our name (typically a member var in our container)
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+void CTHash<Data,I>::Validate( CValidator &validator, const char *pchName )
+{
+	VALIDATE_SCOPE();
+
+	validator.ClaimMemory( m_pBucket );
+	ValidatePtr( m_pMemoryPoolRecord );
+
+#if defined( _DEBUG )
+	// first verify m_cRecordInUse
+	Data * pvRecord = PvRecordFirst();
+	int cItems = 0;
+	while ( pvRecord )
+	{
+		Data *pvRecordNext = PvRecordNext( pvRecord );
+		cItems++;
+		pvRecord = pvRecordNext;
+	}
+	Assert( m_cRecordInUse == cItems );
+	// then ask the mempool to verify this
+	if ( m_pMemoryPoolRecord )
+		m_pMemoryPoolRecord->LeakCheck( cItems );
+#endif // _DEBUG
+}
+#endif // DBGFLAG_VALIDATE
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Inserts a new record into the table
+// Input:	unKey -			Primary key of the new record
+// Output:	Pointer to the new record
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+void CTHash<Data,I>::InsertIntoHash( RecHdr_t *pRecHdr, I unKey )
+{
+	m_cRecordInUse++;
+
+	// Init the RecHdr
+	pRecHdr->m_unKey = unKey;
+	pRecHdr->m_nRunRatio = 1;
+
+	// Find our hash bucket
+	int iBucket = IBucket( unKey );
+	pRecHdr->m_iBucket = iBucket;
+#ifdef DBGFLAG_THASH
+	pRecHdr->m_iCycleLast = 0;
+#endif
+
+	// Find where to insert ourselves in the linked list
+	RecHdr_t *pRecHdrInsertBefore = &m_RecHdrTail;
+	// Find the first bucket with anything in it that's at or after our bucket
+	for ( int iBucketT = iBucket; iBucketT < m_cBucket; iBucketT++ )
+	{
+		if ( NULL != m_pBucket[iBucketT].m_pRecHdrFirst )
+		{
+			pRecHdrInsertBefore = m_pBucket[iBucketT].m_pRecHdrFirst;
+			break;
+		}
+	}
+
+	// Insert ourselves
+	pRecHdr->m_pRecHdrNext = pRecHdrInsertBefore;
+	pRecHdr->m_pRecHdrPrev = pRecHdrInsertBefore->m_pRecHdrPrev;
+	pRecHdrInsertBefore->m_pRecHdrPrev = pRecHdr;
+	pRecHdr->m_pRecHdrPrev->m_pRecHdrNext = pRecHdr;
+
+	// Our bucket should point to us
+	m_pBucket[iBucket].m_pRecHdrFirst = pRecHdr;
+}
+
+
+//-----------------------------------------------------------------------------
+// Purpose: Removes the specified entry from the table
+// Input:	pvRemove -		Pointer to the entry to remove
+//-----------------------------------------------------------------------------
+template<class Data, class I>
+void CTHash<Data,I>::RemoveFromHash( Data * pvRemove )
+{
+	// Find our RecHdr
+	RecHdr_t *pRecHdr = PRecHdrFromPvRecord( pvRemove );
+
+	// If our bucket points to us, point it to the next record (or else NULL)
+	int iBucket = IBucket( pRecHdr->m_unKey );
+	if ( pRecHdr == m_pBucket[iBucket].m_pRecHdrFirst )
+	{
+		if ( pRecHdr->m_pRecHdrNext->m_iBucket == iBucket )
+			m_pBucket[iBucket].m_pRecHdrFirst = pRecHdr->m_pRecHdrNext;
+		else
+			m_pBucket[iBucket].m_pRecHdrFirst = NULL;
+	}
+
+	// Remove us from the linked list
+	pRecHdr->m_pRecHdrPrev->m_pRecHdrNext = pRecHdr->m_pRecHdrNext;
+	pRecHdr->m_pRecHdrNext->m_pRecHdrPrev = pRecHdr->m_pRecHdrPrev;
+
+	// Are we the next record to run?
+	if ( pRecHdr == m_pRecHdrRunNext )
+		m_pRecHdrRunNext = pRecHdr->m_pRecHdrNext;
+
+	m_cRecordInUse--;
+}
+
+#endif // THASH_H