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