about summary refs log tree commit diff
path: root/third_party/nix/src/libutil/lru-cache.hh
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/nix/src/libutil/lru-cache.hh')
-rw-r--r--third_party/nix/src/libutil/lru-cache.hh90
1 files changed, 0 insertions, 90 deletions
diff --git a/third_party/nix/src/libutil/lru-cache.hh b/third_party/nix/src/libutil/lru-cache.hh
deleted file mode 100644
index 1832c542449e..000000000000
--- a/third_party/nix/src/libutil/lru-cache.hh
+++ /dev/null
@@ -1,90 +0,0 @@
-#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