CrystalSpace

Public API Reference

Main Page | Modules | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages

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 "array.h"
00028 
00035 CS_CSUTIL_EXPORT unsigned int csHashCompute (char const*);
00036 
00043 CS_CSUTIL_EXPORT unsigned int csHashCompute (char const*, size_t length);
00044 
00048 template <class T>
00049 class csIntegralHashKeyHandler
00050 {
00051 public:
00052   static unsigned int ComputeHash (const T& key)
00053   {
00054 #if (CS_PROCESSOR_SIZE == 32)
00055 #if (_MSC_VER >= 1300)
00056     /*
00057       VC7 with 64bit warnings complains about a pointer truncation when T is
00058       a pointer. This isn't serious (as csHash<> does not rely on the hash of
00059       a key alone to retrieve a value). The __w64 causes VC7 to not emit that
00060       warning (on 32bit compilers at least).
00061      */
00062     return (unsigned int __w64)key;  
00063 #else
00064     return (unsigned int)key;  
00065 #endif
00066 #else
00067     // Cast to uint64 first to avoid compiler warnings about truncation.
00068     return (unsigned int)((uint64)key);
00069 #endif
00070   }
00071 
00072   static bool CompareKeys (const T& key1, const T& key2)
00073   {
00074     return (key1 == key2);
00075   }
00076 };
00077 
00082 template <class T, class K = unsigned int, 
00083   class KeyHandler = csIntegralHashKeyHandler<K> > 
00084 class csHash
00085 {
00086 protected:
00087   struct Element
00088   {
00089     const K key;
00090     T value;
00091 
00092     Element (const K& key0, const T &value0) : key (key0), value (value0) {}
00093     Element (const Element &other) : key (other.key), value (other.value) {}
00094   };
00095   csArray< csArray<Element> > Elements;
00096 
00097   size_t Modulo;
00098 
00099 private:
00100   size_t InitModulo;
00101   size_t GrowRate;
00102   size_t MaxSize;
00103   size_t Size;
00104 
00105   void Grow ()
00106   {
00107     static const size_t Primes[] =
00108     {
00109       53,         97,         193,       389,       769, 
00110       1543,       3079,       6151,      12289,     24593,
00111       49157,      98317,      196613,    393241,    786433,
00112       1572869,    3145739,    6291469,   12582917,  25165843,
00113       50331653,   100663319,  201326611, 402653189, 805306457,
00114       1610612741, 0
00115     };
00116 
00117     const size_t *p;
00118     size_t elen = Elements.Length ();
00119     for (p = Primes; *p && *p <= elen; p++) ;
00120     Modulo = *p;
00121     CS_ASSERT (Modulo);
00122 
00123     Elements.SetLength (Modulo, csArray<Element> (0, MIN (Modulo / GrowRate, 8)));
00124 
00125     for (size_t i = 0; i < elen; i++)
00126     {
00127       csArray<Element>& src = Elements[i];
00128       size_t slen = src.Length ();
00129       for (size_t j = slen; j > 0; j--)
00130       {
00131         const Element& srcElem = src[j - 1];
00132         csArray<Element>& dst = 
00133           Elements.Get (KeyHandler::ComputeHash (srcElem.key) % Modulo);
00134         if (&src != &dst)
00135         {
00136           dst.Push (srcElem);
00137           src.DeleteIndex (j - 1);
00138         }
00139       }
00140     }
00141   }
00142 
00143 public:
00157   csHash (int size = 23, int grow_rate = 5, int max_size = 20000)
00158     : Elements (size), Modulo (size), InitModulo (size),
00159       GrowRate (MIN (grow_rate, size)), MaxSize (max_size), Size (0)
00160   {
00161     Elements.SetLength (size, csArray<Element> (0, MIN (size / GrowRate, 8)));
00162   }
00163 
00165   csHash (const csHash<T> &o) : Elements (o.Elements),
00166     Modulo (o.Modulo), InitModulo (o.InitModulo),
00167     GrowRate (o.GrowRate), MaxSize (o.MaxSize), Size (o.Size) {}
00168 
00176   void Put (const K& key, const T &value)
00177   {
00178     csArray<Element> &values = 
00179       Elements[KeyHandler::ComputeHash (key) % Modulo];
00180     values.Push (Element (key, value));
00181     Size++;
00182     if (values.Length () > Elements.Length () / GrowRate
00183      && Elements.Length () < MaxSize) Grow ();
00184   }
00185 
00187   csArray<T> GetAll (const K& key) const
00188   {
00189     const csArray<Element> &values = 
00190       Elements[KeyHandler::ComputeHash (key) % Modulo];
00191     csArray<T> ret (values.Length () / 2);
00192     const size_t len = values.Length ();
00193     for (size_t i = 0; i < len; ++i)
00194     {
00195       const Element& v = values[i];
00196       if (KeyHandler::CompareKeys (v.key, key)) 
00197         ret.Push (v.value);
00198     }
00199     return ret;
00200   }
00201 
00203   void PutUnique (const K& key, const T &value)
00204   {
00205     csArray<Element> &values = 
00206       Elements[KeyHandler::ComputeHash (key) % Modulo];
00207     const size_t len = values.Length ();
00208     for (size_t i = 0; i < len; ++i)
00209     {
00210       Element& v = values[i];
00211       if (KeyHandler::CompareKeys (v.key, key))
00212       {
00213         v.value = value;
00214         return;
00215       }
00216     }
00217 
00218     values.Push (Element (key, value));
00219     Size++;
00220     if (values.Length () > Elements.Length () / GrowRate
00221      && Elements.Length () < MaxSize) Grow ();
00222   }
00223 
00228   CS_DEPRECATED_METHOD void PutFirst (const K& key, const T &value)
00229   {
00230     PutUnique(key, value);
00231   }
00232 
00234   bool In (const K& key) const
00235   {
00236     const csArray<Element> &values = 
00237       Elements[KeyHandler::ComputeHash (key) % Modulo];
00238     const size_t len = values.Length ();
00239     for (size_t i = 0; i < len; ++i)
00240       if (KeyHandler::CompareKeys (values[i].key, key)) 
00241         return true;
00242 
00243     return false;
00244   }
00245 
00250   const T* GetElementPointer (const K& key) const
00251   {
00252     const csArray<Element> &values = 
00253       Elements[KeyHandler::ComputeHash (key) % Modulo];
00254     const size_t len = values.Length ();
00255     for (size_t i = 0; i < len; ++i)
00256     {
00257       const Element& v = values[i];
00258       if (KeyHandler::CompareKeys (v.key, key))
00259         return &v.value;
00260     }
00261 
00262     return 0;
00263   }
00264 
00269   T* GetElementPointer (const K& key)
00270   {
00271     csArray<Element> &values = 
00272       Elements[KeyHandler::ComputeHash (key) % Modulo];
00273     const size_t len = values.Length ();
00274     for (size_t i = 0; i < len; ++i)
00275     {
00276       Element& v = values[i];
00277       if (KeyHandler::CompareKeys (v.key, key))
00278         return &v.value;
00279     }
00280 
00281     return 0;
00282   }
00283 
00288   const T& Get (const K& key, const T& fallback) const
00289   {
00290     const csArray<Element> &values = 
00291       Elements[KeyHandler::ComputeHash (key) % Modulo];
00292     const size_t len = values.Length ();
00293     for (size_t i = 0; i < len; ++i)
00294     {
00295       const Element& v = values[i];
00296       if (KeyHandler::CompareKeys (v.key, key))
00297         return v.value;
00298     }
00299 
00300     return fallback;
00301   }
00302 
00307   T& Get (const K& key, T& fallback)
00308   {
00309     csArray<Element> &values = 
00310       Elements[KeyHandler::ComputeHash (key) % Modulo];
00311     const size_t len = values.Length ();
00312     for (size_t i = 0; i < len; ++i)
00313     {
00314       Element& v = values[i];
00315       if (KeyHandler::CompareKeys (v.key, key))
00316         return v.value;
00317     }
00318 
00319     return fallback;
00320   }
00321 
00323   void DeleteAll ()
00324   {
00325     Elements.SetLength (Modulo = InitModulo);
00326     size_t elen = Elements.Length ();
00327     for (size_t i = 0; i < elen; i++)
00328       Elements[i].Empty ();
00329     Size = 0;
00330   }
00331 
00333   bool DeleteAll (const K& key)
00334   {
00335     bool ret = false;
00336     csArray<Element> &values = 
00337       Elements[KeyHandler::ComputeHash (key) % Modulo];
00338     for (size_t i = values.Length (); i > 0; i--)
00339     {
00340       const size_t idx = i - 1;
00341       if (KeyHandler::CompareKeys (values[idx].key, key))
00342       {
00343         values.DeleteIndexFast (idx);
00344         ret = true;
00345         Size--;
00346       }
00347     }
00348     return ret;
00349   }
00350   
00352   bool Delete (const K& key, const T &value)
00353   {
00354     bool ret = false;
00355     csArray<Element> &values = 
00356       Elements[KeyHandler::ComputeHash (key) % Modulo];
00357     for (size_t i = values.Length (); i > 0; i--)
00358     {
00359       const size_t idx = i - 1;
00360       if (KeyHandler::CompareKeys (values[idx].key, key) && 
00361         (values[idx].value == value))
00362       {
00363         values.DeleteIndexFast (idx);
00364         ret = true;
00365         Size--;
00366       }
00367     }
00368     return ret;
00369   }
00370 
00372   size_t GetSize () const
00373   {
00374     return Size;
00375   }
00376 
00378   class Iterator
00379   {
00380   private:
00381     const csHash<T, K, KeyHandler>* hash;
00382     const K key;
00383     size_t bucket, size, element;
00384 
00385     void Seek ()
00386     {
00387       while ((element < size) && 
00388         ! KeyHandler::CompareKeys (hash->Elements[bucket][element].key, key))
00389           element++;
00390     }
00391 
00392   protected:
00393     Iterator (const csHash<T, K, KeyHandler>* hash0, const K& key0) :
00394       hash(hash0),
00395       key(key0), 
00396       bucket(KeyHandler::ComputeHash(key) % hash->Modulo),
00397       size(hash->Elements[bucket].Length ())
00398       { Reset (); }
00399 
00400     friend class csHash<T, K, KeyHandler>;
00401   public:
00403     Iterator (const Iterator &o) :
00404       hash (o.hash),
00405       key(o.key),
00406       bucket(o.bucket),
00407       size(o.size),
00408       element(o.element) {}
00409 
00411     Iterator& operator=(const Iterator& o)
00412     {
00413       hash = o.hash;
00414       key = o.key;
00415       bucket = o.bucket;
00416       size = o.size;
00417       element = o.element;
00418       return *this;
00419     }
00420 
00422     bool HasNext () const
00423     {
00424       return element < size;
00425     }
00426 
00428     const T& Next ()
00429     {
00430       const T &ret = hash->Elements[bucket][element].value;
00431       element++;
00432       Seek ();
00433       return ret;
00434     }
00435 
00437     void Reset () { element = 0; Seek (); }
00438   };
00439   friend class Iterator;
00440 
00442   class GlobalIterator
00443   {
00444   private:
00445     const csHash<T, K, KeyHandler> *hash;
00446     size_t bucket, size, element;
00447 
00448     void Zero () { bucket = element = 0; }
00449     void Init () { size = hash->Elements[bucket].Length (); }
00450 
00451     void FindItem ()
00452     {
00453       if (element >= size)
00454       {
00455         while (++bucket < hash->Elements.Length ())
00456         {
00457           Init ();
00458           if (size != 0)
00459           {
00460             element = 0;
00461             break;
00462           }
00463         }
00464       }
00465     }
00466 
00467   protected:
00468     GlobalIterator (const csHash<T, K, KeyHandler> *hash0) : hash (hash0) 
00469     { 
00470       Zero (); 
00471       Init (); 
00472       FindItem ();
00473     }
00474 
00475     friend class csHash<T, K, KeyHandler>;
00476   public:
00478     GlobalIterator (const Iterator &o) :
00479       hash (o.hash),
00480       bucket (o.bucket),
00481       size (o.size),
00482       element (o.element) {}
00483 
00485     GlobalIterator& operator=(const GlobalIterator& o)
00486     {
00487       hash = o.hash;
00488       bucket = o.bucket;
00489       size = o.size;
00490       element = o.element;
00491       return *this;
00492     }
00493 
00495     bool HasNext () const
00496     {
00497       if (hash->Elements.Length () == 0) return false;
00498       return element < size || bucket < hash->Elements.Length ();
00499     }
00500 
00502     void Advance ()
00503     {
00504       element++;
00505       FindItem ();
00506     }
00507 
00509     const T& NextNoAdvance ()
00510     {
00511       return hash->Elements[bucket][element].value;
00512     }
00513 
00515     const T& Next ()
00516     {
00517       const T &ret = NextNoAdvance ();
00518       Advance ();
00519       return ret;
00520     }
00521 
00522     const T& NextNoAdvance (K &key)
00523     {
00524       key = hash->Elements[bucket][element].key;
00525       return NextNoAdvance ();
00526     }
00527 
00529     const T& Next (K &key)
00530     {
00531       key = hash->Elements[bucket][element].key;
00532       return Next ();
00533     }
00534 
00536     void Reset () { Zero (); Init (); FindItem (); }
00537   };
00538   friend class GlobalIterator;
00539 
00542   void DeleteElement (GlobalIterator& iterator)
00543   {
00544     Elements[iterator.bucket].DeleteIndex(iterator.element);
00545     Size--;
00546     iterator.size--;
00547     iterator.FindItem ();
00548   }
00549 
00556   Iterator GetIterator (const K& key) const
00557   {
00558     return Iterator (this, key);
00559   }
00560 
00566   GlobalIterator GetIterator () const
00567   {
00568     return GlobalIterator (this);
00569   }
00570 };
00571 
00577 template <class T, class KeyHandler = csIntegralHashKeyHandler<T> > 
00578 class csSet
00579 {
00580 private:
00581   csHash<T, T, KeyHandler> map;
00582 
00583 public:
00585   class Iterator : public csHash<T, T, KeyHandler>::Iterator
00586   {
00587   protected:
00588     Iterator () {}
00589   public:
00590   };
00592   class GlobalIterator : public csHash<T, T, KeyHandler>::GlobalIterator
00593   {
00594   protected:
00595     GlobalIterator () {}
00596     GlobalIterator (const csSet<T, KeyHandler> *set0) : 
00597       csHash<T, T, KeyHandler>::GlobalIterator(&set0->map)
00598     { }
00599 
00600   public:
00601     friend class csSet<T, KeyHandler>;
00602   };
00603   friend class GlobalIterator;
00604 
00609   csSet (int size = 23, int grow_rate = 5, int max_size = 20000)
00610         : map (size, grow_rate, max_size)
00611   {
00612   }
00613 
00618   void Add (const T& object)
00619   {
00620     if (In (object)) return;
00621     AddNoTest (object);
00622   }
00623 
00630   void AddNoTest (const T& object)
00631   {
00632     map.Put (object, object);
00633   }
00634 
00638   bool In (const T& object) const
00639   {
00640     return map.In (object);
00641   }
00642 
00646   void DeleteAll ()
00647   {
00648     map.DeleteAll ();
00649   }
00650 
00656   bool Delete (const T& object)
00657   {
00658     return map.Delete (object, object);
00659   }
00660 
00662   size_t GetSize () const
00663   {
00664     return map.GetSize ();
00665   }
00666 
00668   csHash<T, T, KeyHandler>* GetHash () { return &map; }
00669 
00675   GlobalIterator GetIterator () const
00676   {
00677     return GlobalIterator(this);
00678   }
00679 };
00680 
00681 
00682 #endif

Generated for Crystal Space by doxygen 1.3.9.1