lru_cache.hpp

 
#ifndef __PCL_OUTOFCORE_LRU_CACHE__
#define __PCL_OUTOFCORE_LRU_CACHE__
 
#include <cstddef>
#include <cassert>
#include <list>
#include <map>
#include <utility>
 
template<typename T>
class LRUCacheItem
{
public:
 
  virtual std::size_t
  sizeOf () const
  {
    return sizeof (item);
  }
 
  virtual
  ~LRUCacheItem () = default;
 
  T item;
  std::size_t timestamp;
};
 
template<typename KeyT, typename CacheItemT>
class LRUCache
{
public:
 
  using KeyIndex = std::list<KeyT>;
  using KeyIndexIterator = typename KeyIndex::iterator;
  using Cache = std::map<KeyT, std::pair<CacheItemT, typename KeyIndex::iterator> >;
 
  LRUCache (std::size_t c) :
      capacity_ (c)
  {
    assert(capacity_ != 0);
  }
 
  bool
  hasKey (const KeyT& k)
  {
    return (cache_.find (k) != cache_.end ());
  }
 
  CacheItemT&
  get (const KeyT& k)
  {
    // Get existing key
    const auto it = cache_.find (k);
    assert(it != cache_.end ());
 
    // Move key to MRU key index
    key_index_.splice (key_index_.end (), key_index_, (*it).second.second);
 
    // Return the retrieved item
    return it->second.first;
  }
 
  void
  touch (const KeyT& key)
  {
    // Get existing key
    const auto it = cache_.find (key);
    assert(it != cache_.end ());
 
    // Move key to MRU key index
    key_index_.splice (key_index_.end (), key_index_, it->second.second);
  }
 
  // Record a fresh key-value pair in the cache
  bool
  insert (const KeyT& key, const CacheItemT& value)
  {
    if (cache_.find (key) != cache_.end ())
    {
      touch (key);
      return true;
    }
 
    std::size_t size = size_;
    std::size_t item_size = value.sizeOf ();
    int evict_count = 0;
 
    // Get LRU key iterator
    auto key_it = key_index_.begin ();
 
    while (size + item_size >= capacity_)
    {
      const auto cache_it = cache_.find (*key_it);
 
      // Get tail item (Least Recently Used)
      std::size_t tail_timestamp = cache_it->second.first.timestamp;
      std::size_t tail_size = cache_it->second.first.sizeOf ();
 
      // Check timestamp to see if we've completely filled the cache in one go
      if (value.timestamp == tail_timestamp)
      {
        return false;
      }
 
      size -= tail_size;
      ++key_it;
      ++evict_count;
    }
 
    // Evict enough items to make room for the new item
    evict (evict_count);
 
    size_ += item_size;
 
    // Insert most-recently-used key at the end of our key index
    auto it = key_index_.insert (key_index_.end (), key);
 
    // Add to cache
    cache_.insert (std::make_pair (key, std::make_pair (value, it)));
 
    return true;
  }
 
  void
  setCapacity (std::size_t capacity)
  {
    capacity_ = capacity;
  }
 
  CacheItemT&
  tailItem ()
  {
    const auto it = cache_.find (key_index_.front ());
    return it->second.first;
  }
 
  std::size_t
  sizeOf (const CacheItemT& value)
  {
    return value.sizeOf ();
  }
 
  // Evict the least-recently-used item from the cache
  bool
  evict (int item_count=1)
  {
    for (int i=0; i < item_count; i++)
    {
      if (key_index_.empty ())
        return false;
 
      // Get LRU item
      const auto it = cache_.find (key_index_.front ());
      assert(it != cache_.end());
 
      // Remove LRU item from cache and key index
      size_ -= it->second.first.sizeOf ();
      cache_.erase (it);
      key_index_.pop_front ();
    }
 
    return true;
  }
 
  // Cache capacity in kilobytes
  std::size_t capacity_;
 
  // Current cache size in kilobytes
  std::size_t size_{0};
 
  // LRU key index LRU[0] ... MRU[N]
  KeyIndex key_index_;
 
  // LRU cache
  Cache cache_;
};
 
#endif //__PCL_OUTOFCORE_LRU_CACHE__