monotone

monotone Mtn Source Tree

Root/lru_cache.h

1/***************************************************************************
2* Copyright (C) 2004 by Patrick Audley *
3* paudley@blackcat.ca *
4* *
5***************************************************************************/
6/**
7 * @file lru_cache.cpp Template cache with an LRU removal policy
8 * @author Patrick Audley
9 * @version 1.0
10 * @date December 2004
11 * @par
12 * This cache is thread safe if compiled with the _REENTRANT defined. It
13 * uses the BOOST scientific computing library to provide the thread safety
14 * mutexes.
15 */
16#include <map>
17#include <list>
18#ifdef _REENTRANT
19#include <boost/thread/mutex.hpp>
20/// If we are reentrant then use a BOOST scoped mutex where neccessary.
21#define SCOPED_MUTEX boost::mutex::scoped_lock lock(this->_mutex);
22#else
23/// If we aren't reentrant then don't do anything.
24#define SCOPED_MUTEX
25#endif
26
27template <class T>
28struct Countfn {
29unsigned long operator()( const T &x ) { return 1; }
30};
31
32/**
33 * @brief Template cache with an LRU removal policy.
34 * @class LRUCache
35 *
36 * @par
37 * This template creats a simple collection of key-value pairs that grows
38 * until the size specified at construction is reached and then begins
39 * discard the Least Recently Used element on each insertion.
40 *
41 */
42template<class Key,class Data,class Sizefn=Countfn<Data> > class LRUCache {
43public:
44/// Main cache storage typedef
45typedef std::list< std::pair< Key, Data > > List;
46/// Main cache iterator
47typedef typename List::iterator List_Iter;
48/// Index typedef
49typedef std::map< Key, List_Iter > Map;
50/// Index iterator
51typedef typename Map::iterator Map_Iter;
52
53/// Deletion strategies for element removal.
54enum deletion_strategies {
55LRU_IGNORE,///< Simply set erase the element from the cache and allow it leave scope.
56LRU_DELETE,///< Delete the Data elements before removal from the cache.
57};
58
59private:
60/// Main cache storage
61List _list;
62/// Cache storage index
63Map _index;
64
65/// Maximum abstract size of the cache
66unsigned long _max_size;
67
68/// Current abstract size of the cache
69unsigned long _curr_size;
70
71/// Current deletion strategy
72deletion_strategies _deletion_strategy;
73
74#ifdef _REENTRANT
75boost::mutex _mutex;
76#endif
77
78public:
79/** @brief Creates a cache that holds at most Size worth of elements.
80 * @param Size maximum size of cache
81 * @param DeletionStrategy how we dispose of elements when we remove them from the cache
82 */
83LRUCache( const unsigned long Size, const deletion_strategies DeletionStrategy = LRU_IGNORE ) :
84_max_size( Size ),
85_deletion_strategy( DeletionStrategy )
86{}
87/// Destructor - cleans up both index and storage
88~LRUCache() { this->clear(); }
89
90/** @brief Gets the current abstract size of the cache.
91 * @return current size
92 */
93inline const unsigned long size( void ) const { return _curr_size; }
94
95/** @brief Gets the maximum sbstract size of the cache.
96 * @return maximum size
97 */
98inline const unsigned long max_size( void ) const { return _max_size; }
99
100 /** @brief Sets the maximum size of the cache, does not reduce the actual cache size until next insert
101 */
102 inline void set_max_size(const unsigned long Size) { _max_size = Size; }
103
104/// Clears all storage and indices.
105void clear( void ) {
106SCOPED_MUTEX;
107_list.clear();
108_index.clear();
109};
110
111/** @brief Checks for the existance of a key in the cache.
112 * @param key to check for
113 * @return bool indicating whether or not the key was found.
114 */
115inline bool exists( const Key &key ) const {
116return _index.find( key ) != _index.end();
117}
118
119/** @brief Removes a key-data pair from the cache.
120 * @param key to be removed
121 */
122inline void remove( const Key &key ) {
123SCOPED_MUTEX;
124Map_Iter miter = _index.find( key );
125if( miter == _index.end() ) return;
126this->_remove( miter );
127}
128
129/** @brief Touches a key in the Cache and makes it the most recently used.
130 * @param key to be touched
131 */
132inline void touch( const Key &key ) {
133SCOPED_MUTEX;
134// Find the key in the index.
135Map_Iter miter = this->_touch( key );
136}
137
138/** @brief Fetches a pointer to cache data.
139 * @param key to fetch data for
140 * @param touch whether or not to touch the data
141 * @return pointer to data or NULL on error
142 */
143inline Data *fetch( const Key &key, bool touch = true ) {
144Map_Iter miter = _index.find( key );
145if( miter == _index.end() ) return NULL;
146if (touch)
147this->touch( key );
148return &(miter->second->second);
149}
150
151/** @brief Fetches a pointer to cache data.
152 * @param key to fetch data for
153 * @param data to fetch data into
154 * @param touch whether or not to touch the data
155 * @return whether or not data was filled in
156 */
157inline bool fetch( const Key &key, Data &data, bool touch = true ) {
158Map_Iter miter = _index.find( key );
159if( miter == _index.end() ) return false;
160if (touch)
161this->touch( key );
162data = miter->second->second;
163return true;
164}
165
166
167/** @brief Inserts a key-data pair into the cache and removes entries if neccessary.
168 * @param key object key for insertion
169 * @param data object data for insertion
170 * @note This function checks key existance and touches the key if it already exists.
171 */
172inline void insert( const Key &key, const Data &data ) {
173SCOPED_MUTEX;
174// Touch the key, if it exists, then replace the content.
175Map_Iter miter = this->_touch( key );
176if( miter != _index.end() ) {
177this->_remove( miter );
178}
179// Ok, do the actual insert at the head of the list
180_list.push_front(std::make_pair(key,data));
181List_Iter liter = _list.begin();
182// Store the index
183_index[ key ] = liter;
184_curr_size += Sizefn()( data );
185// Check to see if we need to remove an element due to exceeding max_size
186while( _curr_size > _max_size ) {
187// Remove the last element.
188liter = _list.end();
189--liter;
190this->_remove( liter->first );
191}
192}
193
194#ifdef DEBUG
195/** @brief DEBUG only function, this returns the pointer to the internal list.
196 * @return evil pointer to private data for debugging only.
197 */
198 List *debug_get_list_pointer( void ) { return &_list; }
199#endif
200
201private:
202/** @brief Internal touch function.
203 * @param key to be touched
204 * @return a Map_Iter pointing to the key that was touched.
205 */
206inline Map_Iter _touch( const Key &key ) {
207Map_Iter miter = _index.find( key );
208if( miter == _index.end() ) return miter;
209// Move the found node to the head of the list.
210_list.splice( _list.begin(), _list, miter->second );
211return miter;
212}
213
214/** @brief Interal remove function
215 * @param miter Map_Iter that points to the key to remove
216 * @warning miter is now longer usable after being passed to this function.
217 */
218inline void _remove( const Map_Iter &miter ) {
219_curr_size -= Sizefn()(miter->second->second);
220_list.erase( miter->second );
221_index.erase( miter );
222}
223
224/** @brief Interal remove function
225 * @param key to remove
226 */
227inline void _remove( const Key &key ) {
228Map_Iter miter = _index.find( key );
229_remove( miter );
230}
231};
232

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status