cache.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2012 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_CACHE_H
30 #define CXXTOOLS_CACHE_H
31 
32 #include <map>
33 #include <limits>
34 
35 #ifdef DEBUG
36 #include <iostream>
37 #endif
38 
39 namespace cxxtools
40 {
73  template <typename Key, typename Value>
74  class Cache
75  {
76  struct Data
77  {
78  bool winner;
79  unsigned serial;
80  Value value;
81  Data() { }
82  Data(bool winner_, unsigned serial_, const Value& value_)
83  : winner(winner_),
84  serial(serial_),
85  value(value_)
86  { }
87  };
88 
89  typedef std::map<Key, Data> DataType;
90  DataType data;
91 
92  typename DataType::size_type maxElements;
93  unsigned serial;
94  unsigned hits;
95  unsigned misses;
96 
97  unsigned _nextSerial()
98  {
99  if (serial == std::numeric_limits<unsigned>::max())
100  {
101  for (typename DataType::iterator it = data.begin(); it != data.end(); ++it)
102  it->second.serial = 0;
103  serial = 1;
104  }
105 
106  return serial++;
107  }
108 
109  typename DataType::iterator _getOldest(bool winner)
110  {
111  typename DataType::iterator foundElement = data.begin();
112 
113  typename DataType::iterator it = data.begin();
114 
115  for (++it; it != data.end(); ++it)
116  if (it->second.winner == winner
117  && (foundElement->second.winner != winner || it->second.serial < foundElement->second.serial))
118  foundElement = it;
119 
120  return foundElement;
121  }
122 
123  typename DataType::iterator _getNewest(bool winner)
124  {
125  typename DataType::iterator foundElement = data.begin();
126 
127  typename DataType::iterator it = data.begin();
128 
129  for (++it; it != data.end(); ++it)
130  if (it->second.winner == winner
131  && (foundElement->second.winner != winner || it->second.serial > foundElement->second.serial))
132  foundElement = it;
133 
134  return foundElement;
135  }
136 
137  // drop one element
138  void _dropLooser()
139  {
140  // look for the oldest element in the list of loosers to drop it
141  data.erase(_getOldest(false));
142  }
143 
144  void _makeLooser()
145  {
146  // look for the oldest element in the list of winners to make it a looser
147  typename DataType::iterator it = _getOldest(true);
148  it->second.winner = false;
149  it->second.serial = _nextSerial();
150  }
151 
152  public:
153  typedef typename DataType::size_type size_type;
154  typedef Value value_type;
155 
156  explicit Cache(size_type maxElements_)
157  : maxElements(maxElements_ + (maxElements_ & 1)),
158  serial(0),
159  hits(0),
160  misses(0)
161  { }
162 
164  size_type size() const { return data.size(); }
165 
167  size_type getMaxElements() const { return maxElements; }
168 
169  void setMaxElements(size_type maxElements_)
170  {
171  size_type numWinners = winners();
172 
173  maxElements_ += (maxElements_ & 1);
174 
175  if (maxElements_ > maxElements)
176  {
177  while (numWinners < maxElements_ / 2)
178  {
179  _getNewest(false)->second.winner = true;
180  ++numWinners;
181  }
182  }
183  else
184  {
185  while (size() > maxElements_)
186  _dropLooser();
187 
188  numWinners = winners();
189  while (numWinners > maxElements_ / 2)
190  {
191  _makeLooser();
192  --numWinners;
193  }
194  }
195 
196  maxElements = maxElements_;
197  }
198 
200  bool erase(const Key& key)
201  {
202  typename DataType::iterator it = data.find(key);
203  if (it == data.end())
204  return false;
205 
206  if (it->second.winner)
207  _getNewest(false)->second.winner = true;
208 
209  data.erase(it);
210  return true;
211  }
212 
214  void clear(bool stats = false)
215  {
216  data.clear();
217  if (stats)
218  hits = misses = 0;
219  }
220 
224  Value& put(const Key& key, const Value& value)
225  {
226  typename DataType::iterator it = data.find(key);
227  if (it == data.end())
228  {
229  if (data.size() < maxElements)
230  {
231  it = data.insert(data.begin(),
232  typename DataType::value_type(key,
233  Data(data.size() < maxElements / 2, _nextSerial(), value)));
234  }
235  else
236  {
237  // element not found
238  _dropLooser();
239  it = data.insert(data.begin(),
240  typename DataType::value_type(key,
241  Data(false, _nextSerial(), value)));
242  }
243  }
244  else
245  {
246  // element found
247  it->second.serial = _nextSerial();
248  if (!it->second.winner)
249  {
250  // move element to the winner part
251  it->second.winner = true;
252  _makeLooser();
253  }
254  it->second.value = value;
255  }
256 
257  return it->second.value;
258  }
259 
264  void put_top(const Key& key, const Value& value)
265  {
266  typename DataType::iterator it;
267  if (data.size() < maxElements)
268  {
269  if (data.size() >= maxElements / 2)
270  _makeLooser();
271 
272  data.insert(data.begin(),
273  typename DataType::value_type(key,
274  Data(true, _nextSerial(), value)));
275  }
276  else if ((it = data.find(key)) == data.end())
277  {
278  // element not found
279  _dropLooser();
280  _makeLooser();
281  data.insert(data.begin(),
282  typename DataType::value_type(key,
283  Data(true, _nextSerial(), value)));
284  }
285  else
286  {
287  // element found
288  it->second.serial = _nextSerial();
289  if (!it->second.winner)
290  {
291  // move element to the winner part
292  it->second.winner = true;
293  _makeLooser();
294  }
295  }
296  }
297 
298  Value* getptr(const Key& key)
299  {
300  typename DataType::iterator it = data.find(key);
301  if (it == data.end())
302  {
303  ++misses;
304  return 0;
305  }
306 
307  it->second.serial = _nextSerial();
308 
309  if (!it->second.winner)
310  {
311  // move element to the winner part
312  it->second.winner = true;
313  _makeLooser();
314  }
315 
316  ++hits;
317  return &it->second.value;
318  }
319 
323  std::pair<bool, Value> getx(const Key& key, Value def = Value())
324  {
325  Value* v = getptr(key);
326  return v ? std::pair<bool, Value>(true, *v)
327  : std::pair<bool, Value>(false, def);
328  }
329 
333  Value get(const Key& key, Value def = Value())
334  {
335  return getx(key, def).second;
336  }
337 
339  unsigned getHits() const { return hits; }
341  unsigned getMisses() const { return misses; }
343  double hitRatio() const { return hits+misses > 0 ? static_cast<double>(hits)/static_cast<double>(hits+misses) : 0; }
345  double fillfactor() const { return static_cast<double>(data.size()) / static_cast<double>(maxElements); }
346 
347  unsigned winners() const
348  {
349  unsigned w = 0;
350  for (typename DataType::const_iterator it = data.begin(); it != data.end(); ++it)
351  if (it->second.winner)
352  ++w;
353  return w;
354  }
355 
356  unsigned loosers() const
357  {
358  unsigned l = 0;
359  for (typename DataType::const_iterator it = data.begin(); it != data.end(); ++it)
360  if (!it->second.winner)
361  ++l;
362  return l;
363  }
364 
365 #ifdef DEBUG
366  void dump(std::ostream& out) const
367  {
368  out << "cache max size=" << maxElements << " current size=" << size() << '\n';
369  for (typename DataType::const_iterator it = data.begin(); it != data.end(); ++it)
370  {
371  out << "\tkey=\"" << it->first << "\" value=\"" << it->second.value << "\" serial=" << it->second.serial << " winner=" << it->second.winner << '\n';
372  }
373  out << "--------\n";
374  }
375 #endif
376 
377  };
378 
379 }
380 
381 #endif // CXXTOOLS_CACHE_H