CacheImplementation.h
Go to the documentation of this file.
1 #ifndef CACHE_IMPLEMENTATION_H
2 #define CACHE_IMPLEMENTATION_H
3 
4 #include "reporter/reporter.h"
5 
6 #include <cstdio> // for sprintf
7 #include <iostream>
8 
9 template<class KeyClass, class ValueClass>
10 Cache<KeyClass, ValueClass>::Cache (const int maxEntries, const int maxWeight)
11 {
12  _maxEntries = maxEntries;
13  _maxWeight = maxWeight;
14  _rank.clear();
15  _key.clear();
16  _value.clear();
17  _weights.clear();
18  _itKey = _key.end(); /* referring to past-the-end element in the list */
19  _itValue = _value.end(); /* referring to past-the-end element in the list */
20  _weight = 0;
21 }
22 
23 template<class KeyClass, class ValueClass>
25 {
26  return _weight;
27 }
28 
29 template<class KeyClass, class ValueClass>
31 {
32  return _rank.size();
33 }
34 
35 template<class KeyClass, class ValueClass>
37 {
38  _rank.clear();
39  _key.clear();
40  _value.clear();
41  _weights.clear();
42 }
43 
44 template<class KeyClass, class ValueClass>
46 {
47  _rank.clear();
48  _key.clear();
49  _value.clear();
50  _weights.clear();
51 }
52 
53 template<class KeyClass, class ValueClass>
54 bool Cache<KeyClass, ValueClass>::hasKey (const KeyClass& key) const
55 {
56  _itKey = _key.end(); // referring to past-the-end element in the list
57  typename std::list<KeyClass>::const_iterator itKey;
58  _itValue = _value.begin();
59  /* As _key is a sorted list, the following could actually be implemented
60  in logarithmic time, by bisection. However, for lists this does not work.
61  But often, we can still terminate the linear loop before having visited
62  all elements. */
63  for (itKey = _key.begin(); itKey != _key.end(); itKey++)
64  {
65  int c = key.compare(*itKey);
66  if (c == 0)
67  {
68  _itKey = itKey;
69  return true;
70  }
71  if (c == -1) return false;
72  _itValue++;
73  }
74  return false;
75 }
76 
77 template<class KeyClass, class ValueClass>
78 ValueClass Cache<KeyClass, ValueClass>::getValue (const KeyClass& /*key*/) const
79 {
80  if (_itKey == _key.end())
81  /* _itKey refers to past-the-end element in the list;
82  thus, getValue has been called although hasKey
83  produced no match */
84  assume(false);
85 
86  return *_itValue;
87 }
88 
89 template<class KeyClass, class ValueClass>
90 bool Cache<KeyClass, ValueClass>::shrink(const KeyClass& key)
91 {
92  /* We need to return true iff the pair with given key needed to
93  be erased during the shrinking procedure. So far, we assume no: */
94  bool result = false;
95  /* Shrink until both bounds will be met again: */
96  while (int(_key.size()) > _maxEntries || _weight > _maxWeight)
97  {
98  if (deleteLast(key)) result = true;
99  }
100  return result;
101 }
102 
103 template<class KeyClass, class ValueClass>
105 {
106  return _maxEntries;
107 }
108 
109 template<class KeyClass, class ValueClass>
111 {
112  return _maxWeight;
113 }
114 
115 template<class KeyClass, class ValueClass>
117 {
118  if (_rank.size() == 0)
119  {
120  return false; /* nothing to do */
121  };
122  /* We need to perform the following (empty) loop in order to
123  obtain a forward-iterator pointing to the last entry of _rank.
124  Note: We cannot use rbegin() because we need the iterator for
125  erasing the last entry which is only implemented for forward
126  iterators by std::list. */
127  std::list<int>::iterator itRank;
128  for (itRank = _rank.begin(); itRank != _rank.end(); itRank++) { }
129  itRank--; /* Now, this forward iterator points to the last list entry. */
130  int deleteIndex = *itRank; /* index of (_key, _value)-pair with worst,
131  i.e., highest _rank */
132  bool result = false;
133 
134  /* now delete entries in _key and _value with index deleteIndex */
135  int k = 0;
136  typename std::list<KeyClass>::iterator itKey;
137  typename std::list<ValueClass>::iterator itValue = _value.begin();
138  typename std::list<int>::iterator itWeights = _weights.begin();
139  for (itKey = _key.begin(); itKey != _key.end(); itKey++)
140  {
141  if (k == deleteIndex)
142  {
143  result = (key.compare(*itKey) == 0);
144  break;
145  }
146  itValue++;
147  itWeights++;
148  k++;
149  }
150  _key.erase(itKey);
151  int deleteWeight = *itWeights;
152  _value.erase(itValue);
153  _weights.erase(itWeights);
154 
155  /* adjust total weight of this cache */
156  _weight -= deleteWeight;
157 
158  /* now delete last entry of _rank and decrement all those indices
159  // in _rank by 1 which are larger than deleteIndex */
160  _rank.erase(itRank);
161  for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
162  {
163  if (*itRank > deleteIndex) *itRank -= 1;
164  }
165 
166  return result;
167 }
168 
169 template<class KeyClass, class ValueClass>
170 bool Cache<KeyClass, ValueClass>::put (const KeyClass& key,
171  const ValueClass& value)
172 {
173  bool keyWasContained = false;
174  int oldIndexInKey = -1;
175  int newIndexInKey = _key.size(); /* default to enter new (key, value)-pair
176  is at the end of the two lists;
177  only used in the case
178  keyWasContained == false */
179  int k = 0;
180  typename std::list<KeyClass>::iterator itKey;
181  // itOldValue will later only be used in the case keyWasContained == true: */
182  typename std::list<ValueClass>::iterator itOldValue = _value.begin();
183  /* itOldWeights will later only be used in the case
184  keyWasContained == true */
185  typename std::list<int>::iterator itOldWeights = _weights.begin();
186  for (itKey = _key.begin(); itKey != _key.end(); itKey++)
187  {
188  int c = key.compare(*itKey);
189  if (c == -1)
190  {
191  newIndexInKey = k;
192  break;
193  }
194  if (c == 0)
195  {
196  keyWasContained = true;
197  oldIndexInKey = k;
198  break;
199  }
200  itOldValue++;
201  itOldWeights++;
202  k++;
203  }
204  int utility = value.getUtility();
205  int newWeight = value.getWeight();
206  k = 0;
207  typename std::list<ValueClass>::iterator itValue = _value.begin();
208  for (itValue = _value.begin(); itValue != _value.end(); itValue++)
209  {
210  if (itValue->getUtility() > utility) k++;
211  }
212  int newIndexInRank = k;
213 
214  if (keyWasContained)
215  {
216  /* There was already a pair of the form (key --> *). */
217 
218  /*adjusting the weight of the cache */
219  ValueClass oldValue = *itOldValue;
220  _weight += newWeight - *itOldWeights;
221 
222  /* overwriting old value by argument value */
223  itOldValue = _value.erase(itOldValue);
224  itOldWeights = _weights.erase(itOldWeights);
225  ValueClass myValueCopy = value;
226  _value.insert(itOldValue, myValueCopy);
227  _weights.insert(itOldWeights, newWeight);
228 
229  int oldIndexInRank = -1;
230  /* oldIndexInRank is to be the position in _rank such that
231  _rank[oldIndexInRank] == oldIndexInKey, i.e.
232  _key[_rank[oldIndexInRank]] == key: */
233  std::list<int>::iterator itRank;
234  k = 0;
235  for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
236  {
237  if (*itRank == oldIndexInKey)
238  {
239  oldIndexInRank = k;
240  }
241  k++;
242  }
243  /* Although the key stays the same, the ranking of the (key --> value)
244  pair may be completely different from before. Thus, we need to repair
245  the entries of _rank: */
246  if (oldIndexInRank < newIndexInRank)
247  { /* first insert, then erase */
248  k = 0;
249  /* insert 'oldIndexInKey' at new position 'newIndexInRank': */
250  for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
251  {
252  if (k == newIndexInRank) break;
253  k++;
254  }
255  _rank.insert(itRank, oldIndexInKey); /* note that this may also insert
256  at position itRank == _rank.end(),
257  i.e. when above loop did not
258  terminate because of a 'break'
259  statement */
260  k = 0;
261  /* erase 'oldIndexInKey' at old position 'oldIndexInRank': */
262  for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
263  {
264  if (k == oldIndexInRank)
265  {
266  _rank.erase(itRank);
267  break;
268  }
269  k++;
270  }
271  }
272  else
273  { /* oldIndexInRank >= newIndexInRank */
274  if (oldIndexInRank > newIndexInRank)
275  { /* first erase, then insert */
276  k = 0;
277  /* erase 'oldIndexInKey' at old position 'oldIndexInRank': */
278  for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
279  {
280  if (k == oldIndexInRank)
281  {
282  _rank.erase(itRank);
283  break;
284  }
285  k++;
286  }
287  k = 0;
288  /* insert 'oldIndexInKey' at new position 'newIndexInRank': */
289  for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
290  {
291  if (k == newIndexInRank)
292  {
293  _rank.insert(itRank, oldIndexInKey);
294  break;
295  }
296  k++;
297  }
298  }
299  }
300  }
301  else
302  {
303  /* There is no pair of the form (key --> *). We are about to insert
304  a completely new (key, value)-pair.
305  After this "else" branch, we shall have _key[newIndexInKey] = key;
306  _value[newIndexInKey] = value. Note that, after the above computation,
307  newIndexInKey contains the correct target position.
308  Let's make room for the assignment
309  _rank[newIndexInRank] := newIndexInKey: */
310  std::list<int>::iterator itRank;
311  for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
312  {
313  if (newIndexInKey <= *itRank)
314  {
315  *itRank += 1;
316  }
317  }
318  k = 0;
319  for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
320  {
321  if (k == newIndexInRank) break;
322  k++;
323  }
324  _rank.insert(itRank, newIndexInKey);
325  /* let's insert new key and new value at index newIndexInKey: */
326  itValue = _value.begin();
327  typename std::list<int>::iterator itWeights = _weights.begin();
328  k = 0;
329  for (itKey = _key.begin(); itKey != _key.end(); itKey++)
330  {
331  if (k == newIndexInKey) break;
332  itValue++;
333  itWeights++;
334  k++;
335  }
336  KeyClass myKeyCopy = key;
337  ValueClass myValueCopy = value;
338  _key.insert(itKey, myKeyCopy);
339  _value.insert(itValue, myValueCopy);
340  _weights.insert(itWeights, newWeight);
341  /* adjusting the total weight of the cache: */
342  _weight += newWeight;
343  };
344  /* We may now have to shrink the cache: */
345  bool result = shrink(key); /* true iff shrinking deletes the
346  new (key, value)-pair */
347 
348  assume(_rank.size() == _key.size());
349  assume(_rank.size() == _value.size());
350  return !result; /* true iff the new (key --> value) pair is
351  actually in the cache now */
352 }
353 
354 template<class KeyClass, class ValueClass>
356 {
357  char h[10];
358  std::string s = "Cache:";
359  s += "\n entries: ";
360  sprintf(h, "%d", getNumberOfEntries()); s += h;
361  s += " of at most ";
362  sprintf(h, "%d", getMaxNumberOfEntries()); s += h;
363  s += "\n weight: ";
364  sprintf(h, "%d", getWeight()); s += h;
365  s += " of at most ";
366  sprintf(h, "%d", getMaxWeight()); s += h;
367  if (_key.size() == 0)
368  {
369  s += "\n no pairs, i.e. cache is empty";
370  }
371  else
372  {
373  int k = 1;
374  s += "\n (key --> value) pairs in ascending order of keys:";
375  typename std::list<KeyClass>::const_iterator itKey;
376  typename std::list<ValueClass>::const_iterator itValue = _value.begin();
377  for (itKey = _key.begin(); itKey != _key.end(); itKey++)
378  {
379  s += "\n ";
380  sprintf(h, "%d", k); s += h;
381  s += ". ";
382  s += itKey->toString();
383  s += " --> ";
384  s += itValue->toString();
385  itValue++;
386  k++;
387  }
388  s += "\n (key --> value) pairs in descending order of ranks:";
389  std::list<int>::const_iterator itRank;
390  int r = 1;
391  for (itRank = _rank.begin(); itRank != _rank.end(); itRank++)
392  {
393  int index = *itRank;
394  itValue = _value.begin();
395  k = 0;
396  for (itKey = _key.begin(); itKey != _key.end(); itKey++)
397  {
398  if (k == index) break;
399  k++;
400  itValue++;
401  }
402  s += "\n ";
403  sprintf(h, "%d", r); s += h;
404  s += ". ";
405  s += itKey->toString();
406  s += " --> ";
407  s += itValue->toString();
408  r++;
409  }
410  }
411  return s;
412 }
413 
414 template<class KeyClass, class ValueClass>
416 {
417  PrintS(this->toString().c_str());
418 }
419 
420 template<class KeyClass, class ValueClass>
422 
423 template<class KeyClass, class ValueClass>
425 {
426  _rank = c._rank;
427  _value = c._value;
428  _weights = c._weights;
429  _key = c._key;
430  _weight = c._weight;
431  _maxEntries = c._maxEntries;
432  _maxWeight = c._maxWeight;
433 }
434 
435 #endif
436 /* CACHE_IMPLEMENTATION_H */
const CanonicalForm int s
Definition: facAbsFact.cc:55
int _maxEntries
the bound for the number of cached key –> value pairs; The cache will automatically ensure that thi...
Definition: Cache.h:130
std::string toString() const
A method for providing a printable version of the represented cache, including all contained (key –>...
#define string
Definition: libparse.cc:1250
bool hasKey(const KeyClass &key) const
Checks whether the cache contains a pair (k –> v) such that k equals the given key.
int _maxWeight
the bound on total cache weight; The cache will automatically ensure that this bound will never be e...
Definition: Cache.h:138
int k
Definition: cfEzgcd.cc:92
ValueClass getValue(const KeyClass &key) const
Returns the value for a given key.
Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and ...
Definition: Cache.h:68
int getNumberOfEntries() const
A method for retrieving the momentary number of (key –> value) pairs in the cache.
Cache()
A constructor for class Cache.
std::list< int > _rank
A bijection on the set {0, ..., _key.size() - 1}.
Definition: Cache.h:77
#define assume(x)
Definition: mod2.h:390
void print() const
A method for printing a string representation of the given cache to std::cout.
std::list< int > _weights
container for the weights of all cached values
Definition: Cache.h:98
int getMaxNumberOfEntries() const
A method for retrieving the maximum number of (key –> value) pairs in the cache. ...
void PrintS(const char *s)
Definition: reporter.cc:284
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
std::list< ValueClass > _value
_value captures the actual objects of interest; _value[i] corresponds to _key[i] and may be retrieve...
Definition: Cache.h:93
void clear()
Clears the cache so that it has no entry.
bool put(const KeyClass &key, const ValueClass &value)
Inserts the pair (key –> value) in the cache.
int getMaxWeight() const
A method for retrieving the maximum weight of the cache.
bool shrink(const KeyClass &key)
A method for shrinking the given cache so that it meet the bounds on the maximum number of entries an...
std::string toString(const gfan::ZCone *const c)
Definition: bbcone.cc:27
bool deleteLast(const KeyClass &key)
A method for deleting the least-ranked cache entry.
int getWeight() const
A method for retrieving the momentary weight of the cache.
static Poly * h
Definition: janet.cc:972
std::list< KeyClass > _key
_key is sorted in ascending order, i.e., j < i ==> _key(j) < _key(i), where the right-hand side compa...
Definition: Cache.h:85
~Cache()
A destructor for class Cache.
return result
Definition: facAbsBiFact.cc:76
int _weight
for storing the momentary weight of the given cache; This is the sum of _value[i].getWeight() over all i, i.e., over all cached values.
Definition: Cache.h:122