1 files changed, 148 insertions, 0 deletions
diff --git a/chromium/third_party/blink/renderer/platform/wtf/lru_cache.h b/chromium/third_party/blink/renderer/platform/wtf/lru_cache.h
new file mode 100644
index 00000000000..c2d27f0e430
--- /dev/null
+++ b/chromium/third_party/blink/renderer/platform/wtf/lru_cache.h
@@ -0,0 +1,148 @@
+// Copyright 2020 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_LRU_CACHE_H_
+#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_LRU_CACHE_H_
+
+#include <memory>
+
+#include "third_party/blink/renderer/platform/wtf/allocator/allocator.h"
+#include "third_party/blink/renderer/platform/wtf/construct_traits.h"
+#include "third_party/blink/renderer/platform/wtf/doubly_linked_list.h"
+#include "third_party/blink/renderer/platform/wtf/hash_map.h"
+#include "third_party/blink/renderer/platform/wtf/hash_table_deleted_value_type.h"
+
+namespace WTF {
+
+// LruCache is a simple least-recently-used cache based on HashMap and
+// DoublyLinkedList. Useful in situations where caching by using a HashMap is
+// desirable but needs to be limited in size to not grow out of proportions.
+// LruCache uses a HashMap to store cache entries, and uses a DoublyLinkedList
+// in parallel to keep track of the age of entries. Accessing an entry using
+// Get() refreshes its age, Put() places a new entry into the HashMap with
+// youngest age as well. The least recently used entry of the list is pruned
+// when a Put() call would otherwise exceed the max_size limit.
+//
+// Example:
+// const size_t kMaxSize = 2;
+// LruCache<uint16_t, String> my_cache(kMaxSize);
+// my_cache.Put(13, "first string");
+// my_cache.Put(42, "second string");
+// my_cache.Put(256, "third string");
+// my_cache.Get(13) // -> nullptr, has been removed due to kMaxSize == 2.
+// my_cache.Get(42) // -> String* "second string"
+// my_cache.Get(256) // -> String* "third_string"
+//
+// See lru_cache_test.cc for more examples.
+template <typename KeyArg,
+          typename MappedArg,
+          typename HashArg = typename DefaultHash<KeyArg>::Hash,
+          typename KeyTraitsArg = HashTraits<KeyArg>>
+class LruCache {
+  USING_FAST_MALLOC(LruCache);
+
+ private:
+  class MappedListNodeWithKey final
+      : public DoublyLinkedListNode<MappedListNodeWithKey> {
+    USING_FAST_MALLOC(MappedListNodeWithKey);
+
+   public:
+    friend class DoublyLinkedListNode<MappedListNodeWithKey>;
+
+    MappedListNodeWithKey(const KeyArg& key, MappedArg&& mapped_arg)
+        : key_(key), mapped_value_(std::move(mapped_arg)) {}
+
+    MappedArg* Value() { return &mapped_value_; }
+
+    void SetValue(MappedArg&& mapped_arg) {
+      mapped_value_ = std::move(mapped_arg);
+    }
+
+    const KeyArg& Key() const { return key_; }
+
+   private:
+    KeyArg key_;
+    MappedArg mapped_value_;
+    MappedListNodeWithKey* prev_{nullptr};
+    MappedListNodeWithKey* next_{nullptr};
+  };
+
+  using MappedListNode = std::unique_ptr<MappedListNodeWithKey>;
+
+  using HashMapType = HashMap<KeyArg, MappedListNode, HashArg, KeyTraitsArg>;
+
+ public:
+  LruCache(size_t max_size) : max_size_(max_size) {
+    static_assert(!IsGarbageCollectedType<KeyArg>::value ||
+                      !IsGarbageCollectedType<MappedArg>::value,
+                  "Cannot use LruCache<> with garbage collected types.");
+    CHECK_GT(max_size_, 0u);
+  }
+
+  // Retrieve cache entry under |key| if it exists and refresh its age.
+  // Returns: pointer to cache entry or nullptr if no entry is found for that
+  // key.
+  MappedArg* Get(const KeyArg& key) {
+    if (map_.IsEmpty())
+      return nullptr;
+
+    typename HashMapType::iterator find_result = map_.find(key);
+    if (find_result == map_.end())
+      return nullptr;
+
+    // Move result to beginning of list.
+    MappedListNodeWithKey* node = find_result->value.get();
+    ordering_.Remove(node);
+    ordering_.Push(node);
+    return find_result->value->Value();
+  }
+
+  // Place entry in cache as new / youngest. Multiple calls to Put() with an
+  // identical key but differing MappedArg will override the stored value and
+  // refresh the age.
+  void Put(const KeyArg& key, MappedArg&& arg) {
+    {
+      typename HashMapType::iterator find_result = map_.find(key);
+      if (find_result != map_.end()) {
+        find_result->value->SetValue(std::move(arg));
+        ordering_.Remove(find_result->value.get());
+        ordering_.Push(find_result->value.get());
+      } else {
+        auto list_node =
+            std::make_unique<MappedListNodeWithKey>(key, std::move(arg));
+        typename HashMapType::AddResult add_result =
+            map_.insert(key, std::move(list_node));
+        DCHECK(add_result.is_new_entry);
+        ordering_.Push(add_result.stored_value->value.get());
+      }
+    }
+
+    if (map_.size() > max_size_) {
+      RemoveLeastRecentlyUsed();
+    }
+  }
+
+  // Clear the cache, remove all elements.
+  void Clear() {
+    map_.clear();
+    ordering_.Clear();
+  }
+
+  size_t size() { return map_.size(); }
+
+ private:
+  void RemoveLeastRecentlyUsed() {
+    MappedListNodeWithKey* tail = ordering_.Tail();
+    ordering_.Remove(tail);
+    map_.erase(tail->Key());
+  }
+
+  HashMapType map_;
+  DoublyLinkedList<MappedListNodeWithKey> ordering_;
+  size_t max_size_;
+};
+
+}  // namespace WTF
+
+#endif  // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_LRU_CACHE_H_