ALib C++ Library
Library Version: 2510 R0
Documentation generated by doxygen
Loading...
Searching...
No Matches
lrucachetable.inl
Go to the documentation of this file.
1//==================================================================================================
2/// \file
3/// This header-file is part of module \alib_containers of the \aliblong.
4///
5/// \emoji :copyright: 2013-2025 A-Worx GmbH, Germany.
6/// Published under \ref mainpage_license "Boost Software License".
7//==================================================================================================
8ALIB_EXPORT namespace alib { namespace containers {
9
10/// This type implements a container used for caching objects. When its #Size reaches its #Capacity,
11/// one of the least recently used (LRU) objects is replaced with the next insertion of a non-cached
12/// object.
13///
14/// This implementation uses an array of lists. The lists are forward lists of cached elements
15/// sorted by their insertion time, with the latest insertion in the front.
16/// The list (within the array of lists) used to store and later search an object, is chosen by
17/// the hash value of its key, modulo the number of lists in place.
18/// Both, the size of the lists as well the number of lists (the size of the array) can be chosen
19/// on construction or with method #Reserve.
20/// The memory needed for all entries (and the array of pointers to the start of the list)
21/// is allocated once, when the capacity is set. Generic allocation options (heap-, monotonic-
22/// and pool allocation) are given with template parameter \p{TAllocator}.<br>
23/// Together with the custom data, the hashcode of the key of the data is stored with each element.
24/// This can reduce search time dramatically in some cases, because the equal functor is invoked
25/// only if two objects have the same hashcode.
26///
27/// This design has the following consequences:
28/// - The maximum amount of objects stored, equals the product of the size of the hash-array
29/// and the maximum size of the list.
30/// - The maximum number of comparisons performed before a cache miss is detected, equals
31/// the maximum size of the lists.
32/// - The \b last recently used object is always found with only one comparison. The probability
33/// that other previously used objects (the second last, third last, etc) are likewise found
34/// with only one comparison, rises with the size of the array of lists.
35/// - This container does not necessarily free the least recently used object with the insertion
36/// of an unknown one. Instead, the least recently used object of those cached objects whose hash
37/// function leads to the same list index is freed.
38///
39/// As a sample, two reasonable use cases taken from \alib should be quickly discussed:
40/// 1. Class \alib{files;OwnerAndGroupResolver} of camp \alib_files:
41/// - The type translates owner and group IDs of files to corresponding owner and group names.
42/// - For this, the OS has to be called.
43/// - If for example a directory listing similar to bash command <c>ls -la</c> is to be printed,
44/// the entries in a directory usually share the same owner with very few exceptions.
45/// This is true for home directories inside <c>/home</c> as well as for system directories
46/// like <c>/usr/bin</c>.
47/// - A perfect exception is directory <c>/home</c> itself. Here, every subfolder belongs to a
48/// different owner.
49///
50/// This sample shows that already a very small cache capacity can dramatically decrease the
51/// number of calls to the OS. On the other hand, in the case of the exceptional folders, still
52/// the number of searches performed before a cache-miss is detected is limited to the length
53/// of the lists and not to the total capacity.
54/// The default capacity of the \b %LRUCacheTable chosen by class \b OwnerAndGroupResolver is
55/// <c>6 x 6</c> and can be changed with
56/// \alib{files::OwnerAndGroupResolver;SetOwnerCacheCapacity} and
57/// \alib{files::OwnerAndGroupResolver;SetGroupCacheCapacity}.
58/// 2. Camp \alib_alox:
59/// - With each log operation the placement of the call in a sourcefile (\alib{lox;Scope})
60/// is evaluated to resolve the resulting
61/// \"\ref alib_mod_alox_tak_terminology_domains "Log Domain"\".
62/// - For this, the source file name given by the C++ preprocessor, is to be parsed.
63/// - \alox uses an \b %LRUCacheTable to avoid parsing repetitive scopes.
64/// - It is very much depending on the use case of logging, how often repetitive scopes occur.
65/// For example if verbose logging is active, series of log statements comming from the same
66/// code entity should be expected. If logging is limited and furthermore logging is made
67/// in parallel by multiple threads, then the scopes should be rather mixed, but still
68/// resulting from a limited number of files during a certain period of execution time.
69///
70/// The default capacity of the \b %LRUCacheTable chosen by \alib is likewise <c>4 x 6</c>
71/// and can be changed with \alib{lox;Lox::SetFileNameCacheCapacity}.
72///
73/// Choosing the right values for the two dimensions of the capacity, depends on different
74/// factors of the specific use case, and in most cases cannot be chosen to be perfect in
75/// all situations. Among the things to consider are:
76/// - The costs of creating a new object.
77/// - The cost of comparing two keys.
78/// - The statistical distribution of requests on (subsequent) objects. In cases of even
79/// distribution, the use of this type can become counter-productive!
80/// - Potential memory constraints of the target platform, which may limit the capacity to set.
81///
82/// The stored type is not restricted in respect to complexity or construction, destruction, copy
83/// and move semantics, etc. This is reached by deferring construction to
84/// the caller of method #Try, who, in case of a cache miss, is obligated to duly use a
85/// C++ placement-new to construct an entry.
86///
87/// This class provides a forward-iterator type that fetches all currently cached elements.
88/// While this in most cases is not needed, the central interface method #Try also returns an
89/// iterator. While this iterator is always valid, a second returned value indicates whether also
90/// the element the iterator points to is valid. This distinction is necessary, because this
91/// container only reserves memory for the cached element, but it does not construct one.
92/// To support elegant construction of elements, the iterator class provides method
93/// \alib{containers::LRUCacheTable::TForwardIterator;Construct}.
94/// Furthermore, methods
95/// \alib{containers::LRUCacheTable::TForwardIterator;Key} and
96/// \alib{containers::LRUCacheTable::TForwardIterator;Mapped} allow access to the stored types.
97///
98/// @see
99/// - Type definitions \alib{containers;LRUCacheSet} and
100/// \alib{containers;LRUCacheMap} based on this type.
101/// - The approach to distinguish between "sets", "maps" and "sets with embedded keys" are
102/// the same with class \b %HashTable. Therefore, the
103/// \ref alib_ns_containers_hashtable_setandmap "documentation of class HashTable", which introduces
104/// the same template parameter \p{TValueDescriptor} and also provides similar type definitions
105/// \b %HashSet and \b %HashMap, is very helpful to understanding the concept of this type.
106///
107///
108/// @tparam TAllocator The allocator type to use, as prototyped with \alib{lang;Allocator}.
109/// @tparam TValueDescriptor Defines the #StoredType, #KeyType, and #MappedType. Furthermore has to
110/// provide methods that extract the key and the mapped value from the
111/// stored type.<br>
112/// For details on required type definitions and method signatures, see
113/// provided implementations
114/// \alib{containers;TIdentDescriptor} and
115/// \alib{containers;TPairDescriptor} as a sample.<br>
116/// The type is published as #DescriptorType.
117/// @tparam THash The hash functor applicable to the key-type defined by
118/// \p{TValueDescriptor}.<br>
119/// Defaults to <c>std::hash<typename TValueDescriptor::KeyType></c>
120/// and is published as #HashType.
121/// @tparam TEqual The comparison functor on the key-type defined by
122/// \p{TValueDescriptor}.<br>
123/// Defaults to <c>std::equal_to<typename TValueDescriptor::KeyType></c>
124/// and is published as #EqualType.
125template< typename TAllocator,
126 typename TValueDescriptor,
127 typename THash = std::hash <typename TValueDescriptor::KeyType>,
128 typename TEqual = std::equal_to<typename TValueDescriptor::KeyType> >
129class LRUCacheTable : public lang::AllocatorMember<TAllocator>
130#if ALIB_DEBUG_CRITICAL_SECTIONS
132#endif
133{
134 protected:
135 /// The allocator type that \p{TAllocator} specifies.
137
138 public:
139 /// Type definition publishing template parameter \p{TAllocator}.
140 using AllocatorType = TAllocator;
141
142 /// Type definition publishing template parameter \p{TValueDescriptor}.
143 using DescriptorType = TValueDescriptor;
144
145 /// Type definition publishing the stored type of this container as defined with template
146 /// parameter \p{TValueDescriptor}.
147 using StoredType = typename TValueDescriptor::StoredType;
148
149 /// Type definition publishing the key type of this container as defined with template
150 /// parameter \p{TValueDescriptor}.
151 using KeyType = typename TValueDescriptor::KeyType;
152
153 /// Type definition publishing the map type of this container as defined with template
154 /// parameter \p{TValueDescriptor}.
155 using MappedType = typename TValueDescriptor::MappedType;
156
157 /// Type definition publishing template parameter \p{THash}.
158 using HashType = THash;
159
160 /// Type definition publishing template parameter \p{TEqual}.
161 using EqualType = TEqual;
162
163 protected:
164 /// The node type of the cache lists.
165 struct Entry : public lang::SidiNodeBase<Entry>
166 {
167 size_t hashCode; ///< This entries hash code (calculated once on insertion)
168 StoredType data; ///< The data cached.
169 };
170
171 /// Shortcut to a forward list
173
174 /// Pointer to reserved memory for elements. Size is #capacityLists x #capacityEntries.
176
177 /// The next element to use with a cache-miss on a list that is not of full length, yet.
179
180 /// Array of size #capacityLists that holds the list..
182
183 /// The number of LRU-lists.
185
186 /// The number of entries collected in each LRU-list.
188
189 //================================================================================================
190 //=== Iterator implementation
191 //================================================================================================
192
193 //==============================================================================================
194 /// Templated implementation of \c std::iterator_traits.
195 /// Will be exposed by outer class's definitions
196 /// \alib{containers::LRUCacheTable;Iterator} and
197 /// \alib{containers::LRUCacheTable;ConstIterator}.
198 ///
199 /// As the name of the class indicates, this iterator satisfies the C++ standard library concept
200 /// \https{ForwardIterator,en.cppreference.com/w/cpp/named_req/ForwardIterator}.
201 ///
202 /// @tparam TConstOrMutable A constant or mutable version of #StoredType.
203 //==============================================================================================
204 template<typename TConstOrMutable>
206 {
207 #if !DOXYGEN
208 friend class LRUCacheTable;
209 #endif
210
211 using iterator_category = std::forward_iterator_tag; ///< Implementation of <c>std::iterator_traits</c>.
212 using value_type = TConstOrMutable ; ///< Implementation of <c>std::iterator_traits</c>.
213 using difference_type = integer ; ///< Implementation of <c>std::iterator_traits</c>.
214 using pointer = TConstOrMutable* ; ///< Implementation of <c>std::iterator_traits</c>.
215 using reference = TConstOrMutable& ; ///< Implementation of <c>std::iterator_traits</c>.
216
217 protected:
218 /// The pointer to the actual cache entry.
220
221 /// The pointer to the actual cache entry.
223
224 /// The actual list.
226
227 public:
228 /// Default constructor.
231
232 /// Copy constructor (default).
233 /// @param other The iterator to assign from.
234 TForwardIterator( const TForwardIterator& other ) = default;
235
236 /// Copy constructor accepting a mutable iterator.
237 /// Available only for the constant version of this iterator.
238 /// @tparam TMutable The type of this constructor's argument.
239 /// @param mutableIt Mutable iterator to copy from.
240 template<typename TMutable>
241 requires std::same_as<TMutable, TForwardIterator<StoredType>>
242 TForwardIterator( const TMutable& mutableIt )
243 : entry ( mutableIt.entry ) {}
244
245 /// Constructor that explicitly sets a valid iterator.
246 /// @param pEntry Pointer to a valid element.
247 /// @param pTable The cache table we belong to.
248 /// @param pListIdx The index of the list that \p{pEntry} belongs to.
249 explicit
250 TForwardIterator( Entry* pEntry, LRUCacheTable* pTable, integer pListIdx )
251 : entry (pEntry)
252 , table (pTable)
253 , listIdx(pListIdx) {}
254
255
256 /// Constructor.
257 /// @param pTable The cache table we belong to.
258 /// @param pListIdx The index of the list to start with.
259 explicit
261 : table (pTable)
262 {
263 while( pListIdx < pTable->capacityLists )
264 {
265 if( !pTable->lists[pListIdx].isEmpty() )
266 {
267 listIdx= pListIdx;
268 entry = pTable->lists[pListIdx].first();
269 return;
270 }
271 ++pListIdx;
272 }
273 listIdx= pListIdx;
274 entry = nullptr;
275 }
276
277 /// Copy assignment (default).
278 /// @param other The iterator to assign from.
279 /// @return A reference to this object.
280 TForwardIterator& operator=( const TForwardIterator& other) = default;
281
282 // ################### To satisfy concept of InputIterator ####################
283
284 /// Prefix increment operator.
285 /// @return A reference to this object.
287 {
288 ALIB_ASSERT_ERROR( entry != nullptr, "MONOMEM/LRUCACHE", "Illegal iterator." )
289 entry= entry->next();
290 while( entry == nullptr && ++listIdx < table->capacityLists )
291 entry= table->lists[listIdx].first();
292
293 return *this;
294 }
295
296 /// Postfix increment operator.
297 /// @return An iterator value that is not increased, yet.
299 {
300 auto result= TForwardIterator( *this);
301 ++(*this);
302 return result;
303 }
304
305 /// Comparison operator.
306 /// @param other The iterator to compare ourselves to.
307 /// @return \c true if this and the given iterator are pointing to the same entry,
308 /// \c false otherwise.
309 bool operator==( TForwardIterator other) const
310 {
311 return entry == other.entry;
312 }
313
314 /// Comparison operator.
315 /// @param other The iterator to compare ourselves to.
316 /// @return \c true if this and given iterator are not equal, \c false otherwise.
317 bool operator!=( TForwardIterator other) const
318 {
319 return !(*this == other);
320 }
321
322 // ############ access to templated members ############
323
324 /// Retrieves the stored object that this iterator references.
325 /// @return A reference to the stored object.
326 TConstOrMutable& operator*() const
327 {
328 ALIB_ASSERT_ERROR( entry != nullptr, "MONOMEM/LRUCACHE", "Illegal iterator." )
329 return entry->data;
330 }
331
332 /// Retrieves a pointer to the stored object that this iterator references.
333 /// @return A pointer to the stored object.
334 TConstOrMutable* operator->() const
335 {
336 ALIB_ASSERT_ERROR( entry != nullptr, "MONOMEM/LRUCACHE", "Illegal iterator." )
337 return &entry->data;
338 }
339
340 /// Helper method that performs a placement-new on the data this iterator refers to.
341 /// This method can be used if method #Try indicates a cache miss.
342 ///@tparam TArgs Types of variadic parameters given with parameter \p{args}.
343 ///@param args Variadic parameters to be forwarded to the constructor of the inserted
344 /// instance of type #StoredType.
345 ///@return A reference to the just constructed object.
346 template<typename... TArgs>
347 TConstOrMutable& Construct( TArgs&&... args ) const
348 {
349 ALIB_ASSERT_ERROR( entry != nullptr, "MONOMEM/LRUCACHE", "Illegal iterator." )
350 return *new( &entry->data ) TConstOrMutable(std::forward<TArgs>(args)...);
351 }
352
353 /// Retrieves the stored object that this iterator references.
354 /// @return A reference to the stored object.
355 TConstOrMutable& Value() const
356 {
357 ALIB_ASSERT_ERROR( entry != nullptr, "MONOMEM/LRUCACHE", "Illegal iterator." )
358 return entry->data;
359 }
360
361 /// Retrieves the key-portion of the stored object that this iterator references.
362 /// @return A reference to the key-portion of the stored object.
363 const KeyType& Key() const
364 {
365 ALIB_ASSERT_ERROR( entry != nullptr, "MONOMEM/LRUCACHE", "Illegal iterator." )
366 return TValueDescriptor().Key(entry->data);
367 }
368
369 /// Retrieves the stored object that this iterator references.<br>
370 /// This method is an alias to <c>operator*</c>
371 /// @return A reference to the mapped-portion of the stored object.
373 {
374 ALIB_ASSERT_ERROR( entry != nullptr, "MONOMEM/LRUCACHE", "Illegal iterator." )
375 return TValueDescriptor().Mapped(entry->data);
376 }
377 }; // class TForwardIterator
378
379 public:
380 /// The mutable iterator over the cache entries.
381 using Iterator = TForwardIterator < StoredType>;
382
383 /// The constant iterator over the cache entries.
384 using ConstIterator = TForwardIterator <const StoredType>;
385
386 /// Returns an iterator referring to a mutable entry at the start of this cache.
387 /// @return The first of entry in this container.
388 Iterator begin() { return Iterator ( this, 0 ); }
389
390 /// Returns an iterator referring to a mutable, non-existing entry.
391 /// @return The end of the list of entries in this container.
392 Iterator end() { return Iterator ( this, (std::numeric_limits<integer>::max)() ); }
393
394 /// Returns an iterator referring to a constant entry at the start of this container.
395 /// @return The first of entry in this container.
396 ConstIterator begin() const { return ConstIterator( this, 0 ); }
397
398 /// Returns an iterator referring to a constant, non-existing entry.
399 /// @return The end of the list of entries in this container.
400 ConstIterator end() const { return ConstIterator( this, (std::numeric_limits<integer>::max)() ); }
401
402 /// Returns an iterator referring to a constant entry at the start of this container.
403 /// @return The first of entry in this container.
404 ConstIterator cbegin() const { return ConstIterator( this, 0 ); }
405
406 /// Returns an iterator referring to a constant, non-existing entry.
407 /// @return The end of the list of entries in this container.
408 ConstIterator cend() const { return ConstIterator( this, (std::numeric_limits<integer>::max)() ); }
409
410
411 /// Constructor taking an allocator as well as the sizes forming the capacity of the cache.
412 /// If one of the size parameters is \c 0, no pre-allocation is deferred and #Reserve has
413 /// to be invoked before using this type.
414 /// @param pAllocator The allocator type to use.
415 /// @param tableSize The number of LRU-lists.
416 /// @param listSize The (maximum) size of each list.
417 LRUCacheTable(TAllocator& pAllocator, integer tableSize, integer listSize )
418 : allocBase (pAllocator)
420 ,lang::DbgCriticalSections("LRUCacheTable")
421 #endif
422 , elementPool (nullptr)
423 , nextPoolElement (nullptr)
424 , capacityLists (0)
425 , capacityEntries (0) { Reserve( tableSize, listSize ); }
426
427 /// Constructor omitting the allocator, usable only with heap allocation
428 /// If one of the size parameters is \c 0, no pre-allocation is deferred and #Reserve has
429 /// to be invoked before using this type.
430 /// @param tableSize The number of LRU-lists.
431 /// @param listSize The (maximum) size of each list.
432 LRUCacheTable(integer tableSize, integer listSize )
433 :
435 lang::DbgCriticalSections("LRUCacheTable"),
436 #endif
437 elementPool (nullptr)
438 , nextPoolElement (nullptr)
439 , capacityLists (0)
440 , capacityEntries (0) { Reserve( tableSize, listSize ); }
441
442 /// Destructor. Calls the destructor of each cached value.
444 {
445 if( Capacity() == 0 )
446 return;
447 Clear();
448 allocBase::AI().template FreeArray<Entry >(elementPool, Capacity() );
449 allocBase::AI().template FreeArray<ForwardList>(lists , capacityLists );
450 }
451
452 /// Returns the number of lists used for the cache.
453 /// (Given with construction or a later invocation of method #Reserve.)
454 /// @return This caches' size.
456
457 /// Returns the maximum number of entries held in each list.
458 /// (Given with construction or a later invocation of method #Reserve.)
459 /// @return This caches' size.
461
462 /// Returns the product of #CapacityLists and #CapacityEntries.
463 /// (Both given with construction or a later invocation of method #Reserve.)
464 /// @return This caches' size.
466
467 /// Counts the number of stored elements (operates in O(N)).
468 /// @return The number of elements stored in the cache.
469 integer Size() const noexcept
471 integer result= 0;
472 for (int i = 0; i < capacityLists; ++i)
473 result+= lists[i].count();
474 return result;
475 }
476
477 /// Changes the size of this cache.
478 /// @param newQtyLists The number of LRU-lists to use.
479 /// @param newQtyEntriesPerList The maximum length of each LRU-list list.
480 void Reserve( integer newQtyLists, integer newQtyEntriesPerList )
481 {
482 if( CapacityLists() == newQtyLists
483 && CapacityEntries() == newQtyEntriesPerList )
484 return;
485
486 Clear();
488 auto newCapacity= newQtyLists * newQtyEntriesPerList;
489 if( Capacity() != newCapacity)
490 {
491 if( Capacity() != 0 )
492 allocBase::AI(). template FreeArray<Entry>(elementPool, Capacity());
493
494 elementPool = newCapacity ? allocBase::AI(). template AllocArray<Entry>(newCapacity)
495 : nullptr;
496 }
497
498 if( capacityLists != newQtyLists)
499 {
500 if( capacityLists )
501 allocBase::AI(). template FreeArray<ForwardList>(lists, capacityLists );
502 lists= newQtyLists ? allocBase::AI(). template AllocArray<ForwardList>(newQtyLists)
503 : nullptr;
504
505 for( integer i = 0; i < newQtyLists; ++i )
506 lists[i].reset();
507 }
508
509 capacityLists= newQtyLists;
510 capacityEntries= newQtyEntriesPerList;
512 }
513
514 /// Clears this cache.
515 void Clear()
516 {ALIB_DCS
517 for (integer i = 0; i < capacityLists; ++i)
518 {
519 auto* elem= lists[i].first();
520 while(elem)
521 {
522 lang::Destruct(elem->data);
523 elem= elem->next();
524 }
525 lists[i].reset();
526 }
528 }
529
530 /// Retrieves a value through this cache. The following cases can occur:
531 /// 1. No element with matching \p{key} is found in the cache while not all elements
532 /// of #elementPool are used, yet. In this case the next entry is taken from the pool, and
533 /// the entry is added to the front of the list.
534 /// 2. No element is found while all elements of the #elementPool have been inserted into the
535 /// list already. In this case the last entry of the list is removed, the destructor is
536 /// called on its contents, and the entry is moved to the front of the list.
537 /// 3. The element with matching \p{key} is found. In this case, the entry is moved to the start
538 /// of the list (if not already there).
539 ///
540 /// In cases 1. and 2., this method returns \c false in the first element of the result pair,
541 /// which tells the caller that the value found in the second element has to be constructed.
542 /// This can be done using convenient method
543 /// \alib{containers::LRUCacheTable::TForwardIterator;Construct;Iterator::Construct}.
544 /// Note that besides operator*
545 /// \alib{containers::LRUCacheTable::TForwardIterator;operator*}, the iterator type
546 /// offers methods
547 /// \alib{containers::LRUCacheTable::TForwardIterator;Key} and
548 /// \alib{containers::LRUCacheTable::TForwardIterator;Mapped} to directly access
549 /// corresponding portions of the stored value.
550 ///
551 /// @param key The key value to search for.
552 /// @return A pair of a boolean and an iterator. If the boolean value is \c true, a cached
553 /// entry was found and can be used. If it is \c false, the iterator is valid but
554 /// its data is not! In this case, the caller has to use a placement-new on the
555 /// address of the data receivable with the iterator. This might best be done by
556 /// calling \ref Iterator::Construct.
557 [[nodiscard]]
558 std::pair<bool, Iterator> Try(const KeyType& key)
559 {ALIB_DCS
560 ALIB_ASSERT_ERROR(Capacity() > 0, "MONOMEM","Capacity of LRUCacheTable equals 0 (not set).")
561
562 // start the search below with the first element
563 const size_t keyHash = THash{}(key);
564 const integer listIdx = integer(keyHash % size_t(capacityLists));
565 auto& list = lists[listIdx];
566 Entry* prev2 = nullptr;
567 Entry* prev1 = reinterpret_cast<Entry*>(&list);
568 Entry* actual = list.first();
569 integer cnt = 0;
570
571
572 while( actual != nullptr )
573 {
574 if ( actual->hashCode == keyHash
575 && TEqual{}(TValueDescriptor().Key(actual->data), key) )
576 {
577 // Move the accessed item to the front
578 if (prev1 != nullptr)
579 {
580 prev1->next( actual->next() );
581 actual->next( list.next() );
582 list.next( actual );
583 }
584 return std::make_pair(true, Iterator(actual, this, listIdx ));
585 }
586 prev2= prev1;
587 prev1= actual;
588 actual= actual->next();
589 ++cnt;
590 }
591
592 // Value not found
593
594 // cache is full? -> take the last entry, change it and push it to the front.
595 if( cnt == capacityEntries )
596 {
597 prev2->next( nullptr );
598 prev1->data.~StoredType();
599 prev1->hashCode= keyHash;
600 prev1->next( list.next() );
601 list.next( prev1 );
602 return std::make_pair(false, Iterator(list.first(), this, listIdx ));
603 }
604
605 // cache not full yet -> Create new entry
606 Entry* newEntry= nextPoolElement++;
607 newEntry->hashCode= keyHash;
608 newEntry->next(list.next());
609 list.next(newEntry);
610 return std::make_pair(false, Iterator(list.first(), this, listIdx ));
611 }
612
613}; // struct LRUCacheTable
614
615
616
617/// This type definition is a shortcut to \alib{containers;LRUCacheTable}, usable if data
618/// stored in the container does not include a key-portion, and thus the key to the data
619/// retrievable from the cache has to be separately defined.<br>
620/// To achieve this, this type definition aggregates types \p{TKey} and \p{TMapped} into a
621/// <c>std::pair<TKey,TMapped></c>. This is done using special value descriptor type
622/// \alib{containers;TPairDescriptor}.
623///
624/// \see
625/// For a detailed description of this type, see original type
626/// \alib{containers;LRUCacheTable}, as well as alternative type definition
627/// \alib{containers;LRUCacheSet}.
628///
629/// @tparam TAllocator The allocator type to use, as prototyped with \alib{lang;Allocator}.
630/// @tparam TKey The type of the <em>key-portion</em> of the inserted data.<br>
631/// This type is published as \alib{containers;LRUCacheTable::KeyType}.
632/// @tparam TMapped The type of the <em>mapped-portion</em> of the inserted data.<br>
633/// This type is published as
634/// \alib{containers;LRUCacheTable::MappedType}.
635/// @tparam THash The hash functor applicable to \p{TKey}.<br>
636/// Defaults to <c>std::hash<TKey></c> and is published as
637/// \alib{containers;LRUCacheTable::HashType}.
638/// @tparam TEqual The comparison functor on \p{TKey}.<br>
639/// Defaults to <c>std::equal_to<TKey></c> and is published as
640/// \alib{containers;LRUCacheTable::EqualType}.
641template< typename TAllocator,
642 typename TKey, typename TMapped,
643 typename THash = std::hash <TKey>,
644 typename TEqual = std::equal_to<TKey> >
645using LRUCacheMap = LRUCacheTable< TAllocator,
647 THash, TEqual >;
648
649/// This type definition is a shortcut to \alib{containers;LRUCacheTable}, usable if the full
650/// portion of the data stored in the container is used for the comparison of values.
651///
652/// \note
653/// As with this definition template type \p{TKey} equals stored type \p{T}, methods of
654/// target type \alib{containers;LRUCacheTable} that accept an object of template type
655/// \b TKey expect an object of \p{T} when this type type defintion is used.<br>
656/// In case this is not wanted (or possible), and only the true key-portion should be expected
657/// by interface functions such as \alib{containers;LRUCacheTable::Try}, the underlying
658/// original type \alib{containers;LRUCacheTable}) has to be used.
659///
660/// \see
661/// For a detailed description of this type, see original type
662/// \alib{containers;LRUCacheTable}, as well as alternative type definition
663/// \alib{containers;LRUCacheMap}.
664///
665/// @tparam TAllocator The allocator type to use, as prototyped with \alib{lang;Allocator}.
666/// @tparam T The element type stored with this container.
667/// This type is published as
668/// \alib{containers;LRUCacheTable::StoredType} and type definition
669/// \alib{containers;LRUCacheTable::KeyType} becomes a synonym.
670/// @tparam THash The hash functor applicable to \p{T}. If \c void is given, no hashing
671/// is performed.<br>
672/// Defaults to <c>std::hash<T></c> and is published as
673/// \alib{containers;LRUCacheTable::HashType}.
674/// @tparam TEqual The comparison functor on \p{TKey}.<br>
675/// Defaults to <c>std::equal_to<TKey></c> and is published as
676/// \alib{containers;LRUCacheTable::EqualType}.
677template< typename TAllocator,
678 typename T,
679 typename THash = std::hash <T>,
680 typename TEqual = std::equal_to<T> >
681using LRUCacheSet = LRUCacheTable< TAllocator,
683 THash, TEqual >;
684
685} // namespace alib[::containers]
686
687/// Type alias in namespace \b alib.
688template< typename TAllocator,
689 typename TValueDescriptor,
690 typename THash = std::hash <typename TValueDescriptor::KeyType>,
691 typename TEqual = std::equal_to<typename TValueDescriptor::KeyType> >
693
694
695/// Type alias in namespace \b alib.
696template< typename TAllocator,
697 typename TKey, typename TMapped,
698 typename THash = std::hash <TKey>,
699 typename TEqual = std::equal_to<TKey> >
702
703/// Type alias in namespace \b alib.
704template< typename TAllocator,
705 typename T,
706 typename THash = std::hash <T>,
707 typename TEqual = std::equal_to<T> >
710 THash, TEqual >;
711} // namespace [alib]
712
TConstOrMutable & reference
Implementation of std::iterator_traits.
integer difference_type
Implementation of std::iterator_traits.
TConstOrMutable & Construct(TArgs &&... args) const
TConstOrMutable * pointer
Implementation of std::iterator_traits.
TForwardIterator(Entry *pEntry, LRUCacheTable *pTable, integer pListIdx)
TForwardIterator & operator=(const TForwardIterator &other)=default
bool operator==(TForwardIterator other) const
bool operator!=(TForwardIterator other) const
TForwardIterator(const TForwardIterator &other)=default
std::forward_iterator_tag iterator_category
Implementation of std::iterator_traits.
TConstOrMutable value_type
Implementation of std::iterator_traits.
TForwardIterator(LRUCacheTable *pTable, integer pListIdx)
LRUCacheTable(TAllocator &pAllocator, integer tableSize, integer listSize)
void Clear()
Clears this cache.
std::pair< bool, Iterator > Try(const KeyType &key)
TForwardIterator< StoredType > Iterator
The mutable iterator over the cache entries.
lang::AllocatorMember< TAllocator > allocBase
The allocator type that TAllocator specifies.
TForwardIterator< const StoredType > ConstIterator
The constant iterator over the cache entries.
void Reserve(integer newQtyLists, integer newQtyEntriesPerList)
lang::SidiListHook< Entry > ForwardList
Shortcut to a forward list.
TAllocator AllocatorType
Type definition publishing template parameter TAllocator.
LRUCacheTable(integer tableSize, integer listSize)
TValueDescriptor DescriptorType
Type definition publishing template parameter TValueDescriptor.
typename TValueDescriptor::MappedType MappedType
typename TValueDescriptor::StoredType StoredType
typename TValueDescriptor::KeyType KeyType
~LRUCacheTable()
Destructor. Calls the destructor of each cached value.
TEqual EqualType
Type definition publishing template parameter TEqual.
THash HashType
Type definition publishing template parameter THash.
integer Size() const noexcept
#define ALIB_DCS
Definition alib.inl:1375
#define ALIB_EXPORT
Definition alib.inl:488
#define ALIB_ASSERT_ERROR(cond, domain,...)
Definition alib.inl:1049
#define ALIB_DCS_SHARED
Definition alib.inl:1376
#define ALIB_DEBUG_CRITICAL_SECTIONS
Definition prepro.md:43
LRUCacheTable< TAllocator, containers::TPairDescriptor< TKey, TMapped >, THash, TEqual > LRUCacheMap
LRUCacheTable< TAllocator, TIdentDescriptor< T >, THash, TEqual > LRUCacheSet
void Destruct(T &object)
Definition tmp.inl:83
containers::LRUCacheTable< TAllocator, containers::TPairDescriptor< TKey, TMapped > > LRUCacheMap
Type alias in namespace alib.
containers::LRUCacheTable< TAllocator, TValueDescriptor, THash, TEqual > LRUCacheTable
Type alias in namespace alib.
containers::LRUCacheTable< TAllocator, containers::TIdentDescriptor< T >, THash, TEqual > LRUCacheSet
Type alias in namespace alib.
lang::integer integer
Type alias in namespace alib.
Definition integers.inl:149
The node type of the cache lists.
size_t hashCode
This entries hash code (calculated once on insertion)
AllocatorInterface< TAllocator > AI() const noexcept
TElement * first() const noexcept
Definition sidilist.inl:223
bool isEmpty() const noexcept
Definition sidilist.inl:215