881 lines
31 KiB
C++
881 lines
31 KiB
C++
//========= Copyright Valve Corporation, All rights reserved. ============//
|
|
//
|
|
// Purpose:
|
|
//
|
|
// $NoKeywords: $
|
|
//
|
|
// Serialization/unserialization buffer
|
|
//=============================================================================//
|
|
|
|
#ifndef UTLHASH_H
|
|
#define UTLHASH_H
|
|
#pragma once
|
|
|
|
#include <assert.h>
|
|
#include <limits.h>
|
|
#include "../tier0/commonmacros.h"
|
|
#include "generichash.h"
|
|
#include "utllinkedlist.h"
|
|
#include "utlmemory.h"
|
|
#include "utlvector.h"
|
|
|
|
typedef unsigned int UtlHashHandle_t;
|
|
|
|
template <class Data, typename C = bool (*)(Data const &, Data const &),
|
|
typename K = unsigned int (*)(Data const &)>
|
|
class CUtlHash {
|
|
public:
|
|
// compare and key functions - implemented by the
|
|
typedef C CompareFunc_t;
|
|
typedef K KeyFunc_t;
|
|
|
|
// constructor/deconstructor
|
|
CUtlHash(int bucketCount = 0, int growCount = 0, int initCount = 0,
|
|
CompareFunc_t compareFunc = 0, KeyFunc_t keyFunc = 0);
|
|
~CUtlHash();
|
|
|
|
// invalid handle
|
|
static UtlHashHandle_t InvalidHandle(void) { return (UtlHashHandle_t)~0; }
|
|
bool IsValidHandle(UtlHashHandle_t handle) const;
|
|
|
|
// size
|
|
int Count(void) const;
|
|
|
|
// memory
|
|
void Purge(void);
|
|
|
|
// insertion methods
|
|
UtlHashHandle_t Insert(Data const &src);
|
|
UtlHashHandle_t Insert(Data const &src, bool *pDidInsert);
|
|
UtlHashHandle_t AllocEntryFromKey(Data const &src);
|
|
|
|
// removal methods
|
|
void Remove(UtlHashHandle_t handle);
|
|
void RemoveAll();
|
|
|
|
// retrieval methods
|
|
UtlHashHandle_t Find(Data const &src) const;
|
|
|
|
Data &Element(UtlHashHandle_t handle);
|
|
Data const &Element(UtlHashHandle_t handle) const;
|
|
Data &operator[](UtlHashHandle_t handle);
|
|
Data const &operator[](UtlHashHandle_t handle) const;
|
|
|
|
UtlHashHandle_t GetFirstHandle() const;
|
|
UtlHashHandle_t GetNextHandle(UtlHashHandle_t h) const;
|
|
|
|
// debugging!!
|
|
void Log(const char *filename);
|
|
|
|
protected:
|
|
int GetBucketIndex(UtlHashHandle_t handle) const;
|
|
int GetKeyDataIndex(UtlHashHandle_t handle) const;
|
|
UtlHashHandle_t BuildHandle(int ndxBucket, int ndxKeyData) const;
|
|
|
|
bool DoFind(Data const &src, unsigned int *pBucket, int *pIndex) const;
|
|
|
|
protected:
|
|
// handle upper 16 bits = bucket index (bucket heads)
|
|
// handle lower 16 bits = key index (bucket list)
|
|
typedef CUtlVector<Data> HashBucketList_t;
|
|
CUtlVector<HashBucketList_t> m_Buckets;
|
|
|
|
CompareFunc_t
|
|
m_CompareFunc; // function used to handle unique compares on data
|
|
KeyFunc_t m_KeyFunc; // function used to generate the key value
|
|
|
|
bool m_bPowerOfTwo; // if the bucket value is a power of two,
|
|
unsigned int m_ModMask; // use the mod mask to "mod"
|
|
};
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
CUtlHash<Data, C, K>::CUtlHash(int bucketCount, int growCount, int initCount,
|
|
CompareFunc_t compareFunc, KeyFunc_t keyFunc)
|
|
: m_CompareFunc(compareFunc), m_KeyFunc(keyFunc) {
|
|
m_Buckets.SetSize(bucketCount);
|
|
for (int ndxBucket = 0; ndxBucket < bucketCount; ndxBucket++) {
|
|
m_Buckets[ndxBucket].SetSize(initCount);
|
|
m_Buckets[ndxBucket].SetGrowSize(growCount);
|
|
}
|
|
|
|
// check to see if the bucket count is a power of 2 and set up
|
|
// optimizations appropriately
|
|
m_bPowerOfTwo = IsPowerOfTwo(bucketCount);
|
|
m_ModMask = m_bPowerOfTwo ? (bucketCount - 1) : 0;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
CUtlHash<Data, C, K>::~CUtlHash() {
|
|
Purge();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline bool CUtlHash<Data, C, K>::IsValidHandle(UtlHashHandle_t handle) const {
|
|
int ndxBucket = GetBucketIndex(handle);
|
|
int ndxKeyData = GetKeyDataIndex(handle);
|
|
|
|
// ndxBucket and ndxKeyData can't possibly be less than zero -- take a
|
|
// look at the definition of the Get..Index functions for why. However,
|
|
// if you override those functions, you will need to override this one
|
|
// as well.
|
|
if (/*( ndxBucket >= 0 ) && */ (ndxBucket < m_Buckets.Count())) {
|
|
if (/*( ndxKeyData >= 0 ) && */ (ndxKeyData <
|
|
m_Buckets[ndxBucket].Count()))
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline int CUtlHash<Data, C, K>::Count(void) const {
|
|
int count = 0;
|
|
|
|
int bucketCount = m_Buckets.Count();
|
|
for (int ndxBucket = 0; ndxBucket < bucketCount; ndxBucket++) {
|
|
count += m_Buckets[ndxBucket].Count();
|
|
}
|
|
|
|
return count;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline int CUtlHash<Data, C, K>::GetBucketIndex(UtlHashHandle_t handle) const {
|
|
return (((handle >> 16) & 0x0000ffff));
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline int CUtlHash<Data, C, K>::GetKeyDataIndex(UtlHashHandle_t handle) const {
|
|
return (handle & 0x0000ffff);
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline UtlHashHandle_t CUtlHash<Data, C, K>::BuildHandle(int ndxBucket,
|
|
int ndxKeyData) const {
|
|
assert((ndxBucket >= 0) && (ndxBucket < 65536));
|
|
assert((ndxKeyData >= 0) && (ndxKeyData < 65536));
|
|
|
|
UtlHashHandle_t handle = ndxKeyData;
|
|
handle |= (ndxBucket << 16);
|
|
|
|
return handle;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline void CUtlHash<Data, C, K>::Purge(void) {
|
|
int bucketCount = m_Buckets.Count();
|
|
for (int ndxBucket = 0; ndxBucket < bucketCount; ndxBucket++) {
|
|
m_Buckets[ndxBucket].Purge();
|
|
}
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline bool CUtlHash<Data, C, K>::DoFind(Data const &src, unsigned int *pBucket,
|
|
int *pIndex) const {
|
|
// generate the data "key"
|
|
unsigned int key = m_KeyFunc(src);
|
|
|
|
// hash the "key" - get the correct hash table "bucket"
|
|
unsigned int ndxBucket;
|
|
if (m_bPowerOfTwo) {
|
|
*pBucket = ndxBucket = (key & m_ModMask);
|
|
} else {
|
|
int bucketCount = m_Buckets.Count();
|
|
*pBucket = ndxBucket = key % bucketCount;
|
|
}
|
|
|
|
int ndxKeyData;
|
|
const CUtlVector<Data> &bucket = m_Buckets[ndxBucket];
|
|
int keyDataCount = bucket.Count();
|
|
for (ndxKeyData = 0; ndxKeyData < keyDataCount; ndxKeyData++) {
|
|
if (m_CompareFunc(bucket.Element(ndxKeyData), src)) break;
|
|
}
|
|
|
|
if (ndxKeyData == keyDataCount) return false;
|
|
|
|
*pIndex = ndxKeyData;
|
|
return true;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline UtlHashHandle_t CUtlHash<Data, C, K>::Find(Data const &src) const {
|
|
unsigned int ndxBucket;
|
|
int ndxKeyData;
|
|
|
|
if (DoFind(src, &ndxBucket, &ndxKeyData)) {
|
|
return (BuildHandle(ndxBucket, ndxKeyData));
|
|
}
|
|
return (InvalidHandle());
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline UtlHashHandle_t CUtlHash<Data, C, K>::Insert(Data const &src) {
|
|
unsigned int ndxBucket;
|
|
int ndxKeyData;
|
|
|
|
if (DoFind(src, &ndxBucket, &ndxKeyData)) {
|
|
return (BuildHandle(ndxBucket, ndxKeyData));
|
|
}
|
|
|
|
ndxKeyData = m_Buckets[ndxBucket].AddToTail(src);
|
|
|
|
return (BuildHandle(ndxBucket, ndxKeyData));
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline UtlHashHandle_t CUtlHash<Data, C, K>::Insert(Data const &src,
|
|
bool *pDidInsert) {
|
|
unsigned int ndxBucket;
|
|
int ndxKeyData;
|
|
|
|
if (DoFind(src, &ndxBucket, &ndxKeyData)) {
|
|
*pDidInsert = false;
|
|
return (BuildHandle(ndxBucket, ndxKeyData));
|
|
}
|
|
|
|
*pDidInsert = true;
|
|
ndxKeyData = m_Buckets[ndxBucket].AddToTail(src);
|
|
|
|
return (BuildHandle(ndxBucket, ndxKeyData));
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline UtlHashHandle_t CUtlHash<Data, C, K>::AllocEntryFromKey(
|
|
Data const &src) {
|
|
unsigned int ndxBucket;
|
|
int ndxKeyData;
|
|
|
|
if (DoFind(src, &ndxBucket, &ndxKeyData)) {
|
|
return (BuildHandle(ndxBucket, ndxKeyData));
|
|
}
|
|
|
|
ndxKeyData = m_Buckets[ndxBucket].AddToTail();
|
|
|
|
return (BuildHandle(ndxBucket, ndxKeyData));
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline void CUtlHash<Data, C, K>::Remove(UtlHashHandle_t handle) {
|
|
assert(IsValidHandle(handle));
|
|
|
|
// check to see if the bucket exists
|
|
int ndxBucket = GetBucketIndex(handle);
|
|
int ndxKeyData = GetKeyDataIndex(handle);
|
|
|
|
if (m_Buckets[ndxBucket].IsValidIndex(ndxKeyData)) {
|
|
m_Buckets[ndxBucket].FastRemove(ndxKeyData);
|
|
}
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline void CUtlHash<Data, C, K>::RemoveAll() {
|
|
int bucketCount = m_Buckets.Count();
|
|
for (int ndxBucket = 0; ndxBucket < bucketCount; ndxBucket++) {
|
|
m_Buckets[ndxBucket].RemoveAll();
|
|
}
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline Data &CUtlHash<Data, C, K>::Element(UtlHashHandle_t handle) {
|
|
int ndxBucket = GetBucketIndex(handle);
|
|
int ndxKeyData = GetKeyDataIndex(handle);
|
|
|
|
return (m_Buckets[ndxBucket].Element(ndxKeyData));
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline Data const &CUtlHash<Data, C, K>::Element(UtlHashHandle_t handle) const {
|
|
int ndxBucket = GetBucketIndex(handle);
|
|
int ndxKeyData = GetKeyDataIndex(handle);
|
|
|
|
return (m_Buckets[ndxBucket].Element(ndxKeyData));
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline Data &CUtlHash<Data, C, K>::operator[](UtlHashHandle_t handle) {
|
|
int ndxBucket = GetBucketIndex(handle);
|
|
int ndxKeyData = GetKeyDataIndex(handle);
|
|
|
|
return (m_Buckets[ndxBucket].Element(ndxKeyData));
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline Data const &CUtlHash<Data, C, K>::operator[](
|
|
UtlHashHandle_t handle) const {
|
|
int ndxBucket = GetBucketIndex(handle);
|
|
int ndxKeyData = GetKeyDataIndex(handle);
|
|
|
|
return (m_Buckets[ndxBucket].Element(ndxKeyData));
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline UtlHashHandle_t CUtlHash<Data, C, K>::GetFirstHandle() const {
|
|
return GetNextHandle((UtlHashHandle_t)-1);
|
|
}
|
|
|
|
template <class Data, typename C, typename K>
|
|
inline UtlHashHandle_t CUtlHash<Data, C, K>::GetNextHandle(
|
|
UtlHashHandle_t handle) const {
|
|
++handle; // start at the first possible handle after the one given
|
|
|
|
int bi = GetBucketIndex(handle);
|
|
int ki = GetKeyDataIndex(handle);
|
|
|
|
int nBuckets = m_Buckets.Count();
|
|
for (; bi < nBuckets; ++bi) {
|
|
if (ki < m_Buckets[bi].Count()) return BuildHandle(bi, ki);
|
|
|
|
ki = 0;
|
|
}
|
|
|
|
return InvalidHandle();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, typename C, typename K>
|
|
inline void CUtlHash<Data, C, K>::Log(const char *filename) {
|
|
FILE *pDebugFp;
|
|
pDebugFp = fopen(filename, "w");
|
|
if (!pDebugFp) return;
|
|
|
|
int maxBucketSize = 0;
|
|
int numBucketsEmpty = 0;
|
|
|
|
int bucketCount = m_Buckets.Count();
|
|
fprintf(pDebugFp, "\n%d Buckets\n", bucketCount);
|
|
|
|
for (int ndxBucket = 0; ndxBucket < bucketCount; ndxBucket++) {
|
|
int count = m_Buckets[ndxBucket].Count();
|
|
|
|
if (count > maxBucketSize) {
|
|
maxBucketSize = count;
|
|
}
|
|
if (count == 0) numBucketsEmpty++;
|
|
|
|
fprintf(pDebugFp, "Bucket %d: %d\n", ndxBucket, count);
|
|
}
|
|
|
|
fprintf(pDebugFp, "\nBucketHeads Used: %d\n",
|
|
bucketCount - numBucketsEmpty);
|
|
fprintf(pDebugFp, "Max Bucket Size: %d\n", maxBucketSize);
|
|
|
|
fclose(pDebugFp);
|
|
}
|
|
|
|
//=============================================================================
|
|
//
|
|
// Fast Hash
|
|
//
|
|
// Number of buckets must be a power of 2.
|
|
// Key must be 32-bits (unsigned int).
|
|
//
|
|
typedef int UtlHashFastHandle_t;
|
|
|
|
#define UTLHASH_POOL_SCALAR 2
|
|
|
|
class CUtlHashFastNoHash {
|
|
public:
|
|
static int Hash(int key, int bucketMask) { return (key & bucketMask); }
|
|
};
|
|
|
|
class CUtlHashFastGenericHash {
|
|
public:
|
|
static int Hash(int key, int bucketMask) {
|
|
return (HashIntConventional(key) & bucketMask);
|
|
}
|
|
};
|
|
|
|
template <class Data, class HashFuncs = CUtlHashFastNoHash>
|
|
class CUtlHashFast {
|
|
public:
|
|
// Constructor/Deconstructor.
|
|
CUtlHashFast();
|
|
~CUtlHashFast();
|
|
|
|
// Memory.
|
|
void Purge(void);
|
|
|
|
// Invalid handle.
|
|
static UtlHashFastHandle_t InvalidHandle(void) {
|
|
return (UtlHashFastHandle_t)~0;
|
|
}
|
|
|
|
// Initialize.
|
|
bool Init(int nBucketCount);
|
|
|
|
// Size.
|
|
int Count(void);
|
|
|
|
// Insertion.
|
|
UtlHashFastHandle_t Insert(unsigned int uiKey, const Data &data);
|
|
UtlHashFastHandle_t FastInsert(unsigned int uiKey, const Data &data);
|
|
|
|
// Removal.
|
|
void Remove(UtlHashFastHandle_t hHash);
|
|
void RemoveAll(void);
|
|
|
|
// Retrieval.
|
|
UtlHashFastHandle_t Find(unsigned int uiKey);
|
|
|
|
Data &Element(UtlHashFastHandle_t hHash);
|
|
Data const &Element(UtlHashFastHandle_t hHash) const;
|
|
Data &operator[](UtlHashFastHandle_t hHash);
|
|
Data const &operator[](UtlHashFastHandle_t hHash) const;
|
|
|
|
// protected:
|
|
|
|
// Templatized for memory tracking purposes
|
|
template <typename HashData>
|
|
struct HashFastData_t_ {
|
|
unsigned int m_uiKey;
|
|
HashData m_Data;
|
|
};
|
|
|
|
typedef HashFastData_t_<Data> HashFastData_t;
|
|
|
|
unsigned int m_uiBucketMask;
|
|
CUtlVector<UtlHashFastHandle_t> m_aBuckets;
|
|
CUtlFixedLinkedList<HashFastData_t> m_aDataPool;
|
|
};
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Constructor
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, class HashFuncs>
|
|
CUtlHashFast<Data, HashFuncs>::CUtlHashFast() {
|
|
Purge();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Deconstructor
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, class HashFuncs>
|
|
CUtlHashFast<Data, HashFuncs>::~CUtlHashFast() {
|
|
Purge();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Destroy dynamically allocated hash data.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, class HashFuncs>
|
|
inline void CUtlHashFast<Data, HashFuncs>::Purge(void) {
|
|
m_aBuckets.Purge();
|
|
m_aDataPool.Purge();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Initialize the hash - set bucket count and hash grow amount.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, class HashFuncs>
|
|
bool CUtlHashFast<Data, HashFuncs>::Init(int nBucketCount) {
|
|
// Verify the bucket count is power of 2.
|
|
if (!IsPowerOfTwo(nBucketCount)) return false;
|
|
|
|
// Set the bucket size.
|
|
m_aBuckets.SetSize(nBucketCount);
|
|
for (int iBucket = 0; iBucket < nBucketCount; ++iBucket) {
|
|
m_aBuckets[iBucket] = m_aDataPool.InvalidIndex();
|
|
}
|
|
|
|
// Set the mod mask.
|
|
m_uiBucketMask = nBucketCount - 1;
|
|
|
|
// Calculate the grow size.
|
|
int nGrowSize = UTLHASH_POOL_SCALAR * nBucketCount;
|
|
m_aDataPool.SetGrowSize(nGrowSize);
|
|
|
|
return true;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Return the number of elements in the hash.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, class HashFuncs>
|
|
inline int CUtlHashFast<Data, HashFuncs>::Count(void) {
|
|
return m_aDataPool.Count();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Insert data into the hash table given its key (unsigned int), with
|
|
// a check to see if the element already exists within the tree.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, class HashFuncs>
|
|
inline UtlHashFastHandle_t CUtlHashFast<Data, HashFuncs>::Insert(
|
|
unsigned int uiKey, const Data &data) {
|
|
// Check to see if that key already exists in the buckets (should be
|
|
// unique).
|
|
UtlHashFastHandle_t hHash = Find(uiKey);
|
|
if (hHash != InvalidHandle()) return hHash;
|
|
|
|
return FastInsert(uiKey, data);
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Insert data into the hash table given its key (unsigned int),
|
|
// without a check to see if the element already exists within the
|
|
// tree.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, class HashFuncs>
|
|
inline UtlHashFastHandle_t CUtlHashFast<Data, HashFuncs>::FastInsert(
|
|
unsigned int uiKey, const Data &data) {
|
|
// Get a new element from the pool.
|
|
int iHashData = m_aDataPool.Alloc(true);
|
|
HashFastData_t *pHashData = &m_aDataPool[iHashData];
|
|
if (!pHashData) return InvalidHandle();
|
|
|
|
// Add data to new element.
|
|
pHashData->m_uiKey = uiKey;
|
|
pHashData->m_Data = data;
|
|
|
|
// Link element.
|
|
int iBucket = HashFuncs::Hash(uiKey, m_uiBucketMask);
|
|
m_aDataPool.LinkBefore(m_aBuckets[iBucket], iHashData);
|
|
m_aBuckets[iBucket] = iHashData;
|
|
|
|
return iHashData;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Remove a given element from the hash.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, class HashFuncs>
|
|
inline void CUtlHashFast<Data, HashFuncs>::Remove(UtlHashFastHandle_t hHash) {
|
|
int iBucket = HashFuncs::Hash(m_aDataPool[hHash].m_uiKey, m_uiBucketMask);
|
|
if (m_aBuckets[iBucket] == hHash) {
|
|
// It is a bucket head.
|
|
m_aBuckets[iBucket] = m_aDataPool.Next(hHash);
|
|
} else {
|
|
// Not a bucket head.
|
|
m_aDataPool.Unlink(hHash);
|
|
}
|
|
|
|
// Remove the element.
|
|
m_aDataPool.Remove(hHash);
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Remove all elements from the hash
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, class HashFuncs>
|
|
inline void CUtlHashFast<Data, HashFuncs>::RemoveAll(void) {
|
|
m_aBuckets.RemoveAll();
|
|
m_aDataPool.RemoveAll();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, class HashFuncs>
|
|
inline UtlHashFastHandle_t CUtlHashFast<Data, HashFuncs>::Find(
|
|
unsigned int uiKey) {
|
|
// hash the "key" - get the correct hash table "bucket"
|
|
int iBucket = HashFuncs::Hash(uiKey, m_uiBucketMask);
|
|
|
|
for (int iElement = m_aBuckets[iBucket];
|
|
iElement != m_aDataPool.InvalidIndex();
|
|
iElement = m_aDataPool.Next(iElement)) {
|
|
if (m_aDataPool[iElement].m_uiKey == uiKey) return iElement;
|
|
}
|
|
|
|
return InvalidHandle();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Return data given a hash handle.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, class HashFuncs>
|
|
inline Data &CUtlHashFast<Data, HashFuncs>::Element(UtlHashFastHandle_t hHash) {
|
|
return (m_aDataPool[hHash].m_Data);
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Return data given a hash handle.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, class HashFuncs>
|
|
inline Data const &CUtlHashFast<Data, HashFuncs>::Element(
|
|
UtlHashFastHandle_t hHash) const {
|
|
return (m_aDataPool[hHash].m_Data);
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Return data given a hash handle.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, class HashFuncs>
|
|
inline Data &CUtlHashFast<Data, HashFuncs>::operator[](
|
|
UtlHashFastHandle_t hHash) {
|
|
return (m_aDataPool[hHash].m_Data);
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Return data given a hash handle.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, class HashFuncs>
|
|
inline Data const &CUtlHashFast<Data, HashFuncs>::operator[](
|
|
UtlHashFastHandle_t hHash) const {
|
|
return (m_aDataPool[hHash].m_Data);
|
|
}
|
|
|
|
//=============================================================================
|
|
//
|
|
// Fixed Hash
|
|
//
|
|
// Number of buckets must be a power of 2.
|
|
// Key must be 32-bits (unsigned int).
|
|
//
|
|
typedef int UtlHashFixedHandle_t;
|
|
|
|
template <int NUM_BUCKETS>
|
|
class CUtlHashFixedGenericHash {
|
|
public:
|
|
static int Hash(int key, int bucketMask) {
|
|
int hash = HashIntConventional(key);
|
|
if (NUM_BUCKETS <= USHRT_MAX) {
|
|
hash ^= (hash >> 16);
|
|
}
|
|
if (NUM_BUCKETS <= UCHAR_MAX) {
|
|
hash ^= (hash >> 8);
|
|
}
|
|
return (hash & bucketMask);
|
|
}
|
|
};
|
|
|
|
template <class Data, int NUM_BUCKETS, class CHashFuncs = CUtlHashFastNoHash>
|
|
class CUtlHashFixed {
|
|
public:
|
|
// Constructor/Deconstructor.
|
|
CUtlHashFixed();
|
|
~CUtlHashFixed();
|
|
|
|
// Memory.
|
|
void Purge(void);
|
|
|
|
// Invalid handle.
|
|
static UtlHashFixedHandle_t InvalidHandle(void) {
|
|
return (UtlHashFixedHandle_t)~0;
|
|
}
|
|
|
|
// Size.
|
|
int Count(void);
|
|
|
|
// Insertion.
|
|
UtlHashFixedHandle_t Insert(unsigned int uiKey, const Data &data);
|
|
UtlHashFixedHandle_t FastInsert(unsigned int uiKey, const Data &data);
|
|
|
|
// Removal.
|
|
void Remove(UtlHashFixedHandle_t hHash);
|
|
void RemoveAll(void);
|
|
|
|
// Retrieval.
|
|
UtlHashFixedHandle_t Find(unsigned int uiKey);
|
|
|
|
Data &Element(UtlHashFixedHandle_t hHash);
|
|
Data const &Element(UtlHashFixedHandle_t hHash) const;
|
|
Data &operator[](UtlHashFixedHandle_t hHash);
|
|
Data const &operator[](UtlHashFixedHandle_t hHash) const;
|
|
|
|
// protected:
|
|
|
|
// Templatized for memory tracking purposes
|
|
template <typename Data_t>
|
|
struct HashFixedData_t_ {
|
|
unsigned int m_uiKey;
|
|
Data_t m_Data;
|
|
};
|
|
|
|
typedef HashFixedData_t_<Data> HashFixedData_t;
|
|
|
|
enum { BUCKET_MASK = NUM_BUCKETS - 1 };
|
|
CUtlPtrLinkedList<HashFixedData_t> m_aBuckets[NUM_BUCKETS];
|
|
int m_nElements;
|
|
};
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Constructor
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, int NUM_BUCKETS, class HashFuncs>
|
|
CUtlHashFixed<Data, NUM_BUCKETS, HashFuncs>::CUtlHashFixed() {
|
|
Purge();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Deconstructor
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, int NUM_BUCKETS, class HashFuncs>
|
|
CUtlHashFixed<Data, NUM_BUCKETS, HashFuncs>::~CUtlHashFixed() {
|
|
Purge();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Destroy dynamically allocated hash data.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, int NUM_BUCKETS, class HashFuncs>
|
|
inline void CUtlHashFixed<Data, NUM_BUCKETS, HashFuncs>::Purge(void) {
|
|
RemoveAll();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Return the number of elements in the hash.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, int NUM_BUCKETS, class HashFuncs>
|
|
inline int CUtlHashFixed<Data, NUM_BUCKETS, HashFuncs>::Count(void) {
|
|
return m_nElements;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Insert data into the hash table given its key (unsigned int), with
|
|
// a check to see if the element already exists within the tree.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, int NUM_BUCKETS, class HashFuncs>
|
|
inline UtlHashFixedHandle_t CUtlHashFixed<Data, NUM_BUCKETS, HashFuncs>::Insert(
|
|
unsigned int uiKey, const Data &data) {
|
|
// Check to see if that key already exists in the buckets (should be
|
|
// unique).
|
|
UtlHashFixedHandle_t hHash = Find(uiKey);
|
|
if (hHash != InvalidHandle()) return hHash;
|
|
|
|
return FastInsert(uiKey, data);
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Insert data into the hash table given its key (unsigned int),
|
|
// without a check to see if the element already exists within the
|
|
// tree.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, int NUM_BUCKETS, class HashFuncs>
|
|
inline UtlHashFixedHandle_t
|
|
CUtlHashFixed<Data, NUM_BUCKETS, HashFuncs>::FastInsert(unsigned int uiKey,
|
|
const Data &data) {
|
|
int iBucket = HashFuncs::Hash(uiKey, NUM_BUCKETS - 1);
|
|
UtlPtrLinkedListIndex_t iElem = m_aBuckets[iBucket].AddToHead();
|
|
|
|
HashFixedData_t *pHashData = &m_aBuckets[iBucket][iElem];
|
|
|
|
Assert((UtlPtrLinkedListIndex_t)pHashData == iElem);
|
|
|
|
// Add data to new element.
|
|
pHashData->m_uiKey = uiKey;
|
|
pHashData->m_Data = data;
|
|
|
|
m_nElements++;
|
|
return (UtlHashFixedHandle_t)pHashData;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Remove a given element from the hash.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, int NUM_BUCKETS, class HashFuncs>
|
|
inline void CUtlHashFixed<Data, NUM_BUCKETS, HashFuncs>::Remove(
|
|
UtlHashFixedHandle_t hHash) {
|
|
HashFixedData_t *pHashData = (HashFixedData_t *)hHash;
|
|
Assert(Find(pHashData->m_uiKey) != InvalidHandle());
|
|
int iBucket = HashFuncs::Hash(pHashData->m_uiKey, NUM_BUCKETS - 1);
|
|
m_aBuckets[iBucket].Remove((UtlPtrLinkedListIndex_t)pHashData);
|
|
m_nElements--;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Remove all elements from the hash
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, int NUM_BUCKETS, class HashFuncs>
|
|
inline void CUtlHashFixed<Data, NUM_BUCKETS, HashFuncs>::RemoveAll(void) {
|
|
for (int i = 0; i < NUM_BUCKETS; i++) {
|
|
m_aBuckets[i].RemoveAll();
|
|
}
|
|
m_nElements = 0;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, int NUM_BUCKETS, class HashFuncs>
|
|
inline UtlHashFixedHandle_t CUtlHashFixed<Data, NUM_BUCKETS, HashFuncs>::Find(
|
|
unsigned int uiKey) {
|
|
int iBucket = HashFuncs::Hash(uiKey, NUM_BUCKETS - 1);
|
|
CUtlPtrLinkedList<HashFixedData_t> &bucket = m_aBuckets[iBucket];
|
|
|
|
for (UtlPtrLinkedListIndex_t iElement = bucket.Head();
|
|
iElement != bucket.InvalidIndex(); iElement = bucket.Next(iElement)) {
|
|
if (bucket[iElement].m_uiKey == uiKey)
|
|
return (UtlHashFixedHandle_t)iElement;
|
|
}
|
|
|
|
return InvalidHandle();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Return data given a hash handle.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, int NUM_BUCKETS, class HashFuncs>
|
|
inline Data &CUtlHashFixed<Data, NUM_BUCKETS, HashFuncs>::Element(
|
|
UtlHashFixedHandle_t hHash) {
|
|
return ((HashFixedData_t *)hHash)->m_Data;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Return data given a hash handle.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, int NUM_BUCKETS, class HashFuncs>
|
|
inline Data const &CUtlHashFixed<Data, NUM_BUCKETS, HashFuncs>::Element(
|
|
UtlHashFixedHandle_t hHash) const {
|
|
return ((HashFixedData_t *)hHash)->m_Data;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Return data given a hash handle.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, int NUM_BUCKETS, class HashFuncs>
|
|
inline Data &CUtlHashFixed<Data, NUM_BUCKETS, HashFuncs>::operator[](
|
|
UtlHashFixedHandle_t hHash) {
|
|
return ((HashFixedData_t *)hHash)->m_Data;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Purpose: Return data given a hash handle.
|
|
//-----------------------------------------------------------------------------
|
|
template <class Data, int NUM_BUCKETS, class HashFuncs>
|
|
inline Data const &CUtlHashFixed<Data, NUM_BUCKETS, HashFuncs>::operator[](
|
|
UtlHashFixedHandle_t hHash) const {
|
|
return ((HashFixedData_t *)hHash)->m_Data;
|
|
}
|
|
|
|
#endif // UTLHASH_H
|