Main Page Modules Namespace List Class Hierarchy Alphabetical List Compound List File List Namespace Members Compound Members File Members Related Pages

# deHash.hpp

Go to the documentation of this file.

    00001 ///////////////////////////////////////////////////////////////////////////////
    00002 /// @file deHash.hpp
    00003 ///
    00004 /// @brief String, integer, and functor based hash tables
    00005 ///
    00006 /// @author Assassin
    00007 ///
    00008 /// This file is the intellectual property of Novus Delta, LLC.. Usage of the
    00009 /// contents of this file is subject to the Destiny3D Member License which
    00010 /// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
    00011 ///
    00012 /// This file is distributed "AS IS" without warranty of any kind.  Novus
    00013 /// Delta, LLC. does not guarantee the fitness of the contents of this file
    00014 /// for any particular purpose.
    00015 ///
    00016 /// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
    00017 ///
    00018 /// <hr>
    00019 ///                                 Change History
    00020 /// <hr>
    00021 ///
    00022 /// @date Jan 2002
    00023 /// @author Assassin
    00024 /// @remarks Creation
    00025 ///
    00026 ///////////////////////////////////////////////////////////////////////////////
    00027
    00028 #ifndef DEHASH_HPP
    00029 #define DEHASH_HPP
    00030
    00031 #include "deGlobalTypes.hpp"
    00032 #include "deArray.hpp"
    00033
    00034 #ifndef NULL
    00035 #define NULL (0)
    00036 #endif
    00037
    00038 #pragma warning (disable : 4710)
    00039
    00040 template <class T>
    00041 class deTHashString
    00042 {
    00043 public:
    00044     class HashNode
    00045     {
    00046     public:
    00047         char * m_IndexString;
    00048         T m_Data;
    00049         HashNode *Prev, *Next;
    00050         deTHashString * m_Hash;
    00051
    00052         HashNode(const T & data, const char * s, HashNode * NextNode, deTHashString * Hash)
    00053             : m_Data(data)
    00054         {
    00055             if (s)
    00056             {
    00057                 m_IndexString = new char[strlen(s)+1];
    00058                 strcpy(m_IndexString, s);
    00059             }
    00060             else
    00061                 m_IndexString = NULL;
    00062             Next = NextNode;
    00063             Prev = NULL;
    00064             m_Hash = Hash;
    00065             if (NextNode)
    00066                 NextNode->Prev = this;
    00067         }
    00068         ~HashNode()
    00069         {
    00070             if (m_IndexString)
    00071                 delete[] m_IndexString;
    00072             if (Prev)
    00073                 Prev->Next = Next;
    00074             if (Next)
    00075                 Next->Prev = Prev;
    00076         }
    00077     };
    00078
    00079     deTHashString(DWORD size)
    00080     : m_Elements(max(size,1)), m_HashSize(max(size,1))
    00081     {
    00082         DWORD i;
    00083         m_ElementNum = 0;
    00084         for (i = 0; i < m_HashSize; i++)
    00085             m_Elements[i] = NULL;
    00086     }
    00087 /*  deTHashString(const deTHashString <T> & ref)
    00088     : m_HashSize(ref.m_HashSize)
    00089     {
    00090         m_ElementNum = 0;
    00091     }
    00092 */  ~deTHashString()
    00093     {
    00094         RemoveAllElements();
    00095     }
    00096
    00097     DWORD Length()
    00098     {
    00099         return m_ElementNum;
    00100     }
    00101     T * AddElement(const T & element, const char * string)
    00102     {
    00103         DWORD index = HashString(string);
    00104         HashNode * Node = new HashNode(element, string, m_Elements[index], this);
    00105         if (!Node)
    00106             return NULL;
    00107         m_Elements[index] = Node;
    00108         m_ElementNum++;
    00109         return &(Node->m_Data);
    00110     }
    00111     T * FindElement(const char * string, DWORD * Index = NULL) const
    00112     {
    00113         HashNode * p;
    00114         return FindElement(string, p, Index);
    00115     }
    00116     deBoolean RemoveElement(const char * string)
    00117     {
    00118         HashNode * Node;
    00119         DWORD index;
    00120         FindElement(string, Node, &index);
    00121         if (Node && Node->m_Hash == this)
    00122         {
    00123             if (Node->Prev == NULL)
    00124                 m_Elements[index] = Node->Next;
    00125             else
    00126                 Node->Prev->Next = Node->Next;
    00127             delete Node;
    00128             m_ElementNum--;
    00129             return deTRUE;
    00130         }
    00131         return deFALSE;
    00132     }
    00133     void GetAllElements(deTArray <T*> &array)
    00134     {
    00135         DWORD i, j=0;
    00136         HashNode * Node;
    00137         array.Resize(m_ElementNum);
    00138         for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
    00139         {
    00140             Node = m_Elements[i];
    00141             while (Node)
    00142             {
    00143                 array[j] = &(Node->m_Data);
    00144                 j++;
    00145                 Node = Node->Next;
    00146             }
    00147         }
    00148     }
    00149     void RemoveAllElements()
    00150     {
    00151         DWORD i, j=0;
    00152         HashNode *Node, *Node2;
    00153         for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
    00154         {
    00155             Node = m_Elements[i];
    00156             while (Node)
    00157             {
    00158                 Node2 = Node->Next;
    00159                 delete Node;
    00160                 Node = Node2;
    00161                 j++;
    00162             }
    00163             m_Elements[i] = NULL;
    00164         }
    00165         m_ElementNum = 0;
    00166     }
    00167     void operator=(const deTHashString <T> &ref)
    00168     {
    00169         throw "don't copy me";
    00170         if (&ref == NULL)
    00171             return;
    00172     }
    00173     T * operator[](const char * string)
    00174     {
    00175         HashNode * p;
    00176         return FindElement(string, p, NULL);
    00177     }
    00178
    00179 private:
    00180     T * FindElement(const char * string, HashNode *&Node, DWORD * Index) const
    00181     {
    00182         DWORD index = HashString(string);
    00183         if (Index)
    00184             *Index = index;
    00185         Node = m_Elements[index];
    00186         while (Node)
    00187         {
    00188             if (!strcmp(Node->m_IndexString, string))
    00189                 return &(Node->m_Data);
    00190             Node = Node->Next;
    00191         }
    00192         return NULL;
    00193     }
    00194     DWORD HashString(const char * string) const
    00195     {
    00196         DWORD i, length;
    00197         if (string == NULL)
    00198             return 0;
    00199         for (i = 0; string[i]; i++);
    00200         length = (i > 255) ? 255 : i;
    00201         unsigned long * dword = (unsigned long *)string, total = 0;
    00202         for (i = 0; i < length/4; i++)
    00203         {
    00204             total += *dword;
    00205             dword++;
    00206         }
    00207         i *= 4;
    00208         for (; i < length; i++)
    00209             total += string[i];
    00210         return total % m_HashSize;
    00211     }
    00212     DWORD m_ElementNum;
    00213     const DWORD m_HashSize;
    00214     deTArray <HashNode*> m_Elements;
    00215 };
    00216
    00217 template <class T>
    00218 class deTHashInt
    00219 {
    00220 private:
    00221     class HashNode
    00222     {
    00223     public:
    00224         T m_Data;
    00225         DWORD m_IndexInt;
    00226         HashNode *Prev, *Next;
    00227     #ifdef _DEBUG
    00228         deTHashInt * m_Hash;
    00229
    00230         HashNode(const T & data, DWORD i, HashNode * NextNode, deTHashInt * Hash)
    00231             : m_Data(data)
    00232         {
    00233             m_IndexInt = i;
    00234             Next = NextNode;
    00235             Prev = NULL;
    00236             m_Hash = Hash;
    00237             if (NextNode)
    00238                 NextNode->Prev = this;
    00239         }
    00240     #else
    00241         HashNode(const T & data, DWORD i, HashNode * NextNode)
    00242         {
    00243             m_Data = data;
    00244             m_IndexInt = i;
    00245             Next = NextNode;
    00246             Prev = NULL;
    00247             if (NextNode)
    00248                 NextNode->Prev = this;
    00249         }
    00250     #endif
    00251         ~HashNode()
    00252         {
    00253             m_IndexInt = 0;
    00254             if (Prev)
    00255                 Prev->Next = Next;
    00256             if (Next)
    00257                 Next->Prev = Prev;
    00258         }
    00259     };
    00260 public:
    00261     class iterator
    00262     {
    00263     private:
    00264         deTHashInt<T>* mHash;
    00265         long mIndex;
    00266         HashNode* mNode;
    00267     protected:
    00268         friend class deTHashInt<T>;
    00269         iterator(deTHashInt<T>* hash, DWORD index, HashNode* node)
    00270             : mHash(hash), mIndex(index), mNode(node) {}
    00271         void operator++()
    00272         {
    00273             mNode = mNode->Next;
    00274             while (mNode == NULL)
    00275             {   ++mIndex;
    00276             if (mIndex >= mHash->m_Elements.size())
    00277                 break;
    00278             mNode = mHash->m_Elements[mIndex];
    00279             }
    00280         }
    00281     public:
    00282         iterator() : mHash(NULL), mIndex(0), mNode(NULL) {}
    00283         iterator(const iterator& ref) : mHash(ref.mHash), mIndex(ref.mIndex), mNode(ref.mNode) {}
    00284         T& operator*() const
    00285         {
    00286             DE_ASSERT (mNode != 0);
    00287             return mNode->m_Data;
    00288         }
    00289         T* operator->() const { return &operator*(); }
    00290         bool operator==(const iterator & other) const
    00291         { return (mIndex == other.mIndex) && (mNode == other.mNode); }
    00292         bool operator!=(const iterator & other) const
    00293         { return (mIndex != other.mIndex) || (mNode != other.mNode); }
    00294     };
    00295
    00296     deTHashInt(DWORD size)
    00297     : m_Elements(max(size,1)), m_HashSize(max(size,1))
    00298     {
    00299         DWORD i;
    00300         m_ElementNum = 0;
    00301         for (i = 0; i < m_HashSize; i++)
    00302             m_Elements[i] = NULL;
    00303     }
    00304 /*  deTHashInt(const deTHashInt <T> & ref)
    00305     : m_HashSize(ref.m_HashSize)
    00306     {
    00307         m_ElementNum = 0;
    00308     }
    00309 */  ~deTHashInt()
    00310     {
    00311         RemoveAllElements();
    00312     }
    00313
    00314     DWORD Length()
    00315     {
    00316         return m_ElementNum;
    00317     }
    00318     T * AddElement(const T & element, DWORD Int)
    00319     {
    00320         DWORD index = HashInt(Int);
    00321         HashNode * Node;
    00322     #ifdef _DEBUG
    00323             Node = new HashNode(element, Int, m_Elements[index], this);
    00324     #else
    00325             Node = new HashNode(element, Int, m_Elements[index]);
    00326     #endif
    00327         if (!Node)
    00328             return NULL;
    00329         m_Elements[index] = Node;
    00330         m_ElementNum++;
    00331         return &(Node->m_Data);
    00332     }
    00333     T * FindElement(DWORD Int, DWORD * Index = NULL) const
    00334     {
    00335         HashNode * p;
    00336         return FindElement(Int, p, Index);
    00337     }
    00338     deBoolean RemoveElement(DWORD Int)
    00339     {
    00340         HashNode * Node;
    00341         DWORD index;
    00342         FindElement(Int, Node, &index);
    00343     #ifdef _DEBUG
    00344         if (Node->m_Hash != this)
    00345             return deFALSE;
    00346     #endif
    00347         if (Node)
    00348         {
    00349             if (Node->Prev == NULL)
    00350                 m_Elements[index] = Node->Next;
    00351             else
    00352                 Node->Prev->Next = Node->Next;
    00353             delete Node;
    00354             m_ElementNum--;
    00355             return deTRUE;
    00356         }
    00357         return deFALSE;
    00358     }
    00359     void GetAllElements(deTArray <T*> &array)
    00360     {
    00361         DWORD i, j=0;
    00362         HashNode * Node;
    00363         array.Resize(m_ElementNum);
    00364         for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
    00365         {
    00366             Node = m_Elements[i];
    00367             while (Node)
    00368             {
    00369                 array[j] = &(Node->m_Data);
    00370                 j++;
    00371                 Node = Node->Next;
    00372             }
    00373         }
    00374     }
    00375     void RemoveAllElements()
    00376     {
    00377         DWORD i, j=0;
    00378         HashNode *Node, *Node2;
    00379         for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
    00380         {
    00381             Node = m_Elements[i];
    00382             while (Node)
    00383             {
    00384                 Node2 = Node->Next;
    00385                 delete Node;
    00386                 Node = Node2;
    00387                 j++;
    00388             }
    00389             m_Elements[i] = NULL;
    00390         }
    00391         m_ElementNum = 0;
    00392     }
    00393
    00394     void operator=(const deTHashInt <T> &ref)
    00395     {
    00396         if (&ref || !&ref)
    00397             throw "don't copy me";
    00398     }
    00399     T * operator[](DWORD Int) const
    00400     {
    00401         void * p;
    00402         return FindElement(Int, p, NULL);
    00403     }
    00404
    00405
    00406     iterator find(DWORD key)
    00407     {
    00408         DWORD index = HashInt(key);
    00409         HashNode* Node;
    00410         Node = m_Elements[index];
    00411         while (Node)
    00412         {
    00413             if (Node->m_IndexInt == key)
    00414                 return iterator(this, index, Node);
    00415             Node = Node->Next;
    00416         }
    00417         return end();
    00418     }
    00419     iterator erase(iterator & entry)
    00420     {
    00421         iterator next = entry;
    00422         ++next;
    00423         HashNode* current = entry.mNode;
    00424         if (current->Prev)
    00425             current->Prev->Next = current->Next;
    00426         else
    00427             m_Elements[entry.mIndex] = current->Next;
    00428         if (current->Next)
    00429             current->Next->Prev = current->Prev;
    00430         delete current;
    00431         return next;
    00432     }
    00433     iterator begin()
    00434     {
    00435         iterator first(this, -1, NULL);
    00436         ++first;
    00437         return first;
    00438     }
    00439     iterator end()
    00440     {
    00441         return iterator(this, m_Elements.size(), NULL);
    00442     }
    00443
    00444
    00445 private:
    00446     T * FindElement(DWORD Int, HashNode *&Node, DWORD * Index = NULL) const
    00447     {
    00448         DWORD index = HashInt(Int);
    00449         if (Index)
    00450             *Index = index;
    00451         Node = m_Elements[index];
    00452         while (Node)
    00453         {
    00454             if (Node->m_IndexInt == Int)
    00455                 return &(Node->m_Data);
    00456             Node = Node->Next;
    00457         }
    00458         return NULL;
    00459     }
    00460     DWORD HashInt(DWORD Int) const
    00461     {
    00462         return Int % m_HashSize;
    00463     }
    00464     DWORD m_ElementNum;
    00465     const DWORD m_HashSize;
    00466     deTArray <HashNode*> m_Elements;
    00467     friend class deTHashInt<T>::iterator;
    00468 };
    00469
    00470 template <class T, class K> // T is data stored, K is key
    00471 class deTHashFunctor
    00472 {
    00473 public:
    00474 /*
    00475     class HashExample // for use in a deTHashFunctor object
    00476     {
    00477     u32 m_Value;
    00478     public:
    00479     inline HashExample(u16 index1, u16 index2)
    00480     {
    00481         m_Value = index1 | (index2<<16);
    00482     }
    00483     inline u32 Hash() const
    00484     {
    00485         return m_Value;
    00486     }
    00487     };
    00488 */
    00489     class HashNode
    00490     {
    00491     public:
    00492         T m_Data;
    00493         K m_Key;
    00494         DWORD m_HashValue;
    00495         HashNode *Prev, *Next;
    00496     #ifdef _DEBUG
    00497         deTHashFunctor * m_Hash;
    00498
    00499         HashNode(const T & data, const K& key, DWORD hash, HashNode * NextNode, deTHashFunctor * Hash)
    00500             : m_Data(data), m_Key(key)
    00501         {
    00502             m_HashValue = hash;
    00503             Next = NextNode;
    00504             Prev = NULL;
    00505             m_Hash = Hash;
    00506             if (NextNode)
    00507                 NextNode->Prev = this;
    00508         }
    00509     #else
    00510         HashNode(const T & data, const K& key, DWORD hash, HashNode * NextNode)
    00511             : m_Data(data), m_Key(key)
    00512         {
    00513             m_HashValue = hash;
    00514             Next = NextNode;
    00515             Prev = NULL;
    00516             if (NextNode)
    00517                 NextNode->Prev = this;
    00518         }
    00519     #endif
    00520         ~HashNode()
    00521         {
    00522         #ifdef _DEBUG
    00523             m_HashValue = 0;
    00524         #endif
    00525             if (Prev)
    00526                 Prev->Next = Next;
    00527             if (Next)
    00528                 Next->Prev = Prev;
    00529         }
    00530     };
    00531
    00532     deTHashFunctor(const DWORD size)
    00533     : m_Elements(max(size,1)), m_HashSize(max(size,1))
    00534     {
    00535         DWORD i;
    00536         m_ElementNum = 0;
    00537         for (i = 0; i < m_HashSize; i++)
    00538             m_Elements[i] = NULL;
    00539     }
    00540 /*  deTHashFunctor(const deTHashInt <T> & ref)
    00541     : m_HashSize(ref.m_HashSize)
    00542     {
    00543         m_ElementNum = 0;
    00544     }
    00545 */  ~deTHashFunctor()
    00546     {
    00547         RemoveAllElements();
    00548     }
    00549
    00550     DWORD Length()
    00551     {
    00552         return m_ElementNum;
    00553     }
    00554     T * AddElement(const T & element, const K & key)
    00555     {
    00556         DWORD hash = key.Hash(), index = hash%m_HashSize;
    00557         HashNode * Node;
    00558     #ifdef _DEBUG
    00559             Node = new HashNode(element, key, hash, m_Elements[index], this);
    00560     #else
    00561             Node = new HashNode(element, key, hash, m_Elements[index]);
    00562     #endif
    00563         if (!Node)
    00564             return NULL;
    00565         m_Elements[index] = Node;
    00566         m_ElementNum++;
    00567         return &(Node->m_Data);
    00568     }
    00569     T * FindElement(const K & key, DWORD * Index = NULL) const
    00570     {
    00571         HashNode * p;
    00572         return FindElement(key, p, Index);
    00573     }
    00574     deBoolean RemoveElement(const K & key)
    00575     {
    00576         HashNode * Node;
    00577         DWORD index,hashval;
    00578         FindElement(key, Node, &index, &hashval);
    00579     #ifdef _DEBUG
    00580         if (Node->m_Hash != this)
    00581             return deFALSE;
    00582     #endif
    00583         if (Node)
    00584         {
    00585             if (Node->Prev == NULL)
    00586                 m_Elements[index] = Node->Next;
    00587             else
    00588                 Node->Prev->Next = Node->Next;
    00589             delete Node;
    00590             m_ElementNum--;
    00591             return deTRUE;
    00592         }
    00593         return deFALSE;
    00594     }
    00595     void GetAllElements(deTArray <T*> &array)
    00596     {
    00597         DWORD i, j=0;
    00598         HashNode * Node;
    00599         array.Resize(m_ElementNum);
    00600         for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
    00601         {
    00602             Node = m_Elements[i];
    00603             while (Node)
    00604             {
    00605                 array[j] = &(Node->m_Data);
    00606                 j++;
    00607                 Node = Node->Next;
    00608             }
    00609         }
    00610     }
    00611     void RemoveAllElements()
    00612     {
    00613         DWORD i, j=0;
    00614         HashNode *Node, *Node2;
    00615         for (i = 0; i < m_HashSize && j < m_ElementNum; i++)
    00616         {
    00617             Node = m_Elements[i];
    00618             while (Node)
    00619             {
    00620                 Node2 = Node->Next;
    00621                 delete Node;
    00622                 Node = Node2;
    00623                 j++;
    00624             }
    00625             m_Elements[i] = NULL;
    00626         }
    00627         m_ElementNum = 0;
    00628     }
    00629
    00630     void operator=(const deTHashFunctor <T,K> &ref)
    00631     {
    00632         if (&ref || !&ref)
    00633             throw "don't copy me";
    00634     }
    00635     T * operator[](const K & key)
    00636     {
    00637         void * p;
    00638         return FindElement(key, p, NULL);
    00639     }
    00640
    00641
    00642 private:
    00643     T * FindElement(const K & key, HashNode *&Node, DWORD * Index = NULL, DWORD *HashVal = NULL) const
    00644     {
    00645         DWORD HashValue = key.Hash();
    00646         DWORD index = HashValue % m_HashSize;
    00647         if (Index)
    00648             *Index = index;
    00649         if (HashVal)
    00650             *HashVal = HashValue;
    00651         Node = m_Elements[index];
    00652         while (Node)
    00653         {
    00654             if (Node->m_Key == key)
    00655                 return &(Node->m_Data);
    00656
    00657             Node = Node->Next;
    00658         }
    00659         return NULL;
    00660     }
    00661     DWORD m_ElementNum;
    00662     const DWORD m_HashSize;
    00663     deTArray <HashNode*> m_Elements;
    00664 };
    00665
    00666 //#pragma warning (default : 4710)
    00667
    00668 #endif