lru_cache.cpp

#include "lru_cache.h"

LRUCache::LRUCache(std::size_t capacity)
    : cap(capacity), head(nullptr), tail(nullptr) {}

LRUCache::~LRUCache() {
    free_all();
}

void LRUCache::add_front(Node* node) {
    node->prev = nullptr;
    node->next = head;

    if (head != nullptr) {
        head->prev = node;
    } else {
        tail = node;
    }

    head = node;
}

void LRUCache::detach(Node* node) {
    if (node->prev != nullptr) {
        node->prev->next = node->next;
    } else {
        head = node->next;
    }

    if (node->next != nullptr) {
        node->next->prev = node->prev;
    } else {
        tail = node->prev;
    }

    node->prev = nullptr;
    node->next = nullptr;
}

void LRUCache::touch(Node* node) {
    if (node == head) {
        return;
    }

    // 被访问过的节点移动到头部，头部始终代表最近使用。
    detach(node);
    add_front(node);
}

LRUCache::Node* LRUCache::pop_tail() {
    Node* old = tail;
    if (old != nullptr) {
        detach(old);
    }
    return old;
}

void LRUCache::free_all() {
    Node* cur = head;
    while (cur != nullptr) {
        Node* next = cur->next;
        delete cur;
        cur = next;
    }

    head = nullptr;
    tail = nullptr;
    cache.clear();
}

int LRUCache::get(int key) {
    auto it = cache.find(key);
    if (it == cache.end()) {
        return -1;
    }

    Node* node = it->second;
    touch(node);
    return node->value;
}

void LRUCache::put(int key, int value) {
    if (cap == 0) {
        return;
    }

    auto it = cache.find(key);
    if (it != cache.end()) {
        Node* node = it->second;
        node->value = value;
        touch(node);
        return;
    }

    Node* node = new Node(key, value);
    add_front(node);
    cache[key] = node;

    if (cache.size() > cap) {
        Node* old = pop_tail();
        cache.erase(old->key);
        delete old;
    }
}

std::size_t LRUCache::size() const {
    return cache.size();
}

std::size_t LRUCache::capacity() const {
    return cap;
}

bool LRUCache::empty() const {
    return cache.empty();
}

bool LRUCache::contains(int key) const {
    return cache.find(key) != cache.end();
}

std::vector<int> LRUCache::keys() const {
    std::vector<int> out;
    out.reserve(cache.size());

    Node* cur = head;
    while (cur != nullptr) {
        out.push_back(cur->key);
        cur = cur->next;
    }
    return out;
}