CrystalSpace

Public API Reference

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.7.6.1