monotone

monotone Mtn Source Tree

Root/lru_writeback_cache.hh

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

Archive Download this file

Branches

Tags

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