cache.hpp

Go to the documentation of this file.

 
#ifndef __BOXES_CACHE_HPP__
#define __BOXES_CACHE_HPP__
 
#include "compiler.hpp"
 
#include <list>
#include <map>
#include <memory>
#include <unordered_map>
 
namespace boxes {
namespace cache {
 
namespace policy {
 
template <typename K, typename V> class LRU {
public:
  virtual ~LRU() = default;
 
  LRU(std::size_t maxSize) : maxSize{maxSize} {}
 
  using AccessQueue = std::list<K>;
  using Iterator = typename AccessQueue::iterator;
 
  struct Value {
    V value;
    Iterator it;
  };
 
  virtual void clear() { access.clear(); }
 
  virtual void onEvict(const K &, Value &value) { access.erase(value.it); }
 
  virtual void onAccess(const K &key, Value &value) {
    access.erase(value.it);
    value.it = access.insert(access.begin(), key);
  }
 
  virtual Value onInsert(const K &key, V value) {
    return Value{std::move(value), access.insert(access.begin(), key)};
  }
 
  virtual K &front() { return access.front(); }
 
  virtual K &back() { return access.back(); }
 
  virtual Iterator begin() { return access.begin(); }
 
  virtual Iterator end() { return access.end(); }
 
  virtual const K &getKey(Iterator it) { return *it; }
 
  virtual const K *elect() {
    if (access.size() < maxSize) {
      return nullptr;
    }
    return &this->access.back();
  }
 
protected:
  const std::size_t maxSize;
  AccessQueue access;
};
 
template <typename K, typename V> class NoEviction {
public:
  using AccessQueue = std::list<K>;
  using Iterator = typename AccessQueue::iterator;
 
  struct Value {
    V value;
    Iterator it;
  };
 
  const K *elect() { return nullptr; }
 
  void clear() { access.clear(); }
 
  void onEvict(const K &, Value &) {}
 
  void onAccess(const K &, Value &) {}
 
  Value onInsert(const K &key, V value) {
    return Value{std::move(value), access.insert(access.end(), key)};
  }
 
  K &front() { return access.front(); }
 
  K &back() { return access.back(); }
 
  Iterator begin() { return access.begin(); }
 
  Iterator end() { return access.end(); }
 
  const K &getKey(Iterator it) { return *it; }
 
protected:
  AccessQueue access;
};
 
template <typename K, typename V> class MRU : public LRU<K, V> {
public:
  using LRU<K, V>::LRU;
 
  void onAccess(const K &key, typename LRU<K, V>::Value &value) override {
    this->access.erase(value.it);
    value.it = this->access.insert(this->access.rbegin().base(), key);
  }
 
  typename LRU<K, V>::Value onInsert(const K &key, V value) override {
    return typename LRU<K, V>::Value{
        std::move(value),
        this->access.insert(this->access.rbegin().base(), key)};
  }
};
 
template <typename K, typename V> class LFU {
public:
  explicit LFU(std::size_t maxSize) : maxSize{maxSize} {}
 
  using FrequencyMap = std::multimap<std::size_t, K>;
  using Iterator = typename FrequencyMap::reverse_iterator;
 
  struct Value {
    V value;
    Iterator it;
  };
 
  void clear() { freqs.clear(); }
 
  void onAccess(const K &key, Value &value) {
    auto it = value.it.base();
    const auto freq = it->first;
    freqs.erase(it);
    value.it = std::make_reverse_iterator(freqs.emplace(freq + 1, key));
  }
 
  Value onInsert(const K &key, V &&value) {
    constexpr std::size_t initialFreq = 0;
    auto rit = std::make_reverse_iterator(freqs.emplace(initialFreq, key));
    return Value{std::forward<V>(value), rit};
  }
 
  void onEvict(const K &, Value &value) { freqs.erase(value.it.base()); }
 
  const K &getKey(Iterator it) { return it->second; }
 
  K &front() { return freqs.rbegin()->second; }
 
  K &back() { return freqs.begin()->second; }
 
  Iterator begin() { return freqs.rbegin(); }
 
  Iterator end() { return freqs.rend(); }
 
  const K *elect() {
    if (freqs.size() < maxSize) {
      return nullptr;
    }
 
    return &freqs.begin()->second;
  }
 
protected:
  const std::size_t maxSize;
  FrequencyMap freqs;
};
 
} // namespace policy
 
template <typename K, typename V,
          template <typename, typename> class CachePolicy>
class Cache {
public:
  using Policy = CachePolicy<K, V>;
  using PolicyIterator = typename Policy::Iterator;
 
  class iterator {
  public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = std::pair<K, V>;
    using difference_type = std::ptrdiff_t;
 
    iterator(Cache<K, V, CachePolicy> &cache, PolicyIterator it)
        : cache{cache}, it{it} {}
 
    iterator &operator++() {
      ++it;
      return *this;
    }
 
    iterator operator++(int) {
      iterator copy = *this;
      ++it;
      return copy;
    }
 
    iterator &operator--() {
      --it;
      return *this;
    }
 
    iterator operator--(int) {
      iterator copy = *this;
      --it;
      return copy;
    }
 
    value_type &operator*() {
      const auto &key = cache.policy.getKey(it);
      const auto &pv = cache.data[key];
      valueProxy = std::make_pair(key, pv.value);
      return valueProxy;
    }
 
    value_type *operator->() {
      const auto &key = cache.policy.getKey(it);
      auto &pv = cache.data[key];
      valueProxy = std::make_pair(key, pv.value);
      return &valueProxy;
    }
 
    bool operator==(const iterator &other) const { return it == other.it; }
 
    bool operator!=(const iterator &other) const { return it != other.it; }
 
  protected:
    Cache<K, V, CachePolicy> &cache;
    PolicyIterator it;
    std::pair<K, V> valueProxy;
  };
 
  explicit Cache(Policy policy) : policy{std::move(policy)} {}
 
  void reserve(std::size_t size) { data.reserve(size); }
 
  std::size_t size() const { return data.size(); }
 
  std::size_t max_size() const { return data.max_size(); }
 
  bool empty() const { return data.empty(); }
 
  void clear() {
    data.clear();
    policy.clear();
  }
 
  template <typename KArg, typename VArg>
  bool insert(KArg &&key, VArg &&value) {
    if (auto it = data.find(key); it != data.end()) {
      policy.onAccess(key, it->second);
      return false;
    } else {
      // evict if needed
      if (auto elected = policy.elect()) {
        if (auto it = data.find(*elected); it != data.end()) {
          policy.onEvict(*elected, it->second);
          data.erase(it);
        }
      }
 
      data.emplace(key, policy.onInsert(key, std::forward<VArg>(value)));
      return true;
    }
 
    boxes_unreachable();
  }
 
  bool contains(const K &key) const { return data.find(key) != data.end(); }
 
  iterator begin() { return iterator{*this, policy.begin()}; }
 
  iterator end() { return iterator{*this, policy.end()}; }
 
  iterator cbegin() const { return const_cast<Cache *>(this)->begin(); }
 
  iterator cend() const { return const_cast<Cache *>(this)->end(); }
 
  iterator find(const K &key) {
    if (auto it = data.find(key); it != data.end()) {
      policy.onAccess(key, it->second);
      return iterator{*this, it->second.it};
    }
    return end();
  }
 
  V &at(const K &key) {
    if (auto it = data.find(key); it != data.end()) {
      policy.onAccess(key, it->second);
      return it->second.value;
    }
 
    throw std::out_of_range{"Key not found"};
  }
 
  const V &at(const K &key) const { return const_cast<Cache *>(this)->at(key); }
 
  K &front() { return policy.front(); }
 
  K &back() { return policy.back(); }
 
  const K &front() const { return const_cast<Cache *>(this)->front(); }
 
  const K &back() const { return const_cast<Cache *>(this)->back(); }
 
protected:
  using Value = typename Policy::Value;
  using Map = std::unordered_map<K, Value>;
 
  mutable Map data;
  mutable Policy policy;
};
 
template <typename K, typename V>
Cache<K, V, policy::LRU> makeLRU(std::size_t size) {
  return Cache<K, V, policy::LRU>{policy::LRU<K, V>{size}};
}
 
template <typename K, typename V>
Cache<K, V, policy::MRU> makeMRU(std::size_t size) {
  return Cache<K, V, policy::MRU>{policy::MRU<K, V>{size}};
}
 
template <typename K, typename V>
Cache<K, V, policy::NoEviction> makeNoEviction() {
  return Cache<K, V, policy::NoEviction>{policy::NoEviction<K, V>{}};
}
 
template <typename K, typename V>
Cache<K, V, policy::LFU> makeLFU(std::size_t size) {
  return Cache<K, V, policy::LFU>{policy::LFU<K, V>{size}};
}
 
} // namespace cache
} // namespace boxes
 
#endif // __BOXES_CACHE_HPP__