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 00041 CS_CRYSTALSPACE_EXPORT unsigned int csHashCompute (char const*); 00042 00049 CS_CRYSTALSPACE_EXPORT unsigned int csHashCompute (char const*, size_t length); 00050 00055 template <class T> 00056 class csHashComputer 00057 { 00058 public: 00060 static uint ComputeHash (const T& key) 00061 { 00062 return key.GetHash(); 00063 } 00064 }; 00065 00070 template <class T> 00071 class csHashComputerIntegral 00072 { 00073 public: 00075 static uint ComputeHash (const T& key) 00076 { 00077 return (uintptr_t)key; 00078 } 00079 }; 00080 00082 00085 template<> 00086 class csHashComputer<void*> : public csHashComputerIntegral<void*> {}; 00087 00088 template<> 00089 class csHashComputer<int> : public csHashComputerIntegral<int> {}; 00090 template<> 00091 class csHashComputer<unsigned int> : 00092 public csHashComputerIntegral<unsigned int> {}; 00093 00094 template<> 00095 class csHashComputer<long> : public csHashComputerIntegral<long> {}; 00096 template<> 00097 class csHashComputer<unsigned long> : 00098 public csHashComputerIntegral<unsigned long> {}; 00099 00100 #if (CS_LONG_SIZE < 8) 00101 template<> 00102 class csHashComputer<longlong> : 00103 public csHashComputerIntegral<longlong> {}; 00104 template<> 00105 class csHashComputer<ulonglong> : 00106 public csHashComputerIntegral<ulonglong> {}; 00107 #endif 00108 00109 template<> 00110 class csHashComputer<float> 00111 { 00112 public: 00114 static uint ComputeHash (float key) 00115 { 00116 union 00117 { 00118 float f; 00119 uint u; 00120 } float2uint; 00121 float2uint.f = key; 00122 return float2uint.u; 00123 } 00124 }; 00125 template<> 00126 class csHashComputer<double> 00127 { 00128 public: 00130 static uint ComputeHash (double key) 00131 { 00132 union 00133 { 00134 double f; 00135 uint u; 00136 } double2uint; 00137 double2uint.f = key; 00138 return double2uint.u; 00139 } 00140 }; 00142 00146 template <typename T> 00147 class csPtrKey 00148 { 00149 T* ptr; 00150 public: 00151 csPtrKey () : ptr(0) {} 00152 csPtrKey (T* ptr) : ptr(ptr) {} 00153 csPtrKey (csPtrKey const& other) : ptr (other.ptr) {} 00154 00155 uint GetHash () const { return (uintptr_t)ptr; } 00156 inline friend bool operator < (const csPtrKey& r1, const csPtrKey& r2) 00157 { return r1.ptr < r2.ptr; } 00158 operator T* () const 00159 { return ptr; } 00160 T* operator -> () const 00161 { return ptr; } 00162 csPtrKey& operator = (csPtrKey const& other) 00163 { ptr = other.ptr; return *this; } 00164 }; 00165 00169 template <typename T> 00170 class csConstPtrKey 00171 { 00172 const T* ptr; 00173 public: 00174 csConstPtrKey () : ptr(0) {} 00175 csConstPtrKey (const T* ptr) : ptr(ptr) {} 00176 csConstPtrKey (csConstPtrKey const& other) : ptr (other.ptr) {} 00177 00178 uint GetHash () const { return (uintptr_t)ptr; } 00179 inline friend bool operator < (const csConstPtrKey& r1, const csConstPtrKey& r2) 00180 { return r1.ptr < r2.ptr; } 00181 operator const T* () const 00182 { return ptr; } 00183 const T* operator -> () const 00184 { return ptr; } 00185 csConstPtrKey& operator = (csConstPtrKey const& other) 00186 { ptr = other.ptr; return *this; } 00187 }; 00188 00198 template <class T> 00199 class csHashComputerString 00200 { 00201 public: 00202 static uint ComputeHash (const T& key) 00203 { 00204 return csHashCompute ((const char*)key); 00205 } 00206 }; 00207 00211 template<> 00212 class csHashComputer<const char*> : public csHashComputerString<const char*> {}; 00213 00223 template <class T> 00224 class csHashComputerStruct 00225 { 00226 public: 00227 static uint ComputeHash (const T& key) 00228 { 00229 return csHashCompute ((char*)&key, sizeof (T)); 00230 } 00231 }; 00232 00233 00243 template <class T, class K = unsigned int, 00244 class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc> 00245 class csHash 00246 { 00247 public: 00248 typedef csHash<T, K, ArrayMemoryAlloc> ThisType; 00249 typedef T ValueType; 00250 typedef K KeyType; 00251 typedef ArrayMemoryAlloc AllocatorType; 00252 00253 protected: 00254 struct Element 00255 { 00256 const K key; 00257 T value; 00258 00259 Element (const K& key0, const T &value0) : key (key0), value (value0) {} 00260 Element (const Element &other) : key (other.key), value (other.value) {} 00261 }; 00262 typedef csArray<Element, csArrayElementHandler<Element>, 00263 ArrayMemoryAlloc> ElementArray; 00264 csArray<ElementArray, csArrayElementHandler<ElementArray>, 00265 ArrayMemoryAlloc> Elements; 00266 00267 size_t Modulo; 00268 00269 private: 00270 size_t InitModulo; 00271 size_t GrowRate; 00272 size_t MaxSize; 00273 size_t Size; 00274 00275 void Grow () 00276 { 00277 static const size_t Primes[] = 00278 { 00279 53, 97, 193, 389, 769, 00280 1543, 3079, 6151, 12289, 24593, 00281 49157, 98317, 196613, 393241, 786433, 00282 1572869, 3145739, 6291469, 12582917, 25165843, 00283 50331653, 100663319, 201326611, 402653189, 805306457, 00284 1610612741, 0 00285 }; 00286 00287 const size_t *p; 00288 size_t elen = Elements.GetSize (); 00289 for (p = Primes; *p && *p <= elen; p++) ; 00290 Modulo = *p; 00291 CS_ASSERT (Modulo); 00292 00293 Elements.SetSize (Modulo, ElementArray (0, MIN(Modulo / GrowRate, 4))); 00294 00295 for (size_t i = 0; i < elen; i++) 00296 { 00297 ElementArray& src = Elements[i]; 00298 size_t slen = src.GetSize (); 00299 for (size_t j = slen; j > 0; j--) 00300 { 00301 const Element& srcElem = src[j - 1]; 00302 ElementArray& dst = 00303 Elements.Get (csHashComputer<K>::ComputeHash (srcElem.key) % Modulo); 00304 if (&src != &dst) 00305 { 00306 dst.Push (srcElem); 00307 src.DeleteIndex (j - 1); 00308 } 00309 } 00310 } 00311 } 00312 00313 public: 00328 csHash (size_t size = 23, size_t grow_rate = 5, size_t max_size = 20000) 00329 : Modulo (size), InitModulo (size), 00330 GrowRate (MIN (grow_rate, size)), MaxSize (max_size), Size (0) 00331 { 00332 } 00333 00335 csHash (const csHash<T> &o) : Elements (o.Elements), 00336 Modulo (o.Modulo), InitModulo (o.InitModulo), 00337 GrowRate (o.GrowRate), MaxSize (o.MaxSize), Size (o.Size) {} 00338 00346 void Put (const K& key, const T &value) 00347 { 00348 if (Elements.GetSize() == 0) Elements.SetSize (Modulo); 00349 ElementArray& values = 00350 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00351 values.Push (Element (key, value)); 00352 Size++; 00353 if (values.GetSize () > Elements.GetSize () / GrowRate 00354 && Elements.GetSize () < MaxSize) Grow (); 00355 } 00356 00358 csArray<T> GetAll (const K& key) const 00359 { 00360 return GetAll<typename csArray<T>::ElementHandlerType, 00361 typename csArray<T>::AllocatorType> (key); 00362 } 00363 00365 template<typename H, typename M> 00366 csArray<T, H, M> GetAll (const K& key) const 00367 { 00368 if (Elements.GetSize() == 0) return csArray<T> (); 00369 const ElementArray& values = 00370 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00371 csArray<T> ret (values.GetSize () / 2); 00372 const size_t len = values.GetSize (); 00373 for (size_t i = 0; i < len; ++i) 00374 { 00375 const Element& v = values[i]; 00376 if (csComparator<K, K>::Compare (v.key, key) == 0) 00377 ret.Push (v.value); 00378 } 00379 return ret; 00380 } 00381 00383 void PutUnique (const K& key, const T &value) 00384 { 00385 if (Elements.GetSize() == 0) Elements.SetSize (Modulo); 00386 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 Element& v = values[i]; 00392 if (csComparator<K, K>::Compare (v.key, key) == 0) 00393 { 00394 v.value = value; 00395 return; 00396 } 00397 } 00398 00399 values.Push (Element (key, value)); 00400 Size++; 00401 if (values.GetSize () > Elements.GetSize () / GrowRate 00402 && Elements.GetSize () < MaxSize) Grow (); 00403 } 00404 00406 bool Contains (const K& key) const 00407 { 00408 if (Elements.GetSize() == 0) return false; 00409 const ElementArray& values = 00410 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00411 const size_t len = values.GetSize (); 00412 for (size_t i = 0; i < len; ++i) 00413 if (csComparator<K, K>::Compare (values[i].key, key) == 0) 00414 return true; 00415 return false; 00416 } 00417 00423 bool In (const K& key) const 00424 { return Contains(key); } 00425 00430 const T* GetElementPointer (const K& key) const 00431 { 00432 if (Elements.GetSize() == 0) return 0; 00433 const ElementArray& values = 00434 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00435 const size_t len = values.GetSize (); 00436 for (size_t i = 0; i < len; ++i) 00437 { 00438 const Element& v = values[i]; 00439 if (csComparator<K, K>::Compare (v.key, key) == 0) 00440 return &v.value; 00441 } 00442 00443 return 0; 00444 } 00445 00450 T* GetElementPointer (const K& key) 00451 { 00452 if (Elements.GetSize() == 0) return 0; 00453 ElementArray& values = 00454 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00455 const size_t len = values.GetSize (); 00456 for (size_t i = 0; i < len; ++i) 00457 { 00458 Element& v = values[i]; 00459 if (csComparator<K, K>::Compare (v.key, key) == 0) 00460 return &v.value; 00461 } 00462 00463 return 0; 00464 } 00465 00469 T* operator[] (const K& key) 00470 { 00471 return GetElementPointer (key); 00472 } 00473 00478 const T& Get (const K& key, const T& fallback) const 00479 { 00480 if (Elements.GetSize() == 0) return fallback; 00481 const ElementArray& values = 00482 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00483 const size_t len = values.GetSize (); 00484 for (size_t i = 0; i < len; ++i) 00485 { 00486 const Element& v = values[i]; 00487 if (csComparator<K, K>::Compare (v.key, key) == 0) 00488 return v.value; 00489 } 00490 00491 return fallback; 00492 } 00493 00498 T& Get (const K& key, T& fallback) 00499 { 00500 if (Elements.GetSize() == 0) return fallback; 00501 ElementArray& values = 00502 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00503 const size_t len = values.GetSize (); 00504 for (size_t i = 0; i < len; ++i) 00505 { 00506 Element& v = values[i]; 00507 if (csComparator<K, K>::Compare (v.key, key) == 0) 00508 return v.value; 00509 } 00510 00511 return fallback; 00512 } 00513 00515 void DeleteAll () 00516 { 00517 Elements.DeleteAll(); 00518 Modulo = InitModulo; 00519 Size = 0; 00520 } 00521 00523 void Empty() { DeleteAll(); } 00524 00526 bool DeleteAll (const K& key) 00527 { 00528 bool ret = false; 00529 if (Elements.GetSize() == 0) return ret; 00530 ElementArray& values = 00531 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00532 for (size_t i = values.GetSize (); i > 0; i--) 00533 { 00534 const size_t idx = i - 1; 00535 if (csComparator<K, K>::Compare (values[idx].key, key) == 0) 00536 { 00537 values.DeleteIndexFast (idx); 00538 ret = true; 00539 Size--; 00540 } 00541 } 00542 return ret; 00543 } 00544 00546 bool Delete (const K& key, const T &value) 00547 { 00548 bool ret = false; 00549 if (Elements.GetSize() == 0) return ret; 00550 ElementArray& values = 00551 Elements[csHashComputer<K>::ComputeHash (key) % Modulo]; 00552 for (size_t i = values.GetSize (); i > 0; i--) 00553 { 00554 const size_t idx = i - 1; 00555 if ((csComparator<K, K>::Compare (values[idx].key, key) == 0) && 00556 (csComparator<T, T>::Compare (values[idx].value, value) == 0 )) 00557 { 00558 values.DeleteIndexFast (idx); 00559 ret = true; 00560 Size--; 00561 } 00562 } 00563 return ret; 00564 } 00565 00567 size_t GetSize () const 00568 { 00569 return Size; 00570 } 00571 00577 bool IsEmpty() const 00578 { 00579 return GetSize() == 0; 00580 } 00581 00583 class Iterator 00584 { 00585 private: 00586 csHash<T, K>* hash; 00587 const K key; 00588 size_t bucket, size, element; 00589 00590 void Seek () 00591 { 00592 while ((element < size) && 00593 (csComparator<K, K>::Compare (hash->Elements[bucket][element].key, 00594 key) != 0)) 00595 element++; 00596 } 00597 00598 protected: 00599 Iterator (csHash<T, K>* hash0, const K& key0) : 00600 hash(hash0), 00601 key(key0), 00602 bucket(csHashComputer<K>::ComputeHash (key) % hash->Modulo), 00603 size((hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0) 00604 { Reset (); } 00605 00606 friend class csHash<T, K>; 00607 public: 00609 Iterator (const Iterator &o) : 00610 hash (o.hash), 00611 key(o.key), 00612 bucket(o.bucket), 00613 size(o.size), 00614 element(o.element) {} 00615 00617 Iterator& operator=(const Iterator& o) 00618 { 00619 hash = o.hash; 00620 key = o.key; 00621 bucket = o.bucket; 00622 size = o.size; 00623 element = o.element; 00624 return *this; 00625 } 00626 00628 bool HasNext () const 00629 { 00630 return element < size; 00631 } 00632 00634 T& Next () 00635 { 00636 T &ret = hash->Elements[bucket][element].value; 00637 element++; 00638 Seek (); 00639 return ret; 00640 } 00641 00643 void Reset () { element = 0; Seek (); } 00644 }; 00645 friend class Iterator; 00646 00648 class GlobalIterator 00649 { 00650 private: 00651 csHash<T, K> *hash; 00652 size_t bucket, size, element; 00653 00654 void Zero () { bucket = element = 0; } 00655 void Init () 00656 { 00657 size = 00658 (hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0; 00659 } 00660 00661 void FindItem () 00662 { 00663 if (element >= size) 00664 { 00665 while (++bucket < hash->Elements.GetSize ()) 00666 { 00667 Init (); 00668 if (size != 0) 00669 { 00670 element = 0; 00671 break; 00672 } 00673 } 00674 } 00675 } 00676 00677 protected: 00678 GlobalIterator (csHash<T, K> *hash0) : hash (hash0) 00679 { 00680 Zero (); 00681 Init (); 00682 FindItem (); 00683 } 00684 00685 friend class csHash<T, K>; 00686 public: 00688 GlobalIterator (const GlobalIterator &o) : 00689 hash (o.hash), 00690 bucket (o.bucket), 00691 size (o.size), 00692 element (o.element) {} 00693 00695 GlobalIterator& operator=(const GlobalIterator& o) 00696 { 00697 hash = o.hash; 00698 bucket = o.bucket; 00699 size = o.size; 00700 element = o.element; 00701 return *this; 00702 } 00703 00705 bool HasNext () const 00706 { 00707 if (hash->Elements.GetSize () == 0) return false; 00708 return element < size || bucket < hash->Elements.GetSize (); 00709 } 00710 00712 void Advance () 00713 { 00714 element++; 00715 FindItem (); 00716 } 00717 00719 T& NextNoAdvance () 00720 { 00721 return hash->Elements[bucket][element].value; 00722 } 00723 00725 T& Next () 00726 { 00727 T &ret = NextNoAdvance (); 00728 Advance (); 00729 return ret; 00730 } 00731 00733 T& NextNoAdvance (K &key) 00734 { 00735 key = hash->Elements[bucket][element].key; 00736 return NextNoAdvance (); 00737 } 00738 00740 T& Next (K &key) 00741 { 00742 key = hash->Elements[bucket][element].key; 00743 return Next (); 00744 } 00745 00747 const csTuple2<T, K> NextTuple () 00748 { 00749 csTuple2<T, K> t (NextNoAdvance (), 00750 hash->Elements[bucket][element].key); 00751 Advance (); 00752 return t; 00753 } 00754 00756 void Reset () { Zero (); Init (); FindItem (); } 00757 }; 00758 friend class GlobalIterator; 00759 00761 class ConstIterator 00762 { 00763 private: 00764 const csHash<T, K>* hash; 00765 const K key; 00766 size_t bucket, size, element; 00767 00768 void Seek () 00769 { 00770 while ((element < size) && 00771 (csComparator<K, K>::Compare (hash->Elements[bucket][element].key, 00772 key) != 0)) 00773 element++; 00774 } 00775 00776 protected: 00777 ConstIterator (const csHash<T, K>* hash0, const K& key0) : 00778 hash(hash0), 00779 key(key0), 00780 bucket(csHashComputer<K>::ComputeHash (key) % hash->Modulo), 00781 size((hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0) 00782 { Reset (); } 00783 00784 friend class csHash<T, K>; 00785 public: 00787 ConstIterator (const ConstIterator &o) : 00788 hash (o.hash), 00789 key(o.key), 00790 bucket(o.bucket), 00791 size(o.size), 00792 element(o.element) {} 00793 00795 ConstIterator& operator=(const ConstIterator& o) 00796 { 00797 hash = o.hash; 00798 key = o.key; 00799 bucket = o.bucket; 00800 size = o.size; 00801 element = o.element; 00802 return *this; 00803 } 00804 00806 bool HasNext () const 00807 { 00808 return element < size; 00809 } 00810 00812 const T& Next () 00813 { 00814 const T &ret = hash->Elements[bucket][element].value; 00815 element++; 00816 Seek (); 00817 return ret; 00818 } 00819 00821 void Reset () { element = 0; Seek (); } 00822 }; 00823 friend class ConstIterator; 00824 00826 class ConstGlobalIterator 00827 { 00828 private: 00829 const csHash<T, K> *hash; 00830 size_t bucket, size, element; 00831 00832 void Zero () { bucket = element = 0; } 00833 void Init () 00834 { 00835 size = 00836 (hash->Elements.GetSize() > 0) ? hash->Elements[bucket].GetSize () : 0; 00837 } 00838 00839 void FindItem () 00840 { 00841 if (element >= size) 00842 { 00843 while (++bucket < hash->Elements.GetSize ()) 00844 { 00845 Init (); 00846 if (size != 0) 00847 { 00848 element = 0; 00849 break; 00850 } 00851 } 00852 } 00853 } 00854 00855 protected: 00856 ConstGlobalIterator (const csHash<T, K> *hash0) : hash (hash0) 00857 { 00858 Zero (); 00859 Init (); 00860 FindItem (); 00861 } 00862 00863 friend class csHash<T, K>; 00864 public: 00866 ConstGlobalIterator (const ConstGlobalIterator &o) : 00867 hash (o.hash), 00868 bucket (o.bucket), 00869 size (o.size), 00870 element (o.element) {} 00871 00873 ConstGlobalIterator& operator=(const ConstGlobalIterator& o) 00874 { 00875 hash = o.hash; 00876 bucket = o.bucket; 00877 size = o.size; 00878 element = o.element; 00879 return *this; 00880 } 00881 00883 bool HasNext () const 00884 { 00885 if (hash->Elements.GetSize () == 0) return false; 00886 return element < size || bucket < hash->Elements.GetSize (); 00887 } 00888 00890 void Advance () 00891 { 00892 element++; 00893 FindItem (); 00894 } 00895 00897 const T& NextNoAdvance () 00898 { 00899 return hash->Elements[bucket][element].value; 00900 } 00901 00903 const T& Next () 00904 { 00905 const T &ret = NextNoAdvance (); 00906 Advance (); 00907 return ret; 00908 } 00909 00911 const T& NextNoAdvance (K &key) 00912 { 00913 key = hash->Elements[bucket][element].key; 00914 return NextNoAdvance (); 00915 } 00916 00918 const T& Next (K &key) 00919 { 00920 key = hash->Elements[bucket][element].key; 00921 return Next (); 00922 } 00923 00925 const csTuple2<T, K> NextTuple () 00926 { 00927 csTuple2<T, K> t (NextNoAdvance (), 00928 hash->Elements[bucket][element].key); 00929 Advance (); 00930 return t; 00931 } 00932 00934 void Reset () { Zero (); Init (); FindItem (); } 00935 }; 00936 friend class ConstGlobalIterator; 00937 00940 void DeleteElement (GlobalIterator& iterator) 00941 { 00942 Elements[iterator.bucket].DeleteIndex(iterator.element); 00943 Size--; 00944 iterator.size--; 00945 iterator.FindItem (); 00946 } 00947 00950 void DeleteElement (ConstGlobalIterator& iterator) 00951 { 00952 Elements[iterator.bucket].DeleteIndex(iterator.element); 00953 Size--; 00954 iterator.size--; 00955 iterator.FindItem (); 00956 } 00957 00964 Iterator GetIterator (const K& key) 00965 { 00966 return Iterator (this, key); 00967 } 00968 00974 GlobalIterator GetIterator () 00975 { 00976 return GlobalIterator (this); 00977 } 00978 00985 ConstIterator GetIterator (const K& key) const 00986 { 00987 return ConstIterator (this, key); 00988 } 00989 00995 ConstGlobalIterator GetIterator () const 00996 { 00997 return ConstGlobalIterator (this); 00998 } 00999 }; 01000 01003 #endif
Generated for Crystal Space 1.2 by doxygen 1.4.7