Public API Reference

csutil/genericresourcecache.h

/*
    Copyright (C) 2007-2008 by Frank Richter

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public
    License along with this library; if not, write to the Free
    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#ifndef __CS_CSUTIL_GENERICRESOURCECACHE_H__
#define __CS_CSUTIL_GENERICRESOURCECACHE_H__

#include "csutil/blockallocator.h"
#include "csutil/comparator.h"
#include "csutil/list.h"
#include "csutil/redblacktree.h"

namespace CS
{
  namespace Utility
  {
    namespace ResourceCache
    {
      class SortingNone
      {
      public:
        struct KeyType {};
          
        template<typename T1, typename T2>
        static bool IsLargerEqual (const T1&, const T2&)
        {
          return 0;
        }
        template<typename T1, typename T2>
        static bool IsEqual (const T1&, const T2&)
        {
          return 0;
        }
      };
      
      template<typename TimeType = uint>
      class ReuseConditionAfterTime
      {
      public:
        struct AddParameter
        {
          TimeType lifeTime;
          
          AddParameter (TimeType lifeTime = 0) : lifeTime (lifeTime) {}
        };
        struct StoredAuxiliaryInfo
        {
          TimeType timeToDie;
          TimeType lifeTime;
          
          template<typename ResourceCacheType>
          StoredAuxiliaryInfo (const ResourceCacheType& cache, 
            const AddParameter& param) : 
            timeToDie (0),
            lifeTime (param.lifeTime)
          {}
        };
        
        template<typename ResourceCacheType>
        void MarkActive (const ResourceCacheType& cache,
          StoredAuxiliaryInfo& elementInfo)
        {
          elementInfo.timeToDie = cache.GetCurrentTime() + elementInfo.lifeTime;
        }

        template<typename ResourceCacheType>
        bool IsReusable (const ResourceCacheType& cache,
          const StoredAuxiliaryInfo& elementInfo,
          const typename ResourceCacheType::CachedType& data)
        {
          return cache.GetCurrentTime() > elementInfo.timeToDie;
        }
      };

      class ReuseConditionFlagged
      {
      public:
        struct AddParameter
        {
          AddParameter () {}
        };
        struct StoredAuxiliaryInfo
        {
          bool reusable;
          
          template<typename ResourceCacheType>
          StoredAuxiliaryInfo (const ResourceCacheType& cache, 
            const AddParameter& param) : reusable (false)
          {}
        };
        
        
        template<typename ResourceCacheType>
        void MarkActive (const ResourceCacheType& cache,
          StoredAuxiliaryInfo& elementInfo)
        {
          // Reset flag
          elementInfo.reusable = false;
        }

        template<typename ResourceCacheType>
        bool IsReusable (const ResourceCacheType& cache,
          const StoredAuxiliaryInfo& elementInfo,
          const typename ResourceCacheType::CachedType& data)
        {
          return elementInfo.reusable;
        }
      };
      
      class ReuseIfOnlyOneRef
      {
      public:
        struct AddParameter
        {
          AddParameter () {}
        };
        struct StoredAuxiliaryInfo
        {
          template<typename ResourceCacheType>
          StoredAuxiliaryInfo (const ResourceCacheType& cache, 
            const AddParameter& param) {}
        };
        
        template<typename ResourceCacheType>
        void MarkActive (const ResourceCacheType& cache,
            StoredAuxiliaryInfo& elementInfo)
        { }
  
        template<typename ResourceCacheType>
        bool IsReusable (const ResourceCacheType& cache,
          const StoredAuxiliaryInfo& elementInfo,
          const typename ResourceCacheType::CachedType& data)
        {
          return data->GetRefCount() == 1;
        }
      };
      
      class ReuseAlways
      {
      public:
        struct AddParameter
        {
          AddParameter () {}
        };
        struct StoredAuxiliaryInfo
        {
          template<typename ResourceCacheType>
          StoredAuxiliaryInfo (const ResourceCacheType& cache, 
            const AddParameter& param) {}
        };
        
        template<typename ResourceCacheType>
        void MarkActive (const ResourceCacheType& cache,
            StoredAuxiliaryInfo& elementInfo)
        { }
  
        template<typename ResourceCacheType>
        bool IsReusable (const ResourceCacheType& cache,
          const StoredAuxiliaryInfo& elementInfo,
          const typename ResourceCacheType::CachedType& data)
        {
          return true;
        }
      };
      
      template<typename TimeType = uint>
      class PurgeConditionAfterTime
      {
        TimeType purgeAge;
      public:
        struct AddParameter
        {
          AddParameter () {}
        };
        struct StoredAuxiliaryInfo
        {
          TimeType lastTimeUsed;
          
          template<typename ResourceCacheType>
          StoredAuxiliaryInfo (const ResourceCacheType& cache, 
            const AddParameter& param) : lastTimeUsed(0) {}
        };
        
        PurgeConditionAfterTime (TimeType purgeAge = 60)
          : purgeAge (purgeAge) {}
        
        template<typename ResourceCacheType>
        void MarkActive (const ResourceCacheType& cache,
          StoredAuxiliaryInfo& elementInfo)
        {
          elementInfo.lastTimeUsed = cache.GetCurrentTime();
        }

        template<typename ResourceCacheType>
        bool IsPurgeable (const ResourceCacheType& cache,
          const StoredAuxiliaryInfo& elementInfo,
          const typename ResourceCacheType::CachedType& data)
        {
          return (cache.GetCurrentTime() > 
            elementInfo.lastTimeUsed + purgeAge);
        }
      };

      class PurgeIfOnlyOneRef
      {
      public:
        struct AddParameter
        {
          AddParameter () {}
        };
        struct StoredAuxiliaryInfo
        {
          template<typename ResourceCacheType>
          StoredAuxiliaryInfo (const ResourceCacheType& cache, 
            const AddParameter& param) {}
        };
        
        template<typename ResourceCacheType>
        void MarkActive (const ResourceCacheType& cache,
            StoredAuxiliaryInfo& elementInfo)
        { }
  
        template<typename ResourceCacheType>
        bool IsPurgeable (const ResourceCacheType& cache,
          StoredAuxiliaryInfo& elementInfo,
          const typename ResourceCacheType::CachedType& data)
        {
          return data->GetRefCount() == 1;
        }
      };
      
    } // namespace ResourceCache
    
    template<typename T,
      typename _TimeType = uint, 
      typename _ResourceSorting = ResourceCache::SortingNone,
      typename _ReuseCondition = ResourceCache::ReuseConditionAfterTime<_TimeType>,
      typename _PurgeCondition = ResourceCache::PurgeConditionAfterTime<_TimeType> >
    class GenericResourceCache
    {
    public:
      typedef T CachedType;
      typedef _TimeType TimeType;
      typedef _ResourceSorting ResourceSorting;
      typedef _ReuseCondition ReuseCondition;
      typedef _PurgeCondition PurgeCondition;
      
    protected:
      typedef typename ResourceSorting::KeyType ResourceSortingKeyType;
      typedef typename ReuseCondition::AddParameter ReuseConditionAddParameter;
      typedef typename ReuseCondition::StoredAuxiliaryInfo ReuseConditionAuxiliary;
      typedef typename PurgeCondition::AddParameter PurgeConditionAddParameter;
      typedef typename PurgeCondition::StoredAuxiliaryInfo PurgeConditionAuxiliary;

      template<typename Super>
      struct DataStorage : public CS::Memory::CustomAllocatedDerived<Super>
      {
        T data;
        
        template<typename A>
        DataStorage (const T& data, const A& a) : 
          CS::Memory::CustomAllocatedDerived<Super> (a), data (data) {}
      };
      struct Element : public DataStorage<ReuseConditionAuxiliary>,
                       public PurgeConditionAuxiliary
      {
        
        
        Element (const T& data,
          const ReuseConditionAuxiliary& reuseAux,
          const PurgeConditionAuxiliary& purgeAux)
          : DataStorage<ReuseConditionAuxiliary> (data, reuseAux),
            PurgeConditionAuxiliary (purgeAux)
        {
        }
        
        ReuseConditionAuxiliary& GetReuseAuxiliary()
        { return *(static_cast<ReuseConditionAuxiliary*> (this)); }
        const ReuseConditionAuxiliary& GetReuseAuxiliary() const
        { return *(static_cast<const ReuseConditionAuxiliary*> (this)); }
        
        PurgeConditionAuxiliary& GetPurgeAuxiliary()
        { return *(static_cast<PurgeConditionAuxiliary*> (this)); }
        const PurgeConditionAuxiliary& GetPurgeAuxiliary() const
        { return *(static_cast<const PurgeConditionAuxiliary*> (this)); }
      };
      
      struct ElementWrapper
      {
        Element* ptr;
        
        ElementWrapper () {}
        ElementWrapper (Element* ptr) : ptr (ptr) {}
        ElementWrapper (const ElementWrapper& other) : ptr (other.ptr) { }
        
        Element* operator->() { return ptr; }
        
        // Comparisons among ElementWrappers
        bool operator== (const ElementWrapper& other) const
        {
          return ResourceSorting::IsEqual (ptr->data, other.ptr->data);
        }
        bool operator<= (const ElementWrapper& other) const
        {
          return ResourceSorting::IsLargerEqual (ptr->data, other.ptr->data);
        }
        
        // Comparisons against ResourceSortingKeyType
        bool operator== (const ResourceSortingKeyType& other) const
        {
          return ResourceSorting::IsEqual (ptr->data, other);
        }
        bool operator<= (const ResourceSortingKeyType& other) const
        {
          return ResourceSorting::IsLargerEqual (ptr->data, other);
        }
        friend bool operator<= (const ResourceSortingKeyType& key, 
                                const ElementWrapper& el)
        {
          return ResourceSorting::IsLargerEqual (key, el.ptr->data);
        }
        
      };
      
      csBlockAllocator<Element> elementAlloc;
      typedef csRedBlackTree<ElementWrapper,
          CS::Container::DefaultRedBlackTreeAllocator<ElementWrapper>,
          CS::Container::RedBlackTreeOrderingPartial> AvailableResourcesTree;
      // Tree of available resources
      struct AvailableResourcesWrapper : public ReuseCondition
      {
      private:
        csBlockAllocator<Element>& elementAlloc;
        struct RBTraverser
        {
          csBlockAllocator<Element>& elementAlloc;
          
          RBTraverser (csBlockAllocator<Element>& elementAlloc) :
            elementAlloc (elementAlloc) {}
          
          void operator() (ElementWrapper& el)
          {
            elementAlloc.Free (el.ptr);
          }
        };
      public:
        AvailableResourcesTree v;
        
        AvailableResourcesWrapper (const ReuseCondition& other,
          csBlockAllocator<Element>& elementAlloc)
          : ReuseCondition (other), elementAlloc (elementAlloc) { }
        
        void Destroy()
        {
          RBTraverser trav (elementAlloc);
          v.TraverseInOrder (trav);
          v.DeleteAll();
        }
      } availableResources;
      // List of active resources
      struct ActiveResourcesWrapper : public PurgeCondition
      {
      protected:
        csBlockAllocator<Element>& elementAlloc;
      public:
        csList<ElementWrapper> v;
        
        ActiveResourcesWrapper (const PurgeCondition& other,
          csBlockAllocator<Element>& elementAlloc)
          : PurgeCondition (other), elementAlloc (elementAlloc) { }
        
        void Destroy()
        {
          typename csList<ElementWrapper>::Iterator listIt (v);
          while (listIt.HasNext())
          {
            Element* el = listIt.Next().ptr;
            elementAlloc.Free (el);
          }
          v.DeleteAll();
        }
      } activeResources;
      
      TimeType currentTime;
      TimeType lastPurgeAged;
      bool clearReq;
      
      ReuseCondition& GetReuseCondition()
      { return *(static_cast<ReuseCondition*> (&availableResources)); }
      PurgeCondition& GetPurgeCondition()
      { return *(static_cast<PurgeCondition*> (&activeResources)); }
      
      class SearchDataTraverser
      {
        T* entry;
        Element*& ret;
        
      public:
        SearchDataTraverser (T* entry, Element*& ret) 
          : entry (entry), ret (ret) {}
        
        bool operator() (ElementWrapper& el)
        {
          if (&(el.ptr->data) == entry)
          {
            ret = el.ptr;
            return false;
          }
          return true;
        }
      };
      
      Element* ElementFromData (T* entry)
      {
        // Given some cached data, obtain the Element from it.
        
        /* @@@ Right now the only way is to search both the active and
         * available resource lists. */
        
        // Search active resource list.
        typename csList<ElementWrapper>::Iterator listIt (activeResources.v);
        while (listIt.HasNext())
        {
          Element* el = listIt.Next().ptr;
          if (&(el->data) == entry) return el;
        }
        
        // Search available resource tree.
        Element* treeSearchRet = 0;
        SearchDataTraverser sdt (entry, treeSearchRet);
        availableResources.v.TraverseInOrder (sdt);
        if (treeSearchRet != 0) return treeSearchRet;
        
        CS_ASSERT_MSG("Element is not from this resource cache", false);
        return 0;
      }
    public:
      TimeType agedPurgeInterval;
    
      GenericResourceCache (const ReuseCondition& reuse = ReuseCondition(),
        const PurgeCondition& purge = PurgeCondition()) : 
        availableResources (reuse, elementAlloc),
        activeResources (purge, elementAlloc), 
        currentTime (0), lastPurgeAged (0),
        clearReq (false), agedPurgeInterval (60)
      {
      }
      
      ~GenericResourceCache()
      {
        availableResources.Destroy ();
      }

      void Clear (bool instaClear = false)
      {
        if (instaClear)
        {
          availableResources.Destroy ();
          activeResources.Destroy ();
          clearReq = false;
        }
        else
          // Don't clear just yet, rather, clear when we advance the next time
          clearReq = true;
      }
      
#ifdef CS_DEBUG
      class VerifyTraverser
      {
        Element* el;
      public:
        VerifyTraverser (Element* el) : el (el) {}
        
        bool operator() (ElementWrapper& el)
        {
          CS_ASSERT(el.ptr != this->el);
          return true;
        }
      };
#endif

      void VerifyElementNotInTree (Element* el)
      {
        (void)el;
#ifdef CS_DEBUG
        VerifyTraverser verify (el);
        availableResources.v.TraverseInOrder (verify);
#endif
      }
      
      void AdvanceTime (TimeType time)
      {
        if (clearReq)
        {
          Clear (true);
          clearReq = false;
        }
        
        currentTime = time;
        
        if (time >= lastPurgeAged + agedPurgeInterval)
        {
          typename AvailableResourcesTree::Iterator treeIt (
            availableResources.v.GetIterator ());
          while (treeIt.HasNext())
          {
            Element* el = treeIt.PeekNext ().ptr;
            if (GetPurgeCondition().IsPurgeable (*this, 
                el->GetPurgeAuxiliary(), el->data))
            {
              availableResources.v.Delete (treeIt);
              VerifyElementNotInTree (el);
              elementAlloc.Free (el);
            }
            else
            {
              treeIt.Next ();
            }
          }
          
          lastPurgeAged = time;
        }
        
        typename csList<ElementWrapper>::Iterator listIt (activeResources.v);
        while (listIt.HasNext())
        {
          ElementWrapper& el = listIt.Next();
          
          if (GetReuseCondition().IsReusable (*this,
              el->GetReuseAuxiliary(), el->data))
          {
            VerifyElementNotInTree (el.ptr);
            availableResources.v.Insert (el);
            activeResources.v.Delete (listIt);
          }
        }
      }
      TimeType GetCurrentTime() const { return currentTime; }

      T* Query (const ResourceSortingKeyType& key = 
        ResourceSortingKeyType(), bool exact = false)
      {
        const AvailableResourcesTree& constTree = availableResources.v;
        ElementWrapper const* el;
        if (exact)
          el = constTree.Find (key);
        else
          el = constTree.FindGreatestSmallerEqual (key);
        if (el != 0)
        {
          ElementWrapper myElement = *el;
          availableResources.v.DeleteExact (el);
          VerifyElementNotInTree (myElement.ptr);
          activeResources.v.PushFront (myElement);
          GetPurgeCondition().MarkActive (*this, myElement->GetPurgeAuxiliary());
          GetReuseCondition().MarkActive (*this, myElement->GetReuseAuxiliary());
          return &(myElement->data);
        }
        return 0;
      }
      T* AddActive (const T& value,
        const ReuseConditionAddParameter& reuseParam = ReuseConditionAddParameter (),
        const PurgeConditionAddParameter& purgeParam = PurgeConditionAddParameter ())
      {
        ReuseConditionAuxiliary reuseAux (*this, reuseParam);
        PurgeConditionAuxiliary purgeAux (*this, purgeParam);
        Element* el = elementAlloc.Alloc (value, reuseAux, purgeAux);
        GetPurgeCondition().MarkActive (*this, el->GetPurgeAuxiliary());
        GetReuseCondition().MarkActive (*this, el->GetReuseAuxiliary());
        activeResources.v.PushFront (el);
        return &(el->data);
      }

      void NudgeLastUsedTime (T* data)
      {
        Element* el = static_cast<Element*> (
          DataStorage<typename ReuseCondition::StoredAuxiliaryInfo>::CastFromData (data));
        el->lastTimeUsed = currentTime;
      }


      void SetAvailable (T* data)
      {
        Element* el = ElementFromData (data);
          
        VerifyElementNotInTree (el);
        availableResources.v.Insert (el);
        activeResources.v.Delete (el);
      }
      
      void RemoveActive (T* data)
      {
        Element* el = ElementFromData (data);
          
        activeResources.v.Delete (el);
        elementAlloc.Free (el);
      }
      
      typename ReuseCondition::StoredAuxiliaryInfo* GetReuseAuxiliary (
        T* entry)
      {
        return &(ElementFromData (entry)->GetReuseAuxiliary());
      }
      
      typename PurgeCondition::StoredAuxiliaryInfo* GetPurgeAuxiliary (
        T* entry)
      {
        return &(ElementFromData (entry)->GetPurgeAuxiliary());
      }
    };
    
  } // namespace Utility
} // namespace CS

#endif // __CS_CSUTIL_GENERICRESOURCECACHE_H__

---