| 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 | ␊ |
