3.13.3. LRU Cache

The LRU caching scheme is to evict the least recently used item when the cache is full. Since it is a cache or a key value store, the basic data structure should be a map. To maintain the insertion order, we need to use a list to store the ordered items.

🐾 When getting an item from LRU cache, the item will be refreshed.

struct lru_cache {
  lru_cache(int capacity) : capa_(capacity) {}
  int get(int key) {
    if (map_.count(key)) {  // It key exists, update it.
      const auto& value = map_[key]->second;
      promote(key, value);
      return value;
    }
    return -1;
  }
  void put(int key, int value) {
    // If cache is full while inserting, remove the last one.
    if (map_.count(key) == 0 and list_.size() == capa_) {
      auto del = list_.back();
      list_.pop_back();
      map_.erase(del.first);
    }
    promote(key, value);
  }

 private:
  list<pair<int, int>> list_;      // key, value
  unordered_map<int, LITER> map_;  // key, list iterator
  int capa_;
  // Promote (key, iterator of (key, value) pair)
  void promote(int key, int value) {
    if (map_.count(key)) {
      list_.erase(map_[key]);
    }
    list_.emplace_front(key, value);
    map_[key] = list_.begin();
  }

3.13.3.1. LRU-Customized Eviction Scheme

struct node {
  int k;
  int v;
  int z;  // vol, or size
};

class lru_by_size {
  list<node> l;  // key is unique in the ll
  unordered_map<int, list<node>::iterator> m;
  const int CAPSIZE;

 protected:
  int cz = 0;  // current size
  bool __promote(list<node> &l, list<node>::iterator it) {
    if (l.begin() != it) {
      l.splice(l.begin(), l, it, next(it));  // a.splice(x, b, [, ))
      return true;
    }
    return false;
  }

  void __remove_node(list<node>::iterator it) {
    m.erase(it->k);
    l.erase(it);
    cz -= it->z;
  }

  // nn - new node we just add to the list
  void __evict(const node &nn) {
    while (CAPSIZE < cz) {
      // eviction policy
      // traverse list backward and find the node with size equal to nn.z and
      // distance(or time) less than T with tail (concept of time window), if we
      // couldn't find it, evict the last one policy 1
      auto it = l.end();
      int count = 0, T = 10, evicted = 0;
      while (it != l.begin() and count < T) {
        it--;
        count++;
        if (it->z == nn.z and it->k != nn.k) {
          __remove_node(it);
          evicted = 1;
          break;
        }
      }
      // policy 2 - remove from the last one until the capacity is enough
      if (!evicted) {
        while (CAPSIZE < cz and !l.empty()) {
          __remove_node(prev(l.end()));
        }
      }
    }
  }

 public:
  lru_by_size(int cap_) : CAPSIZE(cap_) {}

  int get(int k) {
    if (!m.count(k)) return INT_MIN;
    int r = m[k]->v;
    if (__promote(l, m[k])) m[k] = l.begin();
    return r;
  }

  // first we don't consider constraint of size, we just blindly
  // push_front/promote then we do eviction
  bool put(int k, int v, int z) {
    // 0. edge case
    if (z > CAPSIZE) return false;
    node nn = {k, v, z};
    // 1. old node
    if (m.count(k)) {
      if (__promote(l, m[k])) m[k] = l.begin();
      if (l.front().z != z) {
        cz += z - l.front().z;
        l.front().z = z;
      }
      if (l.front().v != v) l.front().v = v;
    } else {
      // 2. new code
      // 2.1 evict ?
      // 2.2 add new node to front
      l.push_front(nn);
      m[k] = l.begin();
      cz += z;
    }
    __evict(nn);
    return true;
  }

  int getsize() { return cz; }
};

How to promote an item in a list to the front:

[cling]$ list<int> l={2,4,1,3,6,5}
(std::list<int> &) { 2, 4, 1, 3, 6, 5 }
[cling]$ auto it = next(next(l.begin()));
[cling]$ l.splice(l.begin(), l, it, next(it))
[cling]$ l
(std::list<int> &) { 1, 2, 4, 3, 6, 5 }

3.13.3.2. LFU