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 ↦ } 00552 00558 GlobalIterator GetIterator () const 00559 { 00560 return GlobalIterator(this); 00561 } 00562 }; 00563 00564 #endif
Generated for Crystal Space by doxygen 1.2.18