OLD | NEW |
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 // This file contains a template for a Most Recently Used cache that allows | 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 | 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 | 7 // least-recently-used items for removal. Each key can only be associated with |
8 // one payload item at a time. | 8 // one payload item at a time. |
9 // | 9 // |
10 // The key object will be stored twice, so it should support efficient copying. | 10 // The key object will be stored twice, so it should support efficient copying. |
11 // | 11 // |
12 // NOTE: While all operations are O(1), this code is written for | 12 // NOTE: While all operations are O(1), this code is written for |
13 // legibility rather than optimality. If future profiling identifies this as | 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). :] | 14 // a bottleneck, there is room for smaller values of 1 in the O(1). :] |
15 | 15 |
16 #ifndef BASE_CONTAINERS_MRU_CACHE_H_ | 16 #ifndef BASE_CONTAINERS_MRU_CACHE_H_ |
17 #define BASE_CONTAINERS_MRU_CACHE_H_ | 17 #define BASE_CONTAINERS_MRU_CACHE_H_ |
18 | 18 |
| 19 #include <algorithm> |
19 #include <list> | 20 #include <list> |
20 #include <map> | 21 #include <map> |
21 #include <utility> | 22 #include <utility> |
22 | 23 |
23 #include "base/basictypes.h" | 24 #include "base/basictypes.h" |
24 #include "base/containers/hash_tables.h" | 25 #include "base/containers/hash_tables.h" |
25 #include "base/logging.h" | 26 #include "base/logging.h" |
26 | 27 |
27 namespace base { | 28 namespace base { |
28 | 29 |
(...skipping 101 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
130 return index_iter->second; | 131 return index_iter->second; |
131 } | 132 } |
132 | 133 |
133 const_iterator Peek(const KeyType& key) const { | 134 const_iterator Peek(const KeyType& key) const { |
134 typename KeyIndex::const_iterator index_iter = index_.find(key); | 135 typename KeyIndex::const_iterator index_iter = index_.find(key); |
135 if (index_iter == index_.end()) | 136 if (index_iter == index_.end()) |
136 return end(); | 137 return end(); |
137 return index_iter->second; | 138 return index_iter->second; |
138 } | 139 } |
139 | 140 |
| 141 // Exchanges the contents of |this| by the contents of the |other|. |
| 142 void Swap(MRUCacheBase& other) { |
| 143 ordering_.swap(other.ordering_); |
| 144 index_.swap(other.index_); |
| 145 std::swap(deletor_, other.deletor_); |
| 146 std::swap(max_size_, other.max_size_); |
| 147 } |
| 148 |
140 // Erases the item referenced by the given iterator. An iterator to the item | 149 // Erases the item referenced by the given iterator. An iterator to the item |
141 // following it will be returned. The iterator must be valid. | 150 // following it will be returned. The iterator must be valid. |
142 iterator Erase(iterator pos) { | 151 iterator Erase(iterator pos) { |
143 deletor_(pos->second); | 152 deletor_(pos->second); |
144 index_.erase(pos->first); | 153 index_.erase(pos->first); |
145 return ordering_.erase(pos); | 154 return ordering_.erase(pos); |
146 } | 155 } |
147 | 156 |
148 // MRUCache entries are often processed in reverse order, so we add this | 157 // MRUCache entries are often processed in reverse order, so we add this |
149 // convenience function (not typically defined by STL containers). | 158 // convenience function (not typically defined by STL containers). |
(...skipping 148 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
298 virtual ~HashingMRUCache() { | 307 virtual ~HashingMRUCache() { |
299 } | 308 } |
300 | 309 |
301 private: | 310 private: |
302 DISALLOW_COPY_AND_ASSIGN(HashingMRUCache); | 311 DISALLOW_COPY_AND_ASSIGN(HashingMRUCache); |
303 }; | 312 }; |
304 | 313 |
305 } // namespace base | 314 } // namespace base |
306 | 315 |
307 #endif // BASE_CONTAINERS_MRU_CACHE_H_ | 316 #endif // BASE_CONTAINERS_MRU_CACHE_H_ |
OLD | NEW |