First version of the SOurce SDK 2013

1 files changed, 698 insertions, 0 deletions

diff --git a/mp/src/public/tier1/thash.h b/mp/src/public/tier1/thash.h
new file mode 100644
index 00000000..453aebf0
--- /dev/null
+++ b/mp/src/public/tier1/thash.h
@@ -0,0 +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