## Public API Reference

- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# csutil/hash.h

Go to the documentation of this file.

    00001 /*
    00002     Copyright (C) 2003 by Mat Sutcliffe <oktal@gmx.co.uk>
    00003
    00004     This library is free software; you can redistribute it and/or
    00005     modify it under the terms of the GNU Lesser General Public
    00006     License as published by the Free Software Foundation; either
    00007     version 2 of the License, or (at your option) any later version.
    00008
    00009     This library is distributed in the hope that it will be useful,
    00010     but WITHOUT ANY WARRANTY; without even the implied warranty of
    00011     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    00012     Library General Public License for more details.
    00013
    00014     You should have received a copy of the GNU Library General Public
    00015     License along with this library; if not, write to the Free
    00016     Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
    00017 */
    00018
    00019 #ifndef __CS_UTIL_HASH_H__
    00020 #define __CS_UTIL_HASH_H__
    00021
    00026 #include "csextern.h"
    00027 #include "csutil/array.h"
    00028 #include "csutil/comparator.h"
    00029
    00030
    00040 CS_CRYSTALSPACE_EXPORT unsigned int csHashCompute (char const*);
    00041
    00048 CS_CRYSTALSPACE_EXPORT unsigned int csHashCompute (char const*, size_t length);
    00049
    00054 template <class T>
    00055 class csHashComputer
    00056 {
    00057 public:
    00059   static uint ComputeHash (const T& key)
    00060   {
    00061     return key.GetHash();
    00062   }
    00063 };
    00064
    00069 template <class T>
    00070 class csHashComputerIntegral
    00071 {
    00072 public:
    00074   static uint ComputeHash (const T& key)
    00075   {
    00076     return (uintptr_t)key;
    00077   }
    00078 };
    00079
    00081
    00084 CS_SPECIALIZE_TEMPLATE
    00085 class csHashComputer<void*> : public csHashComputerIntegral<void*> {};
    00086
    00087 CS_SPECIALIZE_TEMPLATE
    00088 class csHashComputer<int> : public csHashComputerIntegral<int> {};
    00089 CS_SPECIALIZE_TEMPLATE
    00090 class csHashComputer<unsigned int> :
    00091   public csHashComputerIntegral<unsigned int> {};
    00092
    00093 CS_SPECIALIZE_TEMPLATE
    00094 class csHashComputer<long> : public csHashComputerIntegral<long> {};
    00095 CS_SPECIALIZE_TEMPLATE
    00096 class csHashComputer<unsigned long> :
    00097   public csHashComputerIntegral<unsigned long> {};
    00098
    00099 #if (CS_LONG_SIZE < 8)
    00100 CS_SPECIALIZE_TEMPLATE
    00101 class csHashComputer<longlong> :
    00102   public csHashComputerIntegral<longlong> {};
    00103 CS_SPECIALIZE_TEMPLATE
    00104 class csHashComputer<ulonglong> :
    00105   public csHashComputerIntegral<ulonglong> {};
    00106 #endif
    00107
    00108 CS_SPECIALIZE_TEMPLATE
    00109 class csHashComputer<float>
    00110 {
    00111 public:
    00113   static uint ComputeHash (float key)
    00114   {
    00115     union
    00116     {
    00117       float f;
    00118       uint u;
    00119     } float2uint;
    00120     float2uint.f = key;
    00121     return float2uint.u;
    00122   }
    00123 };
    00124 CS_SPECIALIZE_TEMPLATE
    00125 class csHashComputer<double>
    00126 {
    00127 public:
    00129   static uint ComputeHash (double key)
    00130   {
    00131     union
    00132     {
    00133       double f;
    00134       uint u;
    00135     } double2uint;
    00136     double2uint.f = key;
    00137     return double2uint.u;
    00138   }
    00139 };
    00141
    00145 template <typename T>
    00146 class csPtrKey
    00147 {
    00148   T* ptr;
    00149 public:
    00150   csPtrKey () : ptr(0) {}
    00151   csPtrKey (T* ptr) : ptr(ptr) {}
    00152   csPtrKey (csPtrKey const& other) : ptr (other.ptr) {}
    00153
    00154   uint GetHash () const { return (uintptr_t)ptr; }
    00155   inline friend bool operator < (const csPtrKey& r1, const csPtrKey& r2)
    00156   { return r1.ptr < r2.ptr; }
    00157   operator T* () const
    00158   { return ptr; }
    00159   T* operator -> () const
    00160   { return ptr; }
    00161   csPtrKey& operator = (csPtrKey const& other)
    00162   { ptr = other.ptr; return *this; }
    00163 };
    00164
    00174 template <class T>
    00175 class csHashComputerString
    00176 {
    00177 public:
    00178   static uint ComputeHash (const T& key)
    00179   {
    00180     return csHashCompute ((const char*)key);
    00181   }
    00182 };
    00183
    00187 CS_SPECIALIZE_TEMPLATE
    00188 class csHashComputer<const char*> : public csHashComputerString<const char*> {};
    00189
    00199 template <class T>
    00200 class csHashComputerStruct
    00201 {
    00202 public:
    00203   static uint ComputeHash (const T& key)
    00204   {
    00205     return csHashCompute ((char*)&key, sizeof (T));
    00206   }
    00207 };
    00208
    00214 class csStrKey
    00215 {
    00216 private:
    00217   char* str;
    00218
    00219 public:
    00220   csStrKey () { str = 0; }
    00221   csStrKey (const char* s) { str = csStrNew (s); }
    00222   csStrKey (const csStrKey& c) { str = csStrNew (c.str); }
    00223   ~csStrKey () { delete[] str; }
    00224   csStrKey& operator=(const csStrKey& o)
    00225   {
    00226     delete[] str; str = csStrNew (o.str);
    00227     return *this;
    00228   }
    00229   operator const char* () const { return str; }
    00230   uint GetHash() const { return csHashCompute (str); }
    00231 };
    00232
    00236 CS_SPECIALIZE_TEMPLATE
    00237 class csComparator<csStrKey, csStrKey> : public csComparatorString<csStrKey> {};
    00238
    00248 template <class T, class K = unsigned int>
    00249 class csHash
    00250 {
    00251 protected:
    00252   struct Element
    00253   {
    00254     const K key;
    00255     T value;
    00256
    00257     Element (const K& key0, const T &value0) : key (key0), value (value0) {}
    00258     Element (const Element &other) : key (other.key), value (other.value) {}
    00259   };
    00260   csArray< csArray<Element> > Elements;
    00261
    00262   size_t Modulo;
    00263
    00264 private:
    00265   size_t InitModulo;
    00266   size_t GrowRate;
    00267   size_t MaxSize;
    00268   size_t Size;
    00269
    00270   void Grow ()
    00271   {
    00272     static const size_t Primes[] =
    00273     {
    00274       53,         97,         193,       389,       769,
    00275       1543,       3079,       6151,      12289,     24593,
    00276       49157,      98317,      196613,    393241,    786433,
    00277       1572869,    3145739,    6291469,   12582917,  25165843,
    00278       50331653,   100663319,  201326611, 402653189, 805306457,
    00279       1610612741, 0
    00280     };
    00281
    00282     const size_t *p;
    00283     size_t elen = Elements.Length ();
    00284     for (p = Primes; *p && *p <= elen; p++) ;
    00285     Modulo = *p;
    00286     CS_ASSERT (Modulo);
    00287
    00288     Elements.SetLength(Modulo, csArray<Element>(0, MIN(Modulo / GrowRate, 8)));
    00289
    00290     for (size_t i = 0; i < elen; i++)
    00291     {
    00292       csArray<Element>& src = Elements[i];
    00293       size_t slen = src.Length ();
    00294       for (size_t j = slen; j > 0; j--)
    00295       {
    00296         const Element& srcElem = src[j - 1];
    00297         csArray<Element>& dst =
    00298           Elements.Get (csHashComputer<K>::ComputeHash (srcElem.key) % Modulo);
    00299         if (&src != &dst)
    00300         {
    00301           dst.Push (srcElem);
    00302           src.DeleteIndex (j - 1);
    00303         }
    00304       }
    00305     }
    00306   }
    00307
    00308 public:
    00323   csHash (size_t size = 23, size_t grow_rate = 5, size_t max_size = 20000)
    00324     : Elements (size), Modulo (size), InitModulo (size),
    00325       GrowRate (MIN (grow_rate, size)), MaxSize (max_size), Size (0)
    00326   {
    00327     Elements.SetLength (size, csArray<Element> (0, MIN (size / GrowRate, 8)));
    00328   }
    00329
    00331   csHash (const csHash<T> &o) : Elements (o.Elements),
    00332     Modulo (o.Modulo), InitModulo (o.InitModulo),
    00333     GrowRate (o.GrowRate), MaxSize (o.MaxSize), Size (o.Size) {}
    00334
    00342   void Put (const K& key, const T &value)
    00343   {
    00344     csArray<Element> &values =
    00345       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    00346     values.Push (Element (key, value));
    00347     Size++;
    00348     if (values.Length () > Elements.Length () / GrowRate
    00349      && Elements.Length () < MaxSize) Grow ();
    00350   }
    00351
    00353   csArray<T> GetAll (const K& key) const
    00354   {
    00355     const csArray<Element> &values =
    00356       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    00357     csArray<T> ret (values.Length () / 2);
    00358     const size_t len = values.Length ();
    00359     for (size_t i = 0; i < len; ++i)
    00360     {
    00361       const Element& v = values[i];
    00362       if (csComparator<K, K>::Compare (v.key, key) == 0)
    00363         ret.Push (v.value);
    00364     }
    00365     return ret;
    00366   }
    00367
    00369   void PutUnique (const K& key, const T &value)
    00370   {
    00371     csArray<Element> &values =
    00372       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    00373     const size_t len = values.Length ();
    00374     for (size_t i = 0; i < len; ++i)
    00375     {
    00376       Element& v = values[i];
    00377       if (csComparator<K, K>::Compare (v.key, key) == 0)
    00378       {
    00379         v.value = value;
    00380         return;
    00381       }
    00382     }
    00383
    00384     values.Push (Element (key, value));
    00385     Size++;
    00386     if (values.Length () > Elements.Length () / GrowRate
    00387      && Elements.Length () < MaxSize) Grow ();
    00388   }
    00389
    00394   CS_DEPRECATED_METHOD void PutFirst (const K& key, const T &value)
    00395   {
    00396     PutUnique(key, value);
    00397   }
    00398
    00400   bool Contains (const K& key) const
    00401   {
    00402     const csArray<Element> &values =
    00403       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    00404     const size_t len = values.Length ();
    00405     for (size_t i = 0; i < len; ++i)
    00406       if (csComparator<K, K>::Compare (values[i].key, key) == 0)
    00407         return true;
    00408     return false;
    00409   }
    00410
    00416   bool In (const K& key) const
    00417   { return Contains(key); }
    00418
    00423   const T* GetElementPointer (const K& key) const
    00424   {
    00425     const csArray<Element> &values =
    00426       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    00427     const size_t len = values.Length ();
    00428     for (size_t i = 0; i < len; ++i)
    00429     {
    00430       const Element& v = values[i];
    00431       if (csComparator<K, K>::Compare (v.key, key) == 0)
    00432         return &v.value;
    00433     }
    00434
    00435     return 0;
    00436   }
    00437
    00442   T* GetElementPointer (const K& key)
    00443   {
    00444     csArray<Element> &values =
    00445       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    00446     const size_t len = values.Length ();
    00447     for (size_t i = 0; i < len; ++i)
    00448     {
    00449       Element& v = values[i];
    00450       if (csComparator<K, K>::Compare (v.key, key) == 0)
    00451         return &v.value;
    00452     }
    00453
    00454     return 0;
    00455   }
    00456
    00461   const T& Get (const K& key, const T& fallback) const
    00462   {
    00463     const csArray<Element> &values =
    00464       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    00465     const size_t len = values.Length ();
    00466     for (size_t i = 0; i < len; ++i)
    00467     {
    00468       const Element& v = values[i];
    00469       if (csComparator<K, K>::Compare (v.key, key) == 0)
    00470         return v.value;
    00471     }
    00472
    00473     return fallback;
    00474   }
    00475
    00480   T& Get (const K& key, T& fallback)
    00481   {
    00482     csArray<Element> &values =
    00483       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    00484     const size_t len = values.Length ();
    00485     for (size_t i = 0; i < len; ++i)
    00486     {
    00487       Element& v = values[i];
    00488       if (csComparator<K, K>::Compare (v.key, key) == 0)
    00489         return v.value;
    00490     }
    00491
    00492     return fallback;
    00493   }
    00494
    00496   void DeleteAll ()
    00497   {
    00498     Elements.SetLength (Modulo = InitModulo);
    00499     size_t elen = Elements.Length ();
    00500     for (size_t i = 0; i < elen; i++)
    00501       Elements[i].Empty ();
    00502     Size = 0;
    00503   }
    00504
    00506   void Empty() { DeleteAll(); }
    00507
    00509   bool DeleteAll (const K& key)
    00510   {
    00511     bool ret = false;
    00512     csArray<Element> &values =
    00513       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    00514     for (size_t i = values.Length (); i > 0; i--)
    00515     {
    00516       const size_t idx = i - 1;
    00517       if (csComparator<K, K>::Compare (values[idx].key, key) == 0)
    00518       {
    00519         values.DeleteIndexFast (idx);
    00520         ret = true;
    00521         Size--;
    00522       }
    00523     }
    00524     return ret;
    00525   }
    00526
    00528   bool Delete (const K& key, const T &value)
    00529   {
    00530     bool ret = false;
    00531     csArray<Element> &values =
    00532       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
    00533     for (size_t i = values.Length (); i > 0; i--)
    00534     {
    00535       const size_t idx = i - 1;
    00536       if ((csComparator<K, K>::Compare (values[idx].key, key) == 0) &&
    00537         (values[idx].value == value))
    00538       {
    00539         values.DeleteIndexFast (idx);
    00540         ret = true;
    00541         Size--;
    00542       }
    00543     }
    00544     return ret;
    00545   }
    00546
    00548   size_t GetSize () const
    00549   {
    00550     return Size;
    00551   }
    00552
    00558   bool IsEmpty() const
    00559   {
    00560     return GetSize() == 0;
    00561   }
    00562
    00564   class Iterator
    00565   {
    00566   private:
    00567     const csHash<T, K>* hash;
    00568     const K key;
    00569     size_t bucket, size, element;
    00570
    00571     void Seek ()
    00572     {
    00573       while ((element < size) &&
    00574         (csComparator<K, K>::Compare (hash->Elements[bucket][element].key,
    00575         key) != 0))
    00576           element++;
    00577     }
    00578
    00579   protected:
    00580     Iterator (const csHash<T, K>* hash0, const K& key0) :
    00581       hash(hash0),
    00582       key(key0),
    00583       bucket(csHashComputer<K>::ComputeHash (key) % hash->Modulo),
    00584       size(hash->Elements[bucket].Length ())
    00585       { Reset (); }
    00586
    00587     friend class csHash<T, K>;
    00588   public:
    00590     Iterator (const Iterator &o) :
    00591       hash (o.hash),
    00592       key(o.key),
    00593       bucket(o.bucket),
    00594       size(o.size),
    00595       element(o.element) {}
    00596
    00598     Iterator& operator=(const Iterator& o)
    00599     {
    00600       hash = o.hash;
    00601       key = o.key;
    00602       bucket = o.bucket;
    00603       size = o.size;
    00604       element = o.element;
    00605       return *this;
    00606     }
    00607
    00609     bool HasNext () const
    00610     {
    00611       return element < size;
    00612     }
    00613
    00615     const T& Next ()
    00616     {
    00617       const T &ret = hash->Elements[bucket][element].value;
    00618       element++;
    00619       Seek ();
    00620       return ret;
    00621     }
    00622
    00624     void Reset () { element = 0; Seek (); }
    00625   };
    00626   friend class Iterator;
    00627
    00629   class GlobalIterator
    00630   {
    00631   private:
    00632     const csHash<T, K> *hash;
    00633     size_t bucket, size, element;
    00634
    00635     void Zero () { bucket = element = 0; }
    00636     void Init () { size = hash->Elements[bucket].Length (); }
    00637
    00638     void FindItem ()
    00639     {
    00640       if (element >= size)
    00641       {
    00642         while (++bucket < hash->Elements.Length ())
    00643         {
    00644           Init ();
    00645           if (size != 0)
    00646           {
    00647             element = 0;
    00648             break;
    00649           }
    00650         }
    00651       }
    00652     }
    00653
    00654   protected:
    00655     GlobalIterator (const csHash<T, K> *hash0) : hash (hash0)
    00656     {
    00657       Zero ();
    00658       Init ();
    00659       FindItem ();
    00660     }
    00661
    00662     friend class csHash<T, K>;
    00663   public:
    00665     GlobalIterator (const Iterator &o) :
    00666       hash (o.hash),
    00667       bucket (o.bucket),
    00668       size (o.size),
    00669       element (o.element) {}
    00670
    00672     GlobalIterator& operator=(const GlobalIterator& o)
    00673     {
    00674       hash = o.hash;
    00675       bucket = o.bucket;
    00676       size = o.size;
    00677       element = o.element;
    00678       return *this;
    00679     }
    00680
    00682     bool HasNext () const
    00683     {
    00684       if (hash->Elements.Length () == 0) return false;
    00685       return element < size || bucket < hash->Elements.Length ();
    00686     }
    00687
    00689     void Advance ()
    00690     {
    00691       element++;
    00692       FindItem ();
    00693     }
    00694
    00696     const T& NextNoAdvance ()
    00697     {
    00698       return hash->Elements[bucket][element].value;
    00699     }
    00700
    00702     const T& Next ()
    00703     {
    00704       const T &ret = NextNoAdvance ();
    00705       Advance ();
    00706       return ret;
    00707     }
    00708
    00710     const T& NextNoAdvance (K &key)
    00711     {
    00712       key = hash->Elements[bucket][element].key;
    00713       return NextNoAdvance ();
    00714     }
    00715
    00717     const T& Next (K &key)
    00718     {
    00719       key = hash->Elements[bucket][element].key;
    00720       return Next ();
    00721     }
    00722
    00724     void Reset () { Zero (); Init (); FindItem (); }
    00725   };
    00726   friend class GlobalIterator;
    00727
    00730   void DeleteElement (GlobalIterator& iterator)
    00731   {
    00732     Elements[iterator.bucket].DeleteIndex(iterator.element);
    00733     Size--;
    00734     iterator.size--;
    00735     iterator.FindItem ();
    00736   }
    00737
    00744   Iterator GetIterator (const K& key) const
    00745   {
    00746     return Iterator (this, key);
    00747   }
    00748
    00754   GlobalIterator GetIterator () const
    00755   {
    00756     return GlobalIterator (this);
    00757   }
    00758 };
    00759
    00762 #endif