CrystalSpace

Public API Reference

csutil/genericresourcecache.h
00001 /*
00002     Copyright (C) 2007-2008 by Frank Richter
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_GENERICRESOURCECACHE_H__
00020 #define __CS_CSUTIL_GENERICRESOURCECACHE_H__
00021 
00022 #include "csutil/blockallocator.h"
00023 #include "csutil/comparator.h"
00024 #include "csutil/list.h"
00025 #include "csutil/redblacktree.h"
00026 
00027 namespace CS
00028 {
00029   namespace Utility
00030   {
00034     namespace ResourceCache
00035     {
00037       class SortingNone
00038       {
00039       public:
00040         struct KeyType {};
00041           
00042         template<typename T1, typename T2>
00043         static bool IsLargerEqual (const T1&, const T2&)
00044         {
00045           return 0;
00046         }
00047         template<typename T1, typename T2>
00048         static bool IsEqual (const T1&, const T2&)
00049         {
00050           return 0;
00051         }
00052       };
00053       
00057       template<typename TimeType = uint>
00058       class ReuseConditionAfterTime
00059       {
00060       public:
00061         struct AddParameter
00062         {
00064           TimeType lifeTime;
00065           
00066           AddParameter (TimeType lifeTime = 0) : lifeTime (lifeTime) {}
00067         };
00068         struct StoredAuxiliaryInfo
00069         {
00071           TimeType timeToDie;
00072           TimeType lifeTime;
00073           
00074           template<typename ResourceCacheType>
00075           StoredAuxiliaryInfo (const ResourceCacheType& cache, 
00076             const AddParameter& param) : 
00077             timeToDie (0),
00078             lifeTime (param.lifeTime)
00079           {}
00080         };
00081         
00083         template<typename ResourceCacheType>
00084         void MarkActive (const ResourceCacheType& cache,
00085           StoredAuxiliaryInfo& elementInfo)
00086         {
00087           elementInfo.timeToDie = cache.GetCurrentTime() + elementInfo.lifeTime;
00088         }
00089 
00090         template<typename ResourceCacheType>
00091         bool IsReusable (const ResourceCacheType& cache,
00092           const StoredAuxiliaryInfo& elementInfo,
00093           const typename ResourceCacheType::CachedType& data)
00094         {
00095           return cache.GetCurrentTime() > elementInfo.timeToDie;
00096         }
00097       };
00098 
00100       class ReuseConditionFlagged
00101       {
00102       public:
00103         struct AddParameter
00104         {
00105           AddParameter () {}
00106         };
00107         struct StoredAuxiliaryInfo
00108         {
00110           bool reusable;
00111           
00112           template<typename ResourceCacheType>
00113           StoredAuxiliaryInfo (const ResourceCacheType& cache, 
00114             const AddParameter& param) : reusable (false)
00115           {}
00116         };
00117         
00118         
00120         template<typename ResourceCacheType>
00121         void MarkActive (const ResourceCacheType& cache,
00122           StoredAuxiliaryInfo& elementInfo)
00123         {
00124           // Reset flag
00125           elementInfo.reusable = false;
00126         }
00127 
00128         template<typename ResourceCacheType>
00129         bool IsReusable (const ResourceCacheType& cache,
00130           const StoredAuxiliaryInfo& elementInfo,
00131           const typename ResourceCacheType::CachedType& data)
00132         {
00133           return elementInfo.reusable;
00134         }
00135       };
00136       
00141       class ReuseIfOnlyOneRef
00142       {
00143       public:
00144         struct AddParameter
00145         {
00146           AddParameter () {}
00147         };
00148         struct StoredAuxiliaryInfo
00149         {
00150           template<typename ResourceCacheType>
00151           StoredAuxiliaryInfo (const ResourceCacheType& cache, 
00152             const AddParameter& param) {}
00153         };
00154         
00155         template<typename ResourceCacheType>
00156         void MarkActive (const ResourceCacheType& cache,
00157             StoredAuxiliaryInfo& elementInfo)
00158         { }
00159   
00160         template<typename ResourceCacheType>
00161         bool IsReusable (const ResourceCacheType& cache,
00162           const StoredAuxiliaryInfo& elementInfo,
00163           const typename ResourceCacheType::CachedType& data)
00164         {
00165           return data->GetRefCount() == 1;
00166         }
00167       };
00168       
00172       class ReuseAlways
00173       {
00174       public:
00175         struct AddParameter
00176         {
00177           AddParameter () {}
00178         };
00179         struct StoredAuxiliaryInfo
00180         {
00181           template<typename ResourceCacheType>
00182           StoredAuxiliaryInfo (const ResourceCacheType& cache, 
00183             const AddParameter& param) {}
00184         };
00185         
00186         template<typename ResourceCacheType>
00187         void MarkActive (const ResourceCacheType& cache,
00188             StoredAuxiliaryInfo& elementInfo)
00189         { }
00190   
00191         template<typename ResourceCacheType>
00192         bool IsReusable (const ResourceCacheType& cache,
00193           const StoredAuxiliaryInfo& elementInfo,
00194           const typename ResourceCacheType::CachedType& data)
00195         {
00196           return true;
00197         }
00198       };
00199       
00203       template<typename TimeType = uint>
00204       class PurgeConditionAfterTime
00205       {
00210         TimeType purgeAge;
00211       public:
00212         struct AddParameter
00213         {
00214           AddParameter () {}
00215         };
00216         struct StoredAuxiliaryInfo
00217         {
00218           TimeType lastTimeUsed;
00219           
00220           template<typename ResourceCacheType>
00221           StoredAuxiliaryInfo (const ResourceCacheType& cache, 
00222             const AddParameter& param) : lastTimeUsed(0) {}
00223         };
00224         
00225         PurgeConditionAfterTime (TimeType purgeAge = 60)
00226           : purgeAge (purgeAge) {}
00227         
00229         template<typename ResourceCacheType>
00230         void MarkActive (const ResourceCacheType& cache,
00231           StoredAuxiliaryInfo& elementInfo)
00232         {
00233           elementInfo.lastTimeUsed = cache.GetCurrentTime();
00234         }
00235 
00236         template<typename ResourceCacheType>
00237         bool IsPurgeable (const ResourceCacheType& cache,
00238           const StoredAuxiliaryInfo& elementInfo,
00239           const typename ResourceCacheType::CachedType& data)
00240         {
00241           return (cache.GetCurrentTime() > 
00242             elementInfo.lastTimeUsed + purgeAge);
00243         }
00244       };
00245 
00250       class PurgeIfOnlyOneRef
00251       {
00252       public:
00253         struct AddParameter
00254         {
00255           AddParameter () {}
00256         };
00257         struct StoredAuxiliaryInfo
00258         {
00259           template<typename ResourceCacheType>
00260           StoredAuxiliaryInfo (const ResourceCacheType& cache, 
00261             const AddParameter& param) {}
00262         };
00263         
00264         template<typename ResourceCacheType>
00265         void MarkActive (const ResourceCacheType& cache,
00266             StoredAuxiliaryInfo& elementInfo)
00267         { }
00268   
00269         template<typename ResourceCacheType>
00270         bool IsPurgeable (const ResourceCacheType& cache,
00271           StoredAuxiliaryInfo& elementInfo,
00272           const typename ResourceCacheType::CachedType& data)
00273         {
00274           return data->GetRefCount() == 1;
00275         }
00276       };
00277       
00278     } // namespace ResourceCache
00279     
00287     template<typename T,
00288       typename _TimeType = uint, 
00289       typename _ResourceSorting = ResourceCache::SortingNone,
00290       typename _ReuseCondition = ResourceCache::ReuseConditionAfterTime<_TimeType>,
00291       typename _PurgeCondition = ResourceCache::PurgeConditionAfterTime<_TimeType> >
00292     class GenericResourceCache
00293     {
00294     public:
00295       typedef T CachedType;
00296       typedef _TimeType TimeType;
00297       typedef _ResourceSorting ResourceSorting;
00298       typedef _ReuseCondition ReuseCondition;
00299       typedef _PurgeCondition PurgeCondition;
00300       
00301     protected:
00302       typedef typename ResourceSorting::KeyType ResourceSortingKeyType;
00303       typedef typename ReuseCondition::AddParameter ReuseConditionAddParameter;
00304       typedef typename ReuseCondition::StoredAuxiliaryInfo ReuseConditionAuxiliary;
00305       typedef typename PurgeCondition::AddParameter PurgeConditionAddParameter;
00306       typedef typename PurgeCondition::StoredAuxiliaryInfo PurgeConditionAuxiliary;
00307 
00308       template<typename Super>
00309       struct DataStorage : public CS::Memory::CustomAllocatedDerived<Super>
00310       {
00311         T data;
00312         
00313         template<typename A>
00314         DataStorage (const T& data, const A& a) : 
00315           CS::Memory::CustomAllocatedDerived<Super> (a), data (data) {}
00316       };
00317       struct Element : public DataStorage<ReuseConditionAuxiliary>,
00318                        public PurgeConditionAuxiliary
00319       {
00320         
00321         
00322         Element (const T& data,
00323           const ReuseConditionAuxiliary& reuseAux,
00324           const PurgeConditionAuxiliary& purgeAux)
00325           : DataStorage<ReuseConditionAuxiliary> (data, reuseAux),
00326             PurgeConditionAuxiliary (purgeAux)
00327         {
00328         }
00329         
00330         ReuseConditionAuxiliary& GetReuseAuxiliary()
00331         { return *(static_cast<ReuseConditionAuxiliary*> (this)); }
00332         const ReuseConditionAuxiliary& GetReuseAuxiliary() const
00333         { return *(static_cast<const ReuseConditionAuxiliary*> (this)); }
00334         
00335         PurgeConditionAuxiliary& GetPurgeAuxiliary()
00336         { return *(static_cast<PurgeConditionAuxiliary*> (this)); }
00337         const PurgeConditionAuxiliary& GetPurgeAuxiliary() const
00338         { return *(static_cast<const PurgeConditionAuxiliary*> (this)); }
00339       };
00340       
00341       struct ElementWrapper
00342       {
00343         Element* ptr;
00344         
00345         ElementWrapper () {}
00346         ElementWrapper (Element* ptr) : ptr (ptr) {}
00347         ElementWrapper (const ElementWrapper& other) : ptr (other.ptr) { }
00348         
00349         Element* operator->() { return ptr; }
00350         
00351         // Comparisons among ElementWrappers
00352         bool operator== (const ElementWrapper& other) const
00353         {
00354           return ResourceSorting::IsEqual (ptr->data, other.ptr->data);
00355         }
00356         bool operator<= (const ElementWrapper& other) const
00357         {
00358           return ResourceSorting::IsLargerEqual (ptr->data, other.ptr->data);
00359         }
00360         
00361         // Comparisons against ResourceSortingKeyType
00362         bool operator== (const ResourceSortingKeyType& other) const
00363         {
00364           return ResourceSorting::IsEqual (ptr->data, other);
00365         }
00366         bool operator<= (const ResourceSortingKeyType& other) const
00367         {
00368           return ResourceSorting::IsLargerEqual (ptr->data, other);
00369         }
00370         friend bool operator<= (const ResourceSortingKeyType& key, 
00371                                 const ElementWrapper& el)
00372         {
00373           return ResourceSorting::IsLargerEqual (key, el.ptr->data);
00374         }
00375         
00376       };
00377       
00378       csBlockAllocator<Element> elementAlloc;
00379       typedef csRedBlackTree<ElementWrapper,
00380           CS::Container::DefaultRedBlackTreeAllocator<ElementWrapper>,
00381           CS::Container::RedBlackTreeOrderingPartial> AvailableResourcesTree;
00382       // Tree of available resources
00383       struct AvailableResourcesWrapper : public ReuseCondition
00384       {
00385       private:
00386         csBlockAllocator<Element>& elementAlloc;
00387         struct RBTraverser
00388         {
00389           csBlockAllocator<Element>& elementAlloc;
00390           
00391           RBTraverser (csBlockAllocator<Element>& elementAlloc) :
00392             elementAlloc (elementAlloc) {}
00393           
00394           void operator() (ElementWrapper& el)
00395           {
00396             elementAlloc.Free (el.ptr);
00397           }
00398         };
00399       public:
00400         AvailableResourcesTree v;
00401         
00402         AvailableResourcesWrapper (const ReuseCondition& other,
00403           csBlockAllocator<Element>& elementAlloc)
00404           : ReuseCondition (other), elementAlloc (elementAlloc) { }
00405         
00406         void Destroy()
00407         {
00408           RBTraverser trav (elementAlloc);
00409           v.TraverseInOrder (trav);
00410           v.DeleteAll();
00411         }
00412       } availableResources;
00413       // List of active resources
00414       struct ActiveResourcesWrapper : public PurgeCondition
00415       {
00416       protected:
00417         csBlockAllocator<Element>& elementAlloc;
00418       public:
00419         csList<ElementWrapper> v;
00420         
00421         ActiveResourcesWrapper (const PurgeCondition& other,
00422           csBlockAllocator<Element>& elementAlloc)
00423           : PurgeCondition (other), elementAlloc (elementAlloc) { }
00424         
00425         void Destroy()
00426         {
00427           typename csList<ElementWrapper>::Iterator listIt (v);
00428           while (listIt.HasNext())
00429           {
00430             Element* el = listIt.Next().ptr;
00431             elementAlloc.Free (el);
00432           }
00433           v.DeleteAll();
00434         }
00435       } activeResources;
00436       
00437       TimeType currentTime;
00441       TimeType lastPurgeAged;
00443       bool clearReq;
00444       
00445       ReuseCondition& GetReuseCondition()
00446       { return *(static_cast<ReuseCondition*> (&availableResources)); }
00447       PurgeCondition& GetPurgeCondition()
00448       { return *(static_cast<PurgeCondition*> (&activeResources)); }
00449       
00450       class SearchDataTraverser
00451       {
00452         T* entry;
00453         Element*& ret;
00454         
00455       public:
00456         SearchDataTraverser (T* entry, Element*& ret) 
00457           : entry (entry), ret (ret) {}
00458         
00459         bool operator() (ElementWrapper& el)
00460         {
00461           if (&(el.ptr->data) == entry)
00462           {
00463             ret = el.ptr;
00464             return false;
00465           }
00466           return true;
00467         }
00468       };
00469       
00470       Element* ElementFromData (T* entry)
00471       {
00472         // Given some cached data, obtain the Element from it.
00473         
00474         /* @@@ Right now the only way is to search both the active and
00475          * available resource lists. */
00476         
00477         // Search active resource list.
00478         typename csList<ElementWrapper>::Iterator listIt (activeResources.v);
00479         while (listIt.HasNext())
00480         {
00481           Element* el = listIt.Next().ptr;
00482           if (&(el->data) == entry) return el;
00483         }
00484         
00485         // Search available resource tree.
00486         Element* treeSearchRet = 0;
00487         SearchDataTraverser sdt (entry, treeSearchRet);
00488         availableResources.v.TraverseInOrder (sdt);
00489         if (treeSearchRet != 0) return treeSearchRet;
00490         
00491         CS_ASSERT_MSG("Element is not from this resource cache", false);
00492         return 0;
00493       }
00494     public:
00496       TimeType agedPurgeInterval;
00497     
00498       GenericResourceCache (const ReuseCondition& reuse = ReuseCondition(),
00499         const PurgeCondition& purge = PurgeCondition()) : 
00500         availableResources (reuse, elementAlloc),
00501         activeResources (purge, elementAlloc), 
00502         currentTime (0), lastPurgeAged (0),
00503         clearReq (false), agedPurgeInterval (60)
00504       {
00505       }
00506       
00507       ~GenericResourceCache()
00508       {
00509         availableResources.Destroy ();
00510       }
00511 
00517       void Clear (bool instaClear = false)
00518       {
00519         if (instaClear)
00520         {
00521           availableResources.Destroy ();
00522           activeResources.Destroy ();
00523           clearReq = false;
00524         }
00525         else
00526           // Don't clear just yet, rather, clear when we advance the next time
00527           clearReq = true;
00528       }
00529       
00530 #ifdef CS_DEBUG
00531       class VerifyTraverser
00532       {
00533         Element* el;
00534       public:
00535         VerifyTraverser (Element* el) : el (el) {}
00536         
00537         bool operator() (ElementWrapper& el)
00538         {
00539           CS_ASSERT(el.ptr != this->el);
00540           return true;
00541         }
00542       };
00543 #endif
00544 
00545       void VerifyElementNotInTree (Element* el)
00546       {
00547         (void)el;
00548 #ifdef CS_DEBUG
00549         VerifyTraverser verify (el);
00550         availableResources.v.TraverseInOrder (verify);
00551 #endif
00552       }
00553       
00558       void AdvanceTime (TimeType time)
00559       {
00560         if (clearReq)
00561         {
00562           Clear (true);
00563           clearReq = false;
00564         }
00565         
00566         currentTime = time;
00567         
00568         if (time >= lastPurgeAged + agedPurgeInterval)
00569         {
00570           typename AvailableResourcesTree::Iterator treeIt (
00571             availableResources.v.GetIterator ());
00572           while (treeIt.HasNext())
00573           {
00574             Element* el = treeIt.PeekNext ().ptr;
00575             if (GetPurgeCondition().IsPurgeable (*this, 
00576                 el->GetPurgeAuxiliary(), el->data))
00577             {
00578               availableResources.v.Delete (treeIt);
00579               VerifyElementNotInTree (el);
00580               elementAlloc.Free (el);
00581             }
00582             else
00583             {
00584               treeIt.Next ();
00585             }
00586           }
00587           
00588           lastPurgeAged = time;
00589         }
00590         
00591         typename csList<ElementWrapper>::Iterator listIt (activeResources.v);
00592         while (listIt.HasNext())
00593         {
00594           ElementWrapper& el = listIt.Next();
00595           
00596           if (GetReuseCondition().IsReusable (*this,
00597               el->GetReuseAuxiliary(), el->data))
00598           {
00599             VerifyElementNotInTree (el.ptr);
00600             availableResources.v.Insert (el);
00601             activeResources.v.Delete (listIt);
00602           }
00603         }
00604       }
00605       TimeType GetCurrentTime() const { return currentTime; }
00606 
00608       T* Query (const ResourceSortingKeyType& key = 
00609         ResourceSortingKeyType(), bool exact = false)
00610       {
00611         const AvailableResourcesTree& constTree = availableResources.v;
00612         ElementWrapper const* el;
00613         if (exact)
00614           el = constTree.Find (key);
00615         else
00616           el = constTree.FindGreatestSmallerEqual (key);
00617         if (el != 0)
00618         {
00619           ElementWrapper myElement = *el;
00620           availableResources.v.DeleteExact (el);
00621           VerifyElementNotInTree (myElement.ptr);
00622           activeResources.v.PushFront (myElement);
00623           GetPurgeCondition().MarkActive (*this, myElement->GetPurgeAuxiliary());
00624           GetReuseCondition().MarkActive (*this, myElement->GetReuseAuxiliary());
00625           return &(myElement->data);
00626         }
00627         return 0;
00628       }
00633       T* AddActive (const T& value,
00634         const ReuseConditionAddParameter& reuseParam = ReuseConditionAddParameter (),
00635         const PurgeConditionAddParameter& purgeParam = PurgeConditionAddParameter ())
00636       {
00637         ReuseConditionAuxiliary reuseAux (*this, reuseParam);
00638         PurgeConditionAuxiliary purgeAux (*this, purgeParam);
00639         Element* el = elementAlloc.Alloc (value, reuseAux, purgeAux);
00640         GetPurgeCondition().MarkActive (*this, el->GetPurgeAuxiliary());
00641         GetReuseCondition().MarkActive (*this, el->GetReuseAuxiliary());
00642         activeResources.v.PushFront (el);
00643         return &(el->data);
00644       }
00645 
00654       void NudgeLastUsedTime (T* data)
00655       {
00656         Element* el = static_cast<Element*> (
00657           DataStorage<typename ReuseCondition::StoredAuxiliaryInfo>::CastFromData (data));
00658         el->lastTimeUsed = currentTime;
00659       }
00660 
00661 
00668       void SetAvailable (T* data)
00669       {
00670         Element* el = ElementFromData (data);
00671           
00672         VerifyElementNotInTree (el);
00673         availableResources.v.Insert (el);
00674         activeResources.v.Delete (el);
00675       }
00676       
00680       void RemoveActive (T* data)
00681       {
00682         Element* el = ElementFromData (data);
00683           
00684         activeResources.v.Delete (el);
00685         elementAlloc.Free (el);
00686       }
00687       
00692       typename ReuseCondition::StoredAuxiliaryInfo* GetReuseAuxiliary (
00693         T* entry)
00694       {
00695         return &(ElementFromData (entry)->GetReuseAuxiliary());
00696       }
00697       
00702       typename PurgeCondition::StoredAuxiliaryInfo* GetPurgeAuxiliary (
00703         T* entry)
00704       {
00705         return &(ElementFromData (entry)->GetPurgeAuxiliary());
00706       }
00707     };
00708     
00709   } // namespace Utility
00710 } // namespace CS
00711 
00712 #endif // __CS_CSUTIL_GENERICRESOURCECACHE_H__

Generated for Crystal Space 2.0 by doxygen 1.7.6.1