LRUCache

lru_cache.h

#ifndef LRU_CACHE_H
#define LRU_CACHE_H

#include <cassert>
#include <memory>
#include <string>
#include <unordered_map>

struct CacheNode {
  CacheNode() : pre(nullptr), next(nullptr) {}

  std::string key;
  std::string value;

  CacheNode *pre;
  CacheNode *next;
};

using CacheNodeSPtr = std::shared_ptr<CacheNode>;

class LRUCache {
 public:
  LRUCache(int32_t capacity);
  ~LRUCache();
  LRUCache(const LRUCache &) = delete;
  LRUCache &operator=(const LRUCache &) = delete;

  // make a CacheNode, insert it into cache
  // if key is already in cache, return -1
  // if success, return 0
  int Insert(const std::string &key, const std::string &value);

  // look up CacheNode in cache by key
  CacheNodeSPtr Lookup(const std::string &key);

 private:
  // remove node from link list
  void Remove(CacheNode *node);

  // insert node at the tail of link list
  void Append(CacheNode *node);

 private:
  // max size of cache
  int32_t capacity_;

  std::unordered_map<std::string, CacheNodeSPtr> kv_;
  CacheNode dummy_;  // link list
};

#endif

lru_cache.cc

#include "lru_cache.h"

LRUCache::LRUCache(int32_t capacity) : capacity_(capacity) {
  dummy_.next = &dummy_;
  dummy_.pre = &dummy_;
}

LRUCache::~LRUCache() {}

int LRUCache::Insert(const std::string &key, const std::string &value) {
  // already exist
  auto it = kv_.find(key);
  if (it != kv_.end()) {
    return -1;
  }

  // full, evict
  if (kv_.size() >= capacity_) {
    kv_.erase(dummy_.next->key);
    Remove(dummy_.next);
  }

  // insert
  auto new_node = std::make_shared<CacheNode>();
  new_node->key = key;
  new_node->value = value;
  Append(new_node.get());
  kv_[key] = std::move(new_node);

  return 0;
}

CacheNodeSPtr LRUCache::Lookup(const std::string &key) {
  auto it = kv_.find(key);
  if (it == kv_.end()) {
    return nullptr;
  }

  // update
  auto node = it->second.get();
  Remove(node);
  Append(node);

  return it->second;
}

void LRUCache::Remove(CacheNode *node) {
  if (node) {
    if (node->pre) {
      node->pre->next = node->next;
    }
    if (node->next) {
      node->next->pre = node->pre;
    }
  }
}

void LRUCache::Append(CacheNode *node) {
  if (node) {
    node->next = &dummy_;
    node->pre = dummy_.pre;
    dummy_.pre->next = node;
    dummy_.pre = node;
  }
}