This type implements a container used for caching objects. When its Size reaches its Capacity, one of the least recently used (LRU) objects is replaced with the next insertion of a non-cached object.
This implementation uses an array of lists. The lists are forward lists of cached elements sorted by their insertion time, with the latest insertion in the front. The list (within the array of lists) used to store and later search an object, is chosen by the hash value of its key, modulo the number of lists in place. Both, the size of the lists as well the number of lists (the size of the array) can be chosen on construction or with method Reserve. The memory needed for all entries (and the array of pointers to the start of the list) is allocated once, when the capacity is set. Generic allocation options (heap-, monotonic- and pool allocation) are given with template parameter TAllocator.
Together with the custom data, the hashcode of the key of the data is stored with each element. This can reduce search time dramatically in some cases, because the equal functor is invoked only if two objects have the same hashcode.
This design has the following consequences:
As a sample, two reasonable use cases taken from ALib should be quickly discussed:
Class OwnerAndGroupResolver of camp ALib Files:
ls -la
is to be printed, the entries in a directory usually share the same owner with very few exceptions. This is true for home directories inside /home
as well as for system directories like /usr/bin
./home
itself. Here, every subfolder belongs to a different owner.This sample shows that already a very small cache capacity can dramatically decrease the number of calls to the OS. On the other hand, in the case of the exceptional folders, still the number of searches performed before a cache-miss is detected is limited to the length of the lists and not to the total capacity. The default capacity of the LRUCacheTable chosen by class OwnerAndGroupResolver is 6 x 6
and can be changed with SetOwnerCacheCapacity and SetGroupCacheCapacity.
Camp ALox:
The default capacity of the LRUCacheTable chosen by ALib is likewise 4 x 6
and can be changed with Lox::SetFileNameCacheCapacity.
Choosing the right values for the two dimensions of the capacity, depends on different factors of the specific use case, and in most cases cannot be chosen to be perfect in all situations. Among the things to consider are:
The stored type is not restricted in respect to complexity or construction, destruction, copy and move semantics, etc. This is reached by deferring construction to the caller of method Try, who, in case of a cache miss, is obligated to duly use a C++ placement-new to construct an entry.
This class provides a forward-iterator type that fetches all currently cached elements. While this in most cases is not needed, the central interface method Try also returns an iterator. While this iterator is always valid, a second returned value indicates whether also the element the iterator points to is valid. This distinction is necessary, because this container only reserves memory for the cached element, but it does not construct one. To support elegant construction of elements, the iterator class provides method Construct. Furthermore, methods Key and Mapped allow access to the stored types.
TAllocator | The allocator type to use, as prototyped with Allocator. |
TValueDescriptor | Defines the StoredType, KeyType, and MappedType. Furthermore has to provide methods that extract the key and the mapped value from the stored type. For details on required type definitions and method signatures, see provided implementations TIdentDescriptor and TPairDescriptor as a sample. The type is published as DescriptorType. |
THash | The hash functor applicable to the key-type defined by TValueDescriptor. Defaults to std::hash<typename TValueDescriptor::KeyType> and is published as HashType. |
TEqual | The comparison functor on the key-type defined by TValueDescriptor. Defaults to std::equal_to<typename TValueDescriptor::KeyType> and is published as EqualType. |
Definition at line 129 of file lrucachetable.inl.
Inner Type Index: | |
struct | Entry |
The node type of the cache lists. More... | |
class | TForwardIterator |
Public Type Index: | |
using | AllocatorType = TAllocator |
Type definition publishing template parameter TAllocator. | |
using | ConstIterator = TForwardIterator <const StoredType> |
The constant iterator over the cache entries. | |
using | DescriptorType = TValueDescriptor |
Type definition publishing template parameter TValueDescriptor. | |
using | EqualType = TEqual |
Type definition publishing template parameter TEqual. | |
using | HashType = THash |
Type definition publishing template parameter THash. | |
using | Iterator = TForwardIterator < StoredType> |
The mutable iterator over the cache entries. | |
using | KeyType = typename TValueDescriptor::KeyType |
using | MappedType = typename TValueDescriptor::MappedType |
using | StoredType = typename TValueDescriptor::StoredType |
![]() | |
using | AllocatorType = TAllocator |
Exposes the allocator type. | |
Public Method Index: | |
LRUCacheTable (integer tableSize, integer listSize) | |
LRUCacheTable (TAllocator &pAllocator, integer tableSize, integer listSize) | |
~LRUCacheTable () | |
Destructor. Calls the destructor of each cached value. | |
Iterator | begin () |
ConstIterator | begin () const |
integer | Capacity () const |
integer | CapacityEntries () const |
integer | CapacityLists () const |
ConstIterator | cbegin () const |
ConstIterator | cend () const |
void | Clear () |
Clears this cache. | |
Iterator | end () |
ConstIterator | end () const |
void | Reserve (integer newQtyLists, integer newQtyEntriesPerList) |
integer | Size () const noexcept |
std::pair< bool, Iterator > | Try (const KeyType &key) |
![]() | |
AllocatorMember ()=delete | |
Deleted default constructor. (The allocator has to be given with construction) | |
AllocatorMember (TAllocator &pAllocator) noexcept | |
AllocatorInterface< TAllocator > | AI () const noexcept |
TAllocator & | GetAllocator () const noexcept |
![]() | |
DbgCriticalSections (const char *name) | |
~DbgCriticalSections () | |
Destructor. Checks that this instance is unused. | |
ALIB_DLL void | Acquire (const CallerInfo &ci) const |
ALIB_DLL void | AcquireShared (const CallerInfo &ci) const |
ALIB_DLL void | doAssert (bool cond, const CallerInfo &ciAssert, const CallerInfo &ci, const char *headline) const |
ALIB_DLL void | Release (const CallerInfo &ci) const |
ALIB_DLL void | ReleaseShared (const CallerInfo &ci) const |
void | yieldOrSleep () const |
Protected Type Index: | |
using | allocBase = lang::AllocatorMember<TAllocator> |
The allocator type that TAllocator specifies. | |
using | ForwardList = lang::SidiListHook<Entry> |
Shortcut to a forward list. | |
Protected Field Index: | |
integer | capacityEntries |
The number of entries collected in each LRU-list. | |
integer | capacityLists |
The number of LRU-lists. | |
Entry * | elementPool |
Pointer to reserved memory for elements. Size is capacityLists x capacityEntries. | |
ForwardList * | lists |
Array of size capacityLists that holds the list.. | |
Entry * | nextPoolElement |
The next element to use with a cache-miss on a list that is not of full length, yet. | |
![]() | |
TAllocator & | allocator |
A reference to the allocator. | |
Additional Inherited Members | |
![]() | |
static ALIB_DLL const char * | ASSERTION_FORMAT |
![]() | |
CallerInfo | DCSAcq |
Source location of acquirement. | |
AssociatedLock * | DCSLock {nullptr} |
const char * | DCSName |
The name of this DCS. Used for debug-output. | |
std::atomic< int > | DCSReaderCnt {0} |
Tracks enter/exit calls of readers. | |
CallerInfo | DCSRel |
Source location of the last "reader" seen. | |
CallerInfo | DCSSAcq |
Source location of acquirement. | |
CallerInfo | DCSSRel |
Source location of the last "reader" seen. | |
std::atomic< int > | DCSWriterCnt {0} |
Tracks enter/exit calls (including readers) | |
int | DCSYieldOrSleepTimeInNS = -1 |
using alib::containers::LRUCacheTable< TAllocator, TValueDescriptor, THash, TEqual >::AllocatorType = TAllocator |
Type definition publishing template parameter TAllocator.
Definition at line 140 of file lrucachetable.inl.
|
protected |
The allocator type that TAllocator specifies.
Definition at line 136 of file lrucachetable.inl.
using alib::containers::LRUCacheTable< TAllocator, TValueDescriptor, THash, TEqual >::ConstIterator = TForwardIterator <const StoredType> |
The constant iterator over the cache entries.
Definition at line 384 of file lrucachetable.inl.
using alib::containers::LRUCacheTable< TAllocator, TValueDescriptor, THash, TEqual >::DescriptorType = TValueDescriptor |
Type definition publishing template parameter TValueDescriptor.
Definition at line 143 of file lrucachetable.inl.
using alib::containers::LRUCacheTable< TAllocator, TValueDescriptor, THash, TEqual >::EqualType = TEqual |
Type definition publishing template parameter TEqual.
Definition at line 161 of file lrucachetable.inl.
|
protected |
Shortcut to a forward list.
Definition at line 172 of file lrucachetable.inl.
using alib::containers::LRUCacheTable< TAllocator, TValueDescriptor, THash, TEqual >::HashType = THash |
Type definition publishing template parameter THash.
Definition at line 158 of file lrucachetable.inl.
using alib::containers::LRUCacheTable< TAllocator, TValueDescriptor, THash, TEqual >::Iterator = TForwardIterator < StoredType> |
The mutable iterator over the cache entries.
Definition at line 381 of file lrucachetable.inl.
using alib::containers::LRUCacheTable< TAllocator, TValueDescriptor, THash, TEqual >::KeyType = typename TValueDescriptor::KeyType |
Type definition publishing the key type of this container as defined with template parameter TValueDescriptor.
Definition at line 151 of file lrucachetable.inl.
using alib::containers::LRUCacheTable< TAllocator, TValueDescriptor, THash, TEqual >::MappedType = typename TValueDescriptor::MappedType |
Type definition publishing the map type of this container as defined with template parameter TValueDescriptor.
Definition at line 155 of file lrucachetable.inl.
using alib::containers::LRUCacheTable< TAllocator, TValueDescriptor, THash, TEqual >::StoredType = typename TValueDescriptor::StoredType |
Type definition publishing the stored type of this container as defined with template parameter TValueDescriptor.
Definition at line 147 of file lrucachetable.inl.
|
protected |
The number of entries collected in each LRU-list.
Definition at line 187 of file lrucachetable.inl.
|
protected |
The number of LRU-lists.
Definition at line 184 of file lrucachetable.inl.
|
protected |
Pointer to reserved memory for elements. Size is capacityLists x capacityEntries.
Definition at line 175 of file lrucachetable.inl.
|
protected |
Array of size capacityLists that holds the list..
Definition at line 181 of file lrucachetable.inl.
|
protected |
The next element to use with a cache-miss on a list that is not of full length, yet.
Definition at line 178 of file lrucachetable.inl.
|
inline |
Constructor taking an allocator as well as the sizes forming the capacity of the cache. If one of the size parameters is 0
, no pre-allocation is deferred and Reserve has to be invoked before using this type.
pAllocator | The allocator type to use. |
tableSize | The number of LRU-lists. |
listSize | The (maximum) size of each list. |
Definition at line 417 of file lrucachetable.inl.
|
inline |
Constructor omitting the allocator, usable only with heap allocation If one of the size parameters is 0
, no pre-allocation is deferred and Reserve has to be invoked before using this type.
tableSize | The number of LRU-lists. |
listSize | The (maximum) size of each list. |
Definition at line 432 of file lrucachetable.inl.
|
inline |
Destructor. Calls the destructor of each cached value.
Definition at line 443 of file lrucachetable.inl.
|
inline |
Returns an iterator referring to a mutable entry at the start of this cache.
Definition at line 388 of file lrucachetable.inl.
|
inline |
Returns an iterator referring to a constant entry at the start of this container.
Definition at line 396 of file lrucachetable.inl.
|
inline |
Returns the product of CapacityLists and CapacityEntries. (Both given with construction or a later invocation of method Reserve.)
Definition at line 465 of file lrucachetable.inl.
|
inline |
Returns the maximum number of entries held in each list. (Given with construction or a later invocation of method Reserve.)
Definition at line 460 of file lrucachetable.inl.
|
inline |
Returns the number of lists used for the cache. (Given with construction or a later invocation of method Reserve.)
Definition at line 455 of file lrucachetable.inl.
|
inline |
Returns an iterator referring to a constant entry at the start of this container.
Definition at line 404 of file lrucachetable.inl.
|
inline |
Returns an iterator referring to a constant, non-existing entry.
Definition at line 408 of file lrucachetable.inl.
|
inline |
Clears this cache.
Definition at line 515 of file lrucachetable.inl.
|
inline |
Returns an iterator referring to a mutable, non-existing entry.
Definition at line 392 of file lrucachetable.inl.
|
inline |
Returns an iterator referring to a constant, non-existing entry.
Definition at line 400 of file lrucachetable.inl.
|
inline |
Changes the size of this cache.
newQtyLists | The number of LRU-lists to use. |
newQtyEntriesPerList | The maximum length of each LRU-list list. |
Definition at line 480 of file lrucachetable.inl.
|
inlinenoexcept |
Counts the number of stored elements (operates in O(N)).
Definition at line 469 of file lrucachetable.inl.
|
inlinenodiscard |
Retrieves a value through this cache. The following cases can occur:
In cases 1. and 2., this method returns false
in the first element of the result pair, which tells the caller that the value found in the second element has to be constructed. This can be done using convenient method Iterator::Construct. Note that besides operator* operator*, the iterator type offers methods Key and Mapped to directly access corresponding portions of the stored value.
key | The key value to search for. |
true
, a cached entry was found and can be used. If it is false
, the iterator is valid but its data is not! In this case, the caller has to use a placement-new on the address of the data receivable with the iterator. This might best be done by calling Iterator::Construct. Definition at line 558 of file lrucachetable.inl.