CrystalSpace

Public API Reference

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 #include "csutil/util.h"
00030 
00031 
00041 CS_CRYSTALSPACE_EXPORT unsigned int csHashCompute (char const*);
00042 
00049 CS_CRYSTALSPACE_EXPORT unsigned int csHashCompute (char const*, size_t length);
00050 
00055 template <class T>
00056 class csHashComputer
00057 {
00058 public:
00060   static uint ComputeHash (const T& key)
00061   {
00062     return key.GetHash();
00063   }
00064 };
00065 
00070 template <class T>
00071 class csHashComputerIntegral
00072 {
00073 public:
00075   static uint ComputeHash (const T& key)
00076   {
00077     return (uintptr_t)key;
00078   }
00079 };
00080 
00082 
00085 template<>
00086 class csHashComputer<void*> : public csHashComputerIntegral<void*> {};
00087   
00088 template<>
00089 class csHashComputer<int> : public csHashComputerIntegral<int> {}; 
00090 template<>
00091 class csHashComputer<unsigned int> : 
00092   public csHashComputerIntegral<unsigned int> {}; 
00093     
00094 template<>
00095 class csHashComputer<long> : public csHashComputerIntegral<long> {}; 
00096 template<>
00097 class csHashComputer<unsigned long> : 
00098   public csHashComputerIntegral<unsigned long> {}; 
00099 
00100 #if (CS_LONG_SIZE < 8)    
00101 template<>
00102 class csHashComputer<longlong> : 
00103   public csHashComputerIntegral<longlong> {}; 
00104 template<>
00105 class csHashComputer<ulonglong> : 
00106   public csHashComputerIntegral<ulonglong> {}; 
00107 #endif
00108     
00109 template<>
00110 class csHashComputer<float>
00111 {
00112 public:
00114   static uint ComputeHash (float key)
00115   {
00116     union
00117     {
00118       float f;
00119       uint u;
00120     } float2uint;
00121     float2uint.f = key;
00122     return float2uint.u;
00123   }
00124 };
00125 template<>
00126 class csHashComputer<double>
00127 {
00128 public:
00130   static uint ComputeHash (double key)
00131   {
00132     union
00133     {
00134       double f;
00135       uint u;
00136     } double2uint;
00137     double2uint.f = key;
00138     return double2uint.u;
00139   }
00140 };
00142 
00146 template <typename T>
00147 class csPtrKey
00148 {
00149   T* ptr;
00150 public:
00151   csPtrKey () : ptr(0) {}
00152   csPtrKey (T* ptr) : ptr(ptr) {}
00153   csPtrKey (csPtrKey const& other) : ptr (other.ptr) {}
00154 
00155   uint GetHash () const { return (uintptr_t)ptr; }
00156   inline friend bool operator < (const csPtrKey& r1, const csPtrKey& r2)
00157   { return r1.ptr < r2.ptr; }
00158   operator T* () const
00159   { return ptr; }
00160   T* operator -> () const
00161   { return ptr; }
00162   csPtrKey& operator = (csPtrKey const& other)
00163   { ptr = other.ptr; return *this; }
00164 };
00165 
00175 template <class T>
00176 class csHashComputerString
00177 {
00178 public:
00179   static uint ComputeHash (const T& key)
00180   {
00181     return csHashCompute ((const char*)key);
00182   }
00183 };
00184 
00188 template<>
00189 class csHashComputer<const char*> : public csHashComputerString<const char*> {};
00190 
00200 template <class T>
00201 class csHashComputerStruct
00202 {
00203 public:
00204   static uint ComputeHash (const T& key)
00205   {
00206     return csHashCompute ((char*)&key, sizeof (T));
00207   }
00208 };
00209 
00210 #include "csutil/win32/msvc_deprecated_warn_off.h"
00211 
00217 class CS_DEPRECATED_TYPE_MSG("csString can also be used for hash keys") 
00218   csStrKey
00219 {
00220 private:
00221   char* str;
00222 
00223 public:
00224   csStrKey () { str = 0; }
00225   csStrKey (const char* s) { str = csStrNew (s); }
00226   csStrKey (const csStrKey& c) { str = csStrNew (c.str); }
00227   ~csStrKey () { delete[] str; }
00228   csStrKey& operator=(const csStrKey& o)
00229   {
00230     delete[] str; str = csStrNew (o.str);
00231     return *this;
00232   }
00233   operator const char* () const { return str; }
00234   uint GetHash() const { return csHashCompute (str); }
00235 };
00236 
00240 template<>
00241 class csComparator<csStrKey, csStrKey> : public csComparatorString<csStrKey> {};
00242 
00243 #include "csutil/win32/msvc_deprecated_warn_on.h"
00244 
00254 template <class T, class K = unsigned int, 
00255   class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc> 
00256 class csHash
00257 {
00258 protected:
00259   struct Element
00260   {
00261     const K key;
00262     T value;
00263 
00264     Element (const K& key0, const T &value0) : key (key0), value (value0) {}
00265     Element (const Element &other) : key (other.key), value (other.value) {}
00266   };
00267   typedef csArray<Element, csArrayElementHandler<Element>,
00268     ArrayMemoryAlloc> ElementArray;
00269   csArray<ElementArray, csArrayElementHandler<ElementArray>,
00270     ArrayMemoryAlloc> Elements;
00271 
00272   size_t Modulo;
00273 
00274 private:
00275   size_t InitModulo;
00276   size_t GrowRate;
00277   size_t MaxSize;
00278   size_t Size;
00279 
00280   void Grow ()
00281   {
00282     static const size_t Primes[] =
00283     {
00284       53,         97,         193,       389,       769, 
00285       1543,       3079,       6151,      12289,     24593,
00286       49157,      98317,      196613,    393241,    786433,
00287       1572869,    3145739,    6291469,   12582917,  25165843,
00288       50331653,   100663319,  201326611, 402653189, 805306457,
00289       1610612741, 0
00290     };
00291 
00292     const size_t *p;
00293     size_t elen = Elements.Length ();
00294     for (p = Primes; *p && *p <= elen; p++) ;
00295     Modulo = *p;
00296     CS_ASSERT (Modulo);
00297 
00298     Elements.SetLength(Modulo, ElementArray (0, MIN(Modulo / GrowRate, 4)));
00299 
00300     for (size_t i = 0; i < elen; i++)
00301     {
00302       ElementArray& src = Elements[i];
00303       size_t slen = src.Length ();
00304       for (size_t j = slen; j > 0; j--)
00305       {
00306         const Element& srcElem = src[j - 1];
00307         ElementArray& dst = 
00308           Elements.Get (csHashComputer<K>::ComputeHash (srcElem.key) % Modulo);
00309         if (&src != &dst)
00310         {
00311           dst.Push (srcElem);
00312           src.DeleteIndex (j - 1);
00313         }
00314       }
00315     }
00316   }
00317 
00318 public:
00333   csHash (size_t size = 23, size_t grow_rate = 5, size_t max_size = 20000)
00334     : Modulo (size), InitModulo (size),
00335       GrowRate (MIN (grow_rate, size)), MaxSize (max_size), Size (0)
00336   {
00337   }
00338 
00340   csHash (const csHash<T> &o) : Elements (o.Elements),
00341     Modulo (o.Modulo), InitModulo (o.InitModulo),
00342     GrowRate (o.GrowRate), MaxSize (o.MaxSize), Size (o.Size) {}
00343 
00351   void Put (const K& key, const T &value)
00352   {
00353     if (Elements.GetSize() == 0) Elements.SetLength (Modulo);
00354     ElementArray& values = 
00355       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00356     values.Push (Element (key, value));
00357     Size++;
00358     if (values.Length () > Elements.Length () / GrowRate
00359      && Elements.Length () < MaxSize) Grow ();
00360   }
00361 
00363   csArray<T> GetAll (const K& key) const
00364   {
00365     return GetAll<typename csArray<T>::ElementHandlerType, 
00366       typename csArray<T>::AllocatorType> (key);
00367   }
00368 
00370   template<typename H, typename M>
00371   csArray<T, H, M> GetAll (const K& key) const
00372   {
00373     if (Elements.GetSize() == 0) return csArray<T> ();
00374     const ElementArray& values = 
00375       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00376     csArray<T> ret (values.Length () / 2);
00377     const size_t len = values.Length ();
00378     for (size_t i = 0; i < len; ++i)
00379     {
00380       const Element& v = values[i];
00381       if (csComparator<K, K>::Compare (v.key, key) == 0) 
00382         ret.Push (v.value);
00383     }
00384     return ret;
00385   }
00386 
00388   void PutUnique (const K& key, const T &value)
00389   {
00390     if (Elements.GetSize() == 0) Elements.SetLength (Modulo);
00391     ElementArray& values = 
00392       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00393     const size_t len = values.Length ();
00394     for (size_t i = 0; i < len; ++i)
00395     {
00396       Element& v = values[i];
00397       if (csComparator<K, K>::Compare (v.key, key) == 0)
00398       {
00399         v.value = value;
00400         return;
00401       }
00402     }
00403 
00404     values.Push (Element (key, value));
00405     Size++;
00406     if (values.Length () > Elements.Length () / GrowRate
00407      && Elements.Length () < MaxSize) Grow ();
00408   }
00409 
00414   CS_DEPRECATED_METHOD_MSG("Use PutUnique() instead.")
00415   void PutFirst (const K& key, const T &value)
00416   {
00417     PutUnique(key, value);
00418   }
00419 
00421   bool Contains (const K& key) const
00422   {
00423     if (Elements.GetSize() == 0) return false;
00424     const ElementArray& values = 
00425       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00426     const size_t len = values.Length ();
00427     for (size_t i = 0; i < len; ++i)
00428       if (csComparator<K, K>::Compare (values[i].key, key) == 0) 
00429         return true;
00430     return false;
00431   }
00432 
00438   bool In (const K& key) const
00439   { return Contains(key); }
00440 
00445   const T* GetElementPointer (const K& key) const
00446   {
00447     if (Elements.GetSize() == 0) return 0;
00448     const ElementArray& values = 
00449       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00450     const size_t len = values.Length ();
00451     for (size_t i = 0; i < len; ++i)
00452     {
00453       const Element& v = values[i];
00454       if (csComparator<K, K>::Compare (v.key, key) == 0)
00455         return &v.value;
00456     }
00457 
00458     return 0;
00459   }
00460 
00465   T* GetElementPointer (const K& key)
00466   {
00467     if (Elements.GetSize() == 0) return 0;
00468     ElementArray& values = 
00469       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00470     const size_t len = values.Length ();
00471     for (size_t i = 0; i < len; ++i)
00472     {
00473       Element& v = values[i];
00474       if (csComparator<K, K>::Compare (v.key, key) == 0)
00475         return &v.value;
00476     }
00477 
00478     return 0;
00479   }
00480 
00485   const T& Get (const K& key, const T& fallback) const
00486   {
00487     if (Elements.GetSize() == 0) return fallback;
00488     const ElementArray& values = 
00489       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00490     const size_t len = values.Length ();
00491     for (size_t i = 0; i < len; ++i)
00492     {
00493       const Element& v = values[i];
00494       if (csComparator<K, K>::Compare (v.key, key) == 0)
00495         return v.value;
00496     }
00497 
00498     return fallback;
00499   }
00500 
00505   T& Get (const K& key, T& fallback)
00506   {
00507     if (Elements.GetSize() == 0) return fallback;
00508     ElementArray& values = 
00509       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00510     const size_t len = values.Length ();
00511     for (size_t i = 0; i < len; ++i)
00512     {
00513       Element& v = values[i];
00514       if (csComparator<K, K>::Compare (v.key, key) == 0)
00515         return v.value;
00516     }
00517 
00518     return fallback;
00519   }
00520 
00522   void DeleteAll ()
00523   {
00524     Elements.DeleteAll();
00525     Modulo = InitModulo;
00526     Size = 0;
00527   }
00528 
00530   void Empty() { DeleteAll(); }
00531 
00533   bool DeleteAll (const K& key)
00534   {
00535     bool ret = false;
00536     if (Elements.GetSize() == 0) return ret;
00537     ElementArray& values = 
00538       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00539     for (size_t i = values.Length (); i > 0; i--)
00540     {
00541       const size_t idx = i - 1;
00542       if (csComparator<K, K>::Compare (values[idx].key, key) == 0)
00543       {
00544         values.DeleteIndexFast (idx);
00545         ret = true;
00546         Size--;
00547       }
00548     }
00549     return ret;
00550   }
00551   
00553   bool Delete (const K& key, const T &value)
00554   {
00555     bool ret = false;
00556     if (Elements.GetSize() == 0) return ret;
00557     ElementArray& values = 
00558       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00559     for (size_t i = values.Length (); i > 0; i--)
00560     {
00561       const size_t idx = i - 1;
00562       if ((csComparator<K, K>::Compare (values[idx].key, key) == 0) && 
00563           (csComparator<T, T>::Compare (values[idx].value, value) == 0 ))
00564       {
00565         values.DeleteIndexFast (idx);
00566         ret = true;
00567         Size--;
00568       }
00569     }
00570     return ret;
00571   }
00572 
00574   size_t GetSize () const
00575   {
00576     return Size;
00577   }
00578 
00584   bool IsEmpty() const
00585   {
00586     return GetSize() == 0;
00587   }
00588 
00590   class Iterator
00591   {
00592   private:
00593     csHash<T, K>* hash;
00594     const K key;
00595     size_t bucket, size, element;
00596 
00597     void Seek ()
00598     {
00599       while ((element < size) && 
00600         (csComparator<K, K>::Compare (hash->Elements[bucket][element].key, 
00601         key) != 0))
00602           element++;
00603     }
00604 
00605   protected:
00606     Iterator (csHash<T, K>* hash0, const K& key0) :
00607       hash(hash0),
00608       key(key0), 
00609       bucket(csHashComputer<K>::ComputeHash (key) % hash->Modulo),
00610       size((hash->Elements.GetSize() > 0) ? hash->Elements[bucket].Length () : 0)
00611       { Reset (); }
00612 
00613     friend class csHash<T, K>;
00614   public:
00616     Iterator (const Iterator &o) :
00617       hash (o.hash),
00618       key(o.key),
00619       bucket(o.bucket),
00620       size(o.size),
00621       element(o.element) {}
00622 
00624     Iterator& operator=(const Iterator& o)
00625     {
00626       hash = o.hash;
00627       key = o.key;
00628       bucket = o.bucket;
00629       size = o.size;
00630       element = o.element;
00631       return *this;
00632     }
00633 
00635     bool HasNext () const
00636     {
00637       return element < size;
00638     }
00639 
00641     T& Next ()
00642     {
00643       T &ret = hash->Elements[bucket][element].value;
00644       element++;
00645       Seek ();
00646       return ret;
00647     }
00648 
00650     void Reset () { element = 0; Seek (); }
00651   };
00652   friend class Iterator;
00653 
00655   class GlobalIterator
00656   {
00657   private:
00658     csHash<T, K> *hash;
00659     size_t bucket, size, element;
00660 
00661     void Zero () { bucket = element = 0; }
00662     void Init () 
00663     { 
00664       size = 
00665         (hash->Elements.GetSize() > 0) ? hash->Elements[bucket].Length () : 0;
00666     }
00667 
00668     void FindItem ()
00669     {
00670       if (element >= size)
00671       {
00672         while (++bucket < hash->Elements.Length ())
00673         {
00674           Init ();
00675           if (size != 0)
00676           {
00677             element = 0;
00678             break;
00679           }
00680         }
00681       }
00682     }
00683 
00684   protected:
00685     GlobalIterator (csHash<T, K> *hash0) : hash (hash0) 
00686     { 
00687       Zero (); 
00688       Init (); 
00689       FindItem ();
00690     }
00691 
00692     friend class csHash<T, K>;
00693   public:
00695     GlobalIterator (const GlobalIterator &o) :
00696       hash (o.hash),
00697       bucket (o.bucket),
00698       size (o.size),
00699       element (o.element) {}
00700 
00702     GlobalIterator& operator=(const GlobalIterator& o)
00703     {
00704       hash = o.hash;
00705       bucket = o.bucket;
00706       size = o.size;
00707       element = o.element;
00708       return *this;
00709     }
00710 
00712     bool HasNext () const
00713     {
00714       if (hash->Elements.Length () == 0) return false;
00715       return element < size || bucket < hash->Elements.Length ();
00716     }
00717 
00719     void Advance ()
00720     {
00721       element++;
00722       FindItem ();
00723     }
00724 
00726     T& NextNoAdvance ()
00727     {
00728       return hash->Elements[bucket][element].value;
00729     }
00730 
00732     T& Next ()
00733     {
00734       T &ret = NextNoAdvance ();
00735       Advance ();
00736       return ret;
00737     }
00738 
00740     T& NextNoAdvance (K &key)
00741     {
00742       key = hash->Elements[bucket][element].key;
00743       return NextNoAdvance ();
00744     }
00745 
00747     T& Next (K &key)
00748     {
00749       key = hash->Elements[bucket][element].key;
00750       return Next ();
00751     }
00752 
00754     void Reset () { Zero (); Init (); FindItem (); }
00755   };
00756   friend class GlobalIterator;
00757 
00759   class ConstIterator
00760   {
00761   private:
00762     const csHash<T, K>* hash;
00763     const K key;
00764     size_t bucket, size, element;
00765 
00766     void Seek ()
00767     {
00768       while ((element < size) && 
00769         (csComparator<K, K>::Compare (hash->Elements[bucket][element].key, 
00770         key) != 0))
00771           element++;
00772     }
00773 
00774   protected:
00775     ConstIterator (const csHash<T, K>* hash0, const K& key0) :
00776       hash(hash0),
00777       key(key0), 
00778       bucket(csHashComputer<K>::ComputeHash (key) % hash->Modulo),
00779       size((hash->Elements.GetSize() > 0) ? hash->Elements[bucket].Length () : 0)
00780       { Reset (); }
00781 
00782     friend class csHash<T, K>;
00783   public:
00785     ConstIterator (const ConstIterator &o) :
00786       hash (o.hash),
00787       key(o.key),
00788       bucket(o.bucket),
00789       size(o.size),
00790       element(o.element) {}
00791 
00793     ConstIterator& operator=(const ConstIterator& o)
00794     {
00795       hash = o.hash;
00796       key = o.key;
00797       bucket = o.bucket;
00798       size = o.size;
00799       element = o.element;
00800       return *this;
00801     }
00802 
00804     bool HasNext () const
00805     {
00806       return element < size;
00807     }
00808 
00810     const T& Next ()
00811     {
00812       const T &ret = hash->Elements[bucket][element].value;
00813       element++;
00814       Seek ();
00815       return ret;
00816     }
00817 
00819     void Reset () { element = 0; Seek (); }
00820   };
00821   friend class ConstIterator;
00822 
00824   class ConstGlobalIterator
00825   {
00826   private:
00827     const csHash<T, K> *hash;
00828     size_t bucket, size, element;
00829 
00830     void Zero () { bucket = element = 0; }
00831     void Init () 
00832     { 
00833       size = 
00834         (hash->Elements.GetSize() > 0) ? hash->Elements[bucket].Length () : 0;
00835     }
00836 
00837     void FindItem ()
00838     {
00839       if (element >= size)
00840       {
00841         while (++bucket < hash->Elements.Length ())
00842         {
00843           Init ();
00844           if (size != 0)
00845           {
00846             element = 0;
00847             break;
00848           }
00849         }
00850       }
00851     }
00852 
00853   protected:
00854     ConstGlobalIterator (const csHash<T, K> *hash0) : hash (hash0) 
00855     { 
00856       Zero (); 
00857       Init (); 
00858       FindItem ();
00859     }
00860 
00861     friend class csHash<T, K>;
00862   public:
00864     ConstGlobalIterator (const ConstGlobalIterator &o) :
00865       hash (o.hash),
00866       bucket (o.bucket),
00867       size (o.size),
00868       element (o.element) {}
00869 
00871     ConstGlobalIterator& operator=(const ConstGlobalIterator& o)
00872     {
00873       hash = o.hash;
00874       bucket = o.bucket;
00875       size = o.size;
00876       element = o.element;
00877       return *this;
00878     }
00879 
00881     bool HasNext () const
00882     {
00883       if (hash->Elements.Length () == 0) return false;
00884       return element < size || bucket < hash->Elements.Length ();
00885     }
00886 
00888     void Advance ()
00889     {
00890       element++;
00891       FindItem ();
00892     }
00893 
00895     const T& NextNoAdvance ()
00896     {
00897       return hash->Elements[bucket][element].value;
00898     }
00899 
00901     const T& Next ()
00902     {
00903       const T &ret = NextNoAdvance ();
00904       Advance ();
00905       return ret;
00906     }
00907 
00909     const T& NextNoAdvance (K &key)
00910     {
00911       key = hash->Elements[bucket][element].key;
00912       return NextNoAdvance ();
00913     }
00914 
00916     const T& Next (K &key)
00917     {
00918       key = hash->Elements[bucket][element].key;
00919       return Next ();
00920     }
00921 
00923     void Reset () { Zero (); Init (); FindItem (); }
00924   };
00925   friend class ConstGlobalIterator;
00926 
00929   void DeleteElement (GlobalIterator& iterator)
00930   {
00931     Elements[iterator.bucket].DeleteIndex(iterator.element);
00932     Size--;
00933     iterator.size--;
00934     iterator.FindItem ();
00935   }
00936 
00939   void DeleteElement (ConstGlobalIterator& iterator)
00940   {
00941     Elements[iterator.bucket].DeleteIndex(iterator.element);
00942     Size--;
00943     iterator.size--;
00944     iterator.FindItem ();
00945   }
00946 
00953   Iterator GetIterator (const K& key)
00954   {
00955     return Iterator (this, key);
00956   }
00957 
00963   GlobalIterator GetIterator ()
00964   {
00965     return GlobalIterator (this);
00966   }
00967 
00974   ConstIterator GetIterator (const K& key) const
00975   {
00976     return ConstIterator (this, key);
00977   }
00978 
00984   ConstGlobalIterator GetIterator () const
00985   {
00986     return ConstGlobalIterator (this);
00987   }
00988 };
00989 
00992 #endif

Generated for Crystal Space 1.0.2 by doxygen 1.4.7