/* ** 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 . */ /* $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 #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 HashTableClass; // typedef HashNodeClass HashTableNodeClass; // or if using a UserClass // typedef HashListClass HashTableClass; // typedef HashNodeClass HashTableNodeClass; template class HashNodeClass; template class HashNodeFriendClass; template 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 HashNodeClass : public DataNode *>, public U { public: // Creation when key and record are known. HashNodeClass(T record, unsigned key) : Flags(0), Record(record), Key(key) { DataNode *>::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 *>::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 *Next() { return((HashNodeClass *) DataNode *>::Next()); } HashNodeClass *Prev() { return((HashNodeClass *) DataNode *>::Prev()); } // User may use these if he desires not to have to check for valid. HashNodeClass *Next_Valid() { HashNodeClass *next = Next(); if (next && next->Is_Valid()) { return(next); } return(NULL); } HashNodeClass *Prev_Valid() { HashNodeClass *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 *>::Unlink(); } friend class HashNodeFriendClass; }; //////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////// // 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 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 HashNodeFriendClass { protected: void Set_In_List(HashNodeClass *ptr) {ptr->Flag.InList = true; ptr->Flag.NewInList = true;} void Clear_In_List(HashNodeClass *ptr) {ptr->Flag.InList = false; ptr->Flag.NewInList = false;} bool Is_First(HashNodeClass *ptr) {return(ptr->Flag.FirstInTable);} bool Is_Last(HashNodeClass *ptr) {return(ptr->Flag.LastInTable); } void Set_First(HashNodeClass *ptr) {ptr->Flag.FirstInTable = true; } void Set_Last(HashNodeClass *ptr) {ptr->Flag.LastInTable = true; } void Clear_First(HashNodeClass *ptr) {ptr->Flag.FirstInTable = false;} void Clear_Last(HashNodeClass *ptr) {ptr->Flag.LastInTable = false; } void Set_List_Created(HashNodeClass *ptr) {ptr->Flag.ListCreated = true; } void Clear_List_Created(HashNodeClass *ptr) {ptr->Flag.ListCreated = false; } bool Is_List_Created(HashNodeClass *ptr) {return(ptr->Flag.ListCreated);} void Unlink(HashNodeClass *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 HashListClass : protected HashNodeFriendClass { 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 *First() { return((HashNodeClass *)List.First()); } HashNodeClass *First_Valid() { return((HashNodeClass *)List.First_Valid()); } HashNodeClass *Last() { return((HashNodeClass *)List.Last()); } HashNodeClass *Last_Valid() { return((HashNodeClass *)List.Last_Valid()); } // Add a record to hash creating new HashNodeClass. HashNodeClass *Add(T record, unsigned key); // Add an existing node not in a list to this list. // This allows closer behavior to List class. HashNodeClass *Add(HashNodeClass *node); // Search for record based off key in hash table. HashNodeClass *Find(unsigned key); // Use this remove if you know the node * already. It is quicker. void Remove(HashNodeClass *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 *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 *> 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 *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 HashNodeClass *HashListClass::Add(HashNodeClass *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 *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 HashNodeClass *HashListClass::Add(T record, unsigned key) { // Create new node so we can add our record. HashNodeClass *node = new HashNodeClass(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 HashNodeClass *HashListClass::Find(unsigned key) { int hashidx = Hash_Value(key); assert(hashidx < NumHashValues); HashNodeClass *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 *node - node to remove. * * * * OUTPUT: * * * * WARNINGS: * * * * HISTORY: * * 06/02/1999 SKB : Created. * * 01/19/2000 SKB : Remove the node with Unlink. * *=============================================================================================*/ template void HashListClass::Remove(HashNodeClass *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 bool HashListClass::Remove(unsigned key) { int hashidx = Hash_Value(key); assert(hashidx < NumHashValues); HashNodeClass *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 void HashListClass::Move_To(HashListClass *newlist) { HashNodeClass *node = First_Valid(); while (node) { HashNodeClass *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