1  // Modified version of: https://www.boost.org/doc/libs/1_79_0/boost/compute/detail/lru_cache.hpp
  2  // Most important change is the use of an array instead of a map, so that elements are
  3  // statically allocated. The insert and get methods have been merged into the request method.
  4  // Original license:
  5  //
  6  //---------------------------------------------------------------------------//
  7  // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
  8  //
  9  // Distributed under the Boost Software License, Version 1.0
 10  // See accompanying file LICENSE_1_0.txt or copy at
 11  // http://www.boost.org/LICENSE_1_0.txt
 12  //
 13  // See http://boostorg.github.com/compute for more information.
 14  //---------------------------------------------------------------------------//
 15  #pragma once
 16  
 17  #include <array>
 18  #include <list>
 19  #include <tuple>
 20  #include <utility>
 21  
 22  namespace Common {
 23  
 24  // a cache which evicts the least recently used item when it is full
 25  // the cache elements are statically allocated.
 26  template <class Key, class Value, std::size_t Size>
 27  class StaticLRUCache {
 28  public:
 29      using key_type = Key;
 30      using value_type = Value;
 31      using list_type = std::list<std::pair<Key, std::size_t>>;
 32      using array_type = std::array<Value, Size>;
 33  
 34      StaticLRUCache() = default;
 35  
 36      ~StaticLRUCache() = default;
 37  
 38      std::size_t size() const {
 39          return m_list.size();
 40      }
 41  
 42      constexpr std::size_t capacity() const {
 43          return m_array.size();
 44      }
 45  
 46      bool empty() const {
 47          return m_list.empty();
 48      }
 49  
 50      bool contains(const key_type& key) const {
 51          return find(key) != m_list.end();
 52      }
 53  
 54      // Requests an element from the cache. If it is not found,
 55      // the element is inserted using its key.
 56      // Returns whether the element was present in the cache
 57      // and a reference to the element itself.
 58      std::pair<bool, value_type&> request(const key_type& key) {
 59          // lookup value in the cache
 60          auto i = find(key);
 61          if (i == m_list.cend()) {
 62              std::size_t next_index = size();
 63              // insert item into the cache, but first check if it is full
 64              if (next_index >= capacity()) {
 65                  // cache is full, evict the least recently used item
 66                  next_index = evict();
 67              }
 68  
 69              // insert the new item
 70              m_list.push_front(std::make_pair(key, next_index));
 71              return std::pair<bool, value_type&>(false, m_array[next_index]);
 72          }
 73          // return the value, but first update its place in the most
 74          // recently used list
 75          if (i != m_list.cbegin()) {
 76              // move item to the front of the most recently used list
 77              auto backup = *i;
 78              m_list.erase(i);
 79              m_list.push_front(backup);
 80  
 81              // return the value
 82              return std::pair<bool, value_type&>(true, m_array[backup.second]);
 83          } else {
 84              // the item is already at the front of the most recently
 85              // used list so just return it
 86              return std::pair<bool, value_type&>(true, m_array[i->second]);
 87          }
 88      }
 89  
 90      void clear() {
 91          m_list.clear();
 92      }
 93  
 94  private:
 95      typename list_type::const_iterator find(const key_type& key) const {
 96          return std::find_if(m_list.cbegin(), m_list.cend(),
 97                              [&key](const auto& el) { return el.first == key; });
 98      }
 99  
100      std::size_t evict() {
101          // evict item from the end of most recently used list
102          typename list_type::iterator i = --m_list.end();
103          std::size_t evicted_index = i->second;
104          m_list.erase(i);
105          return evicted_index;
106      }
107  
108  private:
109      array_type m_array;
110      list_type m_list;
111  };
112  
113  } // namespace Common