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