| // 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 COBALT_MEDIA_BLINK_LRU_H_ |
| #define COBALT_MEDIA_BLINK_LRU_H_ |
| |
| #include <list> |
| |
| #include "base/basictypes.h" |
| #include "base/hash_tables.h" |
| #include "starboard/types.h" |
| |
| namespace cobalt { |
| namespace media { |
| |
| // Simple LRU (least recently used) class. |
| // Keeps track of a set of data and lets you get the least recently used |
| // (oldest) element at any time. All operations are O(1). Elements are expected |
| // to be hashable and unique. |
| // Example: |
| // LRU<int> lru; |
| // lru.Insert(1); |
| // lru.Insert(2); |
| // lru.Insert(3); |
| // lru.Use(1); |
| // cout << lru.Pop(); // this will print "2" |
| template <typename T> |
| class LRU { |
| public: |
| LRU() {} |
| |
| // Adds |x| to LRU. |
| // |x| must not already be in the LRU. |
| // Faster than Use(), and will DCHECK that |x| is not 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. |
| // Please call Insert() if you know that |x| is not in the LRU. |
| void Use(const T& x) { |
| if (Contains(x)) Remove(x); |
| Insert(x); |
| } |
| |
| bool Empty() const { return lru_.empty(); } |
| |
| // Returns the Least Recently Used T and removes it. |
| T Pop() { |
| DCHECK(!Empty()); |
| T ret = lru_.back(); |
| lru_.pop_back(); |
| pos_.erase(ret); |
| return ret; |
| } |
| |
| // Returns the Least Recently Used T _without_ removing it. |
| T Peek() const { |
| DCHECK(!Empty()); |
| return lru_.back(); |
| } |
| |
| bool Contains(const T& x) const { return pos_.find(x) != pos_.end(); } |
| |
| size_t Size() const { return pos_.size(); } |
| |
| private: |
| friend class LRUTest; |
| |
| // Linear list of elements, most recently used first. |
| std::list<T> lru_; |
| |
| // Maps element values to positions in the list so that we |
| // can quickly remove elements. |
| base::hash_map<T, typename std::list<T>::iterator> pos_; |
| |
| DISALLOW_COPY_AND_ASSIGN(LRU); |
| }; |
| |
| } // namespace media |
| } // namespace cobalt |
| |
| #endif // COBALT_MEDIA_BLINK_LRU_H_ |