My Project
|
Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and values, respectively. More...
#include <Cache.h>
Public Member Functions | |
Cache () | |
A constructor for class Cache. More... | |
~Cache () | |
A destructor for class Cache. More... | |
Cache (const Cache &c) | |
Copy implementation for class Cache. More... | |
Cache (const int maxEntries, const int maxWeight) | |
A user-suited constructor for class Cache. More... | |
int | getWeight () const |
A method for retrieving the momentary weight of the cache. More... | |
int | getNumberOfEntries () const |
A method for retrieving the momentary number of (key --> value) pairs in the cache. More... | |
int | getMaxNumberOfEntries () const |
A method for retrieving the maximum number of (key --> value) pairs in the cache. More... | |
int | getMaxWeight () const |
A method for retrieving the maximum weight of the cache. More... | |
bool | hasKey (const KeyClass &key) const |
Checks whether the cache contains a pair (k --> v) such that k equals the given key. More... | |
ValueClass | getValue (const KeyClass &key) const |
Returns the value for a given key. More... | |
bool | put (const KeyClass &key, const ValueClass &value) |
Inserts the pair (key --> value) in the cache. More... | |
void | clear () |
Clears the cache so that it has no entry. More... | |
std::string | toString () const |
A method for providing a printable version of the represented cache, including all contained (key --> value) pairs. More... | |
void | print () const |
A method for printing a string representation of the given cache to std::cout. More... | |
Private Member Functions | |
int | getIndexInKey (const KeyClass &key) const |
A method for providing the index of a given key in the vector _key. More... | |
int | getIndexInRank (const ValueClass &value) const |
A method for providing the index of a given value in the vector _rank. More... | |
bool | shrink (const KeyClass &key) |
A method for shrinking the given cache so that it meet the bounds on the maximum number of entries and total weight again. More... | |
bool | deleteLast (const KeyClass &key) |
A method for deleting the least-ranked cache entry. More... | |
Private Attributes | |
std::list< int > | _rank |
A bijection on the set {0, ..., _key.size() - 1}. More... | |
std::list< KeyClass > | _key |
_key is sorted in ascending order, i.e., j < i ==> _key(j) < _key(i), where the right-hand side comparator "<" needs to be implemented in KeyClass. More... | |
std::list< ValueClass > | _value |
_value captures the actual objects of interest;_value [i] corresponds to _key [i] and may be retrieved by calling Cache::getValue (const KeyClass&) const with the argument _key [i]). More... | |
std::list< int > | _weights |
container for the weights of all cached values More... | |
std::list< KeyClass >::const_iterator | _itKey |
a pointer to some element of _key; We make this mutable so that methods which leave the cache unmodified but which alter _itKey can still be declared as const, as the user would expect for these methods. More... | |
std::list< ValueClass >::const_iterator | _itValue |
a pointer to some element of _value; We make this mutable so that methods which leave the cache unmodified but which alter _itValue can still be declared as const, as the user would expect for these methods. More... | |
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. More... | |
int | _maxEntries |
the bound for the number of cached key --> value pairs;The cache will automatically ensure that this bound will never be exceeded; see Cache::shrink (const KeyClass&) and Cache::deleteLast (). More... | |
int | _maxWeight |
the bound on total cache weight; The cache will automatically ensure that this bound will never be exceeded; see see Cache::shrink (const KeyClass&) and Cache::deleteLast (). More... | |
Class Cache is a template-implementation of a cache with arbitrary classes for representing keys and values, respectively.
Each entry of the cache is of the form key --> value, where key is an instance of some KeyClass
, and value an instance of some ValueClass
.
This implementation comes with the possibility to define bounds on both the number of cached pairs key --> value and on the total weight of the cache.
Here, the weight of a cache is defined as the sum of weights of all cached values, where the weight of each value needs to be implemented in the actual class ValueClass
. An example for the weight of a cached value may simply be its size in bytes, or may capture some other useful notion of how heavy the value is. E.g., when caching polynomials, the weight may be defined to be equal to the number of its monomials.
The key --> value pairs of a cache are being stored in two standard lists _key
and _value
of equal length L.
In order to enable a fast value lookup, the vector _key
maintains an ordering such that
i < j ==> _key[i] < _key[j],
where the right-hand side comparator < needs to be implemented by class KeyClass
. Note that this ordering allows for value lookup in time O(log(L)), when given a specific key.
In addition to _key
and _value
, there is a third book-keeping structure in Cache: The vector _rank
of integers captures ranking information among all cached values. More concretely,
_rank : {0, 1, 2, ..., L - 1} --> {0, 1, 2, ..., L - 1}
is a bijection with the semantic
_rank[s] < _rank[t] :<==> _value[_rank[s]] < _value[_rank[t]],
where the right-hand side comparator < needs to be implemented by class ValueClass
. The intention here is that any relation _rank[s] < _rank[t] is to imply that the key-value pair _key[_rank[t]] --> _value[_rank[t]] will be kept at least as long in cache as _key[_rank[s]] --> _value[_rank[s]]. (I.e., loosely speaking, the higher the rank, the longer a pair is going to be cached.)
Whenever the cache becomes either too large (in terms of number of entries), or too heavy (in terms of accumulated weight), it will automatically shrink until both bounds will have been re-established. To this end, the key --> value pair with least value rank will be erased from the cache. This process is repeated until the cache is small enough again, in terms of both the number of entries and the weight. (Note that it may be necessary to erase numerous pairs after inserting just one key --> value when this value's weight is unproportionally high.)
In order to make the above procedures work, the two template classes KeyClass
and ValueClass
need to implement the following methods:
bool KeyClass::operator< (const KeyClass& key),
bool KeyClass::operator== (const KeyClass& key),
bool ValueClass::operator< (const ValueClass& key),
bool ValueClass::operator== (const ValueClass& key),
int ValueClass::getWeight ().
A constructor for class Cache.
The method makes sure that all member vectors be empty.
Definition at line 421 of file CacheImplementation.h.
A destructor for class Cache.
The method clears all member vectors. (This includes that destructors are invoked, accordingly.)
Definition at line 45 of file CacheImplementation.h.
Cache< KeyClass, ValueClass >::Cache | ( | const Cache< KeyClass, ValueClass > & | c | ) |
Copy implementation for class Cache.
Apart from copying all flat members, all vectors are being deep-copied.
Definition at line 424 of file CacheImplementation.h.
Cache< KeyClass, ValueClass >::Cache | ( | const int | maxEntries, |
const int | maxWeight | ||
) |
A user-suited constructor for class Cache.
The method makes sure that all member vectors be empty. Moreover, the user can provide bounds for the maximum number of entries in the cache, and for the total weight of the cache.
maxEntries | the (positive) maximum number of pairs (key --> value) in the cache |
maxWeight | the (positive) maximum weight of the cache |
Definition at line 10 of file CacheImplementation.h.
void Cache< KeyClass, ValueClass >::clear |
|
private |
A method for deleting the least-ranked cache entry.
The method returns true iff the deleted pair (k --> v) satisfies k == key.
key | an instance of KeyClass |
Definition at line 116 of file CacheImplementation.h.
|
private |
A method for providing the index of a given key in the vector _key.
Either _key contains the given key, then its index will be returned. Otherwise the position in _key, at which the given key should be placed (with respect to the ordering in _key) is returned.
key | an instance of KeyClass |
|
private |
A method for providing the index of a given value in the vector _rank.
Based on the rank of the given value, the position in _rank at which the given value should be inserted, is returned. (The method also works, when the given value is already contained in the cache.)
value | an instance of ValueClass |
int Cache< KeyClass, ValueClass >::getMaxNumberOfEntries |
A method for retrieving the maximum number of (key --> value) pairs in the cache.
Definition at line 104 of file CacheImplementation.h.
int Cache< KeyClass, ValueClass >::getMaxWeight |
A method for retrieving the maximum weight of the cache.
Definition at line 110 of file CacheImplementation.h.
int Cache< KeyClass, ValueClass >::getNumberOfEntries |
A method for retrieving the momentary number of (key --> value) pairs in the cache.
The return value will always be less than or equal to the result of Cache::getMaxNumberOfEntries () const.
Definition at line 30 of file CacheImplementation.h.
ValueClass Cache< KeyClass, ValueClass >::getValue | ( | const KeyClass & | key | ) | const |
Returns the value for a given key.
The method assumes that there is actually an entry of the form (key --> *) in the cache. This can be checked before using Cache::hasKey (const KeyClass&) const. (Note that calling both methods in direct succession does not result in extra computational efforts.)
key | the key, for which the corresponding value is to be returned |
Definition at line 78 of file CacheImplementation.h.
int Cache< KeyClass, ValueClass >::getWeight |
A method for retrieving the momentary weight of the cache.
The return value will always be less than or equal to the result of Cache::getMaxWeight () const.
Semantically, the total weight of a cache is the sum of weights of all cached values.
Definition at line 24 of file CacheImplementation.h.
bool Cache< KeyClass, ValueClass >::hasKey | ( | const KeyClass & | key | ) | const |
Checks whether the cache contains a pair (k --> v) such that k equals the given key.
If so, the method returns true; false otherwise. In order to make Cache::getValue (const KeyClass&) const work properly, the user is strongly advised to always check key containment by means of Cache::hasKey (const KeyClass&) const. (The implementation at hand ensures that invoking hasKey and getValue does not result in extra computational efforts.)
key | the key for which containment is to be checked |
Definition at line 54 of file CacheImplementation.h.
void Cache< KeyClass, ValueClass >::print |
A method for printing a string representation of the given cache to std::cout.
This includes string representations of all contained (key --> value) pairs.
Definition at line 415 of file CacheImplementation.h.
bool Cache< KeyClass, ValueClass >::put | ( | const KeyClass & | key, |
const ValueClass & | value | ||
) |
Inserts the pair (key --> value) in the cache.
If there is already some entry (key --> value'), then value will be replaced by value'. As putting some new pair in the cache may result in a violation of the maximal number of entries or the weight of the cache, or both, Cache::put (const KeyClass&, const ValueClass&) will always finalize by calling the private method Cache::shrink(const KeyClass&), in order to re-establish both bounds. Note that this may even result in deleting the newly inserted pair (key --> value).
Because of that undesirable but possible effect, the method returns whether the pair is actually contained in the cache after invocation of Cache::put (const KeyClass&, const ValueClass&).
key | an instance of KeyClass |
value | an instance of ValueClass |
Definition at line 170 of file CacheImplementation.h.
|
private |
A method for shrinking the given cache so that it meet the bounds on the maximum number of entries and total weight again.
The method returns true iff the process of shrinking deleted a pair (k --> v) from the cache such that k equals the given key.
key | an instance of KeyClass |
Definition at line 90 of file CacheImplementation.h.
std::string Cache< KeyClass, ValueClass >::toString |
A method for providing a printable version of the represented cache, including all contained (key --> value) pairs.
Definition at line 355 of file CacheImplementation.h.
|
mutableprivate |
|
mutableprivate |
|
private |
|
private |
the bound for the number of cached key --> value
pairs;
The cache will automatically ensure that this bound will never be exceeded; see Cache::shrink (const KeyClass&) and Cache::deleteLast ().
|
private |
the bound on total cache weight;
The cache will automatically ensure that this bound will never be exceeded; see see Cache::shrink (const KeyClass&) and Cache::deleteLast ().
|
private |
|
private |
_value captures the actual objects of interest;
_value
[i] corresponds to _key
[i] and may be retrieved by calling Cache::getValue (const KeyClass&) const with the argument _key
[i]).
|
private |
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.
Equivalently, this is equal to all weights stored in _weights.
|
private |