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 #include "csutil/tuple.h"
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 
00169 template <typename T>
00170 class csConstPtrKey
00171 {
00172   const T* ptr;
00173 public:
00174   csConstPtrKey () : ptr(0) {}
00175   csConstPtrKey (const T* ptr) : ptr(ptr) {}
00176   csConstPtrKey (csConstPtrKey const& other) : ptr (other.ptr) {}
00177 
00178   uint GetHash () const { return (uintptr_t)ptr; }
00179   inline friend bool operator < (const csConstPtrKey& r1, const csConstPtrKey& r2)
00180   { return r1.ptr < r2.ptr; }
00181   operator const T* () const
00182   { return ptr; }
00183   const T* operator -> () const
00184   { return ptr; }
00185   csConstPtrKey& operator = (csConstPtrKey const& other)
00186   { ptr = other.ptr; return *this; }
00187 };
00188 
00198 template <class T>
00199 class csHashComputerString
00200 {
00201 public:
00202   static uint ComputeHash (const T& key)
00203   {
00204     return csHashCompute ((const char*)key);
00205   }
00206 };
00207 
00211 template<>
00212 class csHashComputer<const char*> : public csHashComputerString<const char*> {};
00213 
00223 template <class T>
00224 class csHashComputerStruct
00225 {
00226 public:
00227   static uint ComputeHash (const T& key)
00228   {
00229     return csHashCompute ((char*)&key, sizeof (T));
00230   }
00231 };
00232 
00233 
00243 template <class T, class K = unsigned int, 
00244   class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc> 
00245 class csHash
00246 {
00247 public:
00248   typedef csHash<T, K, ArrayMemoryAlloc> ThisType;
00249   typedef T ValueType;
00250   typedef K KeyType;
00251   typedef ArrayMemoryAlloc AllocatorType;
00252 
00253 protected:
00254   struct Element
00255   {
00256     const K key;
00257     T value;
00258 
00259     Element (const K& key0, const T &value0) : key (key0), value (value0) {}
00260     Element (const Element &other) : key (other.key), value (other.value) {}
00261   };
00262   typedef csArray<Element, csArrayElementHandler<Element>,
00263     ArrayMemoryAlloc> ElementArray;
00264   csArray<ElementArray, csArrayElementHandler<ElementArray>,
00265     ArrayMemoryAlloc> Elements;
00266 
00267   size_t Modulo;
00268 
00269 private:
00270   size_t InitModulo;
00271   size_t GrowRate;
00272   size_t MaxSize;
00273   size_t Size;
00274 
00275   void Grow ()
00276   {
00277     static const size_t Primes[] =
00278     {
00279       53,         97,         193,       389,       769, 
00280       1543,       3079,       6151,      12289,     24593,
00281       49157,      98317,      196613,    393241,    786433,
00282       1572869,    3145739,    6291469,   12582917,  25165843,
00283       50331653,   100663319,  201326611, 402653189, 805306457,
00284       1610612741, 0
00285     };
00286 
00287     const size_t *p;
00288     size_t elen = Elements.GetSize ();
00289     for (p = Primes; *p && *p <= elen; p++) ;
00290     Modulo = *p;
00291     CS_ASSERT (Modulo);
00292 
00293     Elements.SetSize (Modulo, ElementArray (0, MIN(Modulo / GrowRate, 4)));
00294 
00295     for (size_t i = 0; i < elen; i++)
00296     {
00297       ElementArray& src = Elements[i];
00298       size_t slen = src.GetSize ();
00299       for (size_t j = slen; j > 0; j--)
00300       {
00301         const Element& srcElem = src[j - 1];
00302         ElementArray& dst = 
00303           Elements.Get (csHashComputer<K>::ComputeHash (srcElem.key) % Modulo);
00304         if (&src != &dst)
00305         {
00306           dst.Push (srcElem);
00307           src.DeleteIndex (j - 1);
00308         }
00309       }
00310     }
00311   }
00312 
00313 public:
00328   csHash (size_t size = 23, size_t grow_rate = 5, size_t max_size = 20000)
00329     : Modulo (size), InitModulo (size),
00330       GrowRate (MIN (grow_rate, size)), MaxSize (max_size), Size (0)
00331   {
00332   }
00333 
00335   csHash (const csHash<T> &o) : Elements (o.Elements),
00336     Modulo (o.Modulo), InitModulo (o.InitModulo),
00337     GrowRate (o.GrowRate), MaxSize (o.MaxSize), Size (o.Size) {}
00338 
00346   void Put (const K& key, const T &value)
00347   {
00348     if (Elements.GetSize() == 0) Elements.SetSize (Modulo);
00349     ElementArray& values = 
00350       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00351     values.Push (Element (key, value));
00352     Size++;
00353     if (values.GetSize () > Elements.GetSize () / GrowRate
00354      && Elements.GetSize () < MaxSize) Grow ();
00355   }
00356 
00358   csArray<T> GetAll (const K& key) const
00359   {
00360     return GetAll<typename csArray<T>::ElementHandlerType, 
00361       typename csArray<T>::AllocatorType> (key);
00362   }
00363 
00365   template<typename H, typename M>
00366   csArray<T, H, M> GetAll (const K& key) const
00367   {
00368     if (Elements.GetSize() == 0) return csArray<T> ();
00369     const ElementArray& values = 
00370       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00371     csArray<T> ret (values.GetSize () / 2);
00372     const size_t len = values.GetSize ();
00373     for (size_t i = 0; i < len; ++i)
00374     {
00375       const Element& v = values[i];
00376       if (csComparator<K, K>::Compare (v.key, key) == 0) 
00377         ret.Push (v.value);
00378     }
00379     return ret;
00380   }
00381 
00383   void PutUnique (const K& key, const T &value)
00384   {
00385     if (Elements.GetSize() == 0) Elements.SetSize (Modulo);
00386     ElementArray& values = 
00387       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00388     const size_t len = values.GetSize ();
00389     for (size_t i = 0; i < len; ++i)
00390     {
00391       Element& v = values[i];
00392       if (csComparator<K, K>::Compare (v.key, key) == 0)
00393       {
00394         v.value = value;
00395         return;
00396       }
00397     }
00398 
00399     values.Push (Element (key, value));
00400     Size++;
00401     if (values.GetSize () > Elements.GetSize () / GrowRate
00402      && Elements.GetSize () < MaxSize) Grow ();
00403   }
00404 
00406   bool Contains (const K& key) const
00407   {
00408     if (Elements.GetSize() == 0) return false;
00409     const ElementArray& values = 
00410       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00411     const size_t len = values.GetSize ();
00412     for (size_t i = 0; i < len; ++i)
00413       if (csComparator<K, K>::Compare (values[i].key, key) == 0) 
00414         return true;
00415     return false;
00416   }
00417 
00423   bool In (const K& key) const
00424   { return Contains(key); }
00425 
00430   const T* GetElementPointer (const K& key) const
00431   {
00432     if (Elements.GetSize() == 0) return 0;
00433     const ElementArray& values = 
00434       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00435     const size_t len = values.GetSize ();
00436     for (size_t i = 0; i < len; ++i)
00437     {
00438       const Element& v = values[i];
00439       if (csComparator<K, K>::Compare (v.key, key) == 0)
00440         return &v.value;
00441     }
00442 
00443     return 0;
00444   }
00445 
00450   T* GetElementPointer (const K& key)
00451   {
00452     if (Elements.GetSize() == 0) return 0;
00453     ElementArray& values = 
00454       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00455     const size_t len = values.GetSize ();
00456     for (size_t i = 0; i < len; ++i)
00457     {
00458       Element& v = values[i];
00459       if (csComparator<K, K>::Compare (v.key, key) == 0)
00460         return &v.value;
00461     }
00462 
00463     return 0;
00464   }
00465 
00469   T* operator[] (const K& key)
00470   {
00471     return GetElementPointer (key);
00472   }
00473 
00478   const T& Get (const K& key, const T& fallback) const
00479   {
00480     if (Elements.GetSize() == 0) return fallback;
00481     const ElementArray& values = 
00482       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00483     const size_t len = values.GetSize ();
00484     for (size_t i = 0; i < len; ++i)
00485     {
00486       const Element& v = values[i];
00487       if (csComparator<K, K>::Compare (v.key, key) == 0)
00488         return v.value;
00489     }
00490 
00491     return fallback;
00492   }
00493 
00498   T& Get (const K& key, T& fallback)
00499   {
00500     if (Elements.GetSize() == 0) return fallback;
00501     ElementArray& values = 
00502       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00503     const size_t len = values.GetSize ();
00504     for (size_t i = 0; i < len; ++i)
00505     {
00506       Element& v = values[i];
00507       if (csComparator<K, K>::Compare (v.key, key) == 0)
00508         return v.value;
00509     }
00510 
00511     return fallback;
00512   }
00513 
00515   void DeleteAll ()
00516   {
00517     Elements.DeleteAll();
00518     Modulo = InitModulo;
00519     Size = 0;
00520   }
00521 
00523   void Empty() { DeleteAll(); }
00524 
00526   bool DeleteAll (const K& key)
00527   {
00528     bool ret = false;
00529     if (Elements.GetSize() == 0) return ret;
00530     ElementArray& values = 
00531       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00532     for (size_t i = values.GetSize (); i > 0; i--)
00533     {
00534       const size_t idx = i - 1;
00535       if (csComparator<K, K>::Compare (values[idx].key, key) == 0)
00536       {
00537         values.DeleteIndexFast (idx);
00538         ret = true;
00539         Size--;
00540       }
00541     }
00542     return ret;
00543   }
00544   
00546   bool Delete (const K& key, const T &value)
00547   {
00548     bool ret = false;
00549     if (Elements.GetSize() == 0) return ret;
00550     ElementArray& values = 
00551       Elements[csHashComputer<K>::ComputeHash (key) % Modulo];
00552     for (size_t i = values.GetSize (); i > 0; i--)
00553     {
00554       const size_t idx = i - 1;
00555       if ((csComparator<K, K>::Compare (values[idx].key, key) == 0) && 
00556           (csComparator<T, T>::Compare (values[idx].value, value) == 0 ))
00557       {
00558         values.DeleteIndexFast (idx);
00559         ret = true;
00560         Size--;
00561       }
00562     }
00563     return ret;
00564   }
00565 
00567   size_t GetSize () const
00568   {
00569     return Size;
00570   }
00571 
00577   bool IsEmpty() const
00578   {
00579     return GetSize() == 0;
00580   }
00581 
00583   class Iterator
00584   {
00585   private:
00586     csHash<T, K>* hash;
00587     const K key;
00588     size_t bucket, size, element;
00589 
00590     void Seek ()
00591     {
00592       while ((element < size) && 
00593         (csComparator<K, K>::Compare (hash->Elements[bucket][element].key, 
00594         key) != 0))
00595           element++;
00596     }
00597 
00598   protected:
00599     Iterator (csHash<T, K>* hash0, const K& key0) :
00600       hash(hash0),
00601       key(key0), 
00602       bucket(csHashComputer<K>::ComputeHash (key) % hash->Modulo),
00603       size((hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0)
00604       { Reset (); }
00605 
00606     friend class csHash<T, K>;
00607   public:
00609     Iterator (const Iterator &o) :
00610       hash (o.hash),
00611       key(o.key),
00612       bucket(o.bucket),
00613       size(o.size),
00614       element(o.element) {}
00615 
00617     Iterator& operator=(const Iterator& o)
00618     {
00619       hash = o.hash;
00620       key = o.key;
00621       bucket = o.bucket;
00622       size = o.size;
00623       element = o.element;
00624       return *this;
00625     }
00626 
00628     bool HasNext () const
00629     {
00630       return element < size;
00631     }
00632 
00634     T& Next ()
00635     {
00636       T &ret = hash->Elements[bucket][element].value;
00637       element++;
00638       Seek ();
00639       return ret;
00640     }
00641 
00643     void Reset () { element = 0; Seek (); }
00644   };
00645   friend class Iterator;
00646 
00648   class GlobalIterator
00649   {
00650   private:
00651     csHash<T, K> *hash;
00652     size_t bucket, size, element;
00653 
00654     void Zero () { bucket = element = 0; }
00655     void Init () 
00656     { 
00657       size = 
00658         (hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0;
00659     }
00660 
00661     void FindItem ()
00662     {
00663       if (element >= size)
00664       {
00665         while (++bucket < hash->Elements.GetSize ())
00666         {
00667           Init ();
00668           if (size != 0)
00669           {
00670             element = 0;
00671             break;
00672           }
00673         }
00674       }
00675     }
00676 
00677   protected:
00678     GlobalIterator (csHash<T, K> *hash0) : hash (hash0) 
00679     { 
00680       Zero (); 
00681       Init (); 
00682       FindItem ();
00683     }
00684 
00685     friend class csHash<T, K>;
00686   public:
00688     GlobalIterator (const GlobalIterator &o) :
00689       hash (o.hash),
00690       bucket (o.bucket),
00691       size (o.size),
00692       element (o.element) {}
00693 
00695     GlobalIterator& operator=(const GlobalIterator& o)
00696     {
00697       hash = o.hash;
00698       bucket = o.bucket;
00699       size = o.size;
00700       element = o.element;
00701       return *this;
00702     }
00703 
00705     bool HasNext () const
00706     {
00707       if (hash->Elements.GetSize () == 0) return false;
00708       return element < size || bucket < hash->Elements.GetSize ();
00709     }
00710 
00712     void Advance ()
00713     {
00714       element++;
00715       FindItem ();
00716     }
00717 
00719     T& NextNoAdvance ()
00720     {
00721       return hash->Elements[bucket][element].value;
00722     }
00723 
00725     T& Next ()
00726     {
00727       T &ret = NextNoAdvance ();
00728       Advance ();
00729       return ret;
00730     }
00731 
00733     T& NextNoAdvance (K &key)
00734     {
00735       key = hash->Elements[bucket][element].key;
00736       return NextNoAdvance ();
00737     }
00738 
00740     T& Next (K &key)
00741     {
00742       key = hash->Elements[bucket][element].key;
00743       return Next ();
00744     }
00745 
00747     const csTuple2<T, K> NextTuple ()
00748     {
00749       csTuple2<T, K> t (NextNoAdvance (),
00750           hash->Elements[bucket][element].key);
00751       Advance ();
00752       return t;
00753     }
00754 
00756     void Reset () { Zero (); Init (); FindItem (); }
00757   };
00758   friend class GlobalIterator;
00759 
00761   class ConstIterator
00762   {
00763   private:
00764     const csHash<T, K>* hash;
00765     const K key;
00766     size_t bucket, size, element;
00767 
00768     void Seek ()
00769     {
00770       while ((element < size) && 
00771         (csComparator<K, K>::Compare (hash->Elements[bucket][element].key, 
00772         key) != 0))
00773           element++;
00774     }
00775 
00776   protected:
00777     ConstIterator (const csHash<T, K>* hash0, const K& key0) :
00778       hash(hash0),
00779       key(key0), 
00780       bucket(csHashComputer<K>::ComputeHash (key) % hash->Modulo),
00781       size((hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0)
00782       { Reset (); }
00783 
00784     friend class csHash<T, K>;
00785   public:
00787     ConstIterator (const ConstIterator &o) :
00788       hash (o.hash),
00789       key(o.key),
00790       bucket(o.bucket),
00791       size(o.size),
00792       element(o.element) {}
00793 
00795     ConstIterator& operator=(const ConstIterator& o)
00796     {
00797       hash = o.hash;
00798       key = o.key;
00799       bucket = o.bucket;
00800       size = o.size;
00801       element = o.element;
00802       return *this;
00803     }
00804 
00806     bool HasNext () const
00807     {
00808       return element < size;
00809     }
00810 
00812     const T& Next ()
00813     {
00814       const T &ret = hash->Elements[bucket][element].value;
00815       element++;
00816       Seek ();
00817       return ret;
00818     }
00819 
00821     void Reset () { element = 0; Seek (); }
00822   };
00823   friend class ConstIterator;
00824 
00826   class ConstGlobalIterator
00827   {
00828   private:
00829     const csHash<T, K> *hash;
00830     size_t bucket, size, element;
00831 
00832     void Zero () { bucket = element = 0; }
00833     void Init () 
00834     { 
00835       size = 
00836         (hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0;
00837     }
00838 
00839     void FindItem ()
00840     {
00841       if (element >= size)
00842       {
00843         while (++bucket < hash->Elements.GetSize ())
00844         {
00845           Init ();
00846           if (size != 0)
00847           {
00848             element = 0;
00849             break;
00850           }
00851         }
00852       }
00853     }
00854 
00855   protected:
00856     ConstGlobalIterator (const csHash<T, K> *hash0) : hash (hash0) 
00857     { 
00858       Zero (); 
00859       Init (); 
00860       FindItem ();
00861     }
00862 
00863     friend class csHash<T, K>;
00864   public:
00866     ConstGlobalIterator (const ConstGlobalIterator &o) :
00867       hash (o.hash),
00868       bucket (o.bucket),
00869       size (o.size),
00870       element (o.element) {}
00871 
00873     ConstGlobalIterator& operator=(const ConstGlobalIterator& o)
00874     {
00875       hash = o.hash;
00876       bucket = o.bucket;
00877       size = o.size;
00878       element = o.element;
00879       return *this;
00880     }
00881 
00883     bool HasNext () const
00884     {
00885       if (hash->Elements.GetSize () == 0) return false;
00886       return element < size || bucket < hash->Elements.GetSize ();
00887     }
00888 
00890     void Advance ()
00891     {
00892       element++;
00893       FindItem ();
00894     }
00895 
00897     const T& NextNoAdvance ()
00898     {
00899       return hash->Elements[bucket][element].value;
00900     }
00901 
00903     const T& Next ()
00904     {
00905       const T &ret = NextNoAdvance ();
00906       Advance ();
00907       return ret;
00908     }
00909 
00911     const T& NextNoAdvance (K &key)
00912     {
00913       key = hash->Elements[bucket][element].key;
00914       return NextNoAdvance ();
00915     }
00916 
00918     const T& Next (K &key)
00919     {
00920       key = hash->Elements[bucket][element].key;
00921       return Next ();
00922     }
00923 
00925     const csTuple2<T, K> NextTuple ()
00926     {
00927       csTuple2<T, K> t (NextNoAdvance (),
00928           hash->Elements[bucket][element].key);
00929       Advance ();
00930       return t;
00931     }
00932 
00934     void Reset () { Zero (); Init (); FindItem (); }
00935   };
00936   friend class ConstGlobalIterator;
00937 
00940   void DeleteElement (GlobalIterator& iterator)
00941   {
00942     Elements[iterator.bucket].DeleteIndex(iterator.element);
00943     Size--;
00944     iterator.size--;
00945     iterator.FindItem ();
00946   }
00947 
00950   void DeleteElement (ConstGlobalIterator& iterator)
00951   {
00952     Elements[iterator.bucket].DeleteIndex(iterator.element);
00953     Size--;
00954     iterator.size--;
00955     iterator.FindItem ();
00956   }
00957 
00964   Iterator GetIterator (const K& key)
00965   {
00966     return Iterator (this, key);
00967   }
00968 
00974   GlobalIterator GetIterator ()
00975   {
00976     return GlobalIterator (this);
00977   }
00978 
00985   ConstIterator GetIterator (const K& key) const
00986   {
00987     return ConstIterator (this, key);
00988   }
00989 
00995   ConstGlobalIterator GetIterator () const
00996   {
00997     return ConstGlobalIterator (this);
00998   }
00999 };
01000 
01003 #endif

Generated for Crystal Space 1.2.1 by doxygen 1.5.3