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 00140 template<typename TimeType = uint> 00141 class PurgeConditionAfterTime 00142 { 00147 TimeType purgeAge; 00148 public: 00149 struct AddParameter 00150 { 00151 AddParameter () {} 00152 }; 00153 struct StoredAuxiliaryInfo 00154 { 00155 TimeType lastTimeUsed; 00156 00157 template<typename ResourceCacheType> 00158 StoredAuxiliaryInfo (const ResourceCacheType& cache, 00159 const AddParameter& param) : lastTimeUsed(0) {} 00160 }; 00161 00162 PurgeConditionAfterTime (TimeType purgeAge = 60) 00163 : purgeAge (purgeAge) {} 00164 00166 template<typename ResourceCacheType> 00167 void MarkActive (const ResourceCacheType& cache, 00168 StoredAuxiliaryInfo& elementInfo) 00169 { 00170 elementInfo.lastTimeUsed = cache.GetCurrentTime(); 00171 } 00172 00173 template<typename ResourceCacheType> 00174 bool IsPurgeable (const ResourceCacheType& cache, 00175 const StoredAuxiliaryInfo& elementInfo, 00176 const typename ResourceCacheType::CachedType& data) 00177 { 00178 return (cache.GetCurrentTime() > 00179 elementInfo.lastTimeUsed + purgeAge); 00180 } 00181 }; 00182 00183 } // namespace ResourceCache 00184 00192 template<typename T, 00193 typename _TimeType = uint, 00194 typename _ResourceSorting = ResourceCache::SortingNone, 00195 typename _ReuseCondition = ResourceCache::ReuseConditionAfterTime<_TimeType>, 00196 typename _PurgeCondition = ResourceCache::PurgeConditionAfterTime<_TimeType> > 00197 class GenericResourceCache 00198 { 00199 public: 00200 typedef T CachedType; 00201 typedef _TimeType TimeType; 00202 typedef _ResourceSorting ResourceSorting; 00203 typedef _ReuseCondition ReuseCondition; 00204 typedef _PurgeCondition PurgeCondition; 00205 00206 protected: 00207 typedef typename ResourceSorting::KeyType ResourceSortingKeyType; 00208 typedef typename ReuseCondition::AddParameter ReuseConditionAddParameter; 00209 typedef typename ReuseCondition::StoredAuxiliaryInfo ReuseConditionAuxiliary; 00210 typedef typename PurgeCondition::AddParameter PurgeConditionAddParameter; 00211 typedef typename PurgeCondition::StoredAuxiliaryInfo PurgeConditionAuxiliary; 00212 00213 template<typename Super> 00214 struct DataStorage : public CS::Memory::CustomAllocatedDerived<Super> 00215 { 00216 T data; 00217 00218 template<typename A> 00219 DataStorage (const T& data, const A& a) : 00220 CS::Memory::CustomAllocatedDerived<Super> (a), data (data) {} 00221 }; 00222 struct Element : public DataStorage<ReuseConditionAuxiliary>, 00223 public PurgeConditionAuxiliary 00224 { 00225 00226 00227 Element (const T& data, 00228 const ReuseConditionAuxiliary& reuseAux, 00229 const PurgeConditionAuxiliary& purgeAux) 00230 : DataStorage<ReuseConditionAuxiliary> (data, reuseAux), 00231 PurgeConditionAuxiliary (purgeAux) 00232 { 00233 } 00234 00235 ReuseConditionAuxiliary& GetReuseAuxiliary() 00236 { return *(static_cast<ReuseConditionAuxiliary*> (this)); } 00237 const ReuseConditionAuxiliary& GetReuseAuxiliary() const 00238 { return *(static_cast<const ReuseConditionAuxiliary*> (this)); } 00239 00240 PurgeConditionAuxiliary& GetPurgeAuxiliary() 00241 { return *(static_cast<PurgeConditionAuxiliary*> (this)); } 00242 const PurgeConditionAuxiliary& GetPurgeAuxiliary() const 00243 { return *(static_cast<const PurgeConditionAuxiliary*> (this)); } 00244 }; 00245 00246 struct ElementWrapper 00247 { 00248 Element* ptr; 00249 00250 ElementWrapper () {} 00251 ElementWrapper (Element* ptr) : ptr (ptr) {} 00252 ElementWrapper (const ElementWrapper& other) : ptr (other.ptr) { } 00253 00254 Element* operator->() { return ptr; } 00255 operator Element*() const { return ptr; } 00256 00257 // FIXME: Comparisons are fragile, rely on csComparator only using < 00258 bool operator== (const ElementWrapper& other) const 00259 { return ptr == other.ptr; } 00260 00261 bool operator< (const ElementWrapper& other) const 00262 { 00263 // @@@ Make more efficient... 00264 if (ResourceSorting::IsEqual (ptr->data, other.ptr->data)) return false; 00265 if (ResourceSorting::IsLargerEqual (ptr->data, other.ptr->data)) return false; 00266 return true; 00267 } 00268 bool operator< (const ResourceSortingKeyType& other) const 00269 { 00270 // @@@ Make more efficient... 00271 if (ResourceSorting::IsEqual (ptr->data, other)) return false; 00272 if (ResourceSorting::IsLargerEqual (ptr->data, other)) return false; 00273 return true; 00274 } 00275 friend bool operator< (const ResourceSortingKeyType& key, 00276 const ElementWrapper& el) 00277 { 00278 // @@@ Make more efficient... 00279 if (ResourceSorting::IsEqual (el.ptr->data, key)) return false; 00280 if (ResourceSorting::IsLargerEqual (el.ptr->data, key)) return true; 00281 return false; 00282 } 00283 00284 }; 00285 00286 csBlockAllocator<Element> elementAlloc; 00287 // Tree of available resources 00288 struct AvailableResourcesWrapper : public ReuseCondition 00289 { 00290 private: 00291 csBlockAllocator<Element>& elementAlloc; 00292 struct RBTraverser 00293 { 00294 csBlockAllocator<Element>& elementAlloc; 00295 00296 RBTraverser (csBlockAllocator<Element>& elementAlloc) : 00297 elementAlloc (elementAlloc) {} 00298 00299 void Process (Element* el) 00300 { 00301 elementAlloc.Free (el); 00302 } 00303 }; 00304 public: 00305 csRedBlackTree<ElementWrapper> v; 00306 00307 AvailableResourcesWrapper (const ReuseCondition& other, 00308 csBlockAllocator<Element>& elementAlloc) 00309 : ReuseCondition (other), elementAlloc (elementAlloc) { } 00310 00311 void Destroy() 00312 { 00313 RBTraverser trav (elementAlloc); 00314 v.TraverseInOrder (trav); 00315 v.DeleteAll(); 00316 } 00317 } availableResources; 00318 // List of active resources 00319 struct ActiveResourcesWrapper : public PurgeCondition 00320 { 00321 protected: 00322 csBlockAllocator<Element>& elementAlloc; 00323 public: 00324 csList<ElementWrapper> v; 00325 00326 ActiveResourcesWrapper (const PurgeCondition& other, 00327 csBlockAllocator<Element>& elementAlloc) 00328 : PurgeCondition (other), elementAlloc (elementAlloc) { } 00329 00330 void Destroy() 00331 { 00332 typename csList<ElementWrapper>::Iterator listIt (v); 00333 while (listIt.HasNext()) 00334 { 00335 Element* el = listIt.Next(); 00336 elementAlloc.Free (el); 00337 } 00338 v.DeleteAll(); 00339 } 00340 } activeResources; 00341 00342 TimeType currentTime; 00346 TimeType lastPurgeAged; 00348 bool clearReq; 00349 00350 ReuseCondition& GetReuseCondition() 00351 { return *(static_cast<ReuseCondition*> (&availableResources)); } 00352 PurgeCondition& GetPurgeCondition() 00353 { return *(static_cast<PurgeCondition*> (&activeResources)); } 00354 00355 class SearchDataTraverser 00356 { 00357 T* entry; 00358 Element*& ret; 00359 00360 public: 00361 SearchDataTraverser (T* entry, Element*& ret) 00362 : entry (entry), ret (ret) {} 00363 00364 bool Process (Element* el) 00365 { 00366 if (&(el->data) == entry) 00367 { 00368 ret = el; 00369 return false; 00370 } 00371 return true; 00372 } 00373 }; 00374 00375 Element* ElementFromData (T* entry) 00376 { 00377 // Given some cached data, obtain the Element from it. 00378 00379 /* @@@ Right now the only way is to search both the active and 00380 * available resource lists. */ 00381 00382 // Search active resource list. 00383 typename csList<ElementWrapper>::Iterator listIt (activeResources.v); 00384 while (listIt.HasNext()) 00385 { 00386 Element* el = listIt.Next(); 00387 if (&(el->data) == entry) return el; 00388 } 00389 00390 // Search available resource tree. 00391 Element* treeSearchRet = 0; 00392 SearchDataTraverser sdt (entry, treeSearchRet); 00393 availableResources.v.TraverseInOrder (sdt); 00394 if (treeSearchRet != 0) return treeSearchRet; 00395 00396 CS_ASSERT_MSG("Element is not from this resource cache", false); 00397 return 0; 00398 } 00399 public: 00401 TimeType agedPurgeInterval; 00402 00403 GenericResourceCache (const ReuseCondition& reuse = ReuseCondition(), 00404 const PurgeCondition& purge = PurgeCondition()) : 00405 availableResources (reuse, elementAlloc), 00406 activeResources (purge, elementAlloc), 00407 currentTime (0), lastPurgeAged (0), 00408 clearReq (false), agedPurgeInterval (60) 00409 { 00410 } 00411 00412 ~GenericResourceCache() 00413 { 00414 } 00415 00421 void Clear (bool instaClear = false) 00422 { 00423 if (instaClear) 00424 { 00425 availableResources.Destroy (); 00426 activeResources.Destroy (); 00427 clearReq = false; 00428 } 00429 else 00430 // Don't clear just yet, rather, clear when we advance the next time 00431 clearReq = true; 00432 } 00433 00434 #ifdef CS_DEBUG 00435 class VerifyTraverser 00436 { 00437 Element* el; 00438 public: 00439 VerifyTraverser (Element* el) : el (el) {} 00440 00441 bool Process (Element* el) 00442 { 00443 CS_ASSERT(el != this->el); 00444 return true; 00445 } 00446 }; 00447 #endif 00448 00449 void VerifyElementNotInTree (Element* el) 00450 { 00451 (void)el; 00452 #ifdef CS_DEBUG 00453 VerifyTraverser verify (el); 00454 availableResources.v.TraverseInOrder (verify); 00455 #endif 00456 } 00457 00462 void AdvanceTime (TimeType time) 00463 { 00464 if (clearReq) 00465 { 00466 Clear (true); 00467 clearReq = false; 00468 } 00469 00470 currentTime = time; 00471 00472 if (time >= lastPurgeAged + agedPurgeInterval) 00473 { 00474 typename csRedBlackTree<ElementWrapper>::Iterator treeIt ( 00475 availableResources.v.GetIterator ()); 00476 while (treeIt.HasNext()) 00477 { 00478 Element* el = treeIt.PeekNext (); 00479 if (GetPurgeCondition().IsPurgeable (*this, 00480 el->GetPurgeAuxiliary(), el->data)) 00481 { 00482 availableResources.v.Delete (treeIt); 00483 VerifyElementNotInTree (el); 00484 elementAlloc.Free (el); 00485 } 00486 else 00487 { 00488 treeIt.Next (); 00489 } 00490 } 00491 00492 lastPurgeAged = time; 00493 } 00494 00495 typename csList<ElementWrapper>::Iterator listIt (activeResources.v); 00496 while (listIt.HasNext()) 00497 { 00498 ElementWrapper& el = listIt.Next(); 00499 00500 if (GetReuseCondition().IsReusable (*this, 00501 el->GetReuseAuxiliary(), el->data)) 00502 { 00503 VerifyElementNotInTree (el); 00504 availableResources.v.Insert (el); 00505 activeResources.v.Delete (listIt); 00506 } 00507 } 00508 } 00509 TimeType GetCurrentTime() const { return currentTime; } 00510 00512 T* Query (const ResourceSortingKeyType& key = 00513 ResourceSortingKeyType(), bool exact = false) 00514 { 00515 const csRedBlackTree<ElementWrapper>& constTree = availableResources.v; 00516 ElementWrapper const* el; 00517 if (exact) 00518 el = constTree.Find (key); 00519 else 00520 el = constTree.FindSmallestGreaterEqual (key); 00521 if (el != 0) 00522 { 00523 ElementWrapper myElement = *el; 00524 availableResources.v.DeleteExact (el); 00525 VerifyElementNotInTree (myElement); 00526 activeResources.v.PushFront (myElement); 00527 GetPurgeCondition().MarkActive (*this, myElement->GetPurgeAuxiliary()); 00528 GetReuseCondition().MarkActive (*this, myElement->GetReuseAuxiliary()); 00529 return &(myElement->data); 00530 } 00531 return 0; 00532 } 00537 T* AddActive (const T& value, 00538 const ReuseConditionAddParameter& reuseParam = ReuseConditionAddParameter (), 00539 const PurgeConditionAddParameter& purgeParam = PurgeConditionAddParameter ()) 00540 { 00541 ReuseConditionAuxiliary reuseAux (*this, reuseParam); 00542 PurgeConditionAuxiliary purgeAux (*this, purgeParam); 00543 Element* el = elementAlloc.Alloc (value, reuseAux, purgeAux); 00544 GetPurgeCondition().MarkActive (*this, el->GetPurgeAuxiliary()); 00545 GetReuseCondition().MarkActive (*this, el->GetReuseAuxiliary()); 00546 activeResources.v.PushFront (el); 00547 return &(el->data); 00548 } 00549 00558 void NudgeLastUsedTime (T* data) 00559 { 00560 Element* el = static_cast<Element*> ( 00561 DataStorage<typename ReuseCondition::StoredAuxiliaryInfo>::CastFromData (data)); 00562 el->lastTimeUsed = currentTime; 00563 } 00564 00565 00572 void SetAvailable (T* data) 00573 { 00574 Element* el = ElementFromData (data); 00575 00576 VerifyElementNotInTree (el); 00577 availableResources.v.Insert (el); 00578 activeResources.v.Delete (el); 00579 } 00580 00584 void RemoveActive (T* data) 00585 { 00586 Element* el = ElementFromData (data); 00587 00588 activeResources.v.Delete (el); 00589 elementAlloc.Free (el); 00590 } 00591 00596 typename ReuseCondition::StoredAuxiliaryInfo* GetReuseAuxiliary ( 00597 T* entry) 00598 { 00599 return &(ElementFromData (entry)->GetReuseAuxiliary()); 00600 } 00601 00606 typename PurgeCondition::StoredAuxiliaryInfo* GetPurgeAuxiliary ( 00607 T* entry) 00608 { 00609 return &(ElementFromData (entry)->GetPurgeAuxiliary()); 00610 } 00611 }; 00612 00613 } // namespace Utility 00614 } // namespace CS 00615 00616 #endif // __CS_CSUTIL_GENERICRESOURCECACHE_H__
Generated for Crystal Space 1.4.0 by doxygen 1.5.8