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 | ␊ |
16 | template <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␊ |
25 | template <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␊ |
49 | template <typename Key, typename Data,␊ |
50 | typename Sizefn = WritebackCountfn<Data>,␊ |
51 | typename Manager = NullManager<Key, Data> >␊ |
52 | class LRUWritebackCache␊ |
53 | {␊ |
54 | public:␊ |
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 | ␊ |
64 | private:␊ |
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 | ␊ |
80 | public:␊ |
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 | ␊ |
235 | private:␊ |
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 | ␊ |