Utilities/detail/LruCache.hpp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008
0009 #pragma once
0010
0011 #include <cstddef>
0012 #include <functional>
0013 #include <list>
0014 #include <optional>
0015 #include <stdexcept>
0016 #include <unordered_map>
0017
0018 namespace Acts::detail {
0019
0020 /// @brief Fixed-capacity least-recently-used (LRU) cache.
0021 ///
0022 /// Associates keys of type @p Key with values of type @p Value and keeps at
0023 /// most @p capacity entries in memory. When the cache is full and a new entry
0024 /// is inserted the least-recently-used entry is evicted.
0025 ///
0026 /// All operations — @c get, @c put — are O(1). "Age" is structural: entries
0027 /// are stored in a doubly-linked list ordered MRU → LRU; a cache hit splices
0028 /// the found node to the front in O(1) without invalidating any iterators.
0029 ///
0030 /// Not thread-safe. Callers that need concurrent access must hold an external
0031 /// mutex around every @c get / @c put call.
0032 ///
0033 /// @tparam Key   Key type. Must be hashable with @p Hash and comparable with
0034 ///               @p Equal.
0035 /// @tparam Value Value type. Must be copy- or move-constructible.
0036 /// @tparam Hash  Hash functor for @p Key (default: @c std::hash<Key>).
0037 /// @tparam Equal Equality functor for @p Key (default: @c std::equal_to<Key>).
0038 template <typename Key, typename Value, typename Hash = std::hash<Key>,
0039           typename Equal = std::equal_to<Key>>
0040 class LruCache {
0041  public:
0042   /// @brief Construct a cache with the given capacity.
0043   /// @param capacity Maximum number of entries to keep.
0044   /// @throws std::invalid_argument if @p capacity is zero.
0045   explicit LruCache(std::size_t capacity) : m_capacity(capacity) {
0046     if (capacity == 0) {
0047       throw std::invalid_argument("LruCache: capacity must be >= 1");
0048     }
0049   }
0050
0051   /// @brief Look up @p key; promote it to MRU on hit.
0052   /// @param key Key to look up.
0053   /// @return A copy of the cached value, or @c std::nullopt on miss.
0054   std::optional<Value> get(const Key& key) {
0055     auto it = m_index.find(key);
0056     if (it == m_index.end()) {
0057       return std::nullopt;
0058     }
0059     // Splice to front — O(1), does not invalidate other iterators.
0060     m_list.splice(m_list.begin(), m_list, it->second);
0061     return it->second->value;
0062   }
0063
0064   /// @brief Insert or update @p key → @p value; evict LRU when at capacity.
0065   /// @param key Key to insert or update.
0066   /// @param value Value to associate with @p key.
0067   void put(const Key& key, Value value) {
0068     if (auto it = m_index.find(key); it != m_index.end()) {
0069       it->second->value = std::move(value);
0070       m_list.splice(m_list.begin(), m_list, it->second);
0071       return;
0072     }
0073     m_list.push_front(Entry{key, std::move(value)});
0074     m_index.emplace(key, m_list.begin());
0075     if (m_list.size() > m_capacity) {
0076       m_index.erase(m_list.back().key);
0077       m_list.pop_back();
0078     }
0079   }
0080
0081   /// @return Number of entries currently in the cache.
0082   std::size_t size() const { return m_list.size(); }
0083
0084   /// @return Maximum number of entries the cache will hold.
0085   std::size_t capacity() const { return m_capacity; }
0086
0087  private:
0088   struct Entry {
0089     Key key;
0090     Value value;
0091   };
0092
0093   std::size_t m_capacity;
0094   std::list<Entry> m_list;  // front = MRU, back = LRU
0095   std::unordered_map<Key, typename std::list<Entry>::iterator, Hash, Equal>
0096       m_index;
0097 };
0098
0099 }  // namespace Acts::detail