lrucache.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2013 Tommi Maekitalo
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * As a special exception, you may use this file as part of a free
10  * software library without restriction. Specifically, if other files
11  * instantiate templates or use macros or inline functions from this
12  * file, or you compile this file and link it with other files to
13  * produce an executable, this file does not by itself cause the
14  * resulting executable to be covered by the GNU General Public
15  * License. This exception does not however invalidate any other
16  * reasons why the executable file might be covered by the GNU Library
17  * General Public License.
18  *
19  * This library is distributed in the hope that it will be useful,
20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
22  * Lesser General Public License for more details.
23  *
24  * You should have received a copy of the GNU Lesser General Public
25  * License along with this library; if not, write to the Free Software
26  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
27  */
28 
29 #ifndef CXXTOOLS_LRUCACHE_H
30 #define CXXTOOLS_LRUCACHE_H
31 
32 #include <map>
33 #include <limits>
34 
35 namespace cxxtools
36 {
41  template <typename Key, typename Value>
42  class LruCache
43  {
44  struct Data
45  {
46  unsigned serial;
47  Value value;
48  Data() { }
49  Data(unsigned serial_, const Value& value_)
50  : serial(serial_),
51  value(value_)
52  { }
53  };
54 
55  typedef std::map<Key, Data> DataType;
56  DataType data;
57 
58  typename DataType::size_type maxElements;
59  unsigned serial;
60  unsigned hits;
61  unsigned misses;
62 
63  unsigned _nextSerial()
64  {
65  if (serial == std::numeric_limits<unsigned>::max())
66  {
67  for (typename DataType::iterator it = data.begin(); it != data.end(); ++it)
68  it->second.serial = 0;
69  serial = 1;
70  }
71 
72  return serial++;
73  }
74 
75  typename DataType::iterator _getOldest()
76  {
77  typename DataType::iterator foundElement = data.begin();
78 
79  typename DataType::iterator it = data.begin();
80 
81  for (++it; it != data.end(); ++it)
82  if (it->second.serial < foundElement->second.serial)
83  foundElement = it;
84 
85  return foundElement;
86  }
87 
88  public:
89  typedef typename DataType::size_type size_type;
90  typedef Value value_type;
91 
92  explicit LruCache(size_type maxElements_)
93  : maxElements(maxElements_),
94  serial(0),
95  hits(0),
96  misses(0)
97  { }
98 
100  size_type size() const { return data.size(); }
101 
103  size_type getMaxElements() const { return maxElements; }
104 
105  void setMaxElements(size_type maxElements_)
106  {
107  maxElements = maxElements_;
108  while (data.size() > maxElements)
109  data.erase(_getOldest());
110  }
111 
113  bool erase(const Key& key)
114  {
115  typename DataType::iterator it = data.find(key);
116  if (it == data.end())
117  return false;
118 
119  data.erase(it);
120  return true;
121  }
122 
124  void clear(bool stats = false)
125  {
126  data.clear();
127  if (stats)
128  hits = misses = 0;
129  }
130 
134  Value& put(const Key& key, const Value& value)
135  {
136  typename DataType::iterator it = data.find(key);
137  if (it == data.end())
138  {
139  if (data.size() >= maxElements)
140  data.erase(_getOldest());
141 
142  it = data.insert(data.begin(),
143  typename DataType::value_type(key,
144  Data(_nextSerial(), value)));
145  }
146  else
147  {
148  // element found
149  it->second.serial = _nextSerial();
150  }
151 
152  return it->second.value;
153  }
154 
155  Value* getptr(const Key& key)
156  {
157  typename DataType::iterator it = data.find(key);
158  if (it == data.end())
159  {
160  ++misses;
161  return 0;
162  }
163 
164  it->second.serial = _nextSerial();
165 
166  ++hits;
167  return &it->second.value;
168  }
169 
173  std::pair<bool, Value> getx(const Key& key, Value def = Value())
174  {
175  Value* v = getptr(key);
176  return v ? std::pair<bool, Value>(true, *v)
177  : std::pair<bool, Value>(false, def);
178  }
179 
183  Value get(const Key& key, Value def = Value())
184  {
185  return getx(key, def).second;
186  }
187 
189  unsigned getHits() const { return hits; }
191  unsigned getMisses() const { return misses; }
193  double hitRatio() const { return hits+misses > 0 ? static_cast<double>(hits)/static_cast<double>(hits+misses) : 0; }
195  double fillfactor() const { return static_cast<double>(data.size()) / static_cast<double>(maxElements); }
196 
197  };
198 
199 }
200 
201 #endif // CXXTOOLS_LRUCACHE_H