blob: 1dc1f6d8a1035e5f0154c4fa01f6cdd83c32a1fc (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
// 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>
#include "base/containers/hash_tables.h"
#include "base/macros.h"
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
#endif // MEDIA_BLINK_LRU_H
|
