mru_cache.h revision 7d4cd473f85ac64c3747c96c277f9e506a0d2246
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2011 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file contains a template for a Most Recently Used cache that allows 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// constant-time access to items using a key, but easy identification of the 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// least-recently-used items for removal. Each key can only be associated with 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// one payload item at a time. 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The key object will be stored twice, so it should support efficient copying. 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// NOTE: While all operations are O(1), this code is written for 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// legibility rather than optimality. If future profiling identifies this as 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// a bottleneck, there is room for smaller values of 1 in the O(1). :] 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#ifndef BASE_CONTAINERS_MRU_CACHE_H_ 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define BASE_CONTAINERS_MRU_CACHE_H_ 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <list> 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <map> 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <utility> 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 247d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)#include "base/containers/hash_tables.h" 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace base { 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// MRUCacheBase ---------------------------------------------------------------- 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This template is used to standardize map type containers that can be used 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// by MRUCacheBase. This level of indirection is necessary because of the way 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// that template template params and default template params interact. 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class KeyType, class ValueType> 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct MRUCacheStandardMap { 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::map<KeyType, ValueType> Type; 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Base class for the MRU cache specializations defined below. 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The deletor will get called on all payloads that are being removed or 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// replaced. 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class KeyType, class PayloadType, class DeletorType, 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) template <typename, typename> class MapType = MRUCacheStandardMap> 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class MRUCacheBase { 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The payload of the list. This maintains a copy of the key so we can 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // efficiently delete things given an element of the list. 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::pair<KeyType, PayloadType> value_type; 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef std::list<value_type> PayloadList; 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef typename MapType<KeyType, 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typename PayloadList::iterator>::Type KeyIndex; 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef typename PayloadList::size_type size_type; 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef typename PayloadList::iterator iterator; 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef typename PayloadList::const_iterator const_iterator; 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef typename PayloadList::reverse_iterator reverse_iterator; 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef typename PayloadList::const_reverse_iterator const_reverse_iterator; 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enum { NO_AUTO_EVICT = 0 }; 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The max_size is the size at which the cache will prune its members to when 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // a new item is inserted. If the caller wants to manager this itself (for 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // example, maybe it has special work to do when something is evicted), it 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // can pass NO_AUTO_EVICT to not restrict the cache size. 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit MRUCacheBase(size_type max_size) : max_size_(max_size) { 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MRUCacheBase(size_type max_size, const DeletorType& deletor) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : max_size_(max_size), deletor_(deletor) { 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual ~MRUCacheBase() { 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator i = begin(); 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (i != end()) 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = Erase(i); 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_type max_size() const { return max_size_; } 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Inserts a payload item with the given key. If an existing item has 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the same key, it is removed prior to insertion. An iterator indicating the 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // inserted item will be returned (this will always be the front of the list). 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The payload will be copied. In the case of an OwningMRUCache, this function 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // will take ownership of the pointer. 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator Put(const KeyType& key, const PayloadType& payload) { 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Remove any existing payload with that key. 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typename KeyIndex::iterator index_iter = index_.find(key); 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (index_iter != index_.end()) { 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Erase the reference to it. This will call the deletor on the removed 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // element. The index reference will be replaced in the code below. 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Erase(index_iter->second); 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (max_size_ != NO_AUTO_EVICT) { 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // New item is being inserted which might make it larger than the maximum 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // size: kick the oldest thing out if necessary. 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ShrinkToSize(max_size_ - 1); 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ordering_.push_front(value_type(key, payload)); 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) index_.insert(std::make_pair(key, ordering_.begin())); 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ordering_.begin(); 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Retrieves the contents of the given key, or end() if not found. This method 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // has the side effect of moving the requested item to the front of the 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // recency list. 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO(brettw) We may want a const version of this function in the future. 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator Get(const KeyType& key) { 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typename KeyIndex::iterator index_iter = index_.find(key); 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (index_iter == index_.end()) 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return end(); 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typename PayloadList::iterator iter = index_iter->second; 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Move the touched item to the front of the recency ordering. 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ordering_.splice(ordering_.begin(), ordering_, iter); 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ordering_.begin(); 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Retrieves the payload associated with a given key and returns it via 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // result without affecting the ordering (unlike Get). 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO(brettw) We may want a const version of this function in the future. 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator Peek(const KeyType& key) { 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typename KeyIndex::const_iterator index_iter = index_.find(key); 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (index_iter == index_.end()) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return end(); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return index_iter->second; 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Erases the item referenced by the given iterator. An iterator to the item 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // following it will be returned. The iterator must be valid. 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator Erase(iterator pos) { 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deletor_(pos->second); 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) index_.erase(pos->first); 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ordering_.erase(pos); 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // MRUCache entries are often processed in reverse order, so we add this 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // convenience function (not typically defined by STL containers). 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reverse_iterator Erase(reverse_iterator pos) { 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We have to actually give it the incremented iterator to delete, since 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the forward iterator that base() returns is actually one past the item 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // being iterated over. 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return reverse_iterator(Erase((++pos).base())); 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Shrinks the cache so it only holds |new_size| items. If |new_size| is 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // bigger or equal to the current number of items, this will do nothing. 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void ShrinkToSize(size_type new_size) { 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_type i = size(); i > new_size; i--) 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Erase(rbegin()); 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Deletes everything from the cache. 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Clear() { 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (typename PayloadList::iterator i(ordering_.begin()); 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i != ordering_.end(); ++i) 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deletor_(i->second); 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) index_.clear(); 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ordering_.clear(); 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns the number of elements in the cache. 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_type size() const { 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We don't use ordering_.size() for the return value because 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (as a linked list) it can be O(n). 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(index_.size() == ordering_.size()); 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return index_.size(); 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Allows iteration over the list. Forward iteration starts with the most 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // recent item and works backwards. 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Note that since these iterators are actually iterators over a list, you 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // can keep them as you insert or delete things (as long as you don't delete 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the one you are pointing to) and they will still be valid. 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator begin() { return ordering_.begin(); } 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_iterator begin() const { return ordering_.begin(); } 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator end() { return ordering_.end(); } 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_iterator end() const { return ordering_.end(); } 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reverse_iterator rbegin() { return ordering_.rbegin(); } 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_reverse_iterator rbegin() const { return ordering_.rbegin(); } 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reverse_iterator rend() { return ordering_.rend(); } 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_reverse_iterator rend() const { return ordering_.rend(); } 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool empty() const { return ordering_.empty(); } 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PayloadList ordering_; 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) KeyIndex index_; 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_type max_size_; 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DeletorType deletor_; 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(MRUCacheBase); 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// MRUCache -------------------------------------------------------------------- 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A functor that does nothing. Used by the MRUCache. 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<class PayloadType> 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class MRUCacheNullDeletor { 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void operator()(PayloadType& payload) { 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A container that does not do anything to free its data. Use this when storing 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// value types (as opposed to pointers) in the list. 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class KeyType, class PayloadType> 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class MRUCache : public MRUCacheBase<KeyType, 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PayloadType, 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MRUCacheNullDeletor<PayloadType> > { 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef MRUCacheBase<KeyType, PayloadType, 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MRUCacheNullDeletor<PayloadType> > ParentType; 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT. 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit MRUCache(typename ParentType::size_type max_size) 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : ParentType(max_size) { 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual ~MRUCache() { 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(MRUCache); 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OwningMRUCache -------------------------------------------------------------- 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<class PayloadType> 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class MRUCachePointerDeletor { 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void operator()(PayloadType& payload) { 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delete payload; 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A cache that owns the payload type, which must be a non-const pointer type. 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The pointers will be deleted when they are removed, replaced, or when the 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// cache is destroyed. 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class KeyType, class PayloadType> 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class OwningMRUCache 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : public MRUCacheBase<KeyType, 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PayloadType, 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MRUCachePointerDeletor<PayloadType> > { 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef MRUCacheBase<KeyType, PayloadType, 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MRUCachePointerDeletor<PayloadType> > ParentType; 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT. 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit OwningMRUCache(typename ParentType::size_type max_size) 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : ParentType(max_size) { 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual ~OwningMRUCache() { 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(OwningMRUCache); 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// HashingMRUCache ------------------------------------------------------------ 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class KeyType, class ValueType> 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct MRUCacheHashMap { 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef base::hash_map<KeyType, ValueType> Type; 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This class is similar to MRUCache, except that it uses base::hash_map as 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the map type instead of std::map. Note that your KeyType must be hashable 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// to use this cache. 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <class KeyType, class PayloadType> 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class HashingMRUCache : public MRUCacheBase<KeyType, 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PayloadType, 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MRUCacheNullDeletor<PayloadType>, 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MRUCacheHashMap> { 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef MRUCacheBase<KeyType, PayloadType, 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MRUCacheNullDeletor<PayloadType>, 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MRUCacheHashMap> ParentType; 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT. 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit HashingMRUCache(typename ParentType::size_type max_size) 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : ParentType(max_size) { 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual ~HashingMRUCache() { 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(HashingMRUCache); 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace base 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#endif // BASE_CONTAINERS_MRU_CACHE_H_ 306