monotone

monotone Mtn Source Tree

Root/src/lru_writeback_cache.hh

1// Copyright (C) 2004 Patrick Audley <paudley@blackcat.ca>
2// 2006 Nathaniel Smith <njs@pobox.com>
3//
4// This program is made available under the GNU GPL version 2.0 or
5// greater. See the accompanying file COPYING for details.
6//
7// This program is distributed WITHOUT ANY WARRANTY; without even the
8// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
9// PURPOSE.
10
11#ifndef __LRU_WRITEBACK_CACHE_HH__
12#define __LRU_WRITEBACK_CACHE_HH__
13
14#include <map>
15#include <list>
16
17#include "cache_logger.hh"
18#include "sanity.hh"
19#include "safe_map.hh"
20
21template <typename T> struct WritebackCountfn
22{
23 unsigned long operator () (T const & x)
24 {
25 return 1;
26 }
27};
28
29// for use in caches where objects never become dirty
30template <typename Key, typename Data> struct NullManager
31{
32 inline void writeout(Key const &, Data const &)
33 {
34 I(false);
35 }
36};
37
38/**
39 * @brief Template cache with an LRU removal policy.
40 * @class LRUWritebackCache
41 *
42 * @par
43 * This template creats a simple collection of key-value pairs that grows
44 * until the size specified at construction is reached and then begins
45 * discard the Least Recently Used element on each insertion.
46 *
47 * It also tracks a 'dirty set'. Any given item can be marked clean or dirty.
48 * Importantly, when a dirty item is discarded, a Manager object is first
49 * given the chance to write it out to disk. All managing of the dirty bit is
50 * done manually by calling code.
51 *
52 */
53// Manager is a concept with a writeout(Key, Data) method
54template <typename Key, typename Data,
55 typename Sizefn = WritebackCountfn<Data>,
56 typename Manager = NullManager<Key, Data> >
57class LRUWritebackCache
58{
59public:
60 /// Main cache storage typedef
61 typedef std::list< std::pair<Key, Data> > List;
62 /// Main cache iterator
63 typedef typename List::iterator List_Iter;
64 /// Index typedef
65 typedef std::map<Key, List_Iter> Map;
66 /// Index iterator
67 typedef typename Map::iterator Map_Iter;
68
69private:
70 /// Main cache storage
71 List _list;
72 /// Cache storage index
73 Map _index;
74 /// Dirty list
75 std::set<Key> _dirty;
76 /// Manager
77 Manager _manager;
78
79 /// Maximum abstract size of the cache
80 unsigned long _max_size;
81
82 /// Current abstract size of the cache
83 unsigned long _curr_size;
84
85 /// Minimum number of items in the cache (overrides the abstract size limit)
86 unsigned long _min_items;
87
88 cache_logger logger;
89
90public:
91 /** @brief Creates a cache that holds at most Size worth of elements.
92 * @param Size maximum size of cache
93 */
94 LRUWritebackCache(const unsigned long Size,
95 const unsigned long items,
96 Manager manager,
97 std::string const & logname)
98 : _manager(manager), _max_size(Size), _curr_size(0),
99 _min_items(items),
100 logger(logname, _max_size)
101 {
102 }
103
104 // Also allow a default-instantiated manager, for using this as a pure LRU
105 // cache with no writeback.
106 LRUWritebackCache(const unsigned long Size,
107 const unsigned long items)
108 : _max_size(Size), _curr_size(0),
109 _min_items(items),
110 logger("", 0)
111 {
112 }
113
114 /// Destructor - cleans up both index and storage
115 ~LRUWritebackCache()
116 {
117 I(_dirty.empty());
118 }
119
120 /** @brief Gets the current abstract size of the cache.
121 * @return current size
122 */
123 inline unsigned long size(void) const
124 {
125 return _curr_size;
126 }
127
128 /** @brief Gets the maximum abstract size of the cache.
129 * @return maximum size
130 */
131 inline unsigned long max_size(void) const
132 {
133 return _max_size;
134 }
135
136 /// Checks if all items are clean (this should be true before a SQL BEGIN)
137 bool all_clean()
138 {
139 return _dirty.empty();
140 }
141
142 /// Cleans all dirty items (do this before a SQL COMMIT)
143 void clean_all()
144 {
145 for (typename std::set<Key>::const_iterator i = _dirty.begin(); i != _dirty.end(); ++i)
146 this->_writeout(*i);
147 _dirty.clear();
148 }
149
150 /// Clears all storage and indices (do this at SQL ROLLBACK)
151 void clear_and_drop_writes()
152 {
153 _list.clear();
154 _index.clear();
155 _dirty.clear();
156 _curr_size = 0;
157 };
158
159 /// Mark an item as not needing to be written back (do this when writing an
160 /// alternative form of it to the db, e.g. a delta). No-op if the item was
161 /// already clean.
162 void mark_clean(Key const & key)
163 {
164 _dirty.erase(key);
165 }
166
167 /// Say if we're planning to write back an item (do this to figure out
168 /// whether you should be writing an alternative form of it to the db,
169 /// e.g. a delta).
170 bool is_dirty(Key const & key)
171 {
172 return (_dirty.find(key) != _dirty.end());
173 }
174
175 /** @brief Checks for the existence of a key in the cache.
176 * @param key to check for
177 * @return bool indicating whether or not the key was found.
178 */
179 inline bool exists(Key const & key) const
180 {
181 bool e = _index.find(key) != _index.end();
182 logger.log_exists(e, _position(key), _index.size(), _curr_size);
183 return e;
184 }
185
186 /** @brief Touches a key in the Cache and makes it the most recently used.
187 * @param key to be touched
188 */
189 inline void touch(Key const & key)
190 {
191 Map_Iter miter = _index.find(key);
192 logger.log_touch(miter != _index.end(), _position(key),
193 _index.size(), _curr_size);
194 this->_touch(miter);
195 }
196
197 /** @brief Fetches a copy of cache data.
198 * @param key to fetch data for
199 * @param data to fetch data into
200 * @param touch whether or not to touch the data
201 * @return whether or not data was filled in
202 */
203 inline bool fetch(Key const & key, Data & data, bool touch = true)
204 {
205 Map_Iter miter = _index.find(key);
206 logger.log_fetch(miter != _index.end(), _position(key),
207 _index.size(), _curr_size);
208 if (miter == _index.end())
209 return false;
210 if (touch)
211 this->touch(key);
212 data = miter->second->second;
213 return true;
214 }
215
216
217 /** @brief Inserts a key-data pair into the cache and removes entries if neccessary.
218 * @param key object key for insertion
219 * @param data object data for insertion
220 * @note This function checks key existence and touches the key if it already exists.
221 */
222 inline void insert_clean(Key const & key, const Data & data)
223 {
224 // A little sanity check -- if we were empty, then we should have
225 // been zero-size:
226 if (_list.empty())
227 I(_curr_size == 0);
228 // Ok, do the actual insert at the head of the list
229 _list.push_front(std::make_pair(key, data));
230 List_Iter liter = _list.begin();
231 // Store the index
232 safe_insert(_index, std::make_pair(key, liter));
233 _curr_size += Sizefn()(data);
234 // Check to see if we need to remove an element due to exceeding max_size
235 int num_removed = 0;
236 unsigned long curr_size = _list.size();
237 while (_curr_size > _max_size && curr_size > _min_items)
238 {
239 // Remove the last element.
240 liter = _list.end();
241 I(liter != _list.begin());
242 --liter;
243 // liter now points to the last element. If the last element is also
244 // the first element -- i.e., the list has only one element, and we
245 // know that it's the one we just inserted -- then never mind, we
246 // never want to empty ourselves out completely.
247 if (liter == _list.begin())
248 break;
249 this->_remove(liter->first);
250 ++num_removed;
251 --curr_size;
252 I(curr_size > 0);
253 }
254 I(exists(key));
255 logger.log_insert(num_removed, _index.size(), _curr_size);
256 }
257
258 inline void insert_dirty(Key const & key, const Data & data)
259 {
260 insert_clean(key, data);
261 safe_insert(_dirty, key);
262 I(is_dirty(key));
263 }
264
265private:
266 /** @brief Internal touch function.
267 * @param key to be touched
268 * @return a Map_Iter pointing to the key that was touched.
269 */
270 inline Map_Iter _touch(Map_Iter & miter)
271 {
272 if (miter == _index.end())
273 return miter;
274 // Move the found node to the head of the list.
275 _list.splice(_list.begin(), _list, miter->second);
276 return miter;
277 }
278
279 /** @brief Interal remove function
280 */
281 inline void _remove(const Key & key)
282 {
283 if (_dirty.find(key) != _dirty.end())
284 {
285 this->_writeout(key);
286 safe_erase(_dirty, key);
287 }
288 Map_Iter miter = _index.find(key);
289 I(miter != _index.end());
290 _curr_size -= Sizefn()(miter->second->second);
291 _list.erase(miter->second);
292 _index.erase(miter);
293 }
294
295 // NB: does _not_ remove 'key' from the dirty set
296 inline void _writeout(Key const & key)
297 {
298 List_Iter const & i = safe_get(_index, key);
299 _manager.writeout(i->first, i->second);
300 }
301
302 // Determine where in the cache a given item is,
303 // for use with effectiveness logging.
304 inline int _position(Key const & key) const
305 {
306 if (!logger.logging())
307 {
308 return -2;
309 }
310 int pos = 0;
311 for (typename List::const_iterator liter = _list.begin();
312 liter != _list.end(); ++liter)
313 {
314 if (liter->first == key)
315 return pos;
316 ++pos;
317 }
318 return -1;
319 }
320};
321
322#endif // __LRU_WRITEBACK_CACHE_HH__
323
324// Local Variables:
325// mode: C++
326// fill-column: 76
327// c-file-style: "gnu"
328// indent-tabs-mode: nil
329// End:
330// vim: et:sw=2:sts=2:ts=2:cino=>2s,{s,\:s,+s,t0,g0,^-2,e-2,n-2,p2s,(0,=s:

Archive Download this file

Branches

Tags

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