LruCache.h

/*
 * Copyright (C) 2019-2021 HERE Europe B.V.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * SPDX-License-Identifier: Apache-2.0
 * License-Filename: LICENSE
 */
 
#pragma once
 
#include <cassert>
#include <cstddef>
#include <functional>
#include <map>
#include <utility>
 
#include <olp/core/porting/try_emplace.h>
 
namespace olp {
namespace utils {
template <typename T>
struct CacheCost {
  std::size_t operator()(const T&) const { return 1; }
};
 
template <typename Key, typename Value,
          typename CacheCostFunc = CacheCost<Value>,
          typename Compare = std::less<Key>,
          template <typename> class Alloc = std::allocator>
class LruCache {
  struct Bucket;
  using MapType =
      std::map<Key, Bucket, Compare, Alloc<std::pair<const Key, Bucket> > >;
 
 public:
  using EvictionFunction = std::function<void(const Key&, Value&&)>;
 
  using CompareType = typename MapType::key_compare;
 
  using AllocType = typename MapType::allocator_type;
 
  class ValueType {
   public:
    inline const Key& key() const;
 
    inline const Value& value() const;
 
   protected:
    typename MapType::const_iterator m_it;
  };
 
  class const_iterator : public ValueType {
   public:
    typedef std::bidirectional_iterator_tag iterator_category;
    typedef std::ptrdiff_t difference_type;
    typedef ValueType value_type;
    typedef const value_type& reference;
    typedef const value_type* pointer;
 
    const_iterator() = default;
    const_iterator(const const_iterator&) = default;
    const_iterator& operator=(const const_iterator&) = default;
 
    inline bool operator==(const const_iterator& other) const;
    inline bool operator!=(const const_iterator& other) const {
      return !operator==(other);
    }
 
    inline const_iterator& operator++();
    inline const_iterator operator++(int);
 
    inline const_iterator& operator--();
    inline const_iterator operator--(int);
 
    reference operator*() const { return *this; }
 
    pointer operator->() const { return this; }
 
   private:
    template <typename, typename, typename, typename, template <typename> class>
    friend class LruCache;
 
    explicit const_iterator(const typename MapType::const_iterator& it) {
      this->m_it = it;
    }
 
    explicit const_iterator(const typename MapType::iterator& it) {
      this->m_it = it;
    }
  };
 
  explicit LruCache(const AllocType& alloc = AllocType())
      : map_(alloc),
        first_(map_.end()),
        last_(map_.end()),
        max_size_(0),
        size_(0) {}
 
  LruCache(std::size_t maxSize, CacheCostFunc cacheCostFunc = CacheCostFunc(),
           const CompareType& compare = CompareType(),
           const AllocType& alloc = AllocType())
      : cache_cost_func_(std::move(cacheCostFunc)),
        map_(compare, alloc),
        first_(map_.end()),
        last_(map_.end()),
        max_size_(maxSize),
        size_(0) {}
 
  LruCache(const LruCache&) = delete;
 
  LruCache(LruCache&& other) noexcept
      : eviction_callback_(std::move(other.eviction_callback_)),
        cache_cost_func_(std::move(other.cache_cost_func_)),
        map_(std::move(other.map_)),
        first_(other.first_ != map_.end() ? map_.find(other.first_->first)
                                          : map_.end()),
        last_(other.last_ != map_.end() ? map_.find(other.last_->first)
                                        : map_.end()),
        max_size_(other.max_size_),
        size_(other.size_) {}
 
  LruCache& operator=(const LruCache&) = delete;
 
  LruCache& operator=(LruCache&& other) noexcept {
    eviction_callback_ = std::move(other.eviction_callback_);
    cache_cost_func_ = std::move(other.cache_cost_func_);
    map_ = std::move(other.map_);
    first_ = other.first_ != map_.end() ? map_.find(other.first_->first)
                                        : map_.end();
    last_ =
        other.last_ != map_.end() ? map_.find(other.last_->first) : map_.end();
    std::swap(max_size_, other.max_size_);
    std::swap(size_, other.size_);
 
    return *this;
  }
 
  template <typename _Key, typename _Value>
  std::pair<const_iterator, bool> Insert(_Key&& key, _Value&& value);
 
  template <typename _Value>
  std::pair<const_iterator, bool> InsertOrAssign(Key key, _Value&& value);
 
  bool Erase(const Key& key) {
    auto it = map_.find(key);
    if (it == map_.end())
      return false;
 
    Erase(it, false);
    return true;
  }
 
  const_iterator Erase(const_iterator& it) {
    auto prev = it++;
 
    Erase(prev->key());
 
    return it;
  }
 
  std::size_t Size() const { return size_; }
 
  std::size_t GetMaxSize() const { return max_size_; }
 
  void Resize(size_t maxSize) {
    max_size_ = maxSize;
    evict();
  }
 
  const_iterator Find(const Key& key) {
    auto it = map_.find(key);
    if (it != map_.end())
      Promote(it);
    return const_iterator{it};
  }
 
  const_iterator FindNoPromote(const Key& key) const {
    auto it = map_.find(key);
    return const_iterator{it};
  }
 
  const Value& Find(const Key& key, const Value& nullValue) {
    auto it = Find(key);
    return it == end() ? nullValue : it.value();
  }
 
  const_iterator begin() const { return const_iterator{first_}; }
 
  const_iterator end() const { return const_iterator{map_.end()}; }
 
  const_iterator rbegin() const { return const_iterator{last_}; }
 
  const_iterator rend() const { return const_iterator{map_.end()}; }
 
  void Clear() {
    map_.clear();
    first_ = last_ = map_.end();
    size_ = 0u;
  }
 
  void SetEvictionCallback(EvictionFunction func) {
    eviction_callback_ = std::move(func);
  }
 
 private:
  friend struct CacheLruChecker;  // for unit-tests
 
  EvictionFunction eviction_callback_;
  CacheCostFunc cache_cost_func_;
  MapType map_;
  typename MapType::iterator first_;
  typename MapType::iterator last_;
  std::size_t max_size_;
  std::size_t size_;
 
  // Checks whether two keys are equal using only the comparison
  // operator.
  inline bool IsEqual(const Key& key1, const Key& key2) {
    auto comp = map_.key_comp();
    return !comp(key1, key2) && !comp(key2, key1);
  }
 
  // The bucket that contains the value and the pointer to the previous
  // and next items in the LRU chain.
  struct Bucket {
    using Iterator = typename MapType::iterator;
 
    // note - these constructors are only here because MSVC2013 doesn't
    // auto-generate them as the standard mandates
#if defined(_MSC_VER) && _MSC_VER < 1900
    inline Bucket(Iterator next, Iterator previous, Value&& value)
        : next_(std::move(next)),
          previous_(std::move(previous)),
          value_(std::move(value)) {}
    inline Bucket(Iterator next, Iterator previous, const Value& value)
        : next_(std::move(next)),
          previous_(std::move(previous)),
          value_(value) {}
    inline Bucket(const Bucket&) = delete;
    inline Bucket(Bucket&& other)
        : next_(std::move(other.next_)),
          previous_(std::move(other.previous_)),
          value_(std::move(other.value_)) {}
#endif
 
    Iterator next_;
    Iterator previous_;
    Value value_;
 
    inline void setNext(Iterator it) { next_ = std::move(it); }
 
    inline void setPrevious(Iterator it) { previous_ = std::move(it); }
  };
 
  void Erase(typename MapType::iterator it, bool);
  void AddInternal(const typename MapType::iterator& it, std::size_t cost,
                   std::size_t* oldCost = nullptr);
  void Promote(const typename MapType::iterator& it);
  void PopLast();
  void evict() {
    while (size_ > max_size_)
      PopLast();
  }
};
 
template <typename Key, typename Value, typename CacheCostFunc,
          typename Compare, template <typename> class Alloc>
template <typename _Key, typename _Value>
 
auto LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::Insert(_Key&& key,
                                                                 _Value&& value)
    -> std::pair<const_iterator, bool> {
  Bucket bucket{map_.end(), map_.end(), std::forward<_Value>(value)};
 
  // If the item is too large, do not insert it.
  std::size_t valueCost = cache_cost_func_(bucket.value_);
  if (valueCost > max_size_)
    return std::make_pair(const_iterator{end()}, false);
 
  auto it =
      porting::try_emplace(map_, std::forward<_Key>(key), std::move(bucket));
 
  if (it.second) {
    AddInternal(it.first, valueCost);
    return std::make_pair(const_iterator{it.first}, true);
  }
  Promote(it.first);
  return std::make_pair(const_iterator{it.first}, false);
}
 
template <typename Key, typename Value, typename CacheCostFunc,
          typename Compare, template <typename> class Alloc>
template <typename _Value>
 
auto LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::InsertOrAssign(
    Key key, _Value&& value) -> std::pair<const_iterator, bool> {
  // as we need "key" with the right type a couple of times, create a temp
  // copy to prevent implicit conversions below
  auto it = map_.lower_bound(key);
  if (it != map_.end() && IsEqual(key, it->first)) {
    // element already exists, update it
    std::size_t oldCost = cache_cost_func_(it->second.value_);
    it->second.value_ = std::forward<_Value>(value);
    std::size_t newCost = cache_cost_func_(it->second.value_);
    AddInternal(it, newCost, &oldCost);
    return std::make_pair(const_iterator{it}, false);
  } else {
    // element doesn't exist, insert it
    Bucket bucket{map_.end(), map_.end(), std::forward<_Value>(value)};
    std::size_t newCost = cache_cost_func_(bucket.value_);
    if (newCost > max_size_)
      return std::make_pair(const_iterator{end()}, false);
 
    auto new_it =
        map_.insert(it, std::make_pair(std::move(key), std::move(bucket)));
    AddInternal(new_it, newCost);
    return std::make_pair(const_iterator{new_it}, true);
  }
}
 
template <typename Key, typename Value, typename CacheCostFunc,
          typename Compare, template <typename> class Alloc>
void LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::Promote(
    const typename MapType::iterator& it) {
  if (it == first_)
    return;  // nothing to do
 
  // re-link previous and next buckets together
  it->second.previous_->second.setNext(it->second.next_);
  if (it->second.next_ != map_.end())
    it->second.next_->second.setPrevious(it->second.previous_);
  else
    last_ = it->second.previous_;
 
  // re-link our bucket
  it->second.setPrevious(map_.end());
  it->second.setNext(first_);
 
  // update current head to ourselves
  first_->second.setPrevious(it);
  first_ = it;
}
 
template <typename Key, typename Value, typename CacheCostFunc,
          typename Compare, template <typename> class Alloc>
void LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::AddInternal(
    const typename MapType::iterator& it, std::size_t cost,
    std::size_t* oldCost) {
  if (!oldCost) {
    // new bucket added
    if (map_.size() == 1) {
      // we're the first and only one.
      assert(last_ == map_.end() && first_ == map_.end());
      last_ = first_ = it;
    } else {
      // relink first bucket
      it->second.setNext(first_);
      first_->second.setPrevious(it);
      first_ = it;
    }
    size_ += cost;
  } else {
    // key already in map - only promote
    size_ += cost - *oldCost;
    Promote(it);
  }
 
  evict();
}
 
template <typename Key, typename Value, typename CacheCostFunc,
          typename Compare, template <typename> class Alloc>
void LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::Erase(
    typename MapType::iterator it, bool doEvictionCallback) {
  std::size_t cost = cache_cost_func_(it->second.value_);
 
  if (it->second.next_ == map_.end())
    last_ = it->second.previous_;
  else
    it->second.next_->second.setPrevious(it->second.previous_);
 
  if (it->second.previous_ == map_.end())
    first_ = it->second.next_;
  else
    it->second.previous_->second.setNext(it->second.next_);
 
  if (doEvictionCallback && eviction_callback_)
    eviction_callback_(it->first, std::move(it->second.value_));
 
  map_.erase(it);
  size_ -= cost;
}
 
template <typename Key, typename Value, typename CacheCostFunc,
          typename Compare, template <typename> class Alloc>
void LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::PopLast() {
  // assert if the cache is empty
  assert(last_ != map_.end());
  // assert that our item's 'next' is pointing indeed to the end of the cache
  assert(last_->second.next_ == map_.end());
 
  Erase(last_, true);
}
 
template <typename Key, typename Value, typename CacheCostFunc,
          typename Compare, template <typename> class Alloc>
inline const Key&
LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::ValueType::key() const {
  return m_it->first;
}
 
template <typename Key, typename Value, typename CacheCostFunc,
          typename Compare, template <typename> class Alloc>
inline const Value&
LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::ValueType::value() const {
  return m_it->second.value_;
}
 
template <typename Key, typename Value, typename CacheCostFunc,
          typename Compare, template <typename> class Alloc>
inline bool
LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::const_iterator::operator==(
    const const_iterator& other) const {
  return this->m_it == other.m_it;
}
 
template <typename Key, typename Value, typename CacheCostFunc,
          typename Compare, template <typename> class Alloc>
inline typename LruCache<Key, Value, CacheCostFunc, Compare,
                         Alloc>::const_iterator&
LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::const_iterator::
operator++() {
  this->m_it = this->m_it->second.next_;
  return *this;
}
 
template <typename Key, typename Value, typename CacheCostFunc,
          typename Compare, template <typename> class Alloc>
inline
    typename LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::const_iterator
    LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::const_iterator::
    operator++(int) {
  typename MapType::const_iterator old_value = this->m_it;
  this->m_it = this->m_it->second.next_;
  return const_iterator{old_value};
}
 
template <typename Key, typename Value, typename CacheCostFunc,
          typename Compare, template <typename> class Alloc>
inline typename LruCache<Key, Value, CacheCostFunc, Compare,
                         Alloc>::const_iterator&
LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::const_iterator::
operator--() {
  this->m_it = this->m_it->second.m_previous;
  return *this;
}
 
template <typename Key, typename Value, typename CacheCostFunc,
          typename Compare, template <typename> class Alloc>
inline
    typename LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::const_iterator
    LruCache<Key, Value, CacheCostFunc, Compare, Alloc>::const_iterator::
    operator--(int) {
  typename MapType::const_iterator old_value = this->m_it;
  this->m_it = this->m_it->second.m_previous;
  return const_iterator{old_value};
}
 
}  // namespace utils
}  // namespace olp