CrystalSpace

Public API Reference

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

csutil/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 "array.h"
00023 
00030 uint32 csHashCompute (char const*);
00031 
00038 uint32 csHashCompute (char const*, int length);
00039 
00043 template <class T>
00044 class csIntegralHashKeyHandler
00045 {
00046 public:
00047   static uint32 ComputeHash (const T& key)
00048   {
00049     return (uint32)key;
00050   }
00051 
00052   static bool CompareKeys (const T& key1, const T& key2)
00053   {
00054     return (key1 == key2);
00055   }
00056 };
00057 
00062 template <class T, class K = uint32, 
00063   class KeyHandler = csIntegralHashKeyHandler<K> > 
00064 class csHash
00065 {
00066 protected:
00067   struct Element
00068   {
00069     const K key;
00070     T value;
00071 
00072     Element (const K& key0, const T &value0) : key (key0), value (value0) {}
00073     Element (const Element &other) : key (other.key), value (other.value) {}
00074   };
00075   csArray< csArray<Element> > Elements;
00076 
00077   int Modulo;
00078 
00079 private:
00080   int InitModulo;
00081   int GrowRate;
00082   int MaxSize;
00083   int Size;
00084 
00085   void Grow ()
00086   {
00087     static const int Primes[] =
00088     {
00089       53,         97,         193,       389,       769, 
00090       1543,       3079,       6151,      12289,     24593,
00091       49157,      98317,      196613,    393241,    786433,
00092       1572869,    3145739,    6291469,   12582917,  25165843,
00093       50331653,   100663319,  201326611, 402653189, 805306457,
00094       1610612741, 0
00095     };
00096 
00097     const int *p;
00098     int elen = Elements.Length ();
00099     for (p = Primes; *p && *p <= elen; p++) ;
00100     Modulo = *p;
00101     CS_ASSERT (Modulo);
00102 
00103     Elements.SetLength (Modulo);
00104 
00105     for (int i = 0; i < elen; i++)
00106     {
00107       csArray<Element>& src = Elements[i];
00108       int slen = src.Length ();
00109       for (int j = slen - 1; j >= 0; j--)
00110       {
00111         const Element& srcElem = src[j];
00112         csArray<Element>& dst = 
00113           Elements.Get (KeyHandler::ComputeHash (srcElem.key) % Modulo);
00114         if (&src != &dst)
00115         {
00116           dst.Push (srcElem);
00117           src.DeleteIndex (j);
00118         }
00119       }
00120     }
00121   }
00122 
00123 public:
00137   csHash (int size = 257, int grow_rate = 64, int max_size = 20000)
00138     : Elements (size), Modulo (size), InitModulo (size),
00139       GrowRate (grow_rate), MaxSize (max_size), Size (0)
00140   {
00141     Elements.SetLength (size, csArray<Element> (1, 7));
00142   }
00143 
00145   csHash (const csHash<T> &o) : Elements (o.Elements),
00146     Modulo (o.Modulo), InitModulo (o.InitModulo),
00147     GrowRate (o.GrowRate), MaxSize (o.MaxSize), Size (o.Size) {}
00148 
00150   void Put (const K& key, const T &value)
00151   {
00152     csArray<Element> &values = 
00153       Elements[KeyHandler::ComputeHash (key) % Modulo];
00154     values.Push (Element (key, value));
00155     Size++;
00156     if (values.Length () > Elements.Length () / GrowRate
00157      && Elements.Length () < MaxSize) Grow ();
00158   }
00159 
00161   csArray<T> GetAll (const K& key) const
00162   {
00163     const csArray<Element> &values = 
00164       Elements[KeyHandler::ComputeHash (key) % Modulo];
00165     csArray<T> ret (values.Length () / 2);
00166     const int len = values.Length ();
00167     for (int i = 0; i < len; ++i)
00168     {
00169       const Element& v = values[i];
00170       if (KeyHandler::CompareKeys (v.key, key)) 
00171         ret.Push (v.value);
00172     }
00173     return ret;
00174   }
00175 
00177   void PutFirst (const K& key, const T &value)
00178   {
00179     csArray<Element> &values = 
00180       Elements[KeyHandler::ComputeHash (key) % Modulo];
00181     const int len = values.Length ();
00182     for (int i = 0; i < len; ++i)
00183     {
00184       Element& v = values[i];
00185       if (KeyHandler::CompareKeys (v.key, key))
00186       {
00187         v.value = value;
00188         return;
00189       }
00190     }
00191 
00192     values.Push (Element (key, value));
00193     Size++;
00194     if (values.Length () > Elements.Length () / GrowRate
00195      && Elements.Length () < MaxSize) Grow ();
00196   }
00197 
00199   bool In (const K& key) const
00200   {
00201     const csArray<Element> &values = 
00202       Elements[KeyHandler::ComputeHash (key) % Modulo];
00203     const int len = values.Length ();
00204     for (int i = 0; i < len; ++i)
00205       if (KeyHandler::CompareKeys (values[i].key, key)) 
00206         return true;
00207 
00208     return false;
00209   }
00210 
00212   const T& Get (const K& key) const
00213   {
00214     const csArray<Element> &values = 
00215       Elements[KeyHandler::ComputeHash (key) % Modulo];
00216     const int len = values.Length ();
00217     for (int i = 0; i < len; ++i)
00218     {
00219       const Element& v = values[i];
00220       if (KeyHandler::CompareKeys (v.key, key))
00221         return v.value;
00222     }
00223 
00224     static const T zero (0);
00225     return zero;
00226   }
00227 
00229   void DeleteAll ()
00230   {
00231     Elements.SetLength (Modulo = InitModulo);
00232     int elen = Elements.Length ();
00233     for (int i = 0; i < elen; i++)
00234       Elements[i].Empty ();
00235     Size = 0;
00236   }
00237 
00239   bool DeleteAll (const K& key)
00240   {
00241     bool ret = false;
00242     csArray<Element> &values = 
00243       Elements[KeyHandler::ComputeHash (key) % Modulo];
00244     for (int i = values.Length () - 1; i >= 0; i--)
00245       if (KeyHandler::CompareKeys (values[i].key, key))
00246       {
00247         values.DeleteIndex (i);
00248         ret = true;
00249         Size--;
00250       }
00251     return ret;
00252   }
00253   
00255   bool Delete (const K& key, const T &value)
00256   {
00257     bool ret = false;
00258     csArray<Element> &values = 
00259       Elements[KeyHandler::ComputeHash (key) % Modulo];
00260     for (int i = values.Length () - 1; i >= 0; i--)
00261       if (KeyHandler::CompareKeys (values[i].key, key) && 
00262         (values[i].value == value))
00263       {
00264         values.DeleteIndex (i);
00265         ret = true;
00266         Size--;
00267       }
00268     return ret;
00269   }
00270 
00272   int GetSize () const
00273   {
00274     return Size;
00275   }
00276 
00278   class Iterator
00279   {
00280   private:
00281     const csHash<T, K, KeyHandler>* hash;
00282     const K key;
00283     int bucket, size, element;
00284 
00285     void Seek ()
00286     {
00287       while ((element < size) && 
00288         ! KeyHandler::CompareKeys (hash->Elements[bucket][element].key, key))
00289           element++;
00290     }
00291 
00292   protected:
00293     Iterator (const csHash<T, K, KeyHandler>* hash0, const K& key0) :
00294       hash(hash0),
00295       key(key0), 
00296       bucket(KeyHandler::ComputeHash(key) % hash->Modulo),
00297       size(hash->Elements[bucket].Length ())
00298       { Reset (); }
00299 
00300     friend class csHash;
00301   public:
00303     Iterator (const Iterator &o) :
00304       hash (o.hash),
00305       key(o.key),
00306       bucket(o.bucket),
00307       size(o.size),
00308       element(o.element) {}
00309 
00311     Iterator& operator=(const Iterator& o)
00312     {
00313       hash = o.hash;
00314       key = o.key;
00315       bucket = o.bucket;
00316       size = o.size;
00317       element = o.element;
00318       return *this;
00319     }
00320 
00322     bool HasNext () const
00323     {
00324       return element < size;
00325     }
00326 
00328     const T& Next ()
00329     {
00330       const T &ret = hash->Elements[bucket][element].value;
00331       element++;
00332       Seek ();
00333       return ret;
00334     }
00335 
00337     void DeleteNext ()
00338     {
00339       hash->Elements[bucket].DeleteIndex (element);
00340     }
00341 
00343     void Reset () { element = 0; Seek (); }
00344   };
00345   friend class Iterator;
00346 
00348   class GlobalIterator
00349   {
00350   private:
00351     const csHash<T, K, KeyHandler> *hash;
00352     int bucket, size, element;
00353 
00354     void Zero () { bucket = element = 0; }
00355     void Init () { size = hash->Elements[bucket].Length (); }
00356 
00357     void FindItem ()
00358     {
00359       if (element >= size)
00360       {
00361         while (++bucket < hash->Elements.Length ())
00362         {
00363           Init ();
00364           if (size != 0)
00365           {
00366             element = 0;
00367             break;
00368           }
00369         }
00370       }
00371     }
00372 
00373   protected:
00374     GlobalIterator (const csHash<T, K, KeyHandler> *hash0) : hash (hash0) 
00375     { 
00376       Zero (); 
00377       Init (); 
00378       FindItem ();
00379     }
00380 
00381     friend class csHash;
00382   public:
00384     GlobalIterator (const Iterator &o) :
00385       hash (o.hash),
00386       bucket (o.bucket),
00387       size (o.size),
00388       element (o.element) {}
00389 
00391     GlobalIterator& operator=(const GlobalIterator& o)
00392     {
00393       hash = o.hash;
00394       bucket = o.bucket;
00395       size = o.size;
00396       element = o.element;
00397       return *this;
00398     }
00399 
00401     bool HasNext () const
00402     {
00403       if (hash->Elements.Length () == 0) return false;
00404       return element < size || bucket < hash->Elements.Length ();
00405     }
00406 
00408     const T& Next ()
00409     {
00410       const T &ret = hash->Elements[bucket][element].value;
00411       element++;
00412       FindItem ();
00413       return ret;
00414     }
00415 
00417     const T& Next (K &key)
00418     {
00419       key = hash->Elements[bucket][element].key;
00420       return Next ();
00421     }
00422 
00424     void DeleteNext ()
00425     {
00426       hash->Elements[bucket].DeleteIndex (element);
00427     }
00428 
00430     void Reset () { Zero (); Init (); FindItem (); }
00431   };
00432   friend class GlobalIterator;
00433 
00440   Iterator GetIterator (const K& key) const
00441   {
00442     return Iterator (this, key);
00443   }
00444 
00450   GlobalIterator GetIterator () const
00451   {
00452     return GlobalIterator (this);
00453   }
00454 };
00455 
00461 template <class T, class KeyHandler = csIntegralHashKeyHandler<T> > 
00462 class csSet
00463 {
00464 private:
00465   csHash<T, T, KeyHandler> map;
00466 
00467 public:
00469   class Iterator : public csHash<T, T, KeyHandler>::Iterator
00470   {
00471   protected:
00472     Iterator () {}
00473   public:
00474   };
00476   class GlobalIterator : public csHash<T, T, KeyHandler>::GlobalIterator
00477   {
00478   protected:
00479     GlobalIterator () {}
00480     GlobalIterator (const csSet<T, KeyHandler> *set0) : 
00481       csHash<T, T, KeyHandler>::GlobalIterator(&set0->map)
00482     { }
00483 
00484   public:
00485     friend class csSet;
00486   };
00487   friend class GlobalIterator;
00488 
00493   csSet (int size = 257, int grow_rate = 64, int max_size = 20000)
00494         : map (size, grow_rate, max_size)
00495   {
00496   }
00497 
00502   void Add (const T& object)
00503   {
00504     if (In (object)) return;
00505     AddNoTest (object);
00506   }
00507 
00514   void AddNoTest (const T& object)
00515   {
00516     map.Put (object, object);
00517   }
00518 
00522   bool In (const T& object)
00523   {
00524     return map.In (object);
00525   }
00526 
00530   void DeleteAll ()
00531   {
00532     map.DeleteAll ();
00533   }
00534 
00539   void Delete (const T& object)
00540   {
00541     map.Delete (object, object);
00542   }
00543 
00545   int GetSize () const
00546   {
00547     return map.GetSize ();
00548   }
00549 
00551   csHash<T, T, KeyHandler>* GetHash () { return &map; }
00552 
00558   GlobalIterator GetIterator () const
00559   {
00560     return GlobalIterator(this);
00561   }
00562 };
00563 
00564 #endif

Generated for Crystal Space by doxygen 1.2.18