mru_cache.h revision 5821806d5e7f356e8fa4b058a389a808ea183019
1// Copyright (c) 2011 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5// This file contains a template for a Most Recently Used cache that allows
6// constant-time access to items using a key, but easy identification of the
7// least-recently-used items for removal.  Each key can only be associated with
8// one payload item at a time.
9//
10// The key object will be stored twice, so it should support efficient copying.
11//
12// NOTE: While all operations are O(1), this code is written for
13// legibility rather than optimality. If future profiling identifies this as
14// a bottleneck, there is room for smaller values of 1 in the O(1). :]
15
16#ifndef BASE_MEMORY_MRU_CACHE_H_
17#define BASE_MEMORY_MRU_CACHE_H_
18
19#include <list>
20#include <map>
21#include <utility>
22
23#include "base/basictypes.h"
24#include "base/hash_tables.h"
25#include "base/logging.h"
26
27namespace base {
28
29// MRUCacheBase ----------------------------------------------------------------
30
31// This template is used to standardize map type containers that can be used
32// by MRUCacheBase. This level of indirection is necessary because of the way
33// that template template params and default template params interact.
34template <class KeyType, class ValueType>
35struct MRUCacheStandardMap {
36  typedef std::map<KeyType, ValueType> Type;
37};
38
39// Base class for the MRU cache specializations defined below.
40// The deletor will get called on all payloads that are being removed or
41// replaced.
42template <class KeyType, class PayloadType, class DeletorType,
43          template <typename, typename> class MapType = MRUCacheStandardMap>
44class MRUCacheBase {
45 public:
46  // The payload of the list. This maintains a copy of the key so we can
47  // efficiently delete things given an element of the list.
48  typedef std::pair<KeyType, PayloadType> value_type;
49
50 private:
51  typedef std::list<value_type> PayloadList;
52  typedef typename MapType<KeyType,
53                           typename PayloadList::iterator>::Type KeyIndex;
54
55 public:
56  typedef typename PayloadList::size_type size_type;
57
58  typedef typename PayloadList::iterator iterator;
59  typedef typename PayloadList::const_iterator const_iterator;
60  typedef typename PayloadList::reverse_iterator reverse_iterator;
61  typedef typename PayloadList::const_reverse_iterator const_reverse_iterator;
62
63  enum { NO_AUTO_EVICT = 0 };
64
65  // The max_size is the size at which the cache will prune its members to when
66  // a new item is inserted. If the caller wants to manager this itself (for
67  // example, maybe it has special work to do when something is evicted), it
68  // can pass NO_AUTO_EVICT to not restrict the cache size.
69  explicit MRUCacheBase(size_type max_size) : max_size_(max_size) {
70  }
71
72  MRUCacheBase(size_type max_size, const DeletorType& deletor)
73      : max_size_(max_size), deletor_(deletor) {
74  }
75
76  virtual ~MRUCacheBase() {
77    iterator i = begin();
78    while (i != end())
79      i = Erase(i);
80  }
81
82  size_type max_size() const { return max_size_; }
83
84  // Inserts a payload item with the given key. If an existing item has
85  // the same key, it is removed prior to insertion. An iterator indicating the
86  // inserted item will be returned (this will always be the front of the list).
87  //
88  // The payload will be copied. In the case of an OwningMRUCache, this function
89  // will take ownership of the pointer.
90  iterator Put(const KeyType& key, const PayloadType& payload) {
91    // Remove any existing payload with that key.
92    typename KeyIndex::iterator index_iter = index_.find(key);
93    if (index_iter != index_.end()) {
94      // Erase the reference to it. This will call the deletor on the removed
95      // element. The index reference will be replaced in the code below.
96      Erase(index_iter->second);
97    } else if (max_size_ != NO_AUTO_EVICT) {
98      // New item is being inserted which might make it larger than the maximum
99      // size: kick the oldest thing out if necessary.
100      ShrinkToSize(max_size_ - 1);
101    }
102
103    ordering_.push_front(value_type(key, payload));
104    index_.insert(std::make_pair(key, ordering_.begin()));
105    return ordering_.begin();
106  }
107
108  // Retrieves the contents of the given key, or end() if not found. This method
109  // has the side effect of moving the requested item to the front of the
110  // recency list.
111  //
112  // TODO(brettw) We may want a const version of this function in the future.
113  iterator Get(const KeyType& key) {
114    typename KeyIndex::iterator index_iter = index_.find(key);
115    if (index_iter == index_.end())
116      return end();
117    typename PayloadList::iterator iter = index_iter->second;
118
119    // Move the touched item to the front of the recency ordering.
120    ordering_.splice(ordering_.begin(), ordering_, iter);
121    return ordering_.begin();
122  }
123
124  // Retrieves the payload associated with a given key and returns it via
125  // result without affecting the ordering (unlike Get).
126  //
127  // TODO(brettw) We may want a const version of this function in the future.
128  iterator Peek(const KeyType& key) {
129    typename KeyIndex::const_iterator index_iter = index_.find(key);
130    if (index_iter == index_.end())
131      return end();
132    return index_iter->second;
133  }
134
135  // Erases the item referenced by the given iterator. An iterator to the item
136  // following it will be returned. The iterator must be valid.
137  iterator Erase(iterator pos) {
138    deletor_(pos->second);
139    index_.erase(pos->first);
140    return ordering_.erase(pos);
141  }
142
143  // MRUCache entries are often processed in reverse order, so we add this
144  // convenience function (not typically defined by STL containers).
145  reverse_iterator Erase(reverse_iterator pos) {
146    // We have to actually give it the incremented iterator to delete, since
147    // the forward iterator that base() returns is actually one past the item
148    // being iterated over.
149    return reverse_iterator(Erase((++pos).base()));
150  }
151
152  // Shrinks the cache so it only holds |new_size| items. If |new_size| is
153  // bigger or equal to the current number of items, this will do nothing.
154  void ShrinkToSize(size_type new_size) {
155    for (size_type i = size(); i > new_size; i--)
156      Erase(rbegin());
157  }
158
159  // Deletes everything from the cache.
160  void Clear() {
161    for (typename PayloadList::iterator i(ordering_.begin());
162         i != ordering_.end(); ++i)
163      deletor_(i->second);
164    index_.clear();
165    ordering_.clear();
166  }
167
168  // Returns the number of elements in the cache.
169  size_type size() const {
170    // We don't use ordering_.size() for the return value because
171    // (as a linked list) it can be O(n).
172    DCHECK(index_.size() == ordering_.size());
173    return index_.size();
174  }
175
176  // Allows iteration over the list. Forward iteration starts with the most
177  // recent item and works backwards.
178  //
179  // Note that since these iterators are actually iterators over a list, you
180  // can keep them as you insert or delete things (as long as you don't delete
181  // the one you are pointing to) and they will still be valid.
182  iterator begin() { return ordering_.begin(); }
183  const_iterator begin() const { return ordering_.begin(); }
184  iterator end() { return ordering_.end(); }
185  const_iterator end() const { return ordering_.end(); }
186
187  reverse_iterator rbegin() { return ordering_.rbegin(); }
188  const_reverse_iterator rbegin() const { return ordering_.rbegin(); }
189  reverse_iterator rend() { return ordering_.rend(); }
190  const_reverse_iterator rend() const { return ordering_.rend(); }
191
192  bool empty() const { return ordering_.empty(); }
193
194 private:
195  PayloadList ordering_;
196  KeyIndex index_;
197
198  size_type max_size_;
199
200  DeletorType deletor_;
201
202  DISALLOW_COPY_AND_ASSIGN(MRUCacheBase);
203};
204
205// MRUCache --------------------------------------------------------------------
206
207// A functor that does nothing. Used by the MRUCache.
208template<class PayloadType>
209class MRUCacheNullDeletor {
210 public:
211  void operator()(PayloadType& payload) {
212  }
213};
214
215// A container that does not do anything to free its data. Use this when storing
216// value types (as opposed to pointers) in the list.
217template <class KeyType, class PayloadType>
218class MRUCache : public MRUCacheBase<KeyType,
219                                     PayloadType,
220                                     MRUCacheNullDeletor<PayloadType> > {
221 private:
222  typedef MRUCacheBase<KeyType, PayloadType,
223      MRUCacheNullDeletor<PayloadType> > ParentType;
224
225 public:
226  // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT.
227  explicit MRUCache(typename ParentType::size_type max_size)
228      : ParentType(max_size) {
229  }
230  virtual ~MRUCache() {
231  }
232
233 private:
234  DISALLOW_COPY_AND_ASSIGN(MRUCache);
235};
236
237// OwningMRUCache --------------------------------------------------------------
238
239template<class PayloadType>
240class MRUCachePointerDeletor {
241 public:
242  void operator()(PayloadType& payload) {
243    delete payload;
244  }
245};
246
247// A cache that owns the payload type, which must be a non-const pointer type.
248// The pointers will be deleted when they are removed, replaced, or when the
249// cache is destroyed.
250template <class KeyType, class PayloadType>
251class OwningMRUCache
252    : public MRUCacheBase<KeyType,
253                          PayloadType,
254                          MRUCachePointerDeletor<PayloadType> > {
255 private:
256  typedef MRUCacheBase<KeyType, PayloadType,
257      MRUCachePointerDeletor<PayloadType> > ParentType;
258
259 public:
260  // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT.
261  explicit OwningMRUCache(typename ParentType::size_type max_size)
262      : ParentType(max_size) {
263  }
264  virtual ~OwningMRUCache() {
265  }
266
267 private:
268  DISALLOW_COPY_AND_ASSIGN(OwningMRUCache);
269};
270
271// HashingMRUCache ------------------------------------------------------------
272
273template <class KeyType, class ValueType>
274struct MRUCacheHashMap {
275  typedef base::hash_map<KeyType, ValueType> Type;
276};
277
278// This class is similar to MRUCache, except that it uses base::hash_map as
279// the map type instead of std::map. Note that your KeyType must be hashable
280// to use this cache.
281template <class KeyType, class PayloadType>
282class HashingMRUCache : public MRUCacheBase<KeyType,
283                                            PayloadType,
284                                            MRUCacheNullDeletor<PayloadType>,
285                                            MRUCacheHashMap> {
286 private:
287  typedef MRUCacheBase<KeyType, PayloadType,
288                       MRUCacheNullDeletor<PayloadType>,
289                       MRUCacheHashMap> ParentType;
290
291 public:
292  // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT.
293  explicit HashingMRUCache(typename ParentType::size_type max_size)
294      : ParentType(max_size) {
295  }
296  virtual ~HashingMRUCache() {
297  }
298
299 private:
300  DISALLOW_COPY_AND_ASSIGN(HashingMRUCache);
301};
302
303}  // namespace base
304
305#endif  // BASE_MEMORY_MRU_CACHE_H_
306