DtOsgLRUCache.h

Go to the documentation of this file.

#pragma once


#include <osg/ref_ptr>
#include <vrvOsg/DtOsgThreadingUtils.h>
#include <iostream>

#define LRUCACHE_DEBUG 1

namespace makVrv {

struct CacheStats
{
public:
   CacheStats( unsigned entries, unsigned maxEntries, unsigned queries, float hitRatio )
      : _entries(entries), _maxEntries(maxEntries), _queries(queries), _hitRatio(hitRatio) { }

   virtual ~CacheStats() { }

   unsigned _entries;
   unsigned _maxEntries;
   unsigned _queries;
   float    _hitRatio;
};



template<typename K, typename T, typename COMPARE=std::less<K> >
class LRUCache
{
public:
   struct Record {
      Record() : _valid(false) { }
      Record(const T& value) : _value(value), _valid(true) { }
      bool valid() const { return _valid; }
      const T& value() const { return _value; }
   private:
      bool _valid;
      T    _value;
      friend class LRUCache;
   };

   struct Functor {
      virtual void operator()(const K& key, const T& value) =0;
   };

protected:
   typedef typename std::list<K>::iterator      lru_iter;
   typedef typename std::list<K>                lru_type;
   typedef typename std::pair<T, lru_iter>      map_value_type;
   typedef typename std::map<K, map_value_type> map_type;
   typedef typename map_type::iterator          map_iter;
   typedef typename map_type::const_iterator    map_const_iter;

   map_type _map;
   lru_type _lru;
   unsigned _max;
   unsigned _buf;
   unsigned _queries;
   unsigned _hits;
   bool     _threadsafe;
   mutable Threading::Mutex _mutex;

public:
   LRUCache( unsigned max =100 ) 
      : _max(max)
      , _threadsafe(false)
      , _queries(0)
      , _hits(0)
   {
      setMaxSize_impl(max);
#if LRUCACHE_DEBUG
      myDebug = false;
#endif
   }
   LRUCache( bool threadsafe, unsigned max =100 ) : _max(max), _threadsafe(threadsafe) {
      _queries = 0;
      _hits = 0;
      setMaxSize_impl(max);
#if LRUCACHE_DEBUG
      myDebug = false;
#endif
   }

   virtual ~LRUCache() { }

   void insert( const K& key, const T& value ) {
      if ( _threadsafe ) {
         Threading::ScopedMutexLock lock(_mutex);
         insert_impl( key, value );
      }
      else {
         insert_impl( key, value );
      }
   }

   bool get( const K& key, Record& out ) {
      if ( _threadsafe ) {
         Threading::ScopedMutexLock lock(_mutex);
         get_impl( key, out );
      }
      else {
         get_impl( key, out );
      }
      return out.valid();
   }

   bool has( const K& key ) {
      if ( _threadsafe ) {
         Threading::ScopedMutexLock lock(_mutex);
         return has_impl( key );
      }
      else {
         return has_impl( key );
      }
   }

   void erase( const K& key ) {
      if ( _threadsafe ) {
         Threading::ScopedMutexLock lock(_mutex);
         erase_impl( key );
      }
      else {
         erase_impl( key );
      }
   }

   void clear() {
      if ( _threadsafe ) {
         Threading::ScopedMutexLock lock(_mutex);
         clear_impl();
      }
      else {
         clear_impl();
      }
   }

   void setMaxSize( unsigned max ) {
      if ( _threadsafe ) {
         Threading::ScopedMutexLock lock(_mutex);
         setMaxSize_impl( max );
      }
      else {
         setMaxSize_impl( max );
      }
   }

   unsigned getMaxSize() const {
      return _max;
   }

   CacheStats getStats() const {
      return CacheStats(
         _map.size(), _max, _queries, _queries > 0 ? (float)_hits/(float)_queries : 0.0f );
   }

   void iterate(Functor& functor) const {
      if (_threadsafe) {
         Threading::ScopedMutexLock lock(_mutex);
         iterate_impl(functor);
      }
      else {
         iterate_impl(functor);
      }
   }

#if LRUCACHE_DEBUG
   void enableDebug(bool enable) { myDebug = enable; }
#endif

private:
   void insert_impl( const K& key, const T& value ) {
      map_iter mi = _map.find( key );
      if ( mi != _map.end() ) {
         map_value_type& valType = mi->second;
         _lru.erase(valType.second);
         valType.first = value;
         _lru.push_back( key );
         valType.second = _lru.end();
         valType.second--;
#if LRUCACHE_DEBUG
         if (myDebug)
         {
            std::cout << "Cache hit: " << key << std::endl;
         }
#endif
      }
      else {
         _lru.push_back( key );
         lru_iter last = _lru.end(); --last;
         _map[key] = std::make_pair(value, last);

#if LRUCACHE_DEBUG
         if (myDebug)
         {
            std::cout << "Cache insert: " << key << std::endl;
         }
#endif
      }

      if ( _map.size() > _max ) {
         for( unsigned i=0; i < _buf; ++i ) {
            const K& key = _lru.front();
#if LRUCACHE_DEBUG
            if (myDebug)
            {
               std::cout << "Ejected: " << _map.find(key)->second.first.get() << std::endl;
            }
#endif
            _map.erase( key );
            _lru.pop_front();
         }
      }
   }

   void get_impl( const K& key, Record& result ) {
      _queries++;
      map_iter mi = _map.find( key );
      if ( mi != _map.end() ) {
         map_value_type& valType = mi->second;
         _lru.erase(valType.second);
         _lru.push_back( key );
         lru_iter new_iter = _lru.end(); --new_iter;
         valType.second = new_iter;
         _hits++;
         result._value = valType.first;
         result._valid = true;
      }
   }

   bool has_impl( const K& key ) {
      return _map.find( key ) != _map.end();
   }

   void erase_impl( const K& key ) {
      map_iter mi = _map.find( key );
      if ( mi != _map.end() ) {
         _lru.erase( mi->second.second );
         _map.erase( mi );
      }
   }

   void clear_impl() {
      _lru.clear();
      _map.clear();
      _queries = 0;
      _hits = 0;
   }

   void setMaxSize_impl( unsigned max ) {
      _max = std::max(max, 10u);
      _buf = _max / 10u;
      while( _map.size() > _max ) {
         const K& key = _lru.front();
         _map.erase( key );
         _lru.pop_front();
      }
   }

   void iterate_impl(Functor& f) const {
      for (map_const_iter i = _map.begin(); i != _map.end(); ++i) {
         f(i->first, i->second.first);
      }
   }

#if LRUCACHE_DEBUG
   bool myDebug;
#endif

};
}