LruCache.h

Go to the documentation of this file.

/*
 * MIT License
 *
 * Copyright (c) 2025 nfx
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

 
#pragma once
 
#include <chrono>
#include <functional>
#include <mutex>
#include <optional>
#include <unordered_map>
 
namespace nfx::cache
{
    //=====================================================================
    // LruCacheOptions struct
    //=====================================================================

    struct LruCacheOptions final
    {
        //----------------------------------------------
        // Construction
        //----------------------------------------------

        inline LruCacheOptions(
            std::size_t sizeLimit = 0,
            std::chrono::milliseconds slidingExpiration = std::chrono::hours{ 1 },
            std::chrono::milliseconds backgroundCleanupInterval = std::chrono::milliseconds{ 0 } );
 
        //----------------------------------------------
        // Accessors
        //----------------------------------------------

        [[nodiscard]] inline std::size_t sizeLimit() const;

        [[nodiscard]] inline std::chrono::milliseconds slidingExpiration() const;

        [[nodiscard]] inline std::chrono::milliseconds backgroundCleanupInterval() const;
 
    private:
        std::size_t m_sizeLimit{ 0 };

        std::chrono::milliseconds m_slidingExpiration{ std::chrono::minutes{ 60 } };
 
        /*
         * Background cleanup design:
         * - When enabled (interval > 0), cache tracks last cleanup time
         * - During get/find operations, checks if cleanup interval has elapsed
         * - If elapsed, performs incremental cleanup of expired entries
         * - Amortizes cleanup cost across normal operations without requiring separate thread
         * - Ideal for write-heavy scenarios with unique keys (logging, batch processing)
         * - For very low-activity caches, still requires occasional manual cleanupExpired() calls
         */
        std::chrono::milliseconds m_backgroundCleanupInterval{ std::chrono::milliseconds{ 0 } };
    };
 
    //=====================================================================
    // CacheEntry struct
    //=====================================================================

    struct CacheEntry final
    {
        std::chrono::steady_clock::time_point lastAccessed;

        std::chrono::milliseconds slidingExpiration;

        std::size_t size{ 1 };

        CacheEntry* lruPrev{ nullptr };

        CacheEntry* lruNext{ nullptr };

        const void* keyPtr{ nullptr };
 
        //----------------------------------------------
        // Construction
        //----------------------------------------------

        inline CacheEntry( std::chrono::milliseconds expiration = std::chrono::hours( 1 ) );
 
        //----------------------------------------------
        // Expiration checking
        //----------------------------------------------

        [[nodiscard]] inline bool isExpired() const noexcept;
 
        //----------------------------------------------
        // Access management
        //----------------------------------------------

        void inline touch() noexcept;
    };
 
    //=====================================================================
    // LruCache class
    //=====================================================================

    template <typename TKey, typename TValue>
    class LruCache final
    {
    public:
        //----------------------------------------------
        // Type aliases
        //----------------------------------------------

        using FactoryFunction = std::function<TValue()>;

        using ConfigFunction = std::function<void( CacheEntry& )>;
 
        //----------------------------------------------
        // Construction
        //----------------------------------------------

        inline explicit LruCache( const LruCacheOptions& options = {} );
 
        //----------------------------------------------
        // Copy and move operations
        //----------------------------------------------
 
        LruCache( const LruCache& ) = delete;
        LruCache( LruCache&& ) = delete;
 
        //----------------------------------------------
        // Assignment operations
        //----------------------------------------------
 
        LruCache& operator=( const LruCache& ) = delete;
        LruCache& operator=( LruCache&& ) = delete;
 
        //----------------------------------------------
        // Destruction
        //----------------------------------------------
 
        // Default destructor
        ~LruCache() = default;
 
        //----------------------------------------------
        // Cache operations
        //----------------------------------------------

        inline TValue* get( const TKey& key, FactoryFunction factory, ConfigFunction configure = nullptr );
 
        //----------------------------------------------
        // Lookup operations
        //----------------------------------------------

        inline TValue* find( const TKey& key );
 
        //----------------------------------------------
        // Modification operations
        //----------------------------------------------

        inline bool remove( const TKey& key );

        inline void clear();

        inline std::size_t size() const;
 
        //----------------------------------------------
        // State inspection
        //----------------------------------------------

        inline bool isEmpty() const;

        inline void cleanupExpired();
 
    private:
        //----------------------------------------------
        // Background cleanup
        //----------------------------------------------

        static constexpr size_t MAX_CLEANUP_PER_CYCLE = 10;

        inline void checkAndPerformBackgroundCleanup();
 
        //----------------------------------------------
        // Internal data structures
        //----------------------------------------------

        struct CachedItem
        {
            TValue value;

            CacheEntry metadata;

            CachedItem( TValue val, CacheEntry meta );
        };
 
        mutable std::mutex m_mutex;
        std::unordered_map<TKey, CachedItem> m_cache;
        LruCacheOptions m_options;

        CacheEntry* m_lruHead;

        CacheEntry* m_lruTail;

        std::chrono::steady_clock::time_point m_lastCleanupTime;
 
        //----------------------------------------------
        // LRU list management
        //----------------------------------------------

        inline void addToLruHead( CacheEntry* entry ) noexcept;

        inline void removeFromLru( CacheEntry* entry ) noexcept;

        inline void moveToLruHead( CacheEntry* entry ) noexcept;

        inline void evictLeastRecentlyUsed();
    };
} // namespace nfx::cache
 
#include "nfx/detail/cache/LruCache.inl"