simple_lru_cache.h

Go to the documentation of this file.

// BSD 3-Clause License
// Copyright (c) 2021-2025, 🍀☀🌕🌥 🌊
// See the LICENSE file in the project root for full license information.
 
#pragma once
 
#include <atomic>
#include <chrono>
#include <cstdint>
#include <functional>
#include <list>
#include <memory>
#include <mutex>
#include <optional>
#include <shared_mutex>
#include <string>
#include <unordered_map>
 
namespace kcenon::pacs::services::cache {
 
// ─────────────────────────────────────────────────────
// Forward Declarations
// ─────────────────────────────────────────────────────
 
template <typename Key, typename Value, typename Hash, typename KeyEqual>
class simple_lru_cache;
 
// ─────────────────────────────────────────────────────
// Cache Configuration
// ─────────────────────────────────────────────────────
 
struct cache_config {
    std::size_t max_size{1000};
 
    std::chrono::seconds ttl{300};
 
    bool enable_metrics{true};
 
    std::string cache_name{"lru_cache"};
};
 
// ─────────────────────────────────────────────────────
// Cache Statistics
// ─────────────────────────────────────────────────────
 
struct cache_stats {
    std::atomic<std::uint64_t> hits{0};        
    std::atomic<std::uint64_t> misses{0};      
    std::atomic<std::uint64_t> insertions{0};  
    std::atomic<std::uint64_t> evictions{0};   
    std::atomic<std::uint64_t> expirations{0}; 
    std::atomic<std::size_t> current_size{0};  
 
    [[nodiscard]] double hit_rate() const noexcept {
        const auto total_hits = hits.load(std::memory_order_relaxed);
        const auto total_misses = misses.load(std::memory_order_relaxed);
        const auto total = total_hits + total_misses;
        if (total == 0) {
            return 0.0;
        }
        return (static_cast<double>(total_hits) / static_cast<double>(total)) * 100.0;
    }
 
    [[nodiscard]] std::uint64_t total_accesses() const noexcept {
        return hits.load(std::memory_order_relaxed) +
               misses.load(std::memory_order_relaxed);
    }
 
    void reset() noexcept {
        hits.store(0, std::memory_order_relaxed);
        misses.store(0, std::memory_order_relaxed);
        insertions.store(0, std::memory_order_relaxed);
        evictions.store(0, std::memory_order_relaxed);
        expirations.store(0, std::memory_order_relaxed);
        // Note: current_size is not reset as it reflects actual cache state
    }
};
 
// ─────────────────────────────────────────────────────
// LRU Cache Implementation
// ─────────────────────────────────────────────────────
 
template <typename Key,
          typename Value,
          typename Hash = std::hash<Key>,
          typename KeyEqual = std::equal_to<Key>>
class simple_lru_cache {
public:
    using key_type = Key;
    using value_type = Value;
    using size_type = std::size_t;
    using clock_type = std::chrono::steady_clock;
    using time_point = clock_type::time_point;
 
    // =========================================================================
    // Construction
    // =========================================================================
 
    explicit simple_lru_cache(const cache_config& config = cache_config{})
        : config_(config)
        , max_size_(config.max_size > 0 ? config.max_size : 1) {
    }
 
    simple_lru_cache(size_type max_size, std::chrono::seconds ttl)
        : max_size_(max_size > 0 ? max_size : 1) {
        config_.max_size = max_size_;
        config_.ttl = ttl;
    }
 
    simple_lru_cache(const simple_lru_cache&) = delete;
    simple_lru_cache& operator=(const simple_lru_cache&) = delete;
 
    simple_lru_cache(simple_lru_cache&& other) noexcept {
        std::unique_lock lock(other.mutex_);
        config_ = std::move(other.config_);
        max_size_ = other.max_size_;
        lru_list_ = std::move(other.lru_list_);
        cache_map_ = std::move(other.cache_map_);
        // Stats are not moved (fresh start for moved-to instance)
    }
 
    simple_lru_cache& operator=(simple_lru_cache&& other) noexcept {
        if (this != &other) {
            std::unique_lock lock1(mutex_, std::defer_lock);
            std::unique_lock lock2(other.mutex_, std::defer_lock);
            std::lock(lock1, lock2);
 
            config_ = std::move(other.config_);
            max_size_ = other.max_size_;
            lru_list_ = std::move(other.lru_list_);
            cache_map_ = std::move(other.cache_map_);
        }
        return *this;
    }
 
    ~simple_lru_cache() = default;
 
    // =========================================================================
    // Cache Operations
    // =========================================================================
 
    [[nodiscard]] std::optional<Value> get(const Key& key) {
        std::unique_lock lock(mutex_);
 
        auto it = cache_map_.find(key);
        if (it == cache_map_.end()) {
            // Cache miss
            stats_.misses.fetch_add(1, std::memory_order_relaxed);
            return std::nullopt;
        }
 
        auto& entry = it->second;
 
        // Check TTL expiration
        if (is_expired(entry->expiry_time)) {
            // Entry expired - remove it
            stats_.expirations.fetch_add(1, std::memory_order_relaxed);
            stats_.misses.fetch_add(1, std::memory_order_relaxed);
            remove_entry(it);
            return std::nullopt;
        }
 
        // Cache hit - move to front (most recently used)
        stats_.hits.fetch_add(1, std::memory_order_relaxed);
        lru_list_.splice(lru_list_.begin(), lru_list_, entry);
 
        return entry->value;
    }
 
    void put(const Key& key, const Value& value) {
        std::unique_lock lock(mutex_);
 
        auto it = cache_map_.find(key);
        if (it != cache_map_.end()) {
            // Update existing entry
            auto& entry = it->second;
            entry->value = value;
            entry->expiry_time = calculate_expiry();
            lru_list_.splice(lru_list_.begin(), lru_list_, entry);
            return;
        }
 
        // Evict if at capacity
        while (cache_map_.size() >= max_size_ && !lru_list_.empty()) {
            evict_oldest();
        }
 
        // Insert new entry at front
        lru_list_.emplace_front(cache_entry{key, value, calculate_expiry()});
        cache_map_[key] = lru_list_.begin();
 
        stats_.insertions.fetch_add(1, std::memory_order_relaxed);
        stats_.current_size.store(cache_map_.size(), std::memory_order_relaxed);
    }
 
    void put(const Key& key, Value&& value) {
        std::unique_lock lock(mutex_);
 
        auto it = cache_map_.find(key);
        if (it != cache_map_.end()) {
            // Update existing entry
            auto& entry = it->second;
            entry->value = std::move(value);
            entry->expiry_time = calculate_expiry();
            lru_list_.splice(lru_list_.begin(), lru_list_, entry);
            return;
        }
 
        // Evict if at capacity
        while (cache_map_.size() >= max_size_ && !lru_list_.empty()) {
            evict_oldest();
        }
 
        // Insert new entry at front
        lru_list_.emplace_front(cache_entry{key, std::move(value), calculate_expiry()});
        cache_map_[key] = lru_list_.begin();
 
        stats_.insertions.fetch_add(1, std::memory_order_relaxed);
        stats_.current_size.store(cache_map_.size(), std::memory_order_relaxed);
    }
 
    [[nodiscard]] bool contains(const Key& key) const {
        std::shared_lock lock(mutex_);
        return cache_map_.find(key) != cache_map_.end();
    }
 
    bool invalidate(const Key& key) {
        std::unique_lock lock(mutex_);
 
        auto it = cache_map_.find(key);
        if (it == cache_map_.end()) {
            return false;
        }
 
        remove_entry(it);
        return true;
    }
 
    template <typename Predicate>
    size_type invalidate_if(Predicate pred) {
        std::unique_lock lock(mutex_);
 
        size_type removed = 0;
        auto it = lru_list_.begin();
 
        while (it != lru_list_.end()) {
            if (pred(it->key, it->value)) {
                cache_map_.erase(it->key);
                it = lru_list_.erase(it);
                ++removed;
            } else {
                ++it;
            }
        }
 
        stats_.current_size.store(cache_map_.size(), std::memory_order_relaxed);
        return removed;
    }
 
    void clear() {
        std::unique_lock lock(mutex_);
 
        lru_list_.clear();
        cache_map_.clear();
        stats_.current_size.store(0, std::memory_order_relaxed);
    }
 
    size_type purge_expired() {
        std::unique_lock lock(mutex_);
 
        size_type removed = 0;
        const auto now = clock_type::now();
 
        auto it = lru_list_.begin();
        while (it != lru_list_.end()) {
            if (is_expired(it->expiry_time, now)) {
                cache_map_.erase(it->key);
                it = lru_list_.erase(it);
                ++removed;
                stats_.expirations.fetch_add(1, std::memory_order_relaxed);
            } else {
                ++it;
            }
        }
 
        stats_.current_size.store(cache_map_.size(), std::memory_order_relaxed);
        return removed;
    }
 
    // =========================================================================
    // Cache Information
    // =========================================================================
 
    [[nodiscard]] size_type size() const {
        std::shared_lock lock(mutex_);
        return cache_map_.size();
    }
 
    [[nodiscard]] bool empty() const {
        std::shared_lock lock(mutex_);
        return cache_map_.empty();
    }
 
    [[nodiscard]] size_type max_size() const noexcept {
        return max_size_;
    }
 
    [[nodiscard]] std::chrono::seconds ttl() const noexcept {
        return config_.ttl;
    }
 
    [[nodiscard]] const std::string& name() const noexcept {
        return config_.cache_name;
    }
 
    [[nodiscard]] const cache_config& config() const noexcept {
        return config_;
    }
 
    // =========================================================================
    // Statistics
    // =========================================================================
 
    [[nodiscard]] const cache_stats& stats() const noexcept {
        return stats_;
    }
 
    [[nodiscard]] double hit_rate() const noexcept {
        return stats_.hit_rate();
    }
 
    void reset_stats() noexcept {
        stats_.reset();
    }
 
private:
    // =========================================================================
    // Internal Types
    // =========================================================================
 
    struct cache_entry {
        Key key;
        Value value;
        time_point expiry_time;
    };
 
    using list_type = std::list<cache_entry>;
    using list_iterator = typename list_type::iterator;
    using map_type = std::unordered_map<Key, list_iterator, Hash, KeyEqual>;
 
    // =========================================================================
    // Internal Helpers
    // =========================================================================
 
    [[nodiscard]] time_point calculate_expiry() const {
        return clock_type::now() + config_.ttl;
    }
 
    [[nodiscard]] bool is_expired(time_point expiry) const {
        return clock_type::now() > expiry;
    }
 
    [[nodiscard]] bool is_expired(time_point expiry, time_point now) const {
        return now > expiry;
    }
 
    void evict_oldest() {
        // Evict from the back (least recently used)
        if (lru_list_.empty()) {
            return;
        }
 
        auto& oldest = lru_list_.back();
        cache_map_.erase(oldest.key);
        lru_list_.pop_back();
 
        stats_.evictions.fetch_add(1, std::memory_order_relaxed);
        stats_.current_size.store(cache_map_.size(), std::memory_order_relaxed);
    }
 
    void remove_entry(typename map_type::iterator map_it) {
        lru_list_.erase(map_it->second);
        cache_map_.erase(map_it);
        stats_.current_size.store(cache_map_.size(), std::memory_order_relaxed);
    }
 
    // =========================================================================
    // Member Variables
    // =========================================================================
 
    cache_config config_;
    size_type max_size_;
 
    mutable std::shared_mutex mutex_;
    list_type lru_list_;
    map_type cache_map_;
 
    cache_stats stats_;
};
 
// ─────────────────────────────────────────────────────
// Type Aliases for Common Use Cases
// ─────────────────────────────────────────────────────
 
template <typename Value>
using string_lru_cache = simple_lru_cache<std::string, Value>;
 
}  // namespace kcenon::pacs::services::cache