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.6.1