1 /* 2 * Copyright (c) 2014, lamerman 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are met: 7 * 8 * * Redistributions of source code must retain the above copyright notice, this 9 * list of conditions and the following disclaimer. 10 * 11 * * Redistributions in binary form must reproduce the above copyright notice, 12 * this list of conditions and the following disclaimer in the documentation 13 * and/or other materials provided with the distribution. 14 * 15 * * Neither the name of lamerman nor the names of its 16 * contributors may be used to endorse or promote products derived from 17 * this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 20 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 22 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 25 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 26 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 27 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 * 30 * File: lrucache.hpp 31 * Author: Alexander Ponomarev 32 * 33 * Created on June 20, 2013, 5:09 PM 34 */ 35 36 #ifndef _LRUCACHE_HPP_INCLUDED_ 37 #define _LRUCACHE_HPP_INCLUDED_ 38 39 #include <map> 40 #include <list> 41 #include <cstddef> 42 #include <stdexcept> 43 #include <cassert> 44 45 namespace zim { 46 47 template<typename key_t, typename value_t> 48 class lru_cache { 49 public: // types 50 typedef typename std::pair<key_t, value_t> key_value_pair_t; 51 typedef typename std::list<key_value_pair_t>::iterator list_iterator_t; 52 53 enum AccessStatus { 54 HIT, // key was found in the cache 55 PUT, // key was not in the cache but was created by the getOrPut() access 56 MISS // key was not in the cache; get() access failed 57 }; 58 59 class AccessResult 60 { 61 const AccessStatus status_; 62 const value_t val_; 63 public: AccessResult(const value_t & val,AccessStatus status)64 AccessResult(const value_t& val, AccessStatus status) 65 : status_(status), val_(val) 66 {} AccessResult()67 AccessResult() : status_(MISS), val_() {} 68 hit()69 bool hit() const { return status_ == HIT; } miss()70 bool miss() const { return !hit(); } value()71 const value_t& value() const 72 { 73 if ( status_ == MISS ) 74 throw std::range_error("There is no such key in cache"); 75 return val_; 76 } 77 78 operator const value_t& () const { return value(); } 79 }; 80 81 public: // functions lru_cache(size_t max_size)82 explicit lru_cache(size_t max_size) : 83 _max_size(max_size) { 84 } 85 86 // If 'key' is present in the cache, returns the associated value, 87 // otherwise puts the given value into the cache (and returns it with 88 // a status of a cache miss). getOrPut(const key_t & key,const value_t & value)89 AccessResult getOrPut(const key_t& key, const value_t& value) { 90 auto it = _cache_items_map.find(key); 91 if (it != _cache_items_map.end()) { 92 _cache_items_list.splice(_cache_items_list.begin(), _cache_items_list, it->second); 93 return AccessResult(it->second->second, HIT); 94 } else { 95 putMissing(key, value); 96 return AccessResult(value, PUT); 97 } 98 } 99 put(const key_t & key,const value_t & value)100 void put(const key_t& key, const value_t& value) { 101 auto it = _cache_items_map.find(key); 102 if (it != _cache_items_map.end()) { 103 _cache_items_list.splice(_cache_items_list.begin(), _cache_items_list, it->second); 104 it->second->second = value; 105 } else { 106 putMissing(key, value); 107 } 108 } 109 get(const key_t & key)110 AccessResult get(const key_t& key) { 111 auto it = _cache_items_map.find(key); 112 if (it == _cache_items_map.end()) { 113 return AccessResult(); 114 } else { 115 _cache_items_list.splice(_cache_items_list.begin(), _cache_items_list, it->second); 116 return AccessResult(it->second->second, HIT); 117 } 118 } 119 drop(const key_t & key)120 bool drop(const key_t& key) { 121 try { 122 auto list_it = _cache_items_map.at(key); 123 _cache_items_list.erase(list_it); 124 _cache_items_map.erase(key); 125 return true; 126 } catch (std::out_of_range& e) { 127 return false; 128 } 129 } 130 exists(const key_t & key)131 bool exists(const key_t& key) const { 132 return _cache_items_map.find(key) != _cache_items_map.end(); 133 } 134 size()135 size_t size() const { 136 return _cache_items_map.size(); 137 } 138 139 private: // functions putMissing(const key_t & key,const value_t & value)140 void putMissing(const key_t& key, const value_t& value) { 141 assert(_cache_items_map.find(key) == _cache_items_map.end()); 142 _cache_items_list.push_front(key_value_pair_t(key, value)); 143 _cache_items_map[key] = _cache_items_list.begin(); 144 if (_cache_items_map.size() > _max_size) { 145 _cache_items_map.erase(_cache_items_list.back().first); 146 _cache_items_list.pop_back(); 147 } 148 } 149 150 private: // data 151 std::list<key_value_pair_t> _cache_items_list; 152 std::map<key_t, list_iterator_t> _cache_items_map; 153 size_t _max_size; 154 }; 155 156 } // namespace zim 157 158 #endif /* _LRUCACHE_HPP_INCLUDED_ */ 159