CrystalSpace

Public API Reference

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

hash.h

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 
00022 #include <csutil/array.h>
00023 
00030 uint32 csHashCompute (char const*);
00031 
00038 uint32 csHashCompute (char const*, int length);
00039 
00040 template <class T>
00041 class csIntegralHashKeyHandler
00042 {
00043 public:
00044   static uint32 ComputeHash (const T& key)
00045   {
00046     return (uint32)key;
00047   }
00048 
00049   static bool CompareKeys (const T& key1, const T& key2)
00050   {
00051     return (key1 == key2);
00052   }
00053 };
00054 
00059 template <class T, class K = uint32, 
00060   class KeyHandler = csIntegralHashKeyHandler<K> > 
00061 class csHash
00062 {
00063 protected:
00064   struct Element
00065   {
00066     const K key;
00067     T value;
00068 
00069     Element (const K& key0, const T &value0) : key (key0), value (value0) {}
00070     Element (const Element &other) : key (other.key), value (other.value) {}
00071   };
00072   csArray< csArray<Element> > Elements;
00073 
00074   int Modulo;
00075 
00076 private:
00077   int InitModulo;
00078   int GrowRate;
00079   int MaxSize;
00080   int Size;
00081 
00082   void Grow ()
00083   {
00084     static const int Primes[] =
00085     {
00086       53,         97,         193,       389,       769, 
00087       1543,       3079,       6151,      12289,     24593,
00088       49157,      98317,      196613,    393241,    786433,
00089       1572869,    3145739,    6291469,   12582917,  25165843,
00090       50331653,   100663319,  201326611, 402653189, 805306457,
00091       1610612741, 0
00092     };
00093 
00094     const int *p;
00095     for (p = Primes; *p && *p <= Elements.Length (); p++) ;
00096     Modulo = *p;
00097     CS_ASSERT (Modulo);
00098 
00099     int elen = Elements.Length ();
00100     Elements.SetLength (Modulo, csArray<Element> (1, 7));
00101 
00102     for (int i = 0; i < elen; i++)
00103     {
00104       csArray<Element>& src = Elements[i];
00105       int slen = src.Length ();
00106       for (int j = slen - 1; j >= 0; j--)
00107       {
00108         const Element& srcElem = src[j];
00109         csArray<Element>& dst = 
00110           Elements.Get (KeyHandler::ComputeHash (srcElem.key) % Modulo);
00111         if (&src != &dst)
00112         {
00113           dst.Push (srcElem);
00114           src.DeleteIndex (j);
00115         }
00116       }
00117     }
00118   }
00119 
00120 public:
00134   csHash (int size = 257, int grow_rate = 64, int max_size = 20000)
00135     : Elements (size), Modulo (size), InitModulo (size),
00136       GrowRate (grow_rate), MaxSize (max_size), Size (0)
00137   {
00138     Elements.SetLength (size, csArray<Element> (1, 7));
00139   }
00140 
00142   csHash (const csHash<T> &o) : Elements (o.Elements),
00143     Modulo (o.Modulo), InitModulo (o.InitModulo),
00144     GrowRate (o.GrowRate), MaxSize (o.MaxSize), Size (o.Size) {}
00145 
00147   void Put (const K& key, const T &value)
00148   {
00149     csArray<Element> &values = 
00150       Elements[KeyHandler::ComputeHash (key) % Modulo];
00151     values.Push (Element (key, value));
00152     Size++;
00153     if (values.Length () > Elements.Length () / GrowRate
00154      && Elements.Length () < MaxSize) Grow ();
00155   }
00156 
00158   csArray<T> GetAll (uint32 key) const
00159   {
00160     const csArray<Element> &values = 
00161       Elements[KeyHandler::ComputeHash (key) % Modulo];
00162     csArray<T> ret (values.Length () / 2);
00163     for (int i = values.Length () - 1; i >= 0; i--)
00164       if (KeyHandler::CompareKeys (values[i].key, key)) 
00165         ret.Push (values[i].value);
00166     return ret;
00167   }
00168 
00170   void PutFirst (const K& key, const T &value)
00171   {
00172     csArray<Element> &values = 
00173       Elements[KeyHandler::ComputeHash (key) % Modulo];
00174     for (int i = values.Length () - 1; i >= 0; i--)
00175       if (KeyHandler::CompareKeys (values[i].key, key))
00176       {
00177         values[i].value = value;
00178         return;
00179       }
00180 
00181     values.Push (Element (key, value));
00182     Size++;
00183     if (values.Length () > Elements.Length () / GrowRate
00184      && Elements.Length () < MaxSize) Grow ();
00185   }
00186 
00188   const T& Get (const K& key) const
00189   {
00190     const csArray<Element> &values = 
00191       Elements[KeyHandler::ComputeHash (key) % Modulo];
00192     for (int i = values.Length () - 1; i >= 0; i--)
00193       if (KeyHandler::CompareKeys (values[i].key, key)) 
00194         return values[i].value;
00195 
00196     static const T zero (0);
00197     return zero;
00198   }
00199 
00201   bool DeleteAll ()
00202   {
00203     bool ret = false;
00204     int elen = Elements.Length ();
00205     Elements.SetLength (Modulo = InitModulo);
00206     for (int i = 0; i < elen; i++)
00207     {
00208       if (Elements[i].Length ()) ret = true;
00209       Elements[i].Empty ();
00210     }
00211     Size = 0;
00212     return ret;
00213   }
00214 
00216   bool DeleteAll (const K& key)
00217   {
00218     bool ret = false;
00219     csArray<Element> &values = 
00220       Elements[KeyHandler::ComputeHash (key) % Modulo];
00221     for (int i = values.Length () - 1; i >= 0; i--)
00222       if (KeyHandler::CompareKeys (values[i].key, key))
00223       {
00224         values.DeleteIndex (i);
00225         ret = true;
00226         Size--;
00227       }
00228     return ret;
00229   }
00230   
00232   bool Delete (const K& key, const T &value)
00233   {
00234     bool ret = false;
00235     csArray<Element> &values = 
00236       Elements[KeyHandler::ComputeHash (key) % Modulo];
00237     for (int i = values.Length () - 1; i >= 0; i--)
00238       if (KeyHandler::CompareKeys (values[i].key, key) && 
00239         (values[i].value == value))
00240       {
00241         values.DeleteIndex (i);
00242         ret = true;
00243         Size--;
00244       }
00245     return ret;
00246   }
00247 
00249   int GetSize () const
00250   {
00251     return Size;
00252   }
00253 
00255   class Iterator
00256   {
00257   private:
00258     const csHash<T, K, KeyHandler>* hash;
00259     const K key;
00260     int bucket, size, element;
00261 
00262     void Seek ()
00263     {
00264       while ((element < size) && 
00265         ! KeyHandler::CompareKeys (hash->Elements[bucket][element].key, key))
00266           element++;
00267     }
00268 
00269   protected:
00270     Iterator (const csHash<T, K, KeyHandler>* hash0, const K& key0)
00271     : hash (hash0), key (key0), 
00272       bucket (KeyHandler::ComputeHash (key) % hash->Modulo),
00273       size (hash->Elements[bucket].Length ()) { Return (); }
00274 
00275     friend class csHash<T, K, KeyHandler>;
00276   public:
00277     Iterator (const Iterator &o)
00278     : hash (o.hash), bucket (o.bucket), size (o.size), element (o.element) {}
00279 
00281     bool HasNext () const
00282     {
00283       return element < size;
00284     }
00285 
00287     const T& Next ()
00288     {
00289       const T &ret = hash->Elements[bucket][element].value;
00290       element++;
00291       Seek ();
00292       return ret;
00293     }
00294 
00296     void DeleteNext ()
00297     {
00298       hash->Elements[bucket].DeleteIndex (element);
00299     }
00300 
00302     void Return () { element = 0; Seek (); }
00303   };
00304   friend class csHash<T, K, KeyHandler>::Iterator;
00305 
00307   class GlobalIterator
00308   {
00309   private:
00310     const csHash<T, K, KeyHandler> *hash;
00311     int bucket, size, element;
00312 
00313     void Zero () { bucket = element = 0; }
00314     void Init () { size = hash->Elements[bucket].Length (); }
00315 
00316     void FindItem ()
00317     {
00318       if (element >= size)
00319       {
00320         while (++bucket < hash->Elements.Length ())
00321         {
00322           Init ();
00323           if (size != 0)
00324           {
00325             element = 0;
00326             break;
00327           }
00328         }
00329       }
00330     }
00331 
00332   protected:
00333     GlobalIterator (const csHash<T, K, KeyHandler> *hash0) : hash (hash0) 
00334     { 
00335       Zero (); 
00336       Init (); 
00337       FindItem ();
00338     }
00339 
00340     friend class csHash<T, K, KeyHandler>;
00341   public:
00342     GlobalIterator (const Iterator &o) : hash (o.hash), bucket (o.bucket),
00343       size (o.size), element (o.element) {}
00344 
00346     bool HasNext () const
00347     {
00348       if (hash->Elements.Length () == 0) return false;
00349       return element < size || bucket < hash->Elements.Length ();
00350     }
00351 
00353     const T& Next ()
00354     {
00355       const T &ret = hash->Elements[bucket][element].value;
00356       element++;
00357       FindItem ();
00358       return ret;
00359     }
00360 
00362     const T& Next (K &key)
00363     {
00364       key = hash->Elements[bucket][element].key;
00365       return Next ();
00366     }
00367 
00369     void DeleteNext ()
00370     {
00371       hash->Elements[bucket].DeleteIndex (element);
00372     }
00373 
00375     void Return () { Zero (); Init (); }
00376   };
00377   friend class csHash<T, K, KeyHandler>::GlobalIterator;
00378 
00385   Iterator GetIterator (const K& key) const
00386   {
00387     return Iterator (this, key);
00388   }
00389 
00395   GlobalIterator GetIterator () const
00396   {
00397     return GlobalIterator (this);
00398   }
00399 };
00400 
00401 #endif

Generated for Crystal Space by doxygen 1.2.14