csutil/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 "csutil/array.h" 00028 #include "csutil/comparator.h" 00029 #include "csutil/util.h" 00030 #include "csutil/tuple.h" 00031 #include "csutil/hashcomputer.h" 00032 00040 template <typename T> 00041 class csPtrKey 00042 { 00043 T* ptr; 00044 public: 00045 csPtrKey () : ptr(0) {} 00046 csPtrKey (T* ptr) : ptr(ptr) {} 00047 csPtrKey (csPtrKey const& other) : ptr (other.ptr) {} 00048 00049 uint GetHash () const { return (uintptr_t)ptr; } 00050 inline friend bool operator < (const csPtrKey& r1, const csPtrKey& r2) 00051 { return r1.ptr < r2.ptr; } 00052 operator T* () const 00053 { return ptr; } 00054 T* operator -> () const 00055 { return ptr; } 00056 csPtrKey& operator = (csPtrKey const& other) 00057 { ptr = other.ptr; return *this; } 00058 }; 00059 00063 template <typename T> 00064 class csConstPtrKey 00065 { 00066 const T* ptr; 00067 public: 00068 csConstPtrKey () : ptr(0) {} 00069 csConstPtrKey (const T* ptr) : ptr(ptr) {} 00070 csConstPtrKey (csConstPtrKey const& other) : ptr (other.ptr) {} 00071 00072 uint GetHash () const { return (uintptr_t)ptr; } 00073 inline friend bool operator < (const csConstPtrKey& r1, const csConstPtrKey& r2) 00074 { return r1.ptr < r2.ptr; } 00075 operator const T* () const 00076 { return ptr; } 00077 const T* operator -> () const 00078 { return ptr; } 00079 csConstPtrKey& operator = (csConstPtrKey const& other) 00080 { ptr = other.ptr; return *this; } 00081 }; 00082 00083 template <class T, class K, 00084 class ArrayMemoryAlloc, class ArrayElementHandler> class csHash; 00085 00086 namespace CS 00087 { 00088 namespace Container 00089 { 00095 template <class T, class K> 00096 class HashElement 00097 { 00098 private: 00099 template <class _T, class _K, class ArrayMemoryAlloc, 00100 class ArrayElementHandler> friend class csHash; 00101 00102 K key; 00103 T value; 00104 public: 00105 HashElement (const K& key0, const T &value0) : key (key0), value (value0) {} 00106 HashElement (const HashElement& other) : key (other.key), value (other.value) {} 00107 00108 const K& GetKey() const { return key; } 00109 const T& GetValue() const { return value; } 00110 T& GetValue() { return value; } 00111 }; 00112 } // namespace Container 00113 } // namespace CS 00114 00124 template <class T, class K = unsigned int, 00125 class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, 00126 class ArrayElementHandler = csArrayElementHandler< 00127 CS::Container::HashElement<T, K> > > 00128 class csHash 00129 { 00130 public: 00131 typedef csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler> ThisType; 00132 typedef T ValueType; 00133 typedef K KeyType; 00134 typedef ArrayMemoryAlloc AllocatorType; 00135 00136 protected: 00137 typedef CS::Container::HashElement<T, K> Element; 00138 typedef csArray<Element, ArrayElementHandler, 00139 ArrayMemoryAlloc, csArrayCapacityDefault> ElementArray; 00140 csArray<ElementArray, csArrayElementHandler<ElementArray>, 00141 ArrayMemoryAlloc> Elements; 00142 00143 size_t Modulo; 00144 size_t Size; 00145 00146 size_t InitModulo; 00147 size_t GrowRate; 00148 size_t MaxSize; 00149 00150 void Grow () 00151 { 00152 static const size_t Primes[] = 00153 { 00154 53, 97, 193, 389, 769, 00155 1543, 3079, 6151, 12289, 24593, 00156 49157, 98317, 196613, 393241, 786433, 00157 1572869, 3145739, 6291469, 12582917, 25165843, 00158 50331653, 100663319, 201326611, 402653189, 805306457, 00159 1610612741, 0 00160 }; 00161 00162 const size_t *p; 00163 size_t elen = Elements.GetSize (); 00164 for (p = Primes; *p && *p <= elen; p++) ; 00165 Modulo = *p; 00166 CS_ASSERT (Modulo); 00167 00168 Elements.SetSize (Modulo, ElementArray (0, MIN(Modulo / GrowRate, 4))); 00169 00170 for (size_t i = 0; i < elen; i++) 00171 { 00172 ElementArray& src = Elements[i]; 00173 size_t slen = src.GetSize (); 00174 for (size_t j = slen; j > 0; j--) 00175 { 00176 const Element& srcElem = src[j - 1]; 00177 ElementArray& dst = 00178 Elements.Get (csHashComputer<K>::ComputeHash (srcElem.key) % Modulo); 00179 if (&src != &dst) 00180 { 00181 dst.Push (srcElem); 00182 src.DeleteIndex (j - 1); 00183 } 00184 } 00185 } 00186 } 00187 00188 public: 00203 csHash (size_t size = 23, size_t grow_rate = 5, size_t max_size = 20000) 00204 : Modulo (size), Size(0), InitModulo (size), 00205 GrowRate (MIN (grow_rate, size)), MaxSize (max_size) 00206 { 00207 } 00208 00210 csHash (const csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler> &o) : 00211 Elements (o.Elements), 00212 Modulo (o.Modulo), Size(o.Size), InitModulo (o.InitModulo), 00213 GrowRate (o.GrowRate), MaxSize (o.MaxSize) {} 00214 00222 T& Put (const K& key, const T &value) 00223 { 00224 if (Elements.GetSize() == 0) Elements.SetSize (Modulo); 00225 ElementArray& values = 00226 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00227 size_t idx = values.Push (Element (key, value)); 00228 Size++; 00229 if (values.GetSize () > Elements.GetSize () / GrowRate 00230 && Elements.GetSize () < MaxSize) 00231 { 00232 Grow (); 00233 /* can't use 'values[idx]' since that is no longer the place where 00234 the item is stored. */ 00235 return *(GetElementPointer (key)); 00236 } 00237 return values[idx].value; 00238 } 00239 00241 csArray<T> GetAll () const 00242 { 00243 if (Elements.GetSize() == 0) return csArray<T> (); 00244 00245 ConstGlobalIterator itr = GetIterator(); 00246 csArray<T> ret; 00247 while(itr.HasNext()) 00248 { 00249 ret.Push(itr.Next()); 00250 } 00251 00252 return ret; 00253 } 00254 00256 csArray<T> GetAll (const K& key) const 00257 { 00258 return GetAll<typename csArray<T>::ElementHandlerType, 00259 typename csArray<T>::AllocatorType> (key); 00260 } 00261 00263 template<typename H, typename M> 00264 csArray<T, H, M> GetAll (const K& key) const 00265 { 00266 if (Elements.GetSize() == 0) return csArray<T> (); 00267 const ElementArray& values = 00268 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00269 csArray<T> ret (values.GetSize () / 2); 00270 const size_t len = values.GetSize (); 00271 for (size_t i = 0; i < len; ++i) 00272 { 00273 const Element& v = values[i]; 00274 if (csComparator<K, K>::Compare (v.key, key) == 0) 00275 ret.Push (v.value); 00276 } 00277 return ret; 00278 } 00279 00281 T& PutUnique (const K& key, const T &value) 00282 { 00283 if (Elements.GetSize() == 0) Elements.SetSize (Modulo); 00284 ElementArray& values = 00285 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00286 const size_t len = values.GetSize (); 00287 for (size_t i = 0; i < len; ++i) 00288 { 00289 Element& v = values[i]; 00290 if (csComparator<K, K>::Compare (v.key, key) == 0) 00291 { 00292 v.value = value; 00293 return v.value; 00294 } 00295 } 00296 00297 size_t idx = values.Push (Element (key, value)); 00298 Size++; 00299 if (values.GetSize () > Elements.GetSize () / GrowRate 00300 && Elements.GetSize () < MaxSize) 00301 { 00302 Grow (); 00303 /* can't use 'values[idx]' since that is no longer the place where 00304 the item is stored. */ 00305 return *(GetElementPointer (key)); 00306 } 00307 return values[idx].value; 00308 } 00309 00311 bool Contains (const K& key) const 00312 { 00313 if (Elements.GetSize() == 0) return false; 00314 const ElementArray& values = 00315 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00316 const size_t len = values.GetSize (); 00317 for (size_t i = 0; i < len; ++i) 00318 if (csComparator<K, K>::Compare (values[i].key, key) == 0) 00319 return true; 00320 return false; 00321 } 00322 00328 bool In (const K& key) const 00329 { return Contains(key); } 00330 00335 const T* GetElementPointer (const K& key) const 00336 { 00337 if (Elements.GetSize() == 0) return 0; 00338 const ElementArray& values = 00339 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00340 const size_t len = values.GetSize (); 00341 for (size_t i = 0; i < len; ++i) 00342 { 00343 const Element& v = values[i]; 00344 if (csComparator<K, K>::Compare (v.key, key) == 0) 00345 return &v.value; 00346 } 00347 00348 return 0; 00349 } 00350 00355 T* GetElementPointer (const K& key) 00356 { 00357 if (Elements.GetSize() == 0) return 0; 00358 ElementArray& values = 00359 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00360 const size_t len = values.GetSize (); 00361 for (size_t i = 0; i < len; ++i) 00362 { 00363 Element& v = values[i]; 00364 if (csComparator<K, K>::Compare (v.key, key) == 0) 00365 return &v.value; 00366 } 00367 00368 return 0; 00369 } 00370 00374 T* operator[] (const K& key) 00375 { 00376 return GetElementPointer (key); 00377 } 00378 00383 const T& Get (const K& key, const T& fallback) const 00384 { 00385 if (Elements.GetSize() == 0) return fallback; 00386 const ElementArray& values = 00387 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00388 const size_t len = values.GetSize (); 00389 for (size_t i = 0; i < len; ++i) 00390 { 00391 const Element& v = values[i]; 00392 if (csComparator<K, K>::Compare (v.key, key) == 0) 00393 return v.value; 00394 } 00395 00396 return fallback; 00397 } 00398 00403 T& Get (const K& key, T& fallback) 00404 { 00405 if (Elements.GetSize() == 0) return fallback; 00406 ElementArray& values = 00407 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00408 const size_t len = values.GetSize (); 00409 for (size_t i = 0; i < len; ++i) 00410 { 00411 Element& v = values[i]; 00412 if (csComparator<K, K>::Compare (v.key, key) == 0) 00413 return v.value; 00414 } 00415 00416 return fallback; 00417 } 00418 00423 T& GetOrCreate (const K& key, const T& defaultValue = T()) 00424 { 00425 if (Elements.GetSize() != 0) 00426 { 00427 ElementArray& values = 00428 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00429 const size_t len = values.GetSize (); 00430 for (size_t i = 0; i < len; ++i) 00431 { 00432 Element& v = values[i]; 00433 if (csComparator<K, K>::Compare (v.key, key) == 0) 00434 return v.value; 00435 } 00436 } 00437 00438 return Put (key, defaultValue); 00439 } 00440 00442 void DeleteAll () 00443 { 00444 Elements.DeleteAll(); 00445 Modulo = InitModulo; 00446 Size = 0; 00447 } 00448 00450 void Empty() { DeleteAll(); } 00451 00453 bool DeleteAll (const K& key) 00454 { 00455 bool ret = false; 00456 if (Elements.GetSize() == 0) return ret; 00457 ElementArray& values = 00458 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00459 for (size_t i = values.GetSize (); i > 0; i--) 00460 { 00461 const size_t idx = i - 1; 00462 if (csComparator<K, K>::Compare (values[idx].key, key) == 0) 00463 { 00464 values.DeleteIndexFast (idx); 00465 ret = true; 00466 Size--; 00467 } 00468 } 00469 return ret; 00470 } 00471 00473 bool Delete (const K& key, const T &value) 00474 { 00475 bool ret = false; 00476 if (Elements.GetSize() == 0) return ret; 00477 ElementArray& values = 00478 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00479 for (size_t i = values.GetSize (); i > 0; i--) 00480 { 00481 const size_t idx = i - 1; 00482 if ((csComparator<K, K>::Compare (values[idx].key, key) == 0) && 00483 (csComparator<T, T>::Compare (values[idx].value, value) == 0 )) 00484 { 00485 values.DeleteIndexFast (idx); 00486 ret = true; 00487 Size--; 00488 } 00489 } 00490 return ret; 00491 } 00492 00494 size_t GetSize () const 00495 { 00496 return Size; 00497 } 00498 00504 bool IsEmpty() const 00505 { 00506 return GetSize() == 0; 00507 } 00508 00510 class Iterator 00511 { 00512 private: 00513 csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>* hash; 00514 const K key; 00515 size_t bucket, size, element; 00516 00517 void Seek () 00518 { 00519 while ((element < size) && 00520 (csComparator<K, K>::Compare (hash->Elements[bucket][element].GetKey(), 00521 key) != 0)) 00522 element++; 00523 } 00524 00525 protected: 00526 Iterator (csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>* hash0, 00527 const K& key0) : 00528 hash(hash0), 00529 key(key0), 00530 bucket(csHashComputer<K>::ComputeHash (key) % hash->Modulo), 00531 size((hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0) 00532 { Reset (); } 00533 00534 friend class csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>; 00535 public: 00537 Iterator (const Iterator &o) : 00538 hash (o.hash), 00539 key(o.key), 00540 bucket(o.bucket), 00541 size(o.size), 00542 element(o.element) {} 00543 00545 Iterator& operator=(const Iterator& o) 00546 { 00547 hash = o.hash; 00548 key = o.key; 00549 bucket = o.bucket; 00550 size = o.size; 00551 element = o.element; 00552 return *this; 00553 } 00554 00556 bool HasNext () const 00557 { 00558 return element < size; 00559 } 00560 00562 T& Next () 00563 { 00564 T &ret = hash->Elements[bucket][element].GetValue(); 00565 element++; 00566 Seek (); 00567 return ret; 00568 } 00569 00571 void Reset () { element = 0; Seek (); } 00572 }; 00573 friend class Iterator; 00574 00576 class GlobalIterator 00577 { 00578 private: 00579 csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler> *hash; 00580 size_t bucket, size, element; 00581 00582 void Zero () { bucket = element = 0; } 00583 void Init () 00584 { 00585 size = 00586 (hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0; 00587 } 00588 00589 void FindItem () 00590 { 00591 if (element >= size) 00592 { 00593 while (++bucket < hash->Elements.GetSize ()) 00594 { 00595 Init (); 00596 if (size != 0) 00597 { 00598 element = 0; 00599 break; 00600 } 00601 } 00602 } 00603 } 00604 00605 protected: 00606 GlobalIterator (csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler> *hash0) 00607 : hash (hash0) 00608 { 00609 Zero (); 00610 Init (); 00611 FindItem (); 00612 } 00613 00614 friend class csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>; 00615 public: 00617 GlobalIterator () : hash (0), size (0) { Zero (); } 00618 00620 GlobalIterator (const GlobalIterator &o) : 00621 hash (o.hash), 00622 bucket (o.bucket), 00623 size (o.size), 00624 element (o.element) {} 00625 00627 GlobalIterator& operator=(const GlobalIterator& o) 00628 { 00629 hash = o.hash; 00630 bucket = o.bucket; 00631 size = o.size; 00632 element = o.element; 00633 return *this; 00634 } 00635 00637 bool HasNext () const 00638 { 00639 if (hash->Elements.GetSize () == 0) return false; 00640 return element < size || bucket < hash->Elements.GetSize (); 00641 } 00642 00644 void Advance () 00645 { 00646 element++; 00647 FindItem (); 00648 } 00649 00651 T& NextNoAdvance () 00652 { 00653 return hash->Elements[bucket][element].GetValue(); 00654 } 00655 00657 T& Next () 00658 { 00659 T &ret = NextNoAdvance (); 00660 Advance (); 00661 return ret; 00662 } 00663 00665 T& NextNoAdvance (K &key) 00666 { 00667 key = hash->Elements[bucket][element].GetKey(); 00668 return NextNoAdvance (); 00669 } 00670 00672 T& Next (K &key) 00673 { 00674 key = hash->Elements[bucket][element].GetKey(); 00675 return Next (); 00676 } 00677 00679 const csTuple2<T, K> NextTuple () 00680 { 00681 csTuple2<T, K> t (NextNoAdvance (), 00682 hash->Elements[bucket][element].GetKey()); 00683 Advance (); 00684 return t; 00685 } 00686 00688 void Reset () { Zero (); Init (); FindItem (); } 00689 }; 00690 friend class GlobalIterator; 00691 00693 class ConstIterator 00694 { 00695 private: 00696 const csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>* hash; 00697 const K key; 00698 size_t bucket, size, element; 00699 00700 void Seek () 00701 { 00702 while ((element < size) && 00703 (csComparator<K, K>::Compare (hash->Elements[bucket][element].GetKey(), 00704 key) != 0)) 00705 element++; 00706 } 00707 00708 protected: 00709 ConstIterator (const csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>* 00710 hash0, const K& key0) : 00711 hash(hash0), 00712 key(key0), 00713 bucket(csHashComputer<K>::ComputeHash (key) % hash->Modulo), 00714 size((hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0) 00715 { Reset (); } 00716 00717 friend class csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>; 00718 public: 00720 ConstIterator (const ConstIterator &o) : 00721 hash (o.hash), 00722 key(o.key), 00723 bucket(o.bucket), 00724 size(o.size), 00725 element(o.element) {} 00726 00728 ConstIterator& operator=(const ConstIterator& o) 00729 { 00730 hash = o.hash; 00731 key = o.key; 00732 bucket = o.bucket; 00733 size = o.size; 00734 element = o.element; 00735 return *this; 00736 } 00737 00739 bool HasNext () const 00740 { 00741 return element < size; 00742 } 00743 00745 const T& Next () 00746 { 00747 const T &ret = hash->Elements[bucket][element].GetValue(); 00748 element++; 00749 Seek (); 00750 return ret; 00751 } 00752 00754 void Reset () { element = 0; Seek (); } 00755 }; 00756 friend class ConstIterator; 00757 00759 class ConstGlobalIterator 00760 { 00761 private: 00762 const csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler> *hash; 00763 size_t bucket, size, element; 00764 00765 void Zero () { bucket = element = 0; } 00766 void Init () 00767 { 00768 size = 00769 (hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0; 00770 } 00771 00772 void FindItem () 00773 { 00774 if (element >= size) 00775 { 00776 while (++bucket < hash->Elements.GetSize ()) 00777 { 00778 Init (); 00779 if (size != 0) 00780 { 00781 element = 0; 00782 break; 00783 } 00784 } 00785 } 00786 } 00787 00788 protected: 00789 ConstGlobalIterator (const csHash<T, K, ArrayMemoryAlloc, 00790 ArrayElementHandler> *hash0) : hash (hash0) 00791 { 00792 Zero (); 00793 Init (); 00794 FindItem (); 00795 } 00796 00797 friend class csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>; 00798 public: 00800 ConstGlobalIterator () : hash (0), size (0) { Zero (); } 00801 00803 ConstGlobalIterator (const ConstGlobalIterator &o) : 00804 hash (o.hash), 00805 bucket (o.bucket), 00806 size (o.size), 00807 element (o.element) {} 00808 00810 ConstGlobalIterator& operator=(const ConstGlobalIterator& o) 00811 { 00812 hash = o.hash; 00813 bucket = o.bucket; 00814 size = o.size; 00815 element = o.element; 00816 return *this; 00817 } 00818 00820 bool HasNext () const 00821 { 00822 if (hash->Elements.GetSize () == 0) return false; 00823 return element < size || bucket < hash->Elements.GetSize (); 00824 } 00825 00827 void Advance () 00828 { 00829 element++; 00830 FindItem (); 00831 } 00832 00834 const T& NextNoAdvance () 00835 { 00836 return hash->Elements[bucket][element].GetValue(); 00837 } 00838 00840 const T& Next () 00841 { 00842 const T &ret = NextNoAdvance (); 00843 Advance (); 00844 return ret; 00845 } 00846 00848 const T& NextNoAdvance (K &key) 00849 { 00850 key = hash->Elements[bucket][element].GetKey(); 00851 return NextNoAdvance (); 00852 } 00853 00855 const T& Next (K &key) 00856 { 00857 key = hash->Elements[bucket][element].GetKey(); 00858 return Next (); 00859 } 00860 00862 const csTuple2<T, K> NextTuple () 00863 { 00864 csTuple2<T, K> t (NextNoAdvance (), 00865 hash->Elements[bucket][element].GetKey()); 00866 Advance (); 00867 return t; 00868 } 00869 00871 void Reset () { Zero (); Init (); FindItem (); } 00872 }; 00873 friend class ConstGlobalIterator; 00874 00877 void DeleteElement (GlobalIterator& iterator) 00878 { 00879 Elements[iterator.bucket].DeleteIndex(iterator.element); 00880 Size--; 00881 iterator.size--; 00882 iterator.FindItem (); 00883 } 00884 00887 void DeleteElement (ConstGlobalIterator& iterator) 00888 { 00889 Elements[iterator.bucket].DeleteIndex(iterator.element); 00890 Size--; 00891 iterator.size--; 00892 iterator.FindItem (); 00893 } 00894 00901 Iterator GetIterator (const K& key) 00902 { 00903 return Iterator (this, key); 00904 } 00905 00911 GlobalIterator GetIterator () 00912 { 00913 return GlobalIterator (this); 00914 } 00915 00922 ConstIterator GetIterator (const K& key) const 00923 { 00924 return ConstIterator (this, key); 00925 } 00926 00932 ConstGlobalIterator GetIterator () const 00933 { 00934 return ConstGlobalIterator (this); 00935 } 00936 }; 00937 00940 #endif
Generated for Crystal Space 2.0 by doxygen 1.6.1