//========= 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