1 files changed, 90 insertions, 0 deletions
diff --git a/third_party/nix/src/libutil/lru-cache.hh b/third_party/nix/src/libutil/lru-cache.hh
new file mode 100644
index 000000000000..1832c542449e
--- /dev/null
+++ b/third_party/nix/src/libutil/lru-cache.hh
@@ -0,0 +1,90 @@
+#pragma once
+
+#include <list>
+#include <map>
+#include <optional>
+
+namespace nix {
+
+/* A simple least-recently used cache. Not thread-safe. */
+template <typename Key, typename Value>
+class LRUCache {
+ private:
+  size_t capacity;
+
+  // Stupid wrapper to get around circular dependency between Data
+  // and LRU.
+  struct LRUIterator;
+
+  using Data = std::map<Key, std::pair<LRUIterator, Value>>;
+  using LRU = std::list<typename Data::iterator>;
+
+  struct LRUIterator {
+    typename LRU::iterator it;
+  };
+
+  Data data;
+  LRU lru;
+
+ public:
+  explicit LRUCache(size_t capacity) : capacity(capacity) {}
+
+  /* Insert or upsert an item in the cache. */
+  void upsert(const Key& key, const Value& value) {
+    if (capacity == 0) {
+      return;
+    }
+
+    erase(key);
+
+    if (data.size() >= capacity) {
+      /* Retire the oldest item. */
+      auto oldest = lru.begin();
+      data.erase(*oldest);
+      lru.erase(oldest);
+    }
+
+    auto res = data.emplace(key, std::make_pair(LRUIterator(), value));
+    assert(res.second);
+    auto& i(res.first);
+
+    auto j = lru.insert(lru.end(), i);
+
+    i->second.first.it = j;
+  }
+
+  bool erase(const Key& key) {
+    auto i = data.find(key);
+    if (i == data.end()) {
+      return false;
+    }
+    lru.erase(i->second.first.it);
+    data.erase(i);
+    return true;
+  }
+
+  /* Look up an item in the cache. If it exists, it becomes the most
+     recently used item. */
+  std::optional<Value> get(const Key& key) {
+    auto i = data.find(key);
+    if (i == data.end()) {
+      return {};
+    }
+
+    /* Move this item to the back of the LRU list. */
+    lru.erase(i->second.first.it);
+    auto j = lru.insert(lru.end(), i);
+    i->second.first.it = j;
+
+    return i->second.second;
+  }
+
+  size_t size() { return data.size(); }
+
+  void clear() {
+    data.clear();
+    lru.clear();
+  }
+};
+
+}  // namespace nix