434 lines
12 KiB
C
434 lines
12 KiB
C
|
/*
|
||
|
|
** Command & Conquer Renegade(tm)
|
||
|
|
** Copyright 2025 Electronic Arts Inc.
|
||
|
|
**
|
||
|
|
** This program is free software: you can redistribute it and/or modify
|
||
|
|
** it under the terms of the GNU General Public License as published by
|
||
|
|
** the Free Software Foundation, either version 3 of the License, or
|
||
|
|
** (at your option) any later version.
|
||
|
|
**
|
||
|
|
** This program is distributed in the hope that it will be useful,
|
||
|
|
** but WITHOUT ANY WARRANTY; without even the implied warranty of
|
||
|
|
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
||
|
|
** GNU General Public License for more details.
|
||
|
|
**
|
||
|
|
** You should have received a copy of the GNU General Public License
|
||
|
|
** along with this program. If not, see <http://www.gnu.org/licenses/>.
|
||
|
|
*/
|
||
|
|
|
||
|
|
/***********************************************************************************************
|
||
|
|
*** Confidential - Westwood Studios ***
|
||
|
|
***********************************************************************************************
|
||
|
|
* *
|
||
|
|
* Project Name : Commando *
|
||
|
|
* *
|
||
|
|
* $Archive:: /Commando/Code/wwlib/hashtemplate.h $*
|
||
|
|
* *
|
||
|
|
* Author:: Greg_h *
|
||
|
|
* *
|
||
|
|
* $Modtime:: 11/19/01 12:16p $*
|
||
|
|
* *
|
||
|
|
* $Revision:: 7 $*
|
||
|
|
* *
|
||
|
|
*---------------------------------------------------------------------------------------------*
|
||
|
|
* Functions: *
|
||
|
|
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
|
||
|
|
|
||
|
|
|
||
|
|
#if defined(_MSC_VER)
|
||
|
|
#pragma once
|
||
|
|
#endif
|
||
|
|
|
||
|
|
#ifndef HASH_TEMPLATE_H
|
||
|
|
#define HASH_TEMPLATE_H
|
||
|
|
|
||
|
|
#include "always.h"
|
||
|
|
#include "wwstring.h"
|
||
|
|
|
||
|
|
// Class for providing hash values
|
||
|
|
|
||
|
|
template <class Key> class HashTemplateKeyClass
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
static inline unsigned int Get_Hash_Value (const Key& k);
|
||
|
|
};
|
||
|
|
|
||
|
|
// Default hash function for data types that can be cast into an unsigned int
|
||
|
|
template <class Key> inline unsigned int HashTemplateKeyClass<Key>::Get_Hash_Value (const Key& k)
|
||
|
|
{
|
||
|
|
unsigned int hval = *((const unsigned int*)(&k));
|
||
|
|
hval = hval + (hval>>5) + (hval>>10) + (hval >> 20);
|
||
|
|
return hval;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Specialization for floating point hash values (as the default dword-
|
||
|
|
// casting yields a very bad hash function)
|
||
|
|
template <> inline unsigned int HashTemplateKeyClass<float>::Get_Hash_Value (const float& s)
|
||
|
|
{
|
||
|
|
unsigned int z = *((const unsigned int*)(&s));
|
||
|
|
return ((z>>22)+(z>>12)+(z));
|
||
|
|
}
|
||
|
|
|
||
|
|
// Hash class
|
||
|
|
template <class KeyType, class ValueType>
|
||
|
|
class HashTemplateClass
|
||
|
|
{
|
||
|
|
struct Entry;
|
||
|
|
public:
|
||
|
|
|
||
|
|
enum
|
||
|
|
{
|
||
|
|
NIL = -1 // internal enumeration for representing a NULL link
|
||
|
|
};
|
||
|
|
|
||
|
|
HashTemplateClass(void);
|
||
|
|
~HashTemplateClass(void);
|
||
|
|
|
||
|
|
void Insert(const KeyType& s, const ValueType& d);
|
||
|
|
void Set_Value(const KeyType& s, const ValueType& d);
|
||
|
|
void Remove(const KeyType& s);
|
||
|
|
void Remove(const KeyType& s, const ValueType& d);
|
||
|
|
ValueType Get(const KeyType& s) const;
|
||
|
|
bool Get(const KeyType& s, ValueType& d) const;
|
||
|
|
bool Exists(const KeyType& s) const;
|
||
|
|
bool Exists(const KeyType& s, const ValueType& d) const;
|
||
|
|
void Remove_All(void);
|
||
|
|
unsigned int Get_Size(void) const;
|
||
|
|
|
||
|
|
int* Get_Hash() { return Hash; }
|
||
|
|
Entry* Get_Table() { return Table; }
|
||
|
|
|
||
|
|
private:
|
||
|
|
HashTemplateClass (const HashTemplateClass&); // not allowed
|
||
|
|
HashTemplateClass& operator= (const HashTemplateClass&); // not allowed
|
||
|
|
static unsigned int Get_Hash_Val(const KeyType& s, const unsigned int hash_array_size);
|
||
|
|
void Re_Hash(void);
|
||
|
|
|
||
|
|
int Alloc_Entry(void);
|
||
|
|
|
||
|
|
struct Entry
|
||
|
|
{
|
||
|
|
int Next; // next pointer in linked list
|
||
|
|
KeyType Key; // key
|
||
|
|
ValueType Value; // value
|
||
|
|
};
|
||
|
|
|
||
|
|
int* Hash; // hash pointers
|
||
|
|
Entry* Table; // allocation table
|
||
|
|
int First; // handle of first free entry
|
||
|
|
unsigned int Size; // size of hash table
|
||
|
|
};
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType>
|
||
|
|
class HashTemplateIterator
|
||
|
|
{
|
||
|
|
int HashIndex; // index to hash pointer table
|
||
|
|
int Handle;
|
||
|
|
HashTemplateClass<KeyType,ValueType>& HashTable;
|
||
|
|
|
||
|
|
public:
|
||
|
|
HashTemplateIterator(HashTemplateClass<KeyType,ValueType>& hash_table)
|
||
|
|
:
|
||
|
|
HashTable(hash_table)
|
||
|
|
{
|
||
|
|
First();
|
||
|
|
}
|
||
|
|
|
||
|
|
void First()
|
||
|
|
{
|
||
|
|
Handle=HashTemplateClass<KeyType,ValueType>::NIL;
|
||
|
|
int size=HashTable.Get_Size();
|
||
|
|
for (HashIndex=0;HashIndex<size;++HashIndex) {
|
||
|
|
Handle = HashTable.Get_Hash()[HashIndex];
|
||
|
|
if (Handle!=HashTemplateClass<KeyType,ValueType>::NIL) break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
void Next()
|
||
|
|
{
|
||
|
|
Handle=HashTable.Get_Table()[Handle].Next;
|
||
|
|
if (Handle==HashTemplateClass<KeyType,ValueType>::NIL) {
|
||
|
|
int size=HashTable.Get_Size();
|
||
|
|
for (++HashIndex;HashIndex<size;++HashIndex) {
|
||
|
|
Handle = HashTable.Get_Hash()[HashIndex];
|
||
|
|
if (Handle!=HashTemplateClass<KeyType,ValueType>::NIL) break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
bool Is_Done() const
|
||
|
|
{
|
||
|
|
return HashIndex==int(HashTable.Get_Size());
|
||
|
|
}
|
||
|
|
|
||
|
|
ValueType& Peek_Value()
|
||
|
|
{
|
||
|
|
return HashTable.Get_Table()[Handle].Value;
|
||
|
|
}
|
||
|
|
|
||
|
|
const KeyType& Peek_Key()
|
||
|
|
{
|
||
|
|
return HashTable.Get_Table()[Handle].Key;
|
||
|
|
}
|
||
|
|
|
||
|
|
};
|
||
|
|
|
||
|
|
//------------------------------------------------------------------------
|
||
|
|
// Implementation
|
||
|
|
//------------------------------------------------------------------------
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType> inline void HashTemplateClass<KeyType,ValueType>::Insert(const KeyType& s, const ValueType& d)
|
||
|
|
{
|
||
|
|
int h;
|
||
|
|
h = Alloc_Entry();
|
||
|
|
unsigned int hval = Get_Hash_Val(s,Size);
|
||
|
|
Table[h].Key = s;
|
||
|
|
Table[h].Value = d;
|
||
|
|
Table[h].Next = Hash[hval];
|
||
|
|
Hash[hval] = h;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType> inline unsigned int HashTemplateClass<KeyType,ValueType>::Get_Size (void) const
|
||
|
|
{
|
||
|
|
return Size;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType> inline void HashTemplateClass<KeyType,ValueType>::Remove_All (void)
|
||
|
|
{
|
||
|
|
for (unsigned int i = 0; i < Size; i++)
|
||
|
|
{
|
||
|
|
int f = Hash[i];
|
||
|
|
if (f!=NIL)
|
||
|
|
{
|
||
|
|
int h = f;
|
||
|
|
while (Table[h].Next != NIL)
|
||
|
|
h = Table[h].Next;
|
||
|
|
Table[h].Next = First; // link to first free
|
||
|
|
First = f; // link to beginning
|
||
|
|
Hash[i] = NIL; // kill entry in hash
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType> inline void HashTemplateClass<KeyType,ValueType>::Remove (const KeyType& s)
|
||
|
|
{
|
||
|
|
if (!Hash) return;
|
||
|
|
unsigned int hval = Get_Hash_Val(s,Size);
|
||
|
|
int prev = NIL;
|
||
|
|
int h = Hash[hval];
|
||
|
|
|
||
|
|
while (h != NIL)
|
||
|
|
{
|
||
|
|
if (Table[h].Key == s)
|
||
|
|
{
|
||
|
|
if (prev!=NIL)
|
||
|
|
Table[prev].Next = Table[h].Next;
|
||
|
|
else
|
||
|
|
Hash[hval] = Table[h].Next;
|
||
|
|
Table[h].Next = First;
|
||
|
|
First = h;
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
prev = h;
|
||
|
|
h = Table[h].Next;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType> inline void HashTemplateClass<KeyType,ValueType>::Remove (const KeyType& s, const ValueType& d)
|
||
|
|
{
|
||
|
|
if (!Hash) return;
|
||
|
|
unsigned int hval = Get_Hash_Val(s,Size);
|
||
|
|
int prev = NIL;
|
||
|
|
int h = Hash[hval];
|
||
|
|
|
||
|
|
while (h != NIL)
|
||
|
|
{
|
||
|
|
if (Table[h].Key == s && Table[h].Value == d)
|
||
|
|
{
|
||
|
|
if (prev!=NIL)
|
||
|
|
Table[prev].Next = Table[h].Next;
|
||
|
|
else
|
||
|
|
Hash[hval] = Table[h].Next;
|
||
|
|
Table[h].Next = First;
|
||
|
|
First = h;
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
prev = h;
|
||
|
|
h = Table[h].Next;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Set the value at existing key, or if not found insert a new value
|
||
|
|
template <class KeyType, class ValueType> inline void HashTemplateClass<KeyType,ValueType>::Set_Value (const KeyType& s, const ValueType& v)
|
||
|
|
{
|
||
|
|
if (Hash) {
|
||
|
|
int h = Hash[Get_Hash_Val(s,Size)];
|
||
|
|
while (h!=NIL) {
|
||
|
|
if (Table[h].Key == s) {
|
||
|
|
Table[h].Value=v;
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
h = Table[h].Next;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
Insert(s,v);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType> inline ValueType HashTemplateClass<KeyType,ValueType>::Get (const KeyType& s) const
|
||
|
|
{
|
||
|
|
if (Hash) {
|
||
|
|
int h = Hash[Get_Hash_Val(s,Size)];
|
||
|
|
while (h!=NIL)
|
||
|
|
{
|
||
|
|
if (Table[h].Key == s)
|
||
|
|
return Table[h].Value;
|
||
|
|
h = Table[h].Next;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return ValueType(0);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType> inline bool HashTemplateClass<KeyType,ValueType>::Get(const KeyType& s, ValueType& d) const
|
||
|
|
{
|
||
|
|
if (Hash) {
|
||
|
|
int h = Hash[Get_Hash_Val(s,Size)];
|
||
|
|
while (h!=NIL)
|
||
|
|
{
|
||
|
|
if (Table[h].Key == s)
|
||
|
|
{
|
||
|
|
d = Table[h].Value;
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
h = Table[h].Next;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType> inline bool HashTemplateClass<KeyType,ValueType>::Exists(const KeyType& s) const
|
||
|
|
{
|
||
|
|
if (Hash) {
|
||
|
|
int h = Hash[Get_Hash_Val(s,Size)];
|
||
|
|
while (h!=NIL)
|
||
|
|
{
|
||
|
|
if (Table[h].Key == s)
|
||
|
|
return true;
|
||
|
|
h = Table[h].Next;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType> inline bool HashTemplateClass<KeyType,ValueType>::Exists(const KeyType& s, const ValueType& d) const
|
||
|
|
{
|
||
|
|
if (Hash) {
|
||
|
|
int h = Hash[Get_Hash_Val(s,Size)];
|
||
|
|
while (h!=NIL)
|
||
|
|
{
|
||
|
|
if (Table[h].Key == s && Table[h].Value == d)
|
||
|
|
return true;
|
||
|
|
h = Table[h].Next;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType> inline unsigned int HashTemplateClass<KeyType,ValueType>::Get_Hash_Val(const KeyType& s, const unsigned int hash_array_size)
|
||
|
|
{
|
||
|
|
return HashTemplateKeyClass<KeyType>::Get_Hash_Value (s) & (hash_array_size-1);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType> inline void HashTemplateClass<KeyType,ValueType>::Re_Hash()
|
||
|
|
{
|
||
|
|
unsigned int new_size = Size*2;
|
||
|
|
if (new_size < 4)
|
||
|
|
new_size = 4;
|
||
|
|
|
||
|
|
Entry *new_table = new Entry[new_size];
|
||
|
|
int *new_hash = new int[new_size];
|
||
|
|
|
||
|
|
int cnt = 0;
|
||
|
|
int i;
|
||
|
|
|
||
|
|
for (i = 0; i < (int)new_size; i++)
|
||
|
|
{
|
||
|
|
new_table[i].Next = NIL;
|
||
|
|
new_hash[i] = NIL;
|
||
|
|
}
|
||
|
|
|
||
|
|
if (Size) // if we have existing data, it needs to be rehashed
|
||
|
|
{
|
||
|
|
for (i = 0; i < (int)Size; i++) // step through each old hash set
|
||
|
|
{
|
||
|
|
int h = Hash[i];
|
||
|
|
while (h != NIL)
|
||
|
|
{
|
||
|
|
unsigned int hVal = Get_Hash_Val(Table[h].Key, new_size);
|
||
|
|
new_table[cnt].Key = Table[h].Key;
|
||
|
|
new_table[cnt].Value = Table[h].Value;
|
||
|
|
new_table[cnt].Next = new_hash[hVal];
|
||
|
|
new_hash[hVal] = cnt;
|
||
|
|
cnt++;
|
||
|
|
h = Table[h].Next;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
delete[] Hash;
|
||
|
|
delete[] Table;
|
||
|
|
}
|
||
|
|
|
||
|
|
for (i = cnt; i < (int)new_size; i++)
|
||
|
|
new_table[i].Next = i+1;
|
||
|
|
new_table[new_size-1].Next = NIL;
|
||
|
|
|
||
|
|
First = cnt;
|
||
|
|
Hash = new_hash;
|
||
|
|
Table = new_table;
|
||
|
|
Size = new_size;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType> inline int HashTemplateClass<KeyType,ValueType>::Alloc_Entry()
|
||
|
|
{
|
||
|
|
if (First == NIL) // need to re-alloc and re-hash tables
|
||
|
|
Re_Hash();
|
||
|
|
int h = First;
|
||
|
|
First = Table[First].Next;
|
||
|
|
return h;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType> inline HashTemplateClass<KeyType,ValueType>::HashTemplateClass() : Hash(0),Table(0),First(NIL),Size(0)
|
||
|
|
{
|
||
|
|
// Re_Hash();
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class KeyType, class ValueType> inline HashTemplateClass<KeyType,ValueType>::~HashTemplateClass()
|
||
|
|
{
|
||
|
|
if (Hash)
|
||
|
|
delete[] Hash;
|
||
|
|
if (Table)
|
||
|
|
delete[] Table;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Get_Hash_Value specialization for StringClass. This is intended to be used
|
||
|
|
// for filenames, so it takes into account the four characters that come before
|
||
|
|
// the file extension (.xxx - extension expected to be 4 characters).
|
||
|
|
|
||
|
|
template <> inline unsigned int HashTemplateKeyClass<StringClass>::Get_Hash_Value(const StringClass& s)
|
||
|
|
{
|
||
|
|
unsigned int len=s.Get_Length();
|
||
|
|
unsigned char* buffer=(unsigned char*)s.Peek_Buffer();
|
||
|
|
if (len<8) {
|
||
|
|
unsigned int hval=0;
|
||
|
|
for (unsigned int a=0;a<len;++a) {
|
||
|
|
hval+=37*hval+buffer[a];
|
||
|
|
}
|
||
|
|
return hval;
|
||
|
|
}
|
||
|
|
unsigned int hval = *((const unsigned int*)(buffer+len-8));
|
||
|
|
hval = hval + (hval>>5) + (hval>>10) + (hval >> 20);
|
||
|
|
return hval;
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
#endif
|