311 lines
10 KiB
C++
311 lines
10 KiB
C++
//========= Copyright Valve Corporation, All rights reserved. ============//
|
|
//
|
|
// Purpose:
|
|
//
|
|
//=============================================================================
|
|
|
|
#ifndef UTLHASHDICT_H
|
|
#define UTLHASHDICT_H
|
|
|
|
#if defined(_WIN32)
|
|
#pragma once
|
|
#endif
|
|
|
|
#include "mathlib/mathlib.h"
|
|
#include "tier1/generichash.h"
|
|
#include "tier1/utlhash.h"
|
|
|
|
//-----------------------------------------------------------------------------
|
|
//
|
|
//-----------------------------------------------------------------------------
|
|
template <typename T, bool bCaseInsensitive = true, bool bDupeStrings = true>
|
|
class CUtlHashDict {
|
|
public:
|
|
// constructor, destructor
|
|
CUtlHashDict(int bucketCount = 16, int growCount = 0, int initCount = 0);
|
|
~CUtlHashDict();
|
|
|
|
// gets particular elements
|
|
T &Element(unsigned i);
|
|
const T &Element(unsigned i) const;
|
|
T &operator[](unsigned i);
|
|
const T &operator[](unsigned i) const;
|
|
|
|
// gets element names
|
|
char const *GetElementName(unsigned i) const;
|
|
|
|
// Number of elements
|
|
int Count() const;
|
|
|
|
// Checks if a node is valid and in the tree
|
|
bool IsValidIndex(unsigned i) const;
|
|
|
|
// Invalid index
|
|
static unsigned InvalidHandle();
|
|
|
|
// Insert method (inserts in order)
|
|
unsigned Insert(const char *pName, const T &element);
|
|
unsigned Insert(const char *pName);
|
|
|
|
// Find method
|
|
unsigned Find(const char *pName) const;
|
|
|
|
// Remove methods
|
|
void RemoveAt(unsigned i);
|
|
void Remove(const char *pName);
|
|
void RemoveAll();
|
|
|
|
// Purge memory
|
|
void Purge();
|
|
void PurgeAndDeleteElements(); // Call delete on each element.
|
|
|
|
// Iteration methods
|
|
unsigned First() const;
|
|
unsigned Next(unsigned i) const;
|
|
|
|
protected:
|
|
struct Entry_t {
|
|
const char *pszSymbol;
|
|
T value;
|
|
};
|
|
|
|
template <bool bCaseInsensitive>
|
|
class CCompare {
|
|
public:
|
|
CCompare(int ignored) {}
|
|
|
|
bool operator()(const Entry_t &entry1, const Entry_t &entry2) const {
|
|
return !((bCaseInsensitive)
|
|
? stricmp(entry1.pszSymbol, entry2.pszSymbol)
|
|
: strcmp(entry1.pszSymbol, entry2.pszSymbol));
|
|
}
|
|
};
|
|
|
|
template <bool bCaseInsensitive>
|
|
class CHash {
|
|
public:
|
|
CHash(int ignored) {}
|
|
|
|
unsigned operator()(const Entry_t &entry) const {
|
|
return !((bCaseInsensitive) ? HashStringCaseless(entry.pszSymbol)
|
|
: HashString(entry.pszSymbol));
|
|
}
|
|
};
|
|
|
|
typedef CUtlHash<Entry_t, CCompare<bCaseInsensitive>,
|
|
CHash<bCaseInsensitive> >
|
|
CHashTable;
|
|
CHashTable m_Elements;
|
|
int m_nCount;
|
|
};
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// constructor, destructor
|
|
//-----------------------------------------------------------------------------
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::CUtlHashDict(
|
|
int bucketCount = 16, int growCount = 0, int initCount = 0)
|
|
: m_Elements(SmallestPowerOfTwoGreaterOrEqual(bucketCount), growCount,
|
|
initCount) {
|
|
Assert(SmallestPowerOfTwoGreaterOrEqual(bucketCount) <= 0xffff);
|
|
}
|
|
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::~CUtlHashDict() {
|
|
Purge();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// gets particular elements
|
|
//-----------------------------------------------------------------------------
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
inline T &CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Element(unsigned i) {
|
|
return m_Elements[i].value;
|
|
}
|
|
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
inline const T &CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Element(
|
|
unsigned i) const {
|
|
return m_Elements[i].value;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// gets element names
|
|
//-----------------------------------------------------------------------------
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
inline char const *
|
|
CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::GetElementName(
|
|
unsigned i) const {
|
|
return m_Elements[i].pszSymbol;
|
|
}
|
|
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
inline T &CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::operator[](
|
|
unsigned i) {
|
|
return m_Elements[i].value;
|
|
}
|
|
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
inline const T &CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::operator[](
|
|
unsigned i) const {
|
|
return m_Elements[i].value;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Num elements
|
|
//-----------------------------------------------------------------------------
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
inline int CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Count() const {
|
|
Assert(m_nCount == m_Elements.Count());
|
|
return m_nCount;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Checks if a node is valid and in the tree
|
|
//-----------------------------------------------------------------------------
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
inline bool CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::IsValidIndex(
|
|
unsigned i) const {
|
|
return m_Elements.IsValidHandle(i);
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Invalid index
|
|
//-----------------------------------------------------------------------------
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
inline unsigned
|
|
CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::InvalidHandle() {
|
|
return CHashTable::InvalidHandle();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Delete a node from the tree
|
|
//-----------------------------------------------------------------------------
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
void CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::RemoveAt(unsigned elem) {
|
|
if (bDupeStrings) {
|
|
free((void *)m_Elements[elem].pszSymbol);
|
|
}
|
|
m_Elements.Remove(elem);
|
|
m_nCount--;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// remove a node in the tree
|
|
//-----------------------------------------------------------------------------
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
void CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Remove(
|
|
const char *search) {
|
|
unsigned node = Find(search);
|
|
if (node != InvalidHandle()) {
|
|
RemoveAt(node);
|
|
}
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Removes all nodes from the tree
|
|
//-----------------------------------------------------------------------------
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
void CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::RemoveAll() {
|
|
if (bDupeStrings) {
|
|
typename UtlHashHandle_t index = m_Elements.GetFirstHandle();
|
|
while (index != m_Elements.InvalidHandle()) {
|
|
free((void *)m_Elements[index].pszSymbol);
|
|
index = m_Elements.GetNextHandle(index);
|
|
}
|
|
}
|
|
|
|
m_Elements.RemoveAll();
|
|
m_nCount = 0;
|
|
}
|
|
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
void CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Purge() {
|
|
if (bDupeStrings) {
|
|
typename UtlHashHandle_t index = m_Elements.GetFirstHandle();
|
|
while (index != m_Elements.InvalidHandle()) {
|
|
free((void *)m_Elements[index].pszSymbol);
|
|
index = m_Elements.GetNextHandle(index);
|
|
}
|
|
}
|
|
|
|
m_Elements.Purge();
|
|
m_nCount = 0;
|
|
}
|
|
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
void CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::PurgeAndDeleteElements() {
|
|
// Delete all the elements.
|
|
unsigned index = m_Elements.GetFirstHandle();
|
|
while (index != m_Elements.InvalidHandle()) {
|
|
if (bDupeStrings) {
|
|
free((void *)m_Elements[index].pszSymbol);
|
|
}
|
|
delete m_Elements[index].value;
|
|
index = m_Elements.GetNextHandle(index);
|
|
}
|
|
|
|
m_Elements.RemoveAll();
|
|
m_nCount = 0;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// inserts a node into the tree
|
|
//-----------------------------------------------------------------------------
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
unsigned CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Insert(
|
|
const char *pName, const T &element) {
|
|
MEM_ALLOC_CREDIT_CLASS();
|
|
m_nCount++;
|
|
Entry_t entry = {(bDupeStrings) ? strdup(pName) : pName, element};
|
|
bool bInserted;
|
|
unsigned result = m_Elements.Insert(entry, &bInserted);
|
|
if (bDupeStrings && !bInserted) {
|
|
free((void *)entry.pszSymbol);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
unsigned CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Insert(
|
|
const char *pName) {
|
|
MEM_ALLOC_CREDIT_CLASS();
|
|
m_nCount++;
|
|
Entry_t entry = {(bDupeStrings) ? strdup(pName) : pName};
|
|
bool bInserted;
|
|
unsigned result = m_Elements.Insert(entry, &bInserted);
|
|
if (bDupeStrings && !bInserted) {
|
|
free((void *)entry.pszSymbol);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// finds a node in the tree
|
|
//-----------------------------------------------------------------------------
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
unsigned CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Find(
|
|
const char *pName) const {
|
|
MEM_ALLOC_CREDIT_CLASS();
|
|
if (pName)
|
|
return m_Elements.Find(*((Entry_t *)&pName));
|
|
else
|
|
return InvalidHandle();
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
// Iteration methods
|
|
//-----------------------------------------------------------------------------
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
unsigned CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::First() const {
|
|
return m_Elements.GetFirstHandle();
|
|
}
|
|
|
|
template <typename T, bool bCaseInsensitive, bool bDupeStrings>
|
|
unsigned CUtlHashDict<T, bCaseInsensitive, bDupeStrings>::Next(
|
|
unsigned i) const {
|
|
return m_Elements.GetNextHandle(i);
|
|
}
|
|
|
|
#endif // UTLHASHDICT_H
|