00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
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 }
00113 }
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
00234
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
00304
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