Description:

template<typename TAllocator, typename TValueDescriptor, typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>
class alib::containers::LRUCacheTable< TAllocator, TValueDescriptor, THash, TEqual >

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:

The maximum amount of objects stored, equals the product of the size of the hash-array and the maximum size of the list.
The maximum number of comparisons performed before a cache miss is detected, equals the maximum size of the lists.
The last recently used object is always found with only one comparison. The probability that other previously used objects (the second last, third last, etc) are likewise found with only one comparison, rises with the size of the array of lists.
This container does not necessarily free the least recently used object with the insertion of an unknown one. Instead, the least recently used object of those cached objects whose hash function leads to the same list index is freed.

As a sample, two reasonable use cases taken from ALib should be quickly discussed:

Class OwnerAndGroupResolver of camp ALib Files:
- The type translates owner and group IDs of files to corresponding owner and group names.
- For this, the OS has to be called.
- If for example a directory listing similar to bash command 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.
- A perfect exception is directory /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:
- With each log operation the placement of the call in a sourcefile (Scope) is evaluated to resolve the resulting "Log Domain".
- For this, the source file name given by the C++ preprocessor, is to be parsed.
- ALox uses an LRUCacheTable to avoid parsing repetitive scopes.
- It is very much depending on the use case of logging, how often repetitive scopes occur. For example if verbose logging is active, series of log statements comming from the same code entity should be expected. If logging is limited and furthermore logging is made in parallel by multiple threads, then the scopes should be rather mixed, but still resulting from a limited number of files during a certain period of execution time.
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 costs of creating a new object.
The cost of comparing two keys.
The statistical distribution of requests on (subsequent) objects. In cases of even distribution, the use of this type can become counter-productive!
Potential memory constraints of the target platform, which may limit the capacity to set.

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.

See also

Type definitions LRUCacheSet and LRUCacheMap based on this type.
The approach to distinguish between "sets", "maps" and "sets with embedded keys" are the same with class HashTable. Therefore, the documentation of class HashTable, which introduces the same template parameter TValueDescriptor and also provides similar type definitions HashSet and HashMap, is very helpful to understanding the concept of this type.

Template Parameters

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 140 of file lrucachetable.hpp.

#include <lrucachetable.hpp>

Inheritance diagram for LRUCacheTable< TAllocator, TValueDescriptor, THash, TEqual >:

[legend]

Collaboration diagram for LRUCacheTable< TAllocator, TValueDescriptor, THash, TEqual >:

[legend]

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

Public Type Index: inherited from AllocatorMember< TAllocator >
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)

Public Method Index: inherited from AllocatorMember< TAllocator >
	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

Public Method Index: inherited from DbgCriticalSections
ALIB_FORCE_INLINE	DbgCriticalSections (const char *name)

ALIB_FORCE_INLINE	~DbgCriticalSections ()
	Destructor. Checks that this instance is unused.

ALIB_API void	Acquire (const CallerInfo &ci) const

ALIB_API void	AcquireShared (const CallerInfo &ci) const

ALIB_API void	doAssert (bool cond, const CallerInfo &ciAssert, const CallerInfo &ci, const char *headline) const

ALIB_API void	Release (const CallerInfo &ci) const

ALIB_API void	ReleaseShared (const CallerInfo &ci) const

ALIB_FORCE_INLINE 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.

Protected Field Index: inherited from AllocatorMember< TAllocator >
TAllocator &	allocator
	A reference to the allocator.

Additional Inherited Members
Public Static Field Index: inherited from DbgCriticalSections
static ALIB_API const char *	ASSERTION_FORMAT

Public Field Index: inherited from DbgCriticalSections
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

Type Definition Details:

◆ AllocatorType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

using AllocatorType = TAllocator

Type definition publishing template parameter TAllocator.

Definition at line 151 of file lrucachetable.hpp.

◆ allocBase

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

using allocBase = lang::AllocatorMember<TAllocator>

protected

The allocator type that TAllocator specifies.

Definition at line 147 of file lrucachetable.hpp.

◆ ConstIterator

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

using ConstIterator = TForwardIterator <const StoredType>

The constant iterator over the cache entries.

Definition at line 402 of file lrucachetable.hpp.

◆ DescriptorType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

using DescriptorType = TValueDescriptor

Type definition publishing template parameter TValueDescriptor.

Definition at line 154 of file lrucachetable.hpp.

◆ EqualType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

using EqualType = TEqual

Type definition publishing template parameter TEqual.

Definition at line 172 of file lrucachetable.hpp.

◆ ForwardList

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

using ForwardList = lang::SidiListHook<Entry>

protected

Shortcut to a forward list.

Definition at line 183 of file lrucachetable.hpp.

◆ HashType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

using HashType = THash

Type definition publishing template parameter THash.

Definition at line 169 of file lrucachetable.hpp.

◆ Iterator

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

using Iterator = TForwardIterator < StoredType>

The mutable iterator over the cache entries.

Definition at line 399 of file lrucachetable.hpp.

◆ KeyType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

using KeyType = typename TValueDescriptor::KeyType

Type definition publishing the key type of this container as defined with template parameter TValueDescriptor.

Definition at line 162 of file lrucachetable.hpp.

◆ MappedType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

using MappedType = typename TValueDescriptor::MappedType

Type definition publishing the map type of this container as defined with template parameter TValueDescriptor.

Definition at line 166 of file lrucachetable.hpp.

◆ StoredType

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

using StoredType = typename TValueDescriptor::StoredType

Type definition publishing the stored type of this container as defined with template parameter TValueDescriptor.

Definition at line 158 of file lrucachetable.hpp.

Field Details:

◆ capacityEntries

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

integer capacityEntries

protected

The number of entries collected in each LRU-list.

Definition at line 198 of file lrucachetable.hpp.

◆ capacityLists

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

integer capacityLists

protected

The number of LRU-lists.

Definition at line 195 of file lrucachetable.hpp.

◆ elementPool

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

Entry* elementPool

protected

Pointer to reserved memory for elements. Size is capacityLists x capacityEntries.

Definition at line 186 of file lrucachetable.hpp.

◆ lists

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

ForwardList* lists

protected

Array of size capacityLists that holds the list..

Definition at line 192 of file lrucachetable.hpp.

◆ nextPoolElement

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

Entry* nextPoolElement

protected

The next element to use with a cache-miss on a list that is not of full length, yet.

Definition at line 189 of file lrucachetable.hpp.

Constructor(s) / Destructor Details:

◆ LRUCacheTable() [1/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

LRUCacheTable	(	TAllocator &	pAllocator,
		integer	tableSize,
		integer	listSize )

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.

Parameters

pAllocator	The allocator type to use.
tableSize	The number of LRU-lists.
listSize	The (maximum) size of each list.

Definition at line 435 of file lrucachetable.hpp.

Here is the call graph for this function:

◆ LRUCacheTable() [2/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

LRUCacheTable	(	integer	tableSize,
		integer	listSize )

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.

Parameters

tableSize	The number of LRU-lists.
listSize	The (maximum) size of each list.

Definition at line 450 of file lrucachetable.hpp.

Here is the call graph for this function:

◆ ~LRUCacheTable()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

~LRUCacheTable ( )

inline

Destructor. Calls the destructor of each cached value.

Definition at line 461 of file lrucachetable.hpp.

Here is the call graph for this function:

Method Details:

◆ begin() [1/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

Iterator begin ( )

inline

Returns an iterator referring to a mutable entry at the start of this cache.

Returns: The first of entry in this container.

Definition at line 406 of file lrucachetable.hpp.

◆ begin() [2/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

ConstIterator begin ( ) const

inline

Returns an iterator referring to a constant entry at the start of this container.

Returns: The first of entry in this container.

Definition at line 414 of file lrucachetable.hpp.

◆ Capacity()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

integer Capacity ( ) const

inline

Returns the product of CapacityLists and CapacityEntries. (Both given with construction or a later invocation of method Reserve.)

Returns: This caches' size.

Definition at line 483 of file lrucachetable.hpp.

◆ CapacityEntries()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

integer CapacityEntries ( ) const

inline

Returns the maximum number of entries held in each list. (Given with construction or a later invocation of method Reserve.)

Returns: This caches' size.

Definition at line 478 of file lrucachetable.hpp.

◆ CapacityLists()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

integer CapacityLists ( ) const

inline

Returns the number of lists used for the cache. (Given with construction or a later invocation of method Reserve.)

Returns: This caches' size.

Definition at line 473 of file lrucachetable.hpp.

◆ cbegin()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

ConstIterator cbegin ( ) const

inline

Returns an iterator referring to a constant entry at the start of this container.

Returns: The first of entry in this container.

Definition at line 422 of file lrucachetable.hpp.

◆ cend()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

ConstIterator cend ( ) const

inline

Returns an iterator referring to a constant, non-existing entry.

Returns: The end of the list of entries in this container.

Definition at line 426 of file lrucachetable.hpp.

◆ Clear()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

void Clear ( )

inline

Clears this cache.

Definition at line 535 of file lrucachetable.hpp.

Here is the call graph for this function:

◆ end() [1/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

Iterator end ( )

inline

Returns an iterator referring to a mutable, non-existing entry.

Returns: The end of the list of entries in this container.

Definition at line 410 of file lrucachetable.hpp.

◆ end() [2/2]

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

ConstIterator end ( ) const

inline

Returns an iterator referring to a constant, non-existing entry.

Returns: The end of the list of entries in this container.

Definition at line 418 of file lrucachetable.hpp.

◆ Reserve()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

void Reserve	(	integer	newQtyLists,
		integer	newQtyEntriesPerList )

inline

Changes the size of this cache.

Parameters

newQtyLists	The number of LRU-lists to use.
newQtyEntriesPerList	The maximum length of each LRU-list list.

Definition at line 498 of file lrucachetable.hpp.

Here is the call graph for this function:

◆ Size()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

integer Size ( ) const

inlinenoexcept

Counts the number of stored elements (operates in O(N)).

Returns: The number of elements stored in the cache.

Definition at line 487 of file lrucachetable.hpp.

◆ Try()

template<typename TAllocator , typename TValueDescriptor , typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>>

std::pair< bool, Iterator > Try ( const KeyType & key )

inlinenodiscard

Retrieves a value through this cache. The following cases can occur:

No element with matching key is found in the cache while not all elements of elementPool are used, yet. In this case the next entry is taken from the pool, and the entry is added to the front of the list.
No element is found while all elements of the elementPool have been inserted into the list already. In this case the last entry of the list is removed, the destructor is called on its contents, and the entry is moved to the front of the list.
The element with matching key is found. In this case, the entry is moved to the start of the list (if not already there).

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.

Parameters

key	The key value to search for.

Returns: A pair of a boolean and an iterator. If the boolean value is 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 580 of file lrucachetable.hpp.

Here is the call graph for this function:

The documentation for this class was generated from the following file:

lrucachetable.hpp

Description:

Inner Type Index:

Public Type Index:

Public Method Index:

Protected Type Index:

Protected Field Index:

Additional Inherited Members

Type Definition Details:

◆ AllocatorType

◆ allocBase

◆ ConstIterator

◆ DescriptorType

◆ EqualType

◆ ForwardList

◆ HashType

◆ Iterator

◆ KeyType

◆ MappedType

◆ StoredType

Field Details:

◆ capacityEntries

◆ capacityLists

◆ elementPool

◆ lists

◆ nextPoolElement

Constructor(s) / Destructor Details:

◆ LRUCacheTable() [1/2]

◆ LRUCacheTable() [2/2]

◆ ~LRUCacheTable()

Method Details:

◆ begin() [1/2]

◆ begin() [2/2]

◆ Capacity()

◆ CapacityEntries()

◆ CapacityLists()

◆ cbegin()

◆ cend()

◆ Clear()

◆ end() [1/2]

◆ end() [2/2]

◆ Reserve()

◆ Size()

◆ Try()