17f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/******************************************************************************/ 27f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/* Copyright (c) 2010-2011, Tim Day <timday@timday.com> */ 37f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/* */ 47f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/* Permission to use, copy, modify, and/or distribute this software for any */ 57f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/* purpose with or without fee is hereby granted, provided that the above */ 67f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/* copyright notice and this permission notice appear in all copies. */ 77f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/* */ 87f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES */ 97f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF */ 107f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR */ 117f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */ 127f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN */ 137f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF */ 147f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ 157f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com/******************************************************************************/ 167f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 1781925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com// The original source code is from: 1881925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com// https://bitbucket.org/timday/lru_cache/src/497822a492a8/include/lru_cache_using_std.h 1981925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com 2081925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com#ifndef I18N_ADDRESSINPUT_UTIL_LRU_CACHE_USING_STD_H_ 2181925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com#define I18N_ADDRESSINPUT_UTIL_LRU_CACHE_USING_STD_H_ 227f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 237f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com#include <cassert> 249f47fe3ed525accac995b095d408a825673a2ee1roubert@google.com#include <cstddef> 257f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com#include <list> 2681925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com#include <map> 279f47fe3ed525accac995b095d408a825673a2ee1roubert@google.com#include <utility> 287f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 297f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com// Class providing fixed-size (by number of records) 307f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com// LRU-replacement cache of a function with signature 317f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com// V f(K). 3281925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com// The default comparator/hash/allocator will be used. 337f52881d0ec31f60d786c34091b871440f4848e0roubert@google.comtemplate < 347f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com typename K, 3581925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com typename V 367f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com > class lru_cache_using_std 377f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com{ 387f52881d0ec31f60d786c34091b871440f4848e0roubert@google.compublic: 397f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 407f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com typedef K key_type; 417f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com typedef V value_type; 427f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 437f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Key access history, most recent at back 447f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com typedef std::list<key_type> key_tracker_type; 4581925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com 467f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Key to value and key history iterator 4781925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com typedef std::map< 487f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com key_type, 497f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com std::pair< 507f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com value_type, 517f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com typename key_tracker_type::iterator 527f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com > 537f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com > key_to_value_type; 5481925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com 5581925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com // Constuctor specifies the cached function and 567f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // the maximum number of records to be stored 577f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com lru_cache_using_std( 587f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com value_type (*f)(const key_type&), 597f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com size_t c 607f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com ) 617f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com :_fn(f) 627f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com ,_capacity(c) 637f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com { 647f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com assert(_capacity!=0); 657f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com } 6681925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com 677f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Obtain value of the cached function for k 687f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com value_type operator()(const key_type& k) { 6981925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com 707f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Attempt to find existing record 717f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com const typename key_to_value_type::iterator it 727f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com =_key_to_value.find(k); 7381925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com 747f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com if (it==_key_to_value.end()) { 757f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 767f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // We don't have it: 777f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 787f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Evaluate function and create new record 797f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com const value_type v=_fn(k); 807f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com insert(k,v); 817f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 827f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Return the freshly computed value 837f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com return v; 847f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 857f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com } else { 867f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 877f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // We do have it: 887f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 897f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Update access record by moving 907f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // accessed key to back of list 917f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com _key_tracker.splice( 927f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com _key_tracker.end(), 937f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com _key_tracker, 947f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com (*it).second.second 957f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com ); 9681925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com 977f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Return the retrieved value 987f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com return (*it).second.first; 997f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com } 1007f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com } 10181925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com 1027f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Obtain the cached keys, most recently used element 1037f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // at head, least recently used at tail. 1047f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // This method is provided purely to support testing. 1057f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com template <typename IT> void get_keys(IT dst) const { 1067f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com typename key_tracker_type::const_reverse_iterator src 1077f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com =_key_tracker.rbegin(); 1087f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com while (src!=_key_tracker.rend()) { 1097f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com *dst++ = *src++; 1107f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com } 1117f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com } 11281925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com 1137f52881d0ec31f60d786c34091b871440f4848e0roubert@google.comprivate: 11481925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com 1157f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Record a fresh key-value pair in the cache 1167f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com void insert(const key_type& k,const value_type& v) { 1177f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 1187f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Method is only called on cache misses 1197f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com assert(_key_to_value.find(k)==_key_to_value.end()); 12081925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com 1217f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Make space if necessary 12281925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com if (_key_to_value.size()==_capacity) 1237f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com evict(); 1247f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 1257f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Record k as most-recently-used key 1267f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com typename key_tracker_type::iterator it 1277f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com =_key_tracker.insert(_key_tracker.end(),k); 1287f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 12981925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com // Create the key-value entry, 1307f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // linked to the usage record. 1317f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com _key_to_value.insert( 1327f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com std::make_pair( 1337f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com k, 1347f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com std::make_pair(v,it) 1357f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com ) 1367f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com ); 1377f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // No need to check return, 1387f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // given previous assert. 1397f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com } 14081925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com 1417f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Purge the least-recently-used element in the cache 1427f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com void evict() { 14381925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com 1447f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Assert method is never called when cache is empty 1457f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com assert(!_key_tracker.empty()); 14681925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com 1477f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Identify least recently used key 1487f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com const typename key_to_value_type::iterator it 1497f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com =_key_to_value.find(_key_tracker.front()); 1507f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com assert(it!=_key_to_value.end()); 1517f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 1527f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Erase both elements to completely purge record 1537f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com _key_to_value.erase(it); 1547f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com _key_tracker.pop_front(); 1557f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com } 1567f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 1577f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // The function to be cached 1587f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com value_type (*_fn)(const key_type&); 1597f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 1607f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Maximum number of key-value pairs to be retained 1617f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com const size_t _capacity; 1627f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 1637f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Key access history 1647f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com key_tracker_type _key_tracker; 1657f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 1667f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com // Key-to-value lookup 1677f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com key_to_value_type _key_to_value; 1687f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com}; 1697f52881d0ec31f60d786c34091b871440f4848e0roubert@google.com 17081925d920110e0f1cb23e587ff8d8d0e411433feroubert@google.com#endif // I18N_ADDRESSINPUT_UTIL_LRU_CACHE_USING_STD_H_ 171