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 <list> 25 #include <map> 26 27 // Class providing fixed-size (by number of records) 28 // LRU-replacement cache of a function with signature 29 // V f(K). 30 // The default comparator/hash/allocator will be used. 31 template < 32 typename K, 33 typename V 34 > class lru_cache_using_std 35 { 36 public: 37 38 typedef K key_type; 39 typedef V value_type; 40 41 // Key access history, most recent at back 42 typedef std::list<key_type> key_tracker_type; 43 44 // Key to value and key history iterator 45 typedef std::map< 46 key_type, 47 std::pair< 48 value_type, 49 typename key_tracker_type::iterator 50 > 51 > key_to_value_type; 52 53 // Constuctor specifies the cached function and 54 // the maximum number of records to be stored 55 lru_cache_using_std( 56 value_type (*f)(const key_type&), 57 size_t c 58 ) 59 :_fn(f) 60 ,_capacity(c) 61 { 62 assert(_capacity!=0); 63 } 64 65 // Obtain value of the cached function for k 66 value_type operator()(const key_type& k) { 67 68 // Attempt to find existing record 69 const typename key_to_value_type::iterator it 70 =_key_to_value.find(k); 71 72 if (it==_key_to_value.end()) { 73 74 // We don't have it: 75 76 // Evaluate function and create new record 77 const value_type v=_fn(k); 78 insert(k,v); 79 80 // Return the freshly computed value 81 return v; 82 83 } else { 84 85 // We do have it: 86 87 // Update access record by moving 88 // accessed key to back of list 89 _key_tracker.splice( 90 _key_tracker.end(), 91 _key_tracker, 92 (*it).second.second 93 ); 94 95 // Return the retrieved value 96 return (*it).second.first; 97 } 98 } 99 100 // Obtain the cached keys, most recently used element 101 // at head, least recently used at tail. 102 // This method is provided purely to support testing. 103 template <typename IT> void get_keys(IT dst) const { 104 typename key_tracker_type::const_reverse_iterator src 105 =_key_tracker.rbegin(); 106 while (src!=_key_tracker.rend()) { 107 *dst++ = *src++; 108 } 109 } 110 111 private: 112 113 // Record a fresh key-value pair in the cache 114 void insert(const key_type& k,const value_type& v) { 115 116 // Method is only called on cache misses 117 assert(_key_to_value.find(k)==_key_to_value.end()); 118 119 // Make space if necessary 120 if (_key_to_value.size()==_capacity) 121 evict(); 122 123 // Record k as most-recently-used key 124 typename key_tracker_type::iterator it 125 =_key_tracker.insert(_key_tracker.end(),k); 126 127 // Create the key-value entry, 128 // linked to the usage record. 129 _key_to_value.insert( 130 std::make_pair( 131 k, 132 std::make_pair(v,it) 133 ) 134 ); 135 // No need to check return, 136 // given previous assert. 137 } 138 139 // Purge the least-recently-used element in the cache 140 void evict() { 141 142 // Assert method is never called when cache is empty 143 assert(!_key_tracker.empty()); 144 145 // Identify least recently used key 146 const typename key_to_value_type::iterator it 147 =_key_to_value.find(_key_tracker.front()); 148 assert(it!=_key_to_value.end()); 149 150 // Erase both elements to completely purge record 151 _key_to_value.erase(it); 152 _key_tracker.pop_front(); 153 } 154 155 // The function to be cached 156 value_type (*_fn)(const key_type&); 157 158 // Maximum number of key-value pairs to be retained 159 const size_t _capacity; 160 161 // Key access history 162 key_tracker_type _key_tracker; 163 164 // Key-to-value lookup 165 key_to_value_type _key_to_value; 166 }; 167 168 #endif // I18N_ADDRESSINPUT_UTIL_LRU_CACHE_USING_STD_H_ 169
