1 /******************************************************************************/ 2 /* Copyright (c) 2010-2011, Tim Day <timday (at) timday.com> */ 3 /* */ 4 /* Permission to use, copy, modify, and/or distribute this software for any */ 5 /* purpose with or without fee is hereby granted, provided that the above */ 6 /* copyright notice and this permission notice appear in all copies. */ 7 /* */ 8 /* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES */ 9 /* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF */ 10 /* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR */ 11 /* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */ 12 /* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN */ 13 /* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF */ 14 /* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ 15 /******************************************************************************/ 16 17 // The original source code is from: 18 // https://bitbucket.org/timday/lru_cache/src/497822a492a8/include/lru_cache_using_std.h 19 20 #ifndef I18N_ADDRESSINPUT_UTIL_LRU_CACHE_USING_STD_H_ 21 #define I18N_ADDRESSINPUT_UTIL_LRU_CACHE_USING_STD_H_ 22 23 #include <cassert> 24 #include <cstddef> 25 #include <list> 26 #include <map> 27 #include <utility> 28 29 // Class providing fixed-size (by number of records) 30 // LRU-replacement cache of a function with signature 31 // V f(K). 32 // The default comparator/hash/allocator will be used. 33 template < 34 typename K, 35 typename V 36 > class lru_cache_using_std 37 { 38 public: 39 40 typedef K key_type; 41 typedef V value_type; 42 43 // Key access history, most recent at back 44 typedef std::list<key_type> key_tracker_type; 45 46 // Key to value and key history iterator 47 typedef std::map< 48 key_type, 49 std::pair< 50 value_type, 51 typename key_tracker_type::iterator 52 > 53 > key_to_value_type; 54 55 // Constuctor specifies the cached function and 56 // the maximum number of records to be stored 57 lru_cache_using_std( 58 value_type (*f)(const key_type&), 59 size_t c 60 ) 61 :_fn(f) 62 ,_capacity(c) 63 { 64 assert(_capacity!=0); 65 } 66 67 // Obtain value of the cached function for k 68 value_type operator()(const key_type& k) { 69 70 // Attempt to find existing record 71 const typename key_to_value_type::iterator it 72 =_key_to_value.find(k); 73 74 if (it==_key_to_value.end()) { 75 76 // We don't have it: 77 78 // Evaluate function and create new record 79 const value_type v=_fn(k); 80 insert(k,v); 81 82 // Return the freshly computed value 83 return v; 84 85 } else { 86 87 // We do have it: 88 89 // Update access record by moving 90 // accessed key to back of list 91 _key_tracker.splice( 92 _key_tracker.end(), 93 _key_tracker, 94 (*it).second.second 95 ); 96 97 // Return the retrieved value 98 return (*it).second.first; 99 } 100 } 101 102 // Obtain the cached keys, most recently used element 103 // at head, least recently used at tail. 104 // This method is provided purely to support testing. 105 template <typename IT> void get_keys(IT dst) const { 106 typename key_tracker_type::const_reverse_iterator src 107 =_key_tracker.rbegin(); 108 while (src!=_key_tracker.rend()) { 109 *dst++ = *src++; 110 } 111 } 112 113 private: 114 115 // Record a fresh key-value pair in the cache 116 void insert(const key_type& k,const value_type& v) { 117 118 // Method is only called on cache misses 119 assert(_key_to_value.find(k)==_key_to_value.end()); 120 121 // Make space if necessary 122 if (_key_to_value.size()==_capacity) 123 evict(); 124 125 // Record k as most-recently-used key 126 typename key_tracker_type::iterator it 127 =_key_tracker.insert(_key_tracker.end(),k); 128 129 // Create the key-value entry, 130 // linked to the usage record. 131 _key_to_value.insert( 132 std::make_pair( 133 k, 134 std::make_pair(v,it) 135 ) 136 ); 137 // No need to check return, 138 // given previous assert. 139 } 140 141 // Purge the least-recently-used element in the cache 142 void evict() { 143 144 // Assert method is never called when cache is empty 145 assert(!_key_tracker.empty()); 146 147 // Identify least recently used key 148 const typename key_to_value_type::iterator it 149 =_key_to_value.find(_key_tracker.front()); 150 assert(it!=_key_to_value.end()); 151 152 // Erase both elements to completely purge record 153 _key_to_value.erase(it); 154 _key_tracker.pop_front(); 155 } 156 157 // The function to be cached 158 value_type (*_fn)(const key_type&); 159 160 // Maximum number of key-value pairs to be retained 161 const size_t _capacity; 162 163 // Key access history 164 key_tracker_type _key_tracker; 165 166 // Key-to-value lookup 167 key_to_value_type _key_to_value; 168 }; 169 170 #endif // I18N_ADDRESSINPUT_UTIL_LRU_CACHE_USING_STD_H_ 171
