1 files changed, 70 insertions, 0 deletions
diff --git a/src/lru.hh b/src/lru.hh
new file mode 100644
index 0000000..3279b35
--- /dev/null
+++ b/src/lru.hh
@@ -0,0 +1,70 @@
+// -*- mode: c++; c-basic-offset: 2; -*-
+
+#ifndef LRU_HH
+#define LRU_HH
+
+#include <algorithm>
+#include <deque>
+#include <unordered_map>
+
+template<typename K, typename V>
+class lru {
+public:
+  lru(size_t size)
+    : size_(size) {
+  }
+
+  bool empty() const {
+    return usage_.empty();
+  }
+
+  size_t size() const {
+    return usage_.size();
+  }
+
+  V* get(K const& key) {
+    auto it = data_.find(key);
+    if (it == data_.end()) return nullptr;
+    auto it2 = std::find(usage_.begin(), usage_.end(), key);
+    if (it2 != usage_.begin()) {
+      usage_.erase(it2);
+      usage_.push_front(key);
+    }
+    return &it->second;
+  }
+
+  void insert(K const& key, V const& data) {
+    auto pair = data_.insert(std::make_pair(key, data));
+    if (pair.second) {
+      usage_.push_front(key);
+      shrink_to_size();
+    } else {
+      pair.first->second = data;
+      auto it = std::find(usage_.begin(), usage_.end(), key);
+      if (it != usage_.begin()) {
+        usage_.erase(it);
+        usage_.push_front(key);
+      }
+    }
+  }
+
+  void erase(K const& key) {
+    if (data_.erase(key)) {
+      usage_.erase(std::find(usage_.begin(), usage_.end(), key));
+    }
+  }
+
+private:
+  void shrink_to_size() {
+    if (usage_.size() > size_) {
+      data_.erase(usage_.back());
+      usage_.pop_back();
+    }
+  }
+
+  size_t const size_;
+  std::deque<K> usage_;
+  std::unordered_map<K, V> data_;
+};
+
+#endif  // LRU_HH