Main Page | Modules | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages
hash.h
Go to the documentation of this file.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 00026 #include "csextern.h" 00027 #include "array.h" 00028 00035 CS_CSUTIL_EXPORT unsigned int csHashCompute (char const*); 00036 00043 CS_CSUTIL_EXPORT unsigned int csHashCompute (char const*, size_t length); 00044 00048 template <class T> 00049 class csIntegralHashKeyHandler 00050 { 00051 public: 00052 static unsigned int ComputeHash (const T& key) 00053 { 00054 #if (CS_PROCESSOR_SIZE == 32) 00055 #if (_MSC_VER >= 1300) 00056 /* 00057 VC7 with 64bit warnings complains about a pointer truncation when T is 00058 a pointer. This isn't serious (as csHash<> does not rely on the hash of 00059 a key alone to retrieve a value). The __w64 causes VC7 to not emit that 00060 warning (on 32bit compilers at least). 00061 */ 00062 return (unsigned int __w64)key; 00063 #else 00064 return (unsigned int)key; 00065 #endif 00066 #else 00067 // Cast to uint64 first to avoid compiler warnings about truncation. 00068 return (unsigned int)((uint64)key); 00069 #endif 00070 } 00071 00072 static bool CompareKeys (const T& key1, const T& key2) 00073 { 00074 return (key1 == key2); 00075 } 00076 }; 00077 00082 template <class T, class K = unsigned int, 00083 class KeyHandler = csIntegralHashKeyHandler<K> > 00084 class csHash 00085 { 00086 protected: 00087 struct Element 00088 { 00089 const K key; 00090 T value; 00091 00092 Element (const K& key0, const T &value0) : key (key0), value (value0) {} 00093 Element (const Element &other) : key (other.key), value (other.value) {} 00094 }; 00095 csArray< csArray<Element> > Elements; 00096 00097 size_t Modulo; 00098 00099 private: 00100 size_t InitModulo; 00101 size_t GrowRate; 00102 size_t MaxSize; 00103 size_t Size; 00104 00105 void Grow () 00106 { 00107 static const size_t Primes[] = 00108 { 00109 53, 97, 193, 389, 769, 00110 1543, 3079, 6151, 12289, 24593, 00111 49157, 98317, 196613, 393241, 786433, 00112 1572869, 3145739, 6291469, 12582917, 25165843, 00113 50331653, 100663319, 201326611, 402653189, 805306457, 00114 1610612741, 0 00115 }; 00116 00117 const size_t *p; 00118 size_t elen = Elements.Length (); 00119 for (p = Primes; *p && *p <= elen; p++) ; 00120 Modulo = *p; 00121 CS_ASSERT (Modulo); 00122 00123 Elements.SetLength (Modulo, csArray<Element> (0, MIN (Modulo / GrowRate, 8))); 00124 00125 for (size_t i = 0; i < elen; i++) 00126 { 00127 csArray<Element>& src = Elements[i]; 00128 size_t slen = src.Length (); 00129 for (size_t j = slen; j > 0; j--) 00130 { 00131 const Element& srcElem = src[j - 1]; 00132 csArray<Element>& dst = 00133 Elements.Get (KeyHandler::ComputeHash (srcElem.key) % Modulo); 00134 if (&src != &dst) 00135 { 00136 dst.Push (srcElem); 00137 src.DeleteIndex (j - 1); 00138 } 00139 } 00140 } 00141 } 00142 00143 public: 00157 csHash (int size = 23, int grow_rate = 5, int max_size = 20000) 00158 : Elements (size), Modulo (size), InitModulo (size), 00159 GrowRate (MIN (grow_rate, size)), MaxSize (max_size), Size (0) 00160 { 00161 Elements.SetLength (size, csArray<Element> (0, MIN (size / GrowRate, 8))); 00162 } 00163 00165 csHash (const csHash<T> &o) : Elements (o.Elements), 00166 Modulo (o.Modulo), InitModulo (o.InitModulo), 00167 GrowRate (o.GrowRate), MaxSize (o.MaxSize), Size (o.Size) {} 00168 00176 void Put (const K& key, const T &value) 00177 { 00178 csArray<Element> &values = 00179 Elements[KeyHandler::ComputeHash (key) % Modulo]; 00180 values.Push (Element (key, value)); 00181 Size++; 00182 if (values.Length () > Elements.Length () / GrowRate 00183 && Elements.Length () < MaxSize) Grow (); 00184 } 00185 00187 csArray<T> GetAll (const K& key) const 00188 { 00189 const csArray<Element> &values = 00190 Elements[KeyHandler::ComputeHash (key) % Modulo]; 00191 csArray<T> ret (values.Length () / 2); 00192 const size_t len = values.Length (); 00193 for (size_t i = 0; i < len; ++i) 00194 { 00195 const Element& v = values[i]; 00196 if (KeyHandler::CompareKeys (v.key, key)) 00197 ret.Push (v.value); 00198 } 00199 return ret; 00200 } 00201 00203 void PutUnique (const K& key, const T &value) 00204 { 00205 csArray<Element> &values = 00206 Elements[KeyHandler::ComputeHash (key) % Modulo]; 00207 const size_t len = values.Length (); 00208 for (size_t i = 0; i < len; ++i) 00209 { 00210 Element& v = values[i]; 00211 if (KeyHandler::CompareKeys (v.key, key)) 00212 { 00213 v.value = value; 00214 return; 00215 } 00216 } 00217 00218 values.Push (Element (key, value)); 00219 Size++; 00220 if (values.Length () > Elements.Length () / GrowRate 00221 && Elements.Length () < MaxSize) Grow (); 00222 } 00223 00228 CS_DEPRECATED_METHOD void PutFirst (const K& key, const T &value) 00229 { 00230 PutUnique(key, value); 00231 } 00232 00234 bool In (const K& key) const 00235 { 00236 const csArray<Element> &values = 00237 Elements[KeyHandler::ComputeHash (key) % Modulo]; 00238 const size_t len = values.Length (); 00239 for (size_t i = 0; i < len; ++i) 00240 if (KeyHandler::CompareKeys (values[i].key, key)) 00241 return true; 00242 00243 return false; 00244 } 00245 00250 const T* GetElementPointer (const K& key) const 00251 { 00252 const csArray<Element> &values = 00253 Elements[KeyHandler::ComputeHash (key) % Modulo]; 00254 const size_t len = values.Length (); 00255 for (size_t i = 0; i < len; ++i) 00256 { 00257 const Element& v = values[i]; 00258 if (KeyHandler::CompareKeys (v.key, key)) 00259 return &v.value; 00260 } 00261 00262 return 0; 00263 } 00264 00269 T* GetElementPointer (const K& key) 00270 { 00271 csArray<Element> &values = 00272 Elements[KeyHandler::ComputeHash (key) % Modulo]; 00273 const size_t len = values.Length (); 00274 for (size_t i = 0; i < len; ++i) 00275 { 00276 Element& v = values[i]; 00277 if (KeyHandler::CompareKeys (v.key, key)) 00278 return &v.value; 00279 } 00280 00281 return 0; 00282 } 00283 00288 const T& Get (const K& key, const T& fallback) const 00289 { 00290 const csArray<Element> &values = 00291 Elements[KeyHandler::ComputeHash (key) % Modulo]; 00292 const size_t len = values.Length (); 00293 for (size_t i = 0; i < len; ++i) 00294 { 00295 const Element& v = values[i]; 00296 if (KeyHandler::CompareKeys (v.key, key)) 00297 return v.value; 00298 } 00299 00300 return fallback; 00301 } 00302 00307 T& Get (const K& key, T& fallback) 00308 { 00309 csArray<Element> &values = 00310 Elements[KeyHandler::ComputeHash (key) % Modulo]; 00311 const size_t len = values.Length (); 00312 for (size_t i = 0; i < len; ++i) 00313 { 00314 Element& v = values[i]; 00315 if (KeyHandler::CompareKeys (v.key, key)) 00316 return v.value; 00317 } 00318 00319 return fallback; 00320 } 00321 00323 void DeleteAll () 00324 { 00325 Elements.SetLength (Modulo = InitModulo); 00326 size_t elen = Elements.Length (); 00327 for (size_t i = 0; i < elen; i++) 00328 Elements[i].Empty (); 00329 Size = 0; 00330 } 00331 00333 bool DeleteAll (const K& key) 00334 { 00335 bool ret = false; 00336 csArray<Element> &values = 00337 Elements[KeyHandler::ComputeHash (key) % Modulo]; 00338 for (size_t i = values.Length (); i > 0; i--) 00339 { 00340 const size_t idx = i - 1; 00341 if (KeyHandler::CompareKeys (values[idx].key, key)) 00342 { 00343 values.DeleteIndexFast (idx); 00344 ret = true; 00345 Size--; 00346 } 00347 } 00348 return ret; 00349 } 00350 00352 bool Delete (const K& key, const T &value) 00353 { 00354 bool ret = false; 00355 csArray<Element> &values = 00356 Elements[KeyHandler::ComputeHash (key) % Modulo]; 00357 for (size_t i = values.Length (); i > 0; i--) 00358 { 00359 const size_t idx = i - 1; 00360 if (KeyHandler::CompareKeys (values[idx].key, key) && 00361 (values[idx].value == value)) 00362 { 00363 values.DeleteIndexFast (idx); 00364 ret = true; 00365 Size--; 00366 } 00367 } 00368 return ret; 00369 } 00370 00372 size_t GetSize () const 00373 { 00374 return Size; 00375 } 00376 00378 class Iterator 00379 { 00380 private: 00381 const csHash<T, K, KeyHandler>* hash; 00382 const K key; 00383 size_t bucket, size, element; 00384 00385 void Seek () 00386 { 00387 while ((element < size) && 00388 ! KeyHandler::CompareKeys (hash->Elements[bucket][element].key, key)) 00389 element++; 00390 } 00391 00392 protected: 00393 Iterator (const csHash<T, K, KeyHandler>* hash0, const K& key0) : 00394 hash(hash0), 00395 key(key0), 00396 bucket(KeyHandler::ComputeHash(key) % hash->Modulo), 00397 size(hash->Elements[bucket].Length ()) 00398 { Reset (); } 00399 00400 friend class csHash<T, K, KeyHandler>; 00401 public: 00403 Iterator (const Iterator &o) : 00404 hash (o.hash), 00405 key(o.key), 00406 bucket(o.bucket), 00407 size(o.size), 00408 element(o.element) {} 00409 00411 Iterator& operator=(const Iterator& o) 00412 { 00413 hash = o.hash; 00414 key = o.key; 00415 bucket = o.bucket; 00416 size = o.size; 00417 element = o.element; 00418 return *this; 00419 } 00420 00422 bool HasNext () const 00423 { 00424 return element < size; 00425 } 00426 00428 const T& Next () 00429 { 00430 const T &ret = hash->Elements[bucket][element].value; 00431 element++; 00432 Seek (); 00433 return ret; 00434 } 00435 00437 void Reset () { element = 0; Seek (); } 00438 }; 00439 friend class Iterator; 00440 00442 class GlobalIterator 00443 { 00444 private: 00445 const csHash<T, K, KeyHandler> *hash; 00446 size_t bucket, size, element; 00447 00448 void Zero () { bucket = element = 0; } 00449 void Init () { size = hash->Elements[bucket].Length (); } 00450 00451 void FindItem () 00452 { 00453 if (element >= size) 00454 { 00455 while (++bucket < hash->Elements.Length ()) 00456 { 00457 Init (); 00458 if (size != 0) 00459 { 00460 element = 0; 00461 break; 00462 } 00463 } 00464 } 00465 } 00466 00467 protected: 00468 GlobalIterator (const csHash<T, K, KeyHandler> *hash0) : hash (hash0) 00469 { 00470 Zero (); 00471 Init (); 00472 FindItem (); 00473 } 00474 00475 friend class csHash<T, K, KeyHandler>; 00476 public: 00478 GlobalIterator (const Iterator &o) : 00479 hash (o.hash), 00480 bucket (o.bucket), 00481 size (o.size), 00482 element (o.element) {} 00483 00485 GlobalIterator& operator=(const GlobalIterator& o) 00486 { 00487 hash = o.hash; 00488 bucket = o.bucket; 00489 size = o.size; 00490 element = o.element; 00491 return *this; 00492 } 00493 00495 bool HasNext () const 00496 { 00497 if (hash->Elements.Length () == 0) return false; 00498 return element < size || bucket < hash->Elements.Length (); 00499 } 00500 00502 void Advance () 00503 { 00504 element++; 00505 FindItem (); 00506 } 00507 00509 const T& NextNoAdvance () 00510 { 00511 return hash->Elements[bucket][element].value; 00512 } 00513 00515 const T& Next () 00516 { 00517 const T &ret = NextNoAdvance (); 00518 Advance (); 00519 return ret; 00520 } 00521 00522 const T& NextNoAdvance (K &key) 00523 { 00524 key = hash->Elements[bucket][element].key; 00525 return NextNoAdvance (); 00526 } 00527 00529 const T& Next (K &key) 00530 { 00531 key = hash->Elements[bucket][element].key; 00532 return Next (); 00533 } 00534 00536 void Reset () { Zero (); Init (); FindItem (); } 00537 }; 00538 friend class GlobalIterator; 00539 00542 void DeleteElement (GlobalIterator& iterator) 00543 { 00544 Elements[iterator.bucket].DeleteIndex(iterator.element); 00545 Size--; 00546 iterator.size--; 00547 iterator.FindItem (); 00548 } 00549 00556 Iterator GetIterator (const K& key) const 00557 { 00558 return Iterator (this, key); 00559 } 00560 00566 GlobalIterator GetIterator () const 00567 { 00568 return GlobalIterator (this); 00569 } 00570 }; 00571 00577 template <class T, class KeyHandler = csIntegralHashKeyHandler<T> > 00578 class csSet 00579 { 00580 private: 00581 csHash<T, T, KeyHandler> map; 00582 00583 public: 00585 class Iterator : public csHash<T, T, KeyHandler>::Iterator 00586 { 00587 protected: 00588 Iterator () {} 00589 public: 00590 }; 00592 class GlobalIterator : public csHash<T, T, KeyHandler>::GlobalIterator 00593 { 00594 protected: 00595 GlobalIterator () {} 00596 GlobalIterator (const csSet<T, KeyHandler> *set0) : 00597 csHash<T, T, KeyHandler>::GlobalIterator(&set0->map) 00598 { } 00599 00600 public: 00601 friend class csSet<T, KeyHandler>; 00602 }; 00603 friend class GlobalIterator; 00604 00609 csSet (int size = 23, int grow_rate = 5, int max_size = 20000) 00610 : map (size, grow_rate, max_size) 00611 { 00612 } 00613 00618 void Add (const T& object) 00619 { 00620 if (In (object)) return; 00621 AddNoTest (object); 00622 } 00623 00630 void AddNoTest (const T& object) 00631 { 00632 map.Put (object, object); 00633 } 00634 00638 bool In (const T& object) const 00639 { 00640 return map.In (object); 00641 } 00642 00646 void DeleteAll () 00647 { 00648 map.DeleteAll (); 00649 } 00650 00656 bool Delete (const T& object) 00657 { 00658 return map.Delete (object, object); 00659 } 00660 00662 size_t GetSize () const 00663 { 00664 return map.GetSize (); 00665 } 00666 00668 csHash<T, T, KeyHandler>* GetHash () { return ↦ } 00669 00675 GlobalIterator GetIterator () const 00676 { 00677 return GlobalIterator(this); 00678 } 00679 }; 00680 00681 00682 #endif
Generated for Crystal Space by doxygen 1.3.9.1