Add an LRUBoundedCache class.

base/lru_bounded_cache.h

+// Copyright 2016 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 BASE_LRU_BOUNDED_CACHE_H_
+#define BASE_LRU_BOUNDED_CACHE_H_
+
+#include <list>
+#include <map>
+
+#include "base/base_export.h"
+
+namespace base {
+
+// A cache that stores a bounded number of elements. When the bound is reached,
+// the least-recently-used element is removed to make room for a new element.
+// Inserting an element makes it the most-recently-used element.
+template <typename T>
+class BASE_EXPORT LRUBoundedCache {
+ private:
+  typedef std::list<T> ListType;
+  typedef std::map<T, typename ListType::iterator> MapType;
+
+ public:
+  LRUBoundedCache(size_t max_element_count) :
+    max_element_count_(max_element_count) {
+  }
+
+  // Inserts |x| into the cache, and makes it the most recently used element.
+  // Returns whether or not |x| was already in the cache.
+  bool Insert(const T& x) {
+    auto i = pos_.find(x);
+    bool was_in_cache = pos_.end() != i;
+    if (was_in_cache) {
+      lru_.erase(pos_[x]);
+    } else {
+      if (pos_.size() == max_element_count_) {
+        const T& back = lru_.back();
+        pos_.erase(back);
+        lru_.pop_back();
+      }
+    }
+    lru_.push_front(x);
+    pos_[x] = lru_.begin();
+    return was_in_cache;
+  }
+
+  size_t Size() const {
+    return pos_.size();
+  }
+
+ private:
+  // List of elements, most recently used first.
+  ListType lru_;
+
+  // Maps element values to positions in the list so that we can quickly remove
+  // elements.
+  MapType pos_;
+
+  const size_t max_element_count_;
+};
+
+}  // namespace base
+
+#endif  // BASE_LRU_BOUNDED_CACHE_H_