csutil/fixedsizecache.h
00001 /* 00002 Copyright (C) 2007 by Marten Svanfeldt 00003 00004 This library is free software; you can redistribute it and/or 00005 modify it under the terms of the GNU Library 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_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 // Check if data exists in set 00152 ElementType* e = Find(key); 00153 if(e) 00154 { 00155 return false; 00156 } 00157 00158 // Find a spot to put it 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 // Find a spot to put it 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 // Use linear probing for now 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 // Get bit 2*index 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 // Get bit 2*index 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 // Get bit 2*index+1 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 // Get bit 2*index+1 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 // Check that some invariants are met 00371 // Require that size is log2 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 // Magic... 00519 size_t currNode = 0; 00520 size_t currStep = Size/2; 00521 00522 while (currStep > 0) 00523 { 00524 // Check if we go left or right at current node 00525 if (index < currStep) 00526 { 00527 // Left 00528 SetBit (currNode); 00529 currNode = 2*currNode + 1; 00530 } 00531 else 00532 { 00533 // Right 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 // Traverse tree until we find what we want 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 // Go right 00556 currVictim += currStep; 00557 currNode = 2*currNode + 2; 00558 } 00559 else 00560 { 00561 // Go left 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 // Check that some invariants are met 00596 // Require that size is log2 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 } // namespace Implementation 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 // Some computed constants 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 // Find which set 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 // Find which set 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 // Find which set 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 // Find which set 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 // Check that some invariants are met 00895 // Require that number of sets is log2 00896 CS_COMPILE_ASSERT(CS::Meta::IsLog2<NumberOfSets>::value); 00897 }; 00898 00899 } 00900 } 00901 00902 00903 #include "csutil/custom_new_enable.h" 00904 #endif
Generated for Crystal Space 2.0 by doxygen 1.6.1