tiberium/CnC_Renegade
Archived
2
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
This repository has been archived on 2025-02-27. You can view files and clone it, but cannot push or open issues or pull requests.
CnC_Renegade/Code/wwlib/hashlist.h

652 lines
No EOL
27 KiB
C++
Raw Permalink Blame History

/*
** 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/>.
*/
/* $Header: /Commando/Code/wwlib/hashlist.h 13 4/30/01 3:05p Joe_b $ */
/***********************************************************************************************
*** C O N F I D E N T I A L --- W E S T W O O D S T U D I O S ***
***********************************************************************************************
* *
* Project Name : G *
* *
* $Archive:: /Commando/Code/wwlib/hashlist.h $*
* *
* Creator::Scott K. Bowen - 5/4/99 *
* *
* $Author:: Joe_b $*
* *
* $Modtime:: 4/30/01 2:41p $*
* *
* $Revision:: 13 $*
* *
*---------------------------------------------------------------------------------------------*
* Functions: *
* HashListClass::Find -- Find record in hash table. *
* HashListClass::Remove -- Remove record from hash table. *
* HashListClass::Add -- Add record to hash list. *
* HashListClass::Add -- Add record to list, list creates node for user. *
* HashListClass::Move_To -- Move nodes from one list to another. *
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
#if defined(_MSC_VER)
#pragma once
#endif
#ifndef HASHLIST_H
#define HASHLIST_H
#pragma warning (push)
#pragma warning (disable: 4786)
#include "listnode.h"
#include <memory.h>
#ifndef NULL
#define NULL (0L)
#endif
#define A_LARGE_PRIME_NUMBER 257
// HashListClass<> and HashNodeClass<>:
// The purpose of these templates is to allow a user to insert records into
// a hash table that also contains a double linked list that includes every
// record in the hash table. The functionality of the hash list mirrors
// very closely that of the DataNode<> and List<> templates. The differences
// between them are:
// -User calls Add(?) to add to list instead of Add_Head() or others.
// -A key must be set to hash off of.
//
// Additional features of the HashList<> over List<> are:
// -Quick searching as long as key's are well hashed..
// -Node can inherit user class so additional data can be put in node.
// For example a timestamp to be set by user. Default is
// HashDefaluatUserClass that has no data.
// -If class T is actually a class (not a pointer), user may get a ptr
// to class with Get_Ptr() instead of Get() that returns an INSTANCE
// of the class.
// -Flags to tell user if record was just created or record was just put
// into a list (user must clear flags if desired.)
// -HashListClass<> can create and destroy nodes so that the nodes do not
// need to be put as members in classes. This allows an object to be
// put into an infinite (subject to memory constraints) lists.
// -User may specify number of hash node slots (default is A_LARGE_PRIME_NUMBER).
// You can typedef these templates with the the following:
// typedef HashListClass<TestHashClass *> HashTableClass;
// typedef HashNodeClass<TestHashClass *> HashTableNodeClass;
// or if using a UserClass
// typedef HashListClass<TestHashClass *, 4, UserClass> HashTableClass;
// typedef HashNodeClass<TestHashClass *, UserClass> HashTableNodeClass;
template<class T, class U> class HashNodeClass;
template<class T, class U> class HashNodeFriendClass;
template<class T, class U, int NumHashValues> class HashListClass;
////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////
// This is a default class that is stored in HashNodeClass. It's purpose is
// to allow the user to override it with his/her own class so that additional
// data may be stored in the node about the object.
// Since the object might be in various lists, this data is specific to
// the list that it in.
class HashDefaultUserClass {};
////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////
template<class T, class U = class HashDefaultUserClass>
class HashNodeClass : public DataNode<HashNodeClass<T,U> *>, public U
{
public:
// Creation when key and record are known.
HashNodeClass(T record, unsigned key) :
Flags(0),
Record(record),
Key(key)
{
DataNode<HashNodeClass<T,U> *>::Set(this);
Flag.NewRecord = true;
Flag.KeySet = true;
}
// Creation when key and record are to be set later.
// node may not be put into list until the key is set.
HashNodeClass() :
Flags(0),
Key(-1)
{
DataNode<HashNodeClass<T,U> *>::Set(this);
Flag.NewRecord = true;
}
virtual ~HashNodeClass() {
// Assert is raised when user tries to delete HashNodeClass still in a list
// NOTE: This might be raised because user expected node to clean
// itself up when deleted. Currently, this feature is not available
// because it would require an additional pointer to the HashListClass
// that the node is a member of.
assert(!Flag.InList);
}
// Get next and prev record given a node.
// A node may be retrieved from: HashListClass::Find();
HashNodeClass<T,U> *Next() {
return((HashNodeClass<T,U> *) DataNode<HashNodeClass<T,U> *>::Next());
}
HashNodeClass<T,U> *Prev() {
return((HashNodeClass<T,U> *) DataNode<HashNodeClass<T,U> *>::Prev());
}
// User may use these if he desires not to have to check for valid.
HashNodeClass<T,U> *Next_Valid() {
HashNodeClass<T,U> *next = Next();
if (next && next->Is_Valid()) {
return(next);
}
return(NULL);
}
HashNodeClass<T,U> *Prev_Valid() {
HashNodeClass<T,U> *prev = Prev();
if (prev && prev->Is_Valid()) {
return(prev);
}
return(NULL);
}
// Get record that is in hash table.
T Get_Record() {return(Record);}
T Get_Record_Ptr() {return(&Record);}
// Overload DataNode::Get() to get the record we are pointing to so
// that it behaves how people expect List to operate.
// To Get HashNodeClass - it is this.
T Get() {return(Record);}
// Get a pointer to Record to avoid a copy construction of Record if
// it is an instance of a class that does not want to be copied all
// over the place.
T *Get_Ptr() {return(&Record);}
// To mirror usage of DataNode().
void Set(T record) {Record = record;}
void Set_Key(unsigned key) {
// Can't change key once in a list, we would never find it.
assert(!Flag.InList);
Flag.KeySet = true;
Key = key;
}
// Get key of record for has table.
unsigned Get_Key() {
assert(Flag.KeySet);
return (Key);
}
// Enable user to know if a record has just been added to the list.
// It stays set until user clears it - not required.
int Is_New_Record() {return(Flag.NewRecord);}
void Clear_New_Record() {Flag.NewRecord = false;}
// Each time object gets put into a list NewInList is set.
// Stays set until user clears - not required.
int Is_New_In_List() {return(Flag.NewInList);}
void Clear_New_In_List() {Flag.NewInList = false;}
bool Is_In_List() {return(Flag.InList);}
bool Is_Key_Set() {return(Flag.KeySet);}
protected:
// Record that we are keeping in hash table.
// This is commonly a pointer to the actual record.
T Record;
// Key that user gives to identify record.
// WARNING: Duplicate keys are undefined behavior.
unsigned Key;
// Unioned flags so Flags can be initialized to 0.
union {
struct {
// When record collides in hash list, these ?InTable
// tell when to stop looking for object in hash entry.
unsigned FirstInTable:1;
unsigned LastInTable:1;
// This is set when record is first created. It is up to user
// to clear if he uses flag.
unsigned NewRecord:1;
// This is set when record is first put in list. It is up to user
// to clear if he uses flag.
unsigned NewInList:1;
// Certain functions may not happen if node is InList (in hash table)
// These include delete, Set_Key(), and possibly others.
unsigned InList:1;
// This is set so HashListClass knows if it should delete the
// node when removed from it's list.
unsigned ListCreated:1;
// Make sure someone does not insert a node into a list
// without setting it's key.
unsigned KeySet:1;
} Flag;
unsigned Flags;
};
private:
// Not something the casual user can call.
void Unlink(void) {
DataNode<HashNodeClass<T,U> *>::Unlink();
}
friend class HashNodeFriendClass<T,U>;
};
////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////
// This class is created so that HashListClass can access HashNodeClass.
// HashListClass cannot access directly because it is impossible
// (I could not figure out how) to tell HashNodeClass to be a friend
// to all creations of HashListClass<T,N> since HashNodeClass
// does not need the NumHashValues parameter.
#pragma warning(push)
#pragma warning(disable : 4786) // identifier was truncated to 255 chars in debug information.
template<class T, class U>
class HashNodeFriendClass
{
protected:
void Set_In_List(HashNodeClass<T,U> *ptr) {ptr->Flag.InList = true; ptr->Flag.NewInList = true;}
void Clear_In_List(HashNodeClass<T,U> *ptr) {ptr->Flag.InList = false; ptr->Flag.NewInList = false;}
bool Is_First(HashNodeClass<T,U> *ptr) {return(ptr->Flag.FirstInTable);}
bool Is_Last(HashNodeClass<T,U> *ptr) {return(ptr->Flag.LastInTable); }
void Set_First(HashNodeClass<T,U> *ptr) {ptr->Flag.FirstInTable = true; }
void Set_Last(HashNodeClass<T,U> *ptr) {ptr->Flag.LastInTable = true; }
void Clear_First(HashNodeClass<T,U> *ptr) {ptr->Flag.FirstInTable = false;}
void Clear_Last(HashNodeClass<T,U> *ptr) {ptr->Flag.LastInTable = false; }
void Set_List_Created(HashNodeClass<T,U> *ptr) {ptr->Flag.ListCreated = true; }
void Clear_List_Created(HashNodeClass<T,U> *ptr) {ptr->Flag.ListCreated = false; }
bool Is_List_Created(HashNodeClass<T,U> *ptr) {return(ptr->Flag.ListCreated);}
void Unlink(HashNodeClass<T,U> *ptr) {ptr->Unlink();}
};
#pragma warning(pop)
// The sole purpose of using NumHashValues as a template is to make it easier to
// view in a debugger. If it were an allocated array of pointers, the debugger does
// not easily show each element in the array.
template<class T, class U = class HashDefaultUserClass, int NumHashValues = A_LARGE_PRIME_NUMBER>
class HashListClass : protected HashNodeFriendClass<T,U>
{
public:
// Creation and destruction.
HashListClass() :
List(),NumRecords(0), UsedValues(0)
{
memset(HashTable, 0, sizeof(HashTable));
}
~HashListClass() {Delete();}
// Get first node in list so user can itterate through it.
// CAUTION: Do not destroy pointer returned or itterated though -
// you must call the Remove function on it.
// An assert() will come up if you try.
HashNodeClass<T,U> *First() {
return((HashNodeClass<T,U> *)List.First());
}
HashNodeClass<T,U> *First_Valid() {
return((HashNodeClass<T,U> *)List.First_Valid());
}
HashNodeClass<T,U> *Last() {
return((HashNodeClass<T,U> *)List.Last());
}
HashNodeClass<T,U> *Last_Valid() {
return((HashNodeClass<T,U> *)List.Last_Valid());
}
// Add a record to hash creating new HashNodeClass.
HashNodeClass<T,U> *Add(T record, unsigned key);
// Add an existing node not in a list to this list.
// This allows closer behavior to List class.
HashNodeClass<T,U> *Add(HashNodeClass<T,U> *node);
// Search for record based off key in hash table.
HashNodeClass<T,U> *Find(unsigned key);
// Use this remove if you know the node * already. It is quicker.
void Remove(HashNodeClass<T,U> *node);
// Use this remove if you need to do a find to get the node.
// OK if key does not exist in table.
bool Remove(unsigned key);
// Removes all nodes in list.
void Delete(void) {while (First()->Is_Valid()) Remove(First());}
// Move contents of one list to another (this becomes empty).
void Move_To(HashListClass<T,U> *newlist);
// So we always do it the same way.
unsigned Hash_Value(unsigned key) {
return(unsigned)(key % NumHashValues);
}
// Total number of records in hash table.
int Num_Records() {
return(NumRecords);
}
// how many hash values are used.
// The closer this number is to NumRecords, the
// better hashing going on.
int Num_Used_Values() {
return(UsedValues);
}
protected:
// This list can be walked from start to end of all objects in the list.
// User can use Get_First() to get first (valid) record in linked list.
List<DataNode<T> *> List;
// Points to first record in List that has the right 'value'.
// Must check LaastInTable to see if end of records in has list.
HashNodeClass<T,U> *HashTable[NumHashValues];
// Number of records we have in class.
int NumRecords;
int UsedValues;
};
////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////
/***********************************************************************************************
* HashListClass::Add -- Add record to hash list. *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 05/26/1999 SKB : Created. *
*=============================================================================================*/
template <class T, class U, int NumHashValues>
HashNodeClass<T,U> *HashListClass<T, U, NumHashValues>::Add(HashNodeClass<T,U> *node)
{
// Get our index into the hash table.
int hashidx = Hash_Value(node->Get_Key());
assert(hashidx < NumHashValues);
// Tell system we are being put in the list (and make sure we weren't already in one).
assert(!node->Is_In_List());
Set_In_List(node);
// Get first hit in table.
HashNodeClass<T,U> *first = HashTable[hashidx];
if (first) {
// This will add the new node right after the first node in the list.
first->Link(node);
// If we are the first one to collide, then we will be at end of list.
// otherwise, we are at the end.
if (Is_Last(first)) {
Clear_Last(first);
Set_Last(node);
}
} else {
// We are first hit at hash index. Put ourselves at start of
List.Add_Head(node);
Set_First(node);
Set_Last(node);
HashTable[hashidx] = node;
UsedValues++;
}
NumRecords++;
return (node);
}
/***********************************************************************************************
* HashListClass::Add -- Add record to list, list creates node for user. *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 06/03/1999 SKB : Created. *
*=============================================================================================*/
template <class T, class U, int NumHashValues>
HashNodeClass<T,U> *HashListClass<T, U, NumHashValues>::Add(T record, unsigned key)
{
// Create new node so we can add our record.
HashNodeClass<T,U> *node = new HashNodeClass<T,U>(record, key);
Set_List_Created(node);
// Now let the other add do all the work.
Add(node);
return (node);
}
/***********************************************************************************************
* HashListClass::Find -- Find record in hash table. *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 05/26/1999 SKB : Created. *
*=============================================================================================*/
template <class T, class U, int NumHashValues>
HashNodeClass<T,U> *HashListClass<T, U, NumHashValues>::Find(unsigned key)
{
int hashidx = Hash_Value(key);
assert(hashidx < NumHashValues);
HashNodeClass<T,U> *cur = HashTable[hashidx];
if (cur) for(;;) {
// Have we found our match?
if (cur->Get_Key() == key) {
return(cur);
}
// We have to find record before the end of the list.
if (Is_Last(cur)) {
break;
}
// Continue on because we appear to have some collisions.
cur = cur->Next();
// The end of a list should always be marked with Is_Last().
assert(cur);
assert(cur->Is_Valid());
}
return(NULL);
}
/***********************************************************************************************
* HashListClass::Remove_Node -- Remove node from hash table. *
* Protected function for usage by Remove() routines. *
* *
* INPUT: *
* HashNodeClass<T,U> *node - node to remove. *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 06/02/1999 SKB : Created. *
* 01/19/2000 SKB : Remove the node with Unlink. *
*=============================================================================================*/
template <class T, class U, int NumHashValues>
void HashListClass<T, U, NumHashValues>::Remove(HashNodeClass<T,U> *node)
{
assert(node);
assert(node->Is_In_List());
// See if entry is first in list for hash value.
if (Is_First(node)) {
int hashidx = Hash_Value(node->Get_Key());
assert(HashTable[hashidx]);
// SKB: 2/20/01 - clear incase inserted in new list later.
Clear_First(node);
// is it only one in hash index?
if (Is_Last(node)) {
// SKB: 2/20/01 - clear incase inserted in new list later.
Clear_Last(node);
HashTable[hashidx] = NULL;
UsedValues--;
} else {
HashTable[hashidx] = node->Next_Valid();
Set_First(HashTable[hashidx]);
}
} else if (Is_Last(node)) {
// SKB: 2/20/01 - clear incase inserted in new list later.
Clear_Last(node);
// There is one before us because it failed above.
Set_Last(node->Prev());
}
// All done with you. Set flag to avoid assert.
Clear_In_List(node);
// Delete node if it was created by the this class instead of by the user.
if (Is_List_Created(node)) {
delete node;
} else {
// Remove it from the link list at least so it can be put in another.
Unlink(node);
}
NumRecords--;
}
/***********************************************************************************************
* HashListClass::Remove -- Remove record from hash table. *
* *
* INPUT: *
* unsigned key - key to find node by. *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 05/26/1999 SKB : Created. *
*=============================================================================================*/
template <class T, class U, int NumHashValues>
bool HashListClass<T, U, NumHashValues>::Remove(unsigned key)
{
int hashidx = Hash_Value(key);
assert(hashidx < NumHashValues);
HashNodeClass<T,U> *node = Find(key);
if (node) {
Remove(node);
return(true);
}
return(false);
}
/***********************************************************************************************
* HashListClass::Move_To -- Move nodes from one list to another. *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 06/04/1999 SKB : Created. *
*=============================================================================================*/
template <class T, class U, int NumHashValues>
void HashListClass<T, U, NumHashValues>::Move_To(HashListClass<T,U> *newlist)
{
HashNodeClass<T,U> *node = First_Valid();
while (node) {
HashNodeClass<T,U> *next = node->Next_Valid();
// If list created node, clear that fact for a moment so it
// will not get deleted in the remove.
if (Is_List_Created(node)) {
Clear_List_Created(node);
Remove(node);
newlist->Add(node);
Set_List_Created(node);
} else {
Remove(node);
newlist->Add(node);
}
node = next;
}
}
#pragma warning (pop)
#endif // HASHLIST_H
Reference in a new issue View git blame Copy permalink