1/******************************************************************************/
2/*  Copyright (c) 2010-2011, Tim Day <timday@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.
33template <
34  typename K,
35  typename V
36  > class lru_cache_using_std
37{
38public:
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
113private:
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