CrystalSpace

Public API Reference

csutil/weakkeyedhash.h
00001 /*
00002     Copyright (C) 2011 by Frank Richter
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 __CSUTIL_WEAKKEYEDHASH_H__
00020 #define __CSUTIL_WEAKKEYEDHASH_H__
00021 
00022 #include "hash.h"
00023 
00024 namespace CS
00025 {
00026   namespace Container
00027   {
00047     template <class T, class K,
00048       class ArrayMemoryAlloc = CS::Container::ArrayAllocDefault,
00049       class ArrayElementHandler = csArraySafeCopyElementHandler<
00050         CS::Container::HashElement<T, K> > > 
00051     class WeakKeyedHash :
00052       protected csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>
00053     {
00054       typedef csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler> Superclass;
00055     public:
00056       
00061       const T& Get (const K& key, const T& fallback)
00062       {
00063         if (this->Elements.GetSize() == 0) return fallback;
00064         typename Superclass::ElementArray& values = 
00065           this->Elements[csHashComputer<K>::ComputeHash (key) % this->Modulo];
00066         const size_t len = values.GetSize ();
00067         for (size_t i = 0; i < len; ++i)
00068         {
00069           const typename Superclass::Element& v = values[i];
00070           // Delete any elements with 'invalid' keys while searching
00071           if (!v.GetKey())
00072           {
00073             values.DeleteIndexFast (i);
00074             this->Size--;
00075             i--;
00076             continue;
00077           }
00078           if (csComparator<K, K>::Compare (v.GetKey(), key) == 0)
00079             return v.GetValue();
00080         }
00081 
00082         return fallback;
00083       }
00084       using Superclass::Get;
00085       
00093       T& Put (const K& key, const T &value)
00094       {
00095         if (this->Elements.GetSize() == 0) this->Elements.SetSize (this->Modulo);
00096         typename Superclass::ElementArray& values = 
00097           this->Elements[csHashComputer<K>::ComputeHash (key) % this->Modulo];
00098         // Delete any elements 'invalid' with keys while looking for a slot
00099         size_t idx = 0;
00100         while (idx < values.GetSize())
00101         {
00102           if (!values[idx].GetKey())
00103           {
00104             break;
00105           }
00106           idx++;
00107         }
00108         if (idx >= values.GetSize())
00109         {
00110           values.Push (typename Superclass::Element (key, value));
00111           this->Size++;
00112         }
00113         if (values.GetSize () > this->Elements.GetSize () / this->GrowRate
00114           && this->Elements.GetSize () < this->MaxSize)
00115         {
00116           this->Grow ();
00117           /* can't use 'values[idx]' since that is no longer the place where
00118             the item is stored. */
00119           return *(this->GetElementPointer (key));
00120         }
00121         return values[idx].GetValue();
00122       }
00123       
00124       using Superclass::DeleteAll;
00125       
00127       class GlobalIterator
00128       {
00129       private:
00130         typedef typename Superclass::GlobalIterator WrappedIterator;
00131         WrappedIterator iter;
00132         
00133         bool haveNext;
00134         K key;
00135         T* value;
00136       protected:
00137         void NextElement ()
00138         {
00139           while (iter.HasNext ())
00140           {
00141             K key;
00142             value = &(iter.Next (key));
00143             if (key)
00144             {
00145               this->key = key;
00146               this->value = value;
00147               haveNext = true;
00148               break;
00149             }
00150             // @@@ Would be nice to clear out invalid keys as well here
00151             // like: ...->DeleteElement (*this);
00152           }
00153           haveNext = false;
00154           key = K ();
00155         }
00156         
00157         GlobalIterator (const WrappedIterator& iter)
00158          : iter (iter)
00159         {
00160           NextElement ();
00161         }
00162 
00163         friend class WeakKeyedHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>;
00164       public:
00166         GlobalIterator (const GlobalIterator& o)
00167          : iter (o.iter), haveNext (o.haveNext), key (o.key), value (o.value) {}
00168 
00170         GlobalIterator& operator=(const GlobalIterator& o)
00171         {
00172           iter = o.iter;
00173           haveNext = o.haveNext;
00174           key = o.key;
00175           value = o.value;
00176           return *this;
00177         }
00178 
00180         bool HasNext () const
00181         {
00182           return haveNext;
00183         }
00184 
00186         void Advance ()
00187         {
00188           NextElement ();
00189         }
00190 
00192         T& NextNoAdvance ()
00193         {
00194           return *value;
00195         }
00196 
00198         T& Next ()
00199         {
00200           T &ret = NextNoAdvance ();
00201           Advance ();
00202           return ret;
00203         }
00204 
00206         T& NextNoAdvance (K &key)
00207         {
00208           key = this->key;
00209           return NextNoAdvance ();
00210         }
00211 
00213         T& Next (K &key)
00214         {
00215           key = this->key;
00216           return Next ();
00217         }
00218 
00220         const csTuple2<T, K> NextTuple ()
00221         {
00222           csTuple2<T, K> t (NextNoAdvance (),
00223             this->key);
00224           Advance ();
00225           return t;
00226         }
00227 
00229         void Reset ()
00230         {
00231           iter->Reset ();
00232           NextElement ();
00233         }
00234       };
00235       friend class GlobalIterator;
00236       
00242       GlobalIterator GetIterator ()
00243       {
00244         return GlobalIterator (Superclass::GetIterator ());
00245       }
00246 
00247       // @@@ FIXME: More csHash<> methods (and iterators) need to be 'ported'
00248     };
00249   } // namespace Container
00250 } // namespace CS
00251 
00252 #endif // __CSUTIL_WEAKKEYEDHASH_H__

Generated for Crystal Space 2.0 by doxygen 1.7.6.1