{

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()