Eigen/src/Core/util/LruCache.h

// This file is part of Eigen, a lightweight C++ template library
// for linear algebra.
//
// Copyright (C) 2026 Rasmus Munk Larsen <rmlarsen@gmail.com>
//
// This Source Code Form is subject to the terms of the Mozilla
// Public License v. 2.0. If a copy of the MPL was not distributed
// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
// SPDX-License-Identifier: MPL-2.0

#ifndef EIGEN_LRU_CACHE_H
#define EIGEN_LRU_CACHE_H

#include <cstddef>
#include <functional>
#include <list>
#include <unordered_map>
#include <utility>

#include "../InternalHeaderCheck.h"

namespace Eigen {
namespace internal {

// Bounded least-recently-used cache.
//
// Keyed on Key (hashed by Hash, compared by KeyEqual) and storing movable
// Value objects. find() and insert() are O(1) average: an unordered_map
// lookup plus a constant-time std::list splice. On hit, the touched entry
// is promoted to the front of the list. On insert into a full cache, the
// back of the list (least-recently-used) is destroyed before the new entry
// is added — Value's destructor runs, so an RAII Value handles eviction
// cleanup without any additional callback machinery.
//
// Thread safety: none. Callers must serialize.
//
// Not intended for hot-loop O(n) workloads where n is large; for the small
// caches Eigen uses (handful of entries, low shape cardinality), the
// node-allocation overhead of std::list / std::unordered_map is amortized
// across many hits per insert.
template <typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>>
class LruCache {
 public:
  using key_type = Key;
  using value_type = Value;

  explicit LruCache(std::size_t capacity) : capacity_(capacity) {
    eigen_assert(capacity_ > 0 && "LruCache capacity must be positive");
    // Pre-size the bucket array so the map never rehashes while filling. A
    // rehash is otherwise guaranteed once load factor crosses ~1.0.
    index_.reserve(capacity_);
  }

  LruCache(const LruCache&) = delete;
  LruCache& operator=(const LruCache&) = delete;

  LruCache(LruCache&& o) noexcept : capacity_(o.capacity_), items_(std::move(o.items_)), index_(std::move(o.index_)) {}

  LruCache& operator=(LruCache&& o) noexcept {
    if (this != &o) {
      capacity_ = o.capacity_;
      items_ = std::move(o.items_);
      index_ = std::move(o.index_);
    }
    return *this;
  }

  ~LruCache() = default;

  // Returns a pointer to the cached value and marks it most-recently-used,
  // or nullptr if the key is not present.
  Value* find(const Key& key) {
    auto map_it = index_.find(key);
    if (map_it == index_.end()) return nullptr;
    items_.splice(items_.begin(), items_, map_it->second);
    return &map_it->second->second;
  }

  // Inserts (key, value), evicting the least-recently-used entry if the cache
  // is at capacity. If the key already exists, the existing entry is destroyed
  // and a new entry is inserted as most-recently-used.
  // Returns a pointer to the inserted value, or nullptr if capacity is 0
  // (degenerate case — assert-firing in debug; the early return keeps release
  // builds from dereferencing items_.back() on an empty list).
  Value* insert(const Key& key, Value value) {
    if (capacity_ == 0) return nullptr;
    auto map_it = index_.find(key);
    if (map_it != index_.end()) {
      auto old_it = map_it->second;
      items_.emplace_front(key, std::move(value));
      map_it->second = items_.begin();
      items_.erase(old_it);
      return &map_it->second->second;
    }
    if (items_.size() >= capacity_) {
      index_.erase(items_.back().first);
      items_.pop_back();
    }
    items_.emplace_front(key, std::move(value));
    index_.emplace(key, items_.begin());
    return &items_.front().second;
  }

  void clear() {
    items_.clear();
    index_.clear();
  }

  std::size_t size() const { return items_.size(); }
  std::size_t capacity() const { return capacity_; }
  bool empty() const { return items_.empty(); }

 private:
  using list_type = std::list<std::pair<Key, Value>>;

  std::size_t capacity_;
  list_type items_;
  std::unordered_map<Key, typename list_type::iterator, Hash, KeyEqual> index_;
};

}  // namespace internal
}  // namespace Eigen

#endif  // EIGEN_LRU_CACHE_H