lru_cache.h

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2004-2011 by Patrick Audley                             *
 *   paudley@blackcat.ca                                                   *
 *   http://patrickaudley.com                                              *
 *                                                                         *
 ***************************************************************************/
#ifndef _lru_cache_h
#define _lru_cache_h

#include <stdio.h>
#include <map>
#include <list>
#include <vector>
#include <cstddef>
#ifdef _REENTRANT
#include <boost/thread/mutex.hpp>
#define SCOPED_MUTEX  boost::mutex::scoped_lock lock(this->_mutex);
#else
#define SCOPED_MUTEX
#endif

template < class T >
struct Countfn {
  unsigned long operator()( const T& ) { return 1; }
};


template< class Key, class Data, class Sizefn = Countfn< Data > > class LRUCache {
 public:
 typedef std::list< std::pair< Key, Data > > List;         
 typedef typename List::iterator List_Iter;                
 typedef typename List::const_iterator List_cIter;         
 typedef std::vector< Key > Key_List;                      
 typedef typename Key_List::iterator Key_List_Iter;        
 typedef typename Key_List::const_iterator Key_List_cIter; 
 typedef std::map< Key, List_Iter > Map;                   
 typedef std::pair< Key, List_Iter > Pair;                 
 typedef typename Map::iterator Map_Iter;                       
 typedef typename Map::const_iterator Map_cIter;           
 
 private:
  
 List _list;               
 Map _index;               
 unsigned long _max_size;  
 unsigned long _curr_size; 
 
#ifdef _REENTRANT
 boost::mutex _mutex;
#endif
 
 public:
 
 LRUCache( const unsigned long Size ) :
 _max_size( Size ),
 _curr_size( 0 ) {}
 
  LRUCache( const LRUCache &that) {
   *this = that;
 }
 
 LRUCache& operator=(const LRUCache &that) {
   if (this == &that)
     return *this;
   
   _list = that._list;
   _index.clear();
   for (List_Iter it = _list.begin(); it != _list.end(); ++it)
     _index.insert(std::make_pair(it->first, it));
   _max_size = that._max_size;
   _curr_size = that._curr_size;
   
   return *this;
 } 
 
 ~LRUCache() { clear(); }
 
 inline unsigned long size( void ) const { return _curr_size; }
 
 inline unsigned long max_size( void ) const { return _max_size; }
 
 void clear( void ) {
   SCOPED_MUTEX;
   _list.clear();
   _index.clear();
   _curr_size = 0;
 };
 
#ifdef _REENTRANT
 inline bool exists( const Key &key ) {
   SCOPED_MUTEX;
#else
   inline bool exists( const Key &key ) const {
#endif
     return _index.find( key ) != _index.end();
   }
   
   inline void remove( const Key &key ) {
#ifdef _REENTRANT
     SCOPED_MUTEX;
#endif
     Map_Iter miter = _index.find( key );
     if( miter == _index.end() ) return;
     _remove( miter );
   }
   
   inline void touch( const Key &key ) {
     SCOPED_MUTEX;
     _touch( key );
   }
   
   inline Data *fetch_ptr( const Key &key, bool touch_data = true ) {
     SCOPED_MUTEX;
     Map_Iter miter = _index.find( key );
     if( miter == _index.end() ) return NULL;
     if (touch_data)
       _list.splice( _list.begin(), _list, miter->second ); // Do a touch inline.
     return &(miter->second->second);
   }
   
   inline Data fetch( const Key &key, bool touch_data = true ) {
     SCOPED_MUTEX;
     Map_Iter miter = _index.find( key );
     if( miter == _index.end() )
       return Data();
     Data tmp = miter->second->second;
     if( touch_data )
       _list.splice( _list.begin(), _list, miter->second ); // Do a touch inline.
     return tmp;
   }
   
   inline bool fetch( const Key &key, Data &data, bool touch_data = true ) {
     SCOPED_MUTEX;
     Map_Iter miter = _index.find( key );
     if( miter == _index.end() ) return false;
     if( touch_data )
       _list.splice( _list.begin(), _list, miter->second ); // Do a touch inline.
     data = miter->second->second;
     return true;
   }
   
   inline void insert( const Key &key, const Data &data ) {
     SCOPED_MUTEX;
     // Touch the key, if it exists, then replace the content.
     Map_Iter miter = _touch( key );
     if( miter != _index.end() )
       _remove( miter );
     
     // Ok, do the actual insert at the head of the list
     _list.push_front( std::make_pair( key, data ) );
     List_Iter liter = _list.begin();
     
     // Store the index
     _index.insert( std::make_pair( key, liter ) );
     _curr_size += Sizefn()( data );
     
     //fprintf(stderr, "cache: insert: %p, %p\n", 
     // &(_list.begin()->second),
     // &(_index.find(key)->second->second));
     
     // Check to see if we need to remove an element due to exceeding max_size
     while( _curr_size > _max_size ) {
       // Remove the last element.
       liter = _list.end();
       --liter;
       _remove( liter->first );
     }
   }
   
   void info()
   {
     List_Iter lit = _list.begin();
     for (size_t i=0; i<_curr_size; ++i, ++lit)
       {
     Key k1 = lit->first;
     void *ptr1 = &(lit->second);
     Key k2 = _index.find(k1)->first;
     void *ptr2 = &(_index.find(k1)->second->second);
     fprintf(stderr, "cache: info: [%zu]: %zu, %zu (%zu) | %p, %p (%zu).\n", 
         i, k1, k2, k1 - k2, ptr1, ptr2, (char*)ptr1 - (char*)ptr2);
       }
   }
   
   inline const Key_List get_all_keys( void ) {
     SCOPED_MUTEX;
     Key_List ret;
     for( List_cIter liter = _list.begin(); liter != _list.end(); liter++ )
       ret.push_back( liter->first );
     return ret;
   }
   
 private:
   
   inline Map_Iter _touch( const Key &key ) {
     Map_Iter miter = _index.find( key );
     if( miter == _index.end() ) return miter;
     
     //fprintf(stderr, "cache: _touch: #1 %zu, %p, begin %zu %p.\n", 
     // key, &(miter->second->second), 
     // _list.begin()->first, &(_list.begin()->second));
     
     // Move the found node to the head of the list.
     _list.splice( _list.begin(), _list, miter->second );
     
     //fprintf(stderr, "cache: _touch: #2 %zu, %p.\n", 
     // key, &(miter->second->second));
     
     return miter;
   }
   
   inline void _remove( const Map_Iter &miter ) {
     _curr_size -= Sizefn()( miter->second->second );
     _list.erase( miter->second );
     _index.erase( miter );
   }
   
   inline void _remove( const Key &key ) {
     Map_Iter miter = _index.find( key );
     _remove( miter );
   }
 };
 
#endif // _lru_cache_h