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  }
255 
256  return it->second.value;
257  }
258 
263  void put_top(const Key& key, const Value& value)
264  {
265  typename DataType::iterator it;
266  if (data.size() < maxElements)
267  {
268  if (data.size() >= maxElements / 2)
269  _makeLooser();
270 
271  data.insert(data.begin(),
272  typename DataType::value_type(key,
273  Data(true, _nextSerial(), value)));
274  }
275  else if ((it = data.find(key)) == data.end())
276  {
277  // element not found
278  _dropLooser();
279  _makeLooser();
280  data.insert(data.begin(),
281  typename DataType::value_type(key,
282  Data(true, _nextSerial(), value)));
283  }
284  else
285  {
286  // element found
287  it->second.serial = _nextSerial();
288  if (!it->second.winner)
289  {
290  // move element to the winner part
291  it->second.winner = true;
292  _makeLooser();
293  }
294  }
295  }
296 
297  Value* getptr(const Key& key)
298  {
299  typename DataType::iterator it = data.find(key);
300  if (it == data.end())
301  {
302  ++misses;
303  return 0;
304  }
305 
306  it->second.serial = _nextSerial();
307 
308  if (!it->second.winner)
309  {
310  // move element to the winner part
311  it->second.winner = true;
312  _makeLooser();
313  }
314 
315  ++hits;
316  return &it->second.value;
317  }
318 
322  std::pair<bool, Value> getx(const Key& key, Value def = Value())
323  {
324  Value* v = getptr(key);
325  return v ? std::pair<bool, Value>(true, *v)
326  : std::pair<bool, Value>(false, def);
327  }
328 
332  Value get(const Key& key, Value def = Value())
333  {
334  return getx(key, def).second;
335  }
336 
338  unsigned getHits() const { return hits; }
340  unsigned getMisses() const { return misses; }
342  double hitRatio() const { return hits+misses > 0 ? static_cast<double>(hits)/static_cast<double>(hits+misses) : 0; }
344  double fillfactor() const { return static_cast<double>(data.size()) / static_cast<double>(maxElements); }
345 
346  unsigned winners() const
347  {
348  unsigned w = 0;
349  for (typename DataType::const_iterator it = data.begin(); it != data.end(); ++it)
350  if (it->second.winner)
351  ++w;
352  return w;
353  }
354 
355  unsigned loosers() const
356  {
357  unsigned l = 0;
358  for (typename DataType::const_iterator it = data.begin(); it != data.end(); ++it)
359  if (!it->second.winner)
360  ++l;
361  return l;
362  }
363 
364 #ifdef DEBUG
365  void dump(std::ostream& out) const
366  {
367  out << "cache max size=" << maxElements << " current size=" << size() << '\n';
368  for (typename DataType::const_iterator it = data.begin(); it != data.end(); ++it)
369  {
370  out << "\tkey=\"" << it->first << "\" value=\"" << it->second.value << "\" serial=" << it->second.serial << " winner=" << it->second.winner << '\n';
371  }
372  out << "--------\n";
373  }
374 #endif
375 
376  };
377 
378 }
379 
380 #endif // CXXTOOLS_CACHE_H