00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
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
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 }
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
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
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
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
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
00473
00474
00475
00476
00477
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
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
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 }
00710 }
00711
00712 #endif // __CS_CSUTIL_GENERICRESOURCECACHE_H__