KLruCache.h

#pragma once 

#include <cstring>
#include <list>
#include <memory>
#include <mutex>
#include <unordered_map>

#include "KICachePolicy.h"

namespace KamaCache
{

// 前向声明，让 LruNode 知道 KLruCache 的存在
template<typename Key, typename Value> class KLruCache;

// LRU 缓存的链表节点
template<typename Key, typename Value>
class LruNode 
{
private:
    // 存储键
    Key key_;
    // 存储值
    Value value_;
    // 记录该节点被访问的次数
    size_t accessCount_;  
    // 指向前一个节点的弱指针。使用 weak_ptr 是为了防止与 next_ 产生循环引用导致内存泄漏
    std::weak_ptr<LruNode<Key, Value>> prev_;  
    // 指向后一个节点的强指针
    std::shared_ptr<LruNode<Key, Value>> next_;

public:
    // 构造函数：初始化键值，初始访问次数为 1
    LruNode(Key key, Value value)
        : key_(key)
        , value_(value)
        , accessCount_(1) 
    {}

    // 获取当前节点的键
    Key getKey() const { return key_; }
    // 获取当前节点的值
    Value getValue() const { return value_; }
    // 更新当前节点的值
    void setValue(const Value& value) { value_ = value; }
    // 获取访问次数
    size_t getAccessCount() const { return accessCount_; }
    // 增加访问次数
    void incrementAccessCount() { ++accessCount_; }

    // 允许 KLruCache 直接访问私有成员，方便链表操作
    friend class KLruCache<Key, Value>;
};


// 标准 LRU 缓存实现
template<typename Key, typename Value>
class KLruCache : public KICachePolicy<Key, Value>
{
public:
    // 定义别名，提高代码可读性
    using LruNodeType = LruNode<Key, Value>;
    using NodePtr = std::shared_ptr<LruNodeType>;
    using NodeMap = std::unordered_map<Key, NodePtr>;

    // 构造函数：指定缓存的最大容量
    KLruCache(int capacity)
        : capacity_(capacity)
    {
        // 初始化双向循环链表的虚假头尾节点
        initializeList();
    }

    // 虚析构函数
    ~KLruCache() override = default;

    // 向缓存放入数据
    void put(Key key, Value value) override
    {
        // 容量不合法则直接退出
        if (capacity_ <= 0)
            return;
    
        // 整个操作加锁，确保线程安全
        std::lock_guard<std::mutex> lock(mutex_);
        
        // 在哈希表中查找该键
        auto it = nodeMap_.find(key);
        if (it != nodeMap_.end())
        {
            // 如果数据已存在，则更新值并将其移动到链表最末尾（表示最近访问过）
            updateExistingNode(it->second, value);
            return ;
        }

        // 如果数据不存在，作为新节点添加
        addNewNode(key, value);
    }

    // 从缓存获取数据（通过引用返回）
    bool get(Key key, Value& value) override
    {
        // 加锁确保线程安全
        std::lock_guard<std::mutex> lock(mutex_);
        
        auto it = nodeMap_.find(key);
        if (it != nodeMap_.end())
        {
            // 如果命中缓存，将其移动到链表末尾（代表最新访问）
            moveToMostRecent(it->second);
            // 传出结果
            value = it->second->getValue();
            return true;
        }
        // 未命中
        return false;
    }

    // 从缓存获取数据（直接返回 Value）
    Value get(Key key) override
    {
        Value value{};
        // 内部调用带引用的 get 方法
        get(key, value);
        return value;
    }

    // 从缓存中主动删除某个元素
    void remove(Key key) 
    {   
        std::lock_guard<std::mutex> lock(mutex_);
        auto it = nodeMap_.find(key);
        if (it != nodeMap_.end())
        {
            // 先从双向链表中移除节点
            removeNode(it->second);
            // 再从哈希表中移除
            nodeMap_.erase(it);
        }
    }

private:
    // 初始化链表：创建哨兵节点（Dummy Nodes）
    // 哨兵节点可以简化链表操作，不需要处理 head 或 tail 为空的情况
    void initializeList()
    {
        // 虚拟头结点
        dummyHead_ = std::make_shared<LruNodeType>(Key(), Value());
        // 虚拟尾结点
        dummyTail_ = std::make_shared<LruNodeType>(Key(), Value());
        // 头尾相连
        dummyHead_->next_ = dummyTail_;
        dummyTail_->prev_ = dummyHead_;
    }

    // 更新已存在的节点
    void updateExistingNode(NodePtr node, const Value& value) 
    {
        // 赋新值
        node->setValue(value);
        // 提升该节点到“最近使用”的位置
        moveToMostRecent(node);
    }

    // 添加全新节点
    void addNewNode(const Key& key, const Value& value) 
    {
       // 如果容量已满，需要先淘汰最久未使用的节点
       if (nodeMap_.size() >= capacity_) 
       {
           evictLeastRecent();
       }

       // 创建新节点
       NodePtr newNode = std::make_shared<LruNodeType>(key, value);
       // 插入到链表尾部（靠近 dummyTail 的位置代表最新）
       insertNode(newNode);
       // 存入哈希表方便 $O(1)$ 查找
       nodeMap_[key] = newNode;
    }

    // 将现有节点移动到链表最新端
    void moveToMostRecent(NodePtr node) 
    {
        // 先从当前位置断开
        removeNode(node);
        // 重新插入到尾部
        insertNode(node);
    }

    // 逻辑上从双向链表中剥离该节点
    void removeNode(NodePtr node) 
    {
        // 检查前驱和后继是否有效
        if(!node->prev_.expired() && node->next_) 
        {
            // 将前一个节点的 next 指向后一个节点
            auto prev = node->prev_.lock(); 
            prev->next_ = node->next_;
            // 将后一个节点的 prev 指向前一个节点
            node->next_->prev_ = prev;
            // 彻底切断当前节点向后的联系
            node->next_ = nullptr; 
        }
    }

    // 核心操作：在链表尾部插入节点（紧挨着 dummyTail 之前）
    void insertNode(NodePtr node) 
    {
        // 新节点指向 dummyTail
        node->next_ = dummyTail_;
        // 新节点的 prev 指向原本的末尾节点
        node->prev_ = dummyTail_->prev_;
        // 让原本的末尾节点指向新节点
        dummyTail_->prev_.lock()->next_ = node; 
        // dummyTail 的 prev 更新为新节点
        dummyTail_->prev_ = node;
    }

    // 淘汰策略：删除最久未访问的节点（dummyHead 之后的第一个节点）
    void evictLeastRecent() 
    {
        // 紧跟在 dummyHead 后面的就是“最老”的节点
        NodePtr leastRecent = dummyHead_->next_;
        // 从链表移除
        removeNode(leastRecent);
        // 从哈希表移除
        nodeMap_.erase(leastRecent->getKey());
    }

private:
    // 缓存的最大记录数
    int capacity_; 
    // 用于快速定位节点的哈希表
    NodeMap nodeMap_; 
    // 保证线程安全的互斥锁
    std::mutex mutex_;
    // 哨兵头节点（离它越近表示数据越老）
    NodePtr dummyHead_; 
    // 哨兵尾节点（离它越近表示数据越新）
    NodePtr dummyTail_;
};

// LRU 优化：LRU-K 版本
// 目的：解决“缓存污染”问题。只有当数据被访问过 K 次后，才真正进入缓存。
template<typename Key, typename Value>
class KLruKCache : public KLruCache<Key, Value>
{
public:
    // 构造函数
    // capacity: 主缓存容量
    // historyCapacity: 历史队列容量
    // k: 触发进入主缓存的阈值
    KLruKCache(int capacity, int historyCapacity, int k)
        : KLruCache<Key, Value>(capacity) 
        , historyList_(std::make_unique<KLruCache<Key, size_t>>(historyCapacity))
        , k_(k)
    {}

    // 重写获取逻辑
    Value get(Key key) 
    {
        // 首先尝试从正式的主缓存获取
        Value value{};
        bool inMainCache = KLruCache<Key, Value>::get(key, value);

        // 无论主缓存有没有，都要更新这个 key 的访问历史次数
        size_t historyCount = historyList_->get(key);
        historyCount++;
        // 将新的次数存回历史队列
        historyList_->put(key, historyCount);

        // 如果已经在主缓存，直接返回即可（内部已处理过 LRU 提升）
        if (inMainCache) 
        {
            return value;
        }

        // 如果不在主缓存，检查它的历史访问次数是否达到了 K 次
        if (historyCount >= k_) 
        {
            // 达到次数后，尝试从历史值存储中找回它对应的数据
            auto it = historyValueMap_.find(key);
            if (it != historyValueMap_.end()) 
            {
                // 获取保存的原始值
                Value storedValue = it->second;
                
                // 既然要进入主缓存了，就从历史统计和历史值映射中删除
                historyList_->remove(key);
                historyValueMap_.erase(it);
                
                // 正式晋升：添加到主缓存
                KLruCache<Key, Value>::put(key, storedValue);
                
                return storedValue;
            }
        }

        // 还没达到 K 次，或找不到历史值，返回默认构造的值
        return value;
    }

    // 重写存入逻辑
    void put(Key key, Value value) 
    {
        // 先看主缓存里有没有
        Value existingValue{};
        bool inMainCache = KLruCache<Key, Value>::get(key, existingValue);
        
        if (inMainCache) 
        {
            // 如果已在主缓存，直接更新值，LRU 内部会处理提升
            KLruCache<Key, Value>::put(key, value);
            return;
        }
        
        // 更新访问次数记录
        size_t historyCount = historyList_->get(key);
        historyCount++;
        historyList_->put(key, historyCount);
        
        // 注意：这里需要先把值存起来，因为在达到 K 次之前，它还没资格进主缓存
        historyValueMap_[key] = value;
        
        // 检查是否达到晋升条件
        if (historyCount >= k_) 
        {
            // 达到阈值，将其从临时区（历史记录）移动到正式区（主缓存）
            historyList_->remove(key);
            historyValueMap_.erase(key);
            KLruCache<Key, Value>::put(key, value);
        }
    }

private:
    // 进入主缓存的访问次数门槛
    int k_; 
    // 历史队列：存储 Key 到 访问次数 的映射，其本身也是一个 LRU 结构
    std::unique_ptr<KLruCache<Key, size_t>> historyList_; 
    // 临时存储区：存储那些还没达到 K 次访问的节点的数据值
    std::unordered_map<Key, Value> historyValueMap_; 
};

// LRU 优化：分片（Sharding）缓存
// 目的：降低锁的粒度。如果多个线程同时访问同一个 LRU，会导致锁竞争。
// 分片后，不同的 key 会落到不同的切片上，只有访问同一个切片才会竞争锁。
template<typename Key, typename Value>
class KHashLruCaches
{
public:
    // capacity: 总容量
    // sliceNum: 切片数量（类似 Java ConcurrentHashMap 的分段锁）
    KHashLruCaches(size_t capacity, int sliceNum)
        : capacity_(capacity)
        , sliceNum_(sliceNum > 0 ? sliceNum : std::thread::hardware_concurrency())
    {
        // 向上取整计算每个分片应有的容量
        size_t sliceSize = std::ceil(capacity / static_cast<double>(sliceNum_)); 
        for (int i = 0; i < sliceNum_; ++i)
        {
            // 为每个切片创建一个独立的 KLruCache 对象
            lruSliceCaches_.emplace_back(new KLruCache<Key, Value>(sliceSize)); 
        }
    }

    // 存入数据
    void put(Key key, Value value)
    {
        // 1. 计算 key 的哈希值。2. 取模找到对应的分片。3. 只在这个分片内加锁操作。
        size_t sliceIndex = Hash(key) % sliceNum_;
        lruSliceCaches_[sliceIndex]->put(key, value);
    }

    // 获取数据（引用返回）
    bool get(Key key, Value& value)
    {
        // 定位分片并获取
        size_t sliceIndex = Hash(key) % sliceNum_;
        return lruSliceCaches_[sliceIndex]->get(key, value);
    }

    // 获取数据（直接返回）
    Value get(Key key)
    {
        Value value;
        // 注意：此处的 memset 仅适用于 POD 类型，如果 Value 是 std::string，这行会有问题
        memset(&value, 0, sizeof(value));
        get(key, value);
        return value;
    }

private:
    // 内部哈希函数：将 Key 转换为索引
    size_t Hash(Key key)
    {
        std::hash<Key> hashFunc;
        return hashFunc(key);
    }

private:
    // 总缓存容量上限
    size_t capacity_;  
    // 切片总数
    int sliceNum_;  
    // 存储切片实例的容器
    std::vector<std::unique_ptr<KLruCache<Key, Value>>> lruSliceCaches_; 
};

} // namespace KamaCache