Simple LRU class

media/blink/lru.h

Index: media/blink/lru.h
diff --git a/media/blink/lru.h b/media/blink/lru.h
new file mode 100644
index 0000000000000000000000000000000000000000..837d72df724b08e99008a818a3882e1e77a6193d
--- /dev/null
+++ b/media/blink/lru.h
@@ -0,0 +1,67 @@
+// Copyright 2015 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 MEDIA_BLINK_LRU_H_
+#define MEDIA_BLINK_LRU_H_
+
+#include <list>

[xhwang, 2015/11/10 00:50:01]

nit: one extra line here

[hubbe, 2015/11/10 18:26:15]

Done.

+#include "base/containers/hash_tables.h"
+
+namespace media {
+
+template <typename T>

[xhwang, 2015/11/10 00:50:01]

OOC, what's the typical T we are gonna use? Asking because we are copying T a
lot.

[hubbe, 2015/11/10 18:26:15]

We'll mostly be using a std::pair<multibuffer*, int32_t>

+class LRU {

[xhwang, 2015/11/10 00:50:01]

Add a brief comment and provide a reference for LRU cache, just for easier
readability.

Also, how performance critical will this class be? (Trying to justify the
"simple LRU class" in the CL description).

[hubbe, 2015/11/10 18:26:15]

Comment added. As for performance:
In our use case, we'll might have a few thousand entries in the LRU and we'll be
calling it a couple of times per block, so big-O performance is important,
absolute performance is probably not.

+ public:
+  // Adds |x| to LRU.
+  // |x| must not already be in the LRU.
+  void Insert(const T& x) {
+    DCHECK(!Contains(x));
+    lru_.push_front(x);
+    pos_[x] = lru_.begin();
+  }
+
+  // Removes |x| from LRU.
+  // |x| must be in the LRU.
+  void Remove(const T& x) {
+    DCHECK(Contains(x));
+    lru_.erase(pos_[x]);
+    pos_.erase(x);
+  }
+
+  // Moves |x| to front of LRU. (most recently used)
+  // If |x| is not in LRU, it is added.
+  void Use(const T& x) {
+    if (Contains(x))
+      Remove(x);
+    Insert(x);
+  }
+
+  bool Empty() const { return lru_.empty(); }
+
+  // Returns the Least Recently Used T.

[xhwang, 2015/11/10 00:50:01]

and removes it..

[hubbe, 2015/11/10 18:26:15]

Done.

+  T Pop() {
+    DCHECK(!Empty());
+    T ret = lru_.back();
+    lru_.pop_back();
+    pos_.erase(ret);
+    return ret;
+  }
+
+  T Peek() const {

[xhwang, 2015/11/10 00:50:01]

Add comment.

[hubbe, 2015/11/10 18:26:15]

Done.

+    DCHECK(!Empty());
+    return lru_.back();
+  }
+
+  bool Contains(const T& x) const { return pos_.find(x) != pos_.end(); }

[xhwang, 2015/11/10 00:50:01]

DCHECK it's not in |lru_| either?

[hubbe, 2015/11/10 18:26:15]

That's a pretty expensive DCHECK() I don't think I want to put a linear search
here...

+
+  size_t Size() const { return pos_.size(); }
+
+ private:
+  std::list<T> lru_;
+  base::hash_map<T, typename std::list<T>::iterator> pos_;

[xhwang, 2015/11/10 00:50:01]

Add a brief comment.

[hubbe, 2015/11/10 18:26:15]

Done.

+};
+
+}  // namespace media
+
+#endif  // MEDIA_BLINK_LRU_H