00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef __CS_CSUTIL_FIXEDSIZECACHE_H__
00020 #define __CS_CSUTIL_FIXEDSIZECACHE_H__
00021
00022 #include "csutil/metautils.h"
00023 #include "csutil/compileassert.h"
00024 #include "csutil/hashcomputer.h"
00025
00026 #include "csutil/custom_new_disable.h"
00027
00028 namespace CS
00029 {
00030 namespace Utility
00031 {
00032 namespace Implementation
00033 {
00034
00045 template<typename K, typename T>
00046 class FixedSizeCacheElement
00047 {
00048 public:
00050 void SetKey(const K& k)
00051 {
00052 new (key) K (k);
00053 }
00054
00056 const K& GetKey() const
00057 {
00058 return *reinterpret_cast<const K*>(&key);
00059 }
00060
00062 void InvalidateKey()
00063 {
00064 reinterpret_cast<K*>(&key)->~K();
00065 }
00066
00068 void SetData(const T& t)
00069 {
00070 new (data) T (t);
00071 }
00072
00074 const T& GetData() const
00075 {
00076 return *reinterpret_cast<const T*>(&data);
00077 }
00078
00080 void InvalidateData()
00081 {
00082 reinterpret_cast<T*>(&data)->~T();
00083 }
00084
00085 protected:
00086 private:
00088 union
00089 {
00090 uint8 key[sizeof(K)];
00091 typename CS::Meta::TypeWithAlignment<CS::Meta::AlignmentOf<K>::value >::Type _k_align;
00092 };
00093 union
00094 {
00095 uint8 data[sizeof(T)];
00096 typename CS::Meta::TypeWithAlignment<CS::Meta::AlignmentOf<T>::value >::Type _t_align;
00097 };
00098 };
00099
00100
00110 template<typename K, typename T, unsigned int SetSize, typename LRUPolicy>
00111 class FixedSizeCacheSet
00112 {
00113 public:
00114 typedef FixedSizeCacheSet<K, T, SetSize, LRUPolicy> ThisType;
00115 typedef FixedSizeCacheElement<K, T> ElementType;
00116 typedef typename LRUPolicy::template LRU<SetSize>::Type LRUType;
00117
00119 FixedSizeCacheSet()
00120 {
00121 for (size_t i = 0; i < auxDataSize; ++i)
00122 auxData[i] = 0;
00123 }
00124
00126 ~FixedSizeCacheSet()
00127 {
00128 for (size_t i = 0; i < SetSize; ++i)
00129 {
00130 if(IsElementKeyValid (i))
00131 {
00132 elements[i].InvalidateKey ();
00133 }
00134 if(IsElementDataValid (i))
00135 {
00136 elements[i].InvalidateData ();
00137 }
00138 }
00139 }
00140
00149 bool Insert (const K& key, const T& data)
00150 {
00151
00152 ElementType* e = Find(key);
00153 if(e)
00154 {
00155 return false;
00156 }
00157
00158
00159 e = GetEmptyElement();
00160 e->SetKey (key);
00161 e->SetData (data);
00162 size_t i = e - elements;
00163 lru.Update (i);
00164
00165 return true;
00166 }
00167
00175 void Update (const K& key, const T& data)
00176 {
00177 ElementType* e = Find(key);
00178 if(e)
00179 {
00180 size_t i = e - elements;
00181 if (IsElementDataValid (i))
00182 {
00183 e->InvalidateData ();
00184 }
00185
00186 e->SetData (data);
00187 lru.Update (i);
00188 }
00189 }
00190
00197 void InsertOrUpdate (const K& key, const T& data)
00198 {
00199 size_t i = 0;
00200 ElementType* e = Find(key);
00201 if(e)
00202 {
00203 i = e - elements;
00204 if (IsElementDataValid (i))
00205 {
00206 e->InvalidateData ();
00207 }
00208
00209 e->SetData (data);
00210 }
00211 else
00212 {
00213
00214 e = GetEmptyElement();
00215 e->SetKey (key);
00216 e->SetData (data);
00217 i = e - elements;
00218 }
00219 lru.Update (i);
00220
00221 return;
00222 }
00223
00230 ElementType* Find (const K& key)
00231 {
00232
00233 for (size_t i = 0; i < SetSize; ++i)
00234 {
00235 if (IsElementKeyValid (i) &&
00236 csComparator<K, K>::Compare (elements[i].GetKey (), key) == 0)
00237 {
00238 return &elements[i];
00239 }
00240 }
00241 return 0;
00242 }
00243
00251 bool Get (const K& key, T& data)
00252 {
00253 ElementType* e = Find (key);
00254 size_t i = e - elements;
00255 if (e && IsElementDataValid (i))
00256 {
00257 data = e->GetData ();
00258 lru.Update (i);
00259 return true;
00260 }
00261
00262 return false;
00263 }
00264
00266 void Invalidate (const K& key)
00267 {
00268 ElementType* e = Find (key);
00269 size_t i = e - elements;
00270 if (e && IsElementDataValid (i))
00271 {
00272 e->InvalidateData ();
00273 }
00274 }
00275
00276 private:
00278 bool IsElementKeyValid(size_t index) const
00279 {
00280
00281 index *= 2;
00282 const uint8 a = (SetSize < 8) ? auxData[0] : auxData[index >> 3];
00283 return (a & (1 << (index & 0x7))) != 0;
00284 }
00285
00287 void SetElementKeyValid(size_t index, bool valid)
00288 {
00289
00290 index *= 2;
00291 uint8& a = auxData[index >> 3];
00292 if(valid)
00293 a |= (1 << (index & 0x7));
00294 else
00295 a &= ~(1 << (index & 0x7));
00296 }
00297
00299 bool IsElementDataValid(size_t index) const
00300 {
00301
00302 index = 2*index + 1;
00303 const uint8 a = auxData[index >> 3];
00304 return (a & (1 << (index & 0x7))) != 0;
00305 }
00306
00308 void SetElementDataValid(size_t index, bool valid)
00309 {
00310
00311 index = 2*index + 1;
00312 uint8& a = auxData[index >> 3];
00313 if(valid)
00314 a |= (1 << (index & 0x7));
00315 else
00316 a &= ~(1 << (index & 0x7));
00317 }
00318
00320 ElementType* GetEmptyElement()
00321 {
00322 size_t i = 0;
00323 bool foundEmpty = false;
00324
00325 for (i = 0; i < SetSize; ++i)
00326 {
00327 if (!IsElementDataValid (i))
00328 {
00329 foundEmpty = true;
00330 break;
00331 }
00332 }
00333
00334 if(!foundEmpty)
00335 {
00336 i = lru.GetVictim ();
00337 }
00338
00339 ElementType& e = elements[i];
00340
00341 if (IsElementKeyValid (i))
00342 {
00343 e.InvalidateKey ();
00344 }
00345 if (IsElementDataValid (i))
00346 {
00347 e.InvalidateData ();
00348 }
00349 return &e;
00350 }
00351
00353 ElementType elements[SetSize];
00354
00364 static const size_t auxDataSize = ((SetSize*2)+7) / 8;
00365 uint8 auxData[auxDataSize];
00366
00368 LRUType lru;
00369
00370
00371
00372 CS_COMPILE_ASSERT(CS::Meta::IsLog2<SetSize>::value);
00373 };
00374
00376 template<unsigned int Associativity>
00377 struct SetNumberComputer
00378 {
00379 template<size_t CacheSize>
00380 struct Helper
00381 {
00382 static const unsigned int value = CacheSize / Associativity;
00383 };
00384 };
00385
00387 template<>
00388 struct SetNumberComputer<0>
00389 {
00390 template<size_t CacheSize>
00391 struct Helper
00392 {
00393 static const unsigned int value = 1;
00394 };
00395 };
00396
00397
00405 template<size_t Size>
00406 class FixedSizeLRU
00407 {
00408 public:
00410 FixedSizeLRU()
00411 {
00412 for (size_t i = 0; i < Size; ++i)
00413 {
00414 lruStorage[i] = (LRUType)i;
00415 }
00416 }
00417
00419 void Update (size_t index)
00420 {
00421 size_t i = 0;
00422
00423 while(lruStorage[i] != index)
00424 i++;
00425
00426 while(i > 0)
00427 {
00428 lruStorage[i] = lruStorage[i-1];
00429 --i;
00430 }
00431
00432 lruStorage[0] = (LRUType)index;
00433 }
00434
00436 size_t GetVictim () const
00437 {
00438 return lruStorage[Size-1];
00439 }
00440
00441 private:
00443 static const size_t Log2Size = CS::Meta::Log2<Size>::value;
00444 static const size_t MinBytesInSize = (Log2Size + 7) / 8;
00445 typedef typename CS::Meta::TypeOfSize<MinBytesInSize>::Type LRUType;
00446
00448 LRUType lruStorage[Size];
00449 };
00450
00454 template<>
00455 class FixedSizeLRU<1>
00456 {
00457 public:
00459 void Update (size_t index)
00460 {}
00461
00463 size_t GetVictim () const
00464 {
00465 return 0;
00466 }
00467 };
00468
00472 template<>
00473 class FixedSizeLRU<2>
00474 {
00475 public:
00476 FixedSizeLRU()
00477 : lruStorage(0)
00478 {}
00479
00481 void Update (size_t index)
00482 {
00483 lruStorage = (uint8)(index & 0xff);
00484 }
00485
00487 size_t GetVictim () const
00488 {
00489 return 1-lruStorage;
00490 }
00491
00492 private:
00493 uint8 lruStorage;
00494 };
00495
00502 template<size_t Size>
00503 class FixedSizePseudoLRU
00504 {
00505 public:
00507 FixedSizePseudoLRU ()
00508 {
00509 for (size_t i = 0; i < TreeNodeQW; ++i)
00510 {
00511 lruTree[i] = 0;
00512 }
00513 }
00514
00516 void Update (size_t index)
00517 {
00518
00519 size_t currNode = 0;
00520 size_t currStep = Size/2;
00521
00522 while (currStep > 0)
00523 {
00524
00525 if (index < currStep)
00526 {
00527
00528 SetBit (currNode);
00529 currNode = 2*currNode + 1;
00530 }
00531 else
00532 {
00533
00534 ClearBit (currNode);
00535 currNode = 2*currNode + 2;
00536 index -= currStep;
00537 }
00538
00539 currStep /= 2;
00540 }
00541 }
00542
00544 size_t GetVictim () const
00545 {
00546
00547 size_t currNode = 0;
00548 size_t currVictim = 0;
00549 size_t currStep = Size/2;
00550
00551 while (currStep > 0)
00552 {
00553 if (IsBitSet (currNode))
00554 {
00555
00556 currVictim += currStep;
00557 currNode = 2*currNode + 2;
00558 }
00559 else
00560 {
00561
00562 currNode = 2*currNode + 1;
00563 }
00564
00565 currStep /= 2;
00566 }
00567
00568 return currVictim;
00569 }
00570
00571
00572 private:
00573 void SetBit (size_t index)
00574 {
00575 uint32& a = lruTree[index >> 0x5];
00576 a |= 1 << (index & 0x1F);
00577 }
00578
00579 void ClearBit (size_t index)
00580 {
00581 uint32& a = lruTree[index >> 0x5];
00582 a &= ~(1 << (index & 0x1F));
00583 }
00584
00585 bool IsBitSet (size_t index) const
00586 {
00587 const uint32& a = lruTree[index >> 0x5];
00588 return (a & (1 << (index & 0x1F))) != 0;
00589 }
00590
00591 static const size_t TreeNodeCount = Size-1;
00592 static const size_t TreeNodeQW = (TreeNodeCount+31) / 32;
00593 uint32 lruTree[TreeNodeQW];
00594
00595
00596
00597 CS_COMPILE_ASSERT(CS::Meta::IsLog2<Size>::value);
00598 };
00599
00604 template<>
00605 class FixedSizePseudoLRU<4>
00606 {
00607 public:
00608 FixedSizePseudoLRU()
00609 : lruStorage (0)
00610 {}
00611
00613 void Update (size_t index)
00614 {
00615 switch(index)
00616 {
00617 case 0:
00618 lruStorage = (lruStorage & 0x1) | 0x5;
00619 break;
00620 case 1:
00621 lruStorage = (lruStorage & 0x1) | 0x4;
00622 break;
00623 case 2:
00624 lruStorage = (lruStorage & 0x2) | 0x1;
00625 break;
00626 case 3:
00627 lruStorage = (lruStorage & 0x2);
00628 break;
00629 default:
00630 CS_ASSERT(false);
00631 }
00632 }
00633
00635 size_t GetVictim () const
00636 {
00637 if (lruStorage & 0x4)
00638 {
00639 return (lruStorage & 0x1) ? 3 : 2;
00640 }
00641 else
00642 {
00643 return (lruStorage & 0x2) ? 1 : 0;
00644 }
00645 }
00646
00647 private:
00648 uint8 lruStorage;
00649 };
00650
00655 template<>
00656 class FixedSizePseudoLRU<8>
00657 {
00658 public:
00659 FixedSizePseudoLRU()
00660 : lruStorage (0)
00661 {}
00662
00664 void Update (size_t index)
00665 {
00666 static const uint8 value[] =
00667 {
00668 0xB, 0x3,
00669 0x11, 0x1,
00670 0x24, 0x4,
00671 0x40, 0x0
00672 };
00673
00674 static const uint8 mask[] =
00675 {
00676 0xB, 0xB,
00677 0x13, 0x13,
00678 0x25, 0x25,
00679 0x45, 0x45
00680 };
00681
00682 lruStorage = (lruStorage & ~mask[index]) | value[index];
00683 }
00684
00686 size_t GetVictim () const
00687 {
00688 static const uint8 value[] =
00689 {
00690 0x0, 0x8,
00691 0x2, 0x12,
00692 0x1, 0x21,
00693 0x5, 0x45
00694 };
00695
00696 static const uint8 mask[] =
00697 {
00698 0xB, 0xB,
00699 0x13, 0x13,
00700 0x25, 0x25,
00701 0x45, 0x45
00702 };
00703
00704 for (size_t i = 0; i < 8; ++i)
00705 {
00706 if ((lruStorage & mask[i]) == value[i])
00707 return i;
00708 }
00709
00710 CS_ASSERT(false);
00711 return 0;
00712 }
00713
00714 private:
00715 static const uint8 mask[8];
00716
00717 uint8 lruStorage;
00718 };
00719
00721 template<unsigned int Size>
00722 struct FixedSizeBestChoiceLRU
00723 {
00724 typedef FixedSizePseudoLRU<Size> Type;
00725 };
00726
00728 template<>
00729 struct FixedSizeBestChoiceLRU<1>
00730 {
00731 typedef FixedSizeLRU<1> Type;
00732 };
00733
00735 template<>
00736 struct FixedSizeBestChoiceLRU<2>
00737 {
00738 typedef FixedSizeLRU<2> Type;
00739 };
00740
00741 }
00742
00743
00748 class FixedSizeLRUPolicy
00749 {
00750 public:
00751 template<size_t SetSize>
00752 struct LRU
00753 {
00754 typedef Implementation::FixedSizeLRU<SetSize> Type;
00755 };
00756 };
00757
00763 class FixedSizePseudoLRUPolicy
00764 {
00765 public:
00766 template<size_t SetSize>
00767 struct LRU
00768 {
00769 typedef Implementation::FixedSizePseudoLRU<SetSize> Type;
00770 };
00771 };
00772
00777 class FixedSizeBestChoiceLRUPolicy
00778 {
00779 public:
00780 template<size_t SetSize>
00781 struct LRU
00782 {
00783 typedef typename Implementation::FixedSizeBestChoiceLRU<SetSize>::Type Type;
00784 };
00785 };
00786
00787
00799 template<
00800 typename K,
00801 typename T,
00802 unsigned int CacheSize,
00803 unsigned int Associativity = 1,
00804 typename LRUPolicy = FixedSizeBestChoiceLRUPolicy,
00805 typename HashFold = CS::Utility::HashFoldingFNV1>
00806 class FixedSizeCache
00807 {
00808 public:
00809
00810 typedef Implementation::SetNumberComputer<Associativity> SetComputer;
00811 static const unsigned int NumberOfSets =
00812 (SetComputer::template Helper<CacheSize>::value);
00813 static const unsigned int SetSize = CacheSize / NumberOfSets;
00814
00815 typedef FixedSizeCache<K, T, CacheSize, Associativity, LRUPolicy> ThisType;
00816 typedef Implementation::FixedSizeCacheSet<K, T, SetSize, LRUPolicy> SetType;
00817
00826 bool Insert (const K& key, const T& data)
00827 {
00828
00829 uint h = csHashComputer<K>::ComputeHash (key) & (NumberOfSets-1);
00830 h = HashFold::FoldHash(h);
00831
00832 SetType& set = sets[h];
00833
00834 return set.Insert (key, data);
00835 }
00836
00844 void Update (const K& key, const T& data)
00845 {
00846
00847 uint h = csHashComputer<K>::ComputeHash (key) & (NumberOfSets-1);
00848 h = HashFold::FoldHash(h);
00849
00850 SetType& set = sets[h];
00851
00852 set.Update (key, data);
00853 }
00854
00861 void InsertOrUpdate (const K& key, const T& data)
00862 {
00863
00864 uint h = csHashComputer<K>::ComputeHash (key) & (NumberOfSets-1);
00865 h = HashFold::FoldHash(h);
00866
00867 SetType& set = sets[h];
00868
00869 set.InsertOrUpdate (key, data);
00870 }
00871
00879 bool Get (const K& key, T& data)
00880 {
00881
00882 uint h = csHashComputer<K>::ComputeHash (key) & (NumberOfSets-1);
00883 h = HashFold::FoldHash(h);
00884
00885 SetType& set = sets[h];
00886
00887 return set.Get (key, data);
00888 }
00889
00890 private:
00892 SetType sets[NumberOfSets];
00893
00894
00895
00896 CS_COMPILE_ASSERT(CS::Meta::IsLog2<NumberOfSets>::value);
00897 };
00898
00899 }
00900 }
00901
00902
00903 #include "csutil/custom_new_enable.h"
00904 #endif