ALib C++ Library
Library Version: 2510 R0
Documentation generated by doxygen
Loading...
Searching...
No Matches
hashtablebase.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//==================================================================================================
8// Not exported
9#if ALIB_SIZEOF_INTEGER == 4
10 static constexpr int PRIME_TABLE_SIZE = 26;
11#elif ALIB_SIZEOF_INTEGER == 8
12 /// The size of the static table of prime numbers. Depends on the platform.
13 static constexpr int PRIME_TABLE_SIZE = 58;
14#else
15 #error "Unknown size of integer"
16#endif
17
18// forward declaration of HashTable
20 template< typename TAllocator,
21 typename TValueDescriptor,
22 typename THash,
23 typename TEqual,
24 lang::Caching THashCaching,
25 Recycling TRecycling >
26 class HashTable;
27}
28
30
31/// Table of prime numbers. The effective bucket size is chosen to be the first value found in
32/// this table that is equal or higher than the requested size.
34
35/// A dummy bucket used for nulled hash tables to avoid otherwise necessary checks.
36ALIB_DLL extern void* DUMMY_BUCKET;
37
38/// HashTable element type if hash codes are cached.
39/// @tparam TStored The custom data stored.
40template<typename TStored>
41struct HTElementCached : public lang::SidiNodeBase<HTElementCached<TStored>>
42{
43 /// Denotes that hash codes are cached.
44 static constexpr bool CachedHashCodes = 1;
45
46 /// The custom data stored in nodes of this table.
47 TStored value;
48
49 size_t hashCode; ///< The cached hash code.
50
51 /// Stores the given hash code when an element is recycled or extracted and changed.
52 /// @param pHashCode The new hash code to set for this (recycled) element.
53 void fixHashCode( size_t pHashCode ) { *const_cast<size_t*>(&hashCode)= pHashCode; }
54
55 /// Returns the cached hash code.
56 /// @return The hash code of this element.
57 size_t getCached() { return hashCode; }
58
59};
60
61/// HashTable element type if hash codes are not cached.
62/// @tparam TStored The custom data stored.
63template<typename TStored>
64struct HTElementUncached : public lang::SidiNodeBase<HTElementUncached<TStored>>
65{
66 /// Denotes that hash codes are not cached.
67 static constexpr bool CachedHashCodes = 0;
68
69 /// The custom data stored in nodes of this table.
70 TStored value;
71
72 /// Does nothing, parameter ignored.
73 /// @param pHashCode Ignored
74 void fixHashCode( size_t pHashCode ) { (void) pHashCode; }
75
76 /// Never called.
77 /// @return Undefined.
78 size_t getCached() { return 0; }
79};
80
81/// Node types used with \alib{containers;HashTable}.
82/// @tparam TValueDescriptor The descriptor of contained types provided with a template parameter
83/// of the \b HashTable.
84/// @tparam THashCaching A template parameter of the \b HashTable that determines whether
85/// hash values are cached or not.
86template<typename TValueDescriptor, lang::Caching THashCaching>
88{
89 /// @return \c true, if the selected #Type caches hash values, otherwise \c false.
90 static constexpr bool IsCachingHashes()
91 {
92 return THashCaching == lang::Caching::Enabled
93 || ( THashCaching == lang::Caching::Auto
94 && !std::is_arithmetic<typename TValueDescriptor::KeyType>::value );
95 }
96
97 /// The type stored in a hash table's bucket list.
98 using Type= std::conditional_t< IsCachingHashes(),
99 HTElementCached <typename TValueDescriptor::StoredType>,
101};
102
103//==================================================================================================
104/// Base struct of \alib{containers;HashTable} providing internals.
105/// \note
106/// The separation of the internals of class \b HashTable to this type in namespace \b detail
107/// has no benefit on compilation speed or other positive "technical" effect, nor is it a matter
108/// of software design.<br>
109/// A user of derived class \alib{containers;HashTable} finds all interface methods and types
110/// in one place, which is not cluttered by the documentation of the internals found here.
111/// Otherwise, the separation is exclusively supporting source code organization.
112///
113/// @see For a description of the template parameters and a general introduction to
114/// this module's hash table implementation, see the
115/// \ref alib_ns_containers_hashtable_referencedoc "reference documentation"
116/// of class \b HashTable.
117//==================================================================================================
118template< typename TAllocator,
119 typename TValueDescriptor,
120 typename THash,
121 typename TEqual,
122 lang::Caching THashCaching,
123 Recycling TRecycling >
125: RecyclingSelector<TRecycling>:: template Type< TAllocator,
126 typename HTElementSelector<TValueDescriptor, THashCaching>::Type >
127{
128 /// Our base type.
129 using base= typename RecyclingSelector<TRecycling>:: template Type< TAllocator,
131
132 /// Type definition publishing template parameter \p{T}.
133 using T = typename TValueDescriptor::StoredType;
134
135 /// Type definition publishing template parameter \p{TKey}.
136 using TKey = typename TValueDescriptor::KeyType;
137
138 /// Type definition publishing template parameter \p{TKey}.
139 using TMapped = typename TValueDescriptor::MappedType;
140
141
142 /// Determines whether hash codes are stored with the elements.
143 /// It is done in case the given template parameter \p{THashCashing} equals
144 /// \alib{lang;Caching;Caching::Enabled} or if it equals \alib{lang;Caching;Caching::Auto}
145 /// and the key type is an arithmetic type.
146 /// @return \c true if hash codes are stored for reuse, \c false if not.
149
150 /// The type stored in the bucket of class \b HashTable.
152
153
154 // ###############################################################################################
155 // ### Types and Constants
156 // ###############################################################################################
157
158 /// Type of a single linked node list.
159 using recyclerType= typename RecyclingSelector<TRecycling>:: template Type< TAllocator,
161
162 /// This type definition may be used to define an externally managed shared recycler,
163 /// which can be passed to the alternative constructor of this class when template
164 /// parameter \p{TRecycling} equals \alib{containers;Recycling;Shared}.
165 /// \see
166 /// Chapter \ref alib_contmono_containers_recycling_shared of the Programmer's Manual
167 /// for this \alibmod.
169 :: template HookType<TAllocator,
171
172
173 /// Type of a single linked node list.
175
176 /// Type of a node in the \b List.
178
179
180 // ###############################################################################################
181 // ### internal helpers
182 // ###############################################################################################
183
184 /// Either returns the cached hash code or calculates it.
185 /// @param elem The element to receive the hashcode for.
186 /// @return The hash code of the given element.
187 static size_t getHashCode(Element* elem)
188 {
189 if constexpr ( Element::CachedHashCodes )
190 return elem->getCached();
191 else
192 return THash{}( TValueDescriptor().Key( elem->value ) );
193 }
194
195 /// Returns either a recycled or newly allocated element.
196 /// @param hashCode The hashCode of the new element. Used only in cached case.
197 /// @return A pointer to the element created or recycled.
198 Element* allocElement( const size_t hashCode )
199 {
200 Element* elem= recyclerType::Get();
201 elem->fixHashCode( hashCode );
202 return elem;
203 }
204
205 // ###############################################################################################
206 // std::iterator_traits types.
207 // ###############################################################################################
208
209 //==============================================================================================
210 /// Templated implementation of \c std::iterator_traits.
211 /// Will be exposed by derived class's definitions \alib{containers::HashTable;Iterator} and
212 /// \alib{containers::HashTable;ConstIterator}.
213 ///
214 /// As the name of the class indicates, this iterator satisfies the C++ standard library concept
215 /// \https{ForwardIterator,en.cppreference.com/w/cpp/named_req/ForwardIterator}.
216 ///
217 /// @tparam TConstOrMutable A constant or mutable version of the parent's template type
218 /// \p{TMapped}.
219 //==============================================================================================
220 template<typename TConstOrMutable>
222 {
223 #if !DOXYGEN
224 friend struct HashTableBase;
225 friend class containers::HashTable<TAllocator, TValueDescriptor,THash,TEqual,THashCaching,TRecycling>;
226 #endif
227
228 /// Const or mutable version of HashTableBase.
229 using THashtable = std::conditional_t< !std::is_const_v< TConstOrMutable>,
231 const HashTableBase >;
232 using iterator_category = std::forward_iterator_tag; ///< Implementation of <c>std::iterator_traits</c>.
233 using value_type = TMapped ; ///< Implementation of <c>std::iterator_traits</c>.
234 using difference_type = integer ; ///< Implementation of <c>std::iterator_traits</c>.
235 using pointer = TConstOrMutable* ; ///< Implementation of <c>std::iterator_traits</c>.
236 using reference = TConstOrMutable& ; ///< Implementation of <c>std::iterator_traits</c>.
237
238 protected:
239 /// The pointer to the hash table.
241
242 /// The actual bucket index.
244
245 /// The pointer to the actual element.
247
248
249 /// Internal constructor. Searches the first element, starting with given bucket
250 /// number.
251 /// @param pTable Pointer to the hash table.
252 /// @param pBbucketIx The bucket index.
253 TIterator( THashtable* pTable, uinteger pBbucketIx )
254 : table(pTable)
255 {
256 while( pBbucketIx < pTable->bucketCount )
257 {
258 if( !pTable->buckets[pBbucketIx].isEmpty() )
259 {
260 bucketIdx= pBbucketIx;
261 element = pTable->buckets[pBbucketIx].first();
262 return;
263 }
264 ++pBbucketIx;
265 }
266 bucketIdx= pBbucketIx;
267 element = nullptr;
268 }
269
270 /// Internal constructor creating a specific iterator.
271 /// @param pTable Pointer to the hash table.
272 /// @param pBbucketIx The bucket index.
273 /// @param pElement Pointer to the current element.
274 TIterator( THashtable* pTable, uinteger pBbucketIx, Element* pElement)
275 : table ( pTable )
276 , bucketIdx( pBbucketIx )
277 , element ( pElement )
278 {}
279
280 /// Moves an iterator with a nulled element pointer to the next element.
281 void repair()
282 {
284 if( !table->buckets[bucketIdx].isEmpty() )
285 {
286 element= table->buckets[bucketIdx].first();
287 return;
288 }
289 }
290
291
292 public:
293 /// Default constructor. Keeps everything uninitialized.
294 TIterator() = default;
295
296 /// Copy constructor (default).
297 /// @param other The iterator to assign from.
298 TIterator( const TIterator& other) = default;
299
300
301 /// Copy assignment (default).
302 /// @param other The iterator to assign from.
303 /// @return A reference to this object.
304 TIterator& operator=( const TIterator& other ) = default;
305
306
307 /// Copy constructor accepting a mutable iterator.
308 /// Available only for the constant version of this iterator.
309 /// @tparam TMutable The type of this constructor's argument.
310 /// @param mutableIt Mutable iterator to copy from.
311 template<typename TMutable>
312 requires std::same_as<TMutable, TIterator<T>>
313 TIterator( const TMutable& mutableIt )
314 : table ( mutableIt.table )
315 , bucketIdx( mutableIt.bucketIdx )
316 , element ( mutableIt.element ) {}
317
318 //#################### To satisfy concept of InputIterator ####################
319
320 /// Prefix increment operator.
321 /// @return A reference to this object.
323 {
324 if(element->hasNext())
325 {
326 element= element->next();
327 return *this;
328 }
329
331 {
332 if( !table->buckets[bucketIdx].isEmpty() )
333 {
334 element= table->buckets[bucketIdx].first();
335 return *this;
336 }
337 }
338
339 element= nullptr;
340 return *this;
341 }
342
343 /// Postfix increment operator.
344 /// @return An iterator value that is not increased, yet.
346 {
347 auto result= TIterator( *this);
348 ++(*this);
349 return result;
350 }
351
352 /// Comparison operator.
353 /// @param other The iterator to compare ourselves to.
354 /// @return \c true if this and the given iterator are pointing to the same element,
355 /// \c false otherwise.
356 bool operator==( TIterator other) const
357 {
358 return element == other.element;
359 }
360
361 /// Comparison operator.
362 /// @param other The iterator to compare ourselves to.
363 /// @return \c true if this and given iterator are not equal, \c false otherwise.
364 bool operator!=( TIterator other) const
365 {
366 return !(*this == other);
367 }
368
369
370 // ############ access to templated members ############
371
372 /// Retrieves the stored object that this iterator references.
373 /// @return A reference to the stored object.
374 TConstOrMutable& operator*() const
375 {
376 ALIB_ASSERT_ERROR( element != nullptr, "MONOMEM/HASHTABLE", "Illegal iterator." )
377 return element->value;
378 }
379
380 /// Retrieves a pointer to the stored object that this iterator references.
381 /// @return A pointer to the stored object.
382 TConstOrMutable* operator->() const
383 {
384 ALIB_ASSERT_ERROR( element != nullptr, "MONOMEM/HASHTABLE", "Illegal iterator." )
385 return &element->value;
386 }
387
388 /// Retrieves the stored object that this iterator references.
389 /// @return A reference to the stored object.
390 TConstOrMutable& Value() const
391 {
392 ALIB_ASSERT_ERROR( element != nullptr, "MONOMEM/HASHTABLE", "Illegal iterator." )
393 return element->value;
394 }
395
396 /// Retrieves the key-portion of the stored object that this iterator references.
397 /// @return A reference to the key-portion of the stored object.
398 const TKey& Key() const
399 {
400 ALIB_ASSERT_ERROR( element != nullptr, "MONOMEM/HASHTABLE", "Illegal iterator." )
401 return TValueDescriptor().Key( element->value );
402 }
403
404 /// Retrieves the mapped-portion of the stored object that this iterator references.
405 /// This method is an alias to <c>operator*</c>
406 /// @return A reference to the mapped-portion of the stored object.
408 {
409 ALIB_ASSERT_ERROR( element != nullptr, "MONOMEM/HASHTABLE", "Illegal iterator." )
410 return TValueDescriptor().Mapped( element->value );
411 }
412
413 }; // class TIterator
414
415
416 //==============================================================================================
417 /// Templated implementation of \c std::iterator_traits.
418 /// Will be exposed by derived class's definitions
419 /// \alib{containers::HashTable;LocalIterator} and
420 /// \alib{containers::HashTable;ConstLocalIterator}.
421 ///
422 /// As the name of the class indicates, this iterator satisfies the C++ standard library concept
423 /// \https{ForwardIterator,en.cppreference.com/w/cpp/named_req/ForwardIterator}.
424 ///
425 /// @tparam TConstOrMutable A constant or mutable version of template parameter \p{T}.
426 //==============================================================================================
427 template<typename TConstOrMutable>
429 {
430 #if !DOXYGEN
431 friend struct HashTableBase;
432 friend class containers::HashTable<TAllocator,TValueDescriptor,THash,TEqual,THashCaching,TRecycling>;
433 #endif
434
435 using iterator_category = std::forward_iterator_tag; ///< Implementation of <c>std::iterator_traits</c>.
436 using value_type = TConstOrMutable ; ///< Implementation of <c>std::iterator_traits</c>.
437 using difference_type = integer ; ///< Implementation of <c>std::iterator_traits</c>.
438 using pointer = TConstOrMutable* ; ///< Implementation of <c>std::iterator_traits</c>.
439 using reference = TConstOrMutable& ; ///< Implementation of <c>std::iterator_traits</c>.
440
441 protected:
442 /// The pointer to the actual element.
444
445 /// The index of the bucket that this iterator works on.
447
448 public:
449 /// Default constructor.
452
453 /// Copy constructor (default).
454 /// @param other The iterator to assign from.
455 TLocalIterator( const TLocalIterator& other ) = default;
456
457 /// Copy constructor accepting a mutable iterator.
458 /// Available only for the constant version of this iterator.
459 /// @tparam TMutable The type of this constructor's argument.
460 /// @param mutableIt Mutable iterator to copy from.
461 template<typename TMutable>
462 requires std::same_as<TMutable, TLocalIterator<T>>
463 TLocalIterator( const TMutable& mutableIt )
464 : element ( mutableIt.element )
465 , bucketIdx( mutableIt.bucketIdx ) {}
466
467 /// Constructor.
468 /// @param pBucketIdx Index of the bucket this iterator works on.
469 /// @param pElement Pointer to current element.
470 explicit TLocalIterator( uinteger pBucketIdx, Element* pElement )
471 : element (pElement )
472 , bucketIdx(pBucketIdx)
473 {}
474
475 /// Copy assignment (default).
476 /// @param other The iterator to assign from.
477 /// @return A reference to this object.
478 TLocalIterator& operator=( const TLocalIterator& other) = default;
479
480 // ################### To satisfy concept of InputIterator ####################
481
482 /// Prefix increment operator.
483 /// @return A reference to this object.
485 {
486 ALIB_ASSERT_ERROR( element != nullptr, "MONOMEM/HASHTABLE", "Illegal iterator." )
487 element= element->next();
488 return *this;
489 }
490
491 /// Postfix increment operator.
492 /// @return An iterator value that is not increased, yet.
494 {
495 auto result= TLocalIterator( *this);
496 ++(*this);
497 return result;
498 }
499
500 /// Comparison operator.
501 /// @param other The iterator to compare ourselves to.
502 /// @return \c true if this and the given iterator are pointing to the same element,
503 /// \c false otherwise.
504 bool operator==( TLocalIterator other) const
505 {
506 return element == other.element
507 && bucketIdx == other.bucketIdx;
508 }
509
510 /// Comparison operator.
511 /// @param other The iterator to compare ourselves to.
512 /// @return \c true if this and given iterator are not equal, \c false otherwise.
513 bool operator!=( TLocalIterator other) const
514 {
515 return !(*this == other);
516 }
517
518 // ############ access to templated members ############
519
520 /// Retrieves the stored object that this iterator references.
521 /// @return A reference to the stored object.
522 TConstOrMutable& operator*() const
523 {
524 ALIB_ASSERT_ERROR( element != nullptr, "MONOMEM/HASHTABLE", "Illegal iterator." )
525 return element->value;
526 }
527
528 /// Retrieves a pointer to the stored object that this iterator references.
529 /// @return A pointer to the stored object.
530 TConstOrMutable* operator->() const
531 {
532 ALIB_ASSERT_ERROR( element != nullptr, "MONOMEM/HASHTABLE", "Illegal iterator." )
533 return &element->value;
534 }
535
536 /// Retrieves the stored object that this iterator references.
537 /// @return A reference to the stored object.
538 TConstOrMutable& Value() const
539 {
540 ALIB_ASSERT_ERROR( element != nullptr, "MONOMEM/HASHTABLE", "Illegal iterator." )
541 return element->value;
542 }
543
544 /// Retrieves the key-portion of the stored object that this iterator references.
545 /// @return A reference to the key-portion of the stored object.
546 const TKey& Key() const
547 {
548 ALIB_ASSERT_ERROR( element != nullptr, "MONOMEM/HASHTABLE", "Illegal iterator." )
549 return TValueDescriptor().Key( element->value );
550 }
551
552 /// Retrieves the stored object that this iterator references.<br>
553 /// This method is an alias to <c>operator*</c>
554 /// @return A reference to the mapped-portion of the stored object.
556 {
557 ALIB_ASSERT_ERROR( element != nullptr, "MONOMEM/HASHTABLE", "Illegal iterator." )
558 return TValueDescriptor().Mapped( element->value );
559 }
560 }; // class TLocalIterator
561
562
563 // ###############################################################################################
564 // Fields
565 // ###############################################################################################
566 /// The number of buckets managed by this tree.
568
569 /// The list of buckets.
571
572 /// The load factor that is set when the table is rehashed automatically.
574
575 /// The maximum quotient of #size and #bucketCount that triggers a rehash.
577
578 /// The number of elements stored.
580
581 /// Calculated once with rehash. Product of #maxLoadFactor and #bucketCount.
583
584
585 // ###############################################################################################
586 // ### mini helpers
587 // ###############################################################################################
588
589 /// Compares two elements. If cached mode, the hash code is compared before the keys.
590 /// @param lhs The first node to compare.
591 /// @param rhs The second node to compare.
592 /// @return The result of the comparison.
593 bool areEqual( Element* lhs, Element* rhs ) const
594 {
595 return ( !Element::CachedHashCodes || ( getHashCode(lhs) == getHashCode(rhs) ) )
596 && TEqual{}( TValueDescriptor().Key( lhs->value ),
597 TValueDescriptor().Key( rhs->value ) );
598 }
599
600 /// Compares a key and a node. If cached mode, the hash codes are compared before the
601 /// keys.
602 /// @param elem The element to compare.
603 /// @param key The key to compare.
604 /// @param keyHashCode The hash code of \p{key}.
605 /// @return The result of the comparison.
606 bool areEqual( Element* elem, const TKey& key, size_t keyHashCode ) const
607 {
608 return ( !Element::CachedHashCodes || ( keyHashCode == getHashCode(elem) ) )
609 && TEqual{}( TValueDescriptor().Key( elem->value ), key );
610 }
611
612 /// Searches the first element equal to \p{key} in bucket \p{bucketIdx}.
613 ///
614 /// @param bucketIdx The bucket number to search in (hash code divided by #bucketCount).
615 /// @param key The <em>key-portion</em> of the element to search.
616 /// @param keyHashCode The hash code of \p{key}.
617 /// @return A pointer to the element searched, respectively \c nullptr if not found.
618 Element* findElement( uinteger bucketIdx, const TKey& key, size_t keyHashCode ) const
619 {
620 Node* result= buckets[bucketIdx].first();
621 while( result)
622 {
623 if( areEqual( static_cast<Element*>(result), key, keyHashCode ) )
624 return static_cast<Element*>(result);
625
626 result= result->next();
627 }
628 return nullptr;
629 }
630
631 /// Searches the predecessor of the first element equal to \p{key} in bucket \p{bucketIdx}.
632 ///
633 /// @param bucketIdx The bucket number to search in (hash code divided by #bucketCount).
634 /// @param key The <em>key-portion</em> of the element to search.
635 /// @param keyHashCode The hash code of \p{key}.
636 /// @return A pointer to the element before the searched one, respectively \c nullptr if not
637 /// found.
638 Node* findElementBefore( uinteger bucketIdx, size_t keyHashCode, const TKey& key ) const
639 {
640 Node* result= &buckets[bucketIdx];
641
642 while( result->hasNext() && !areEqual( result->next(), key, keyHashCode ) )
643 result= result->next();
644
645 return result->hasNext() ? result : nullptr;
646 }
647
648 /// Inserts the given element into the bucket.
649 /// If an element of the same key exists, then the element is put in front of that element.
650 /// Otherwise it is added to the start of the bucket.
651 /// @param element The element to insert to its bucket.
652 /// @param hashCode The hash code of parameter \p{element}.
653 /// @return The bucket number that the element was inserted to.
654 uinteger insertInBucket( Element* element, const size_t hashCode )
655 {
656 auto bucketIdx= hashCode % bucketCount;
657 Node* previous= findElementBefore( bucketIdx, hashCode, TValueDescriptor().Key( element->value ) );
658 if( previous == nullptr )
659 previous= &buckets[bucketIdx];
660
661 previous->addBehind( element );
662 return bucketIdx;
663 }
664
665 /// Increases field #size and checks for a rehash.
666 ///
667 /// @param increase The amount to increase.
668 /// @param hashCode A hashCode that caller might want to have converted into a new
669 /// actual bucket index.
670 /// @return The bucket index of \p{hashCode}.
671 size_t increaseSize( integer increase, const size_t hashCode= 0 )
672 {
673 size+= increase;
674 if( size >=sizeLimitToRehash )
675 rehash( (std::max)( uinteger( float(size) / baseLoadFactor ), bucketCount + 1 ) );
676
677 return hashCode % bucketCount;
678 }
679
680 //==============================================================================================
681 /// Constructor.
682 /// @param pAllocator The allocator to use.
683 /// @param pBaseLoadFactor The base load factor.
684 /// @param pMaxLoadFactor The maximum load factor.
685 //==============================================================================================
686 HashTableBase( TAllocator& pAllocator,
687 float pBaseLoadFactor,
688 float pMaxLoadFactor )
689 : recyclerType ( pAllocator )
690 , baseLoadFactor( pBaseLoadFactor )
691 , maxLoadFactor ( pMaxLoadFactor )
692 , size ( 0 )
693 {
694 buckets = reinterpret_cast<FwdList*>(&detail::DUMMY_BUCKET);
695 bucketCount = 1;
696 size = 0;
698 }
699
700 //==============================================================================================
701 /// Constructor using \alib{lang;HeapAllocator}.
702 /// @param pBaseLoadFactor The base load factor.
703 /// @param pMaxLoadFactor The maximum load factor.
704 //==============================================================================================
705 HashTableBase( float pBaseLoadFactor,
706 float pMaxLoadFactor )
707 : baseLoadFactor( pBaseLoadFactor )
708 , maxLoadFactor ( pMaxLoadFactor )
709 , size ( 0 )
710 {
711 buckets = reinterpret_cast<FwdList*>(&detail::DUMMY_BUCKET);
712 bucketCount = 1;
713 size = 0;
715 }
716
717 //==============================================================================================
718 /// Constructor taking a shared recycler.
719 /// @param pSharedRecycler The shared recycler hook.
720 /// @param pBaseLoadFactor The base load factor.
721 /// @param pMaxLoadFactor The maximum load factor.
722 /// @tparam TSharedRecycler Used to select this constructor. Deduced by the compiler.
723 //==============================================================================================
724 template<typename TSharedRecycler= SharedRecyclerType>
725 requires (!std::same_as<TSharedRecycler , void>)
726 HashTableBase( TSharedRecycler& pSharedRecycler,
727 float pBaseLoadFactor = 1.0,
728 float pMaxLoadFactor = 2.0 )
729 : recyclerType ( pSharedRecycler )
730 , baseLoadFactor( pBaseLoadFactor )
731 , maxLoadFactor ( pMaxLoadFactor )
732 , size ( 0 )
733 {
734 buckets = reinterpret_cast<FwdList*>(&detail::DUMMY_BUCKET);
735 bucketCount = 1;
736 size = 0;
738 }
739
740 //==============================================================================================
741 /// Destructor. Destructs all elements in this object.
742 /// Deletes recyclables, buckets and bucket array.
743 //==============================================================================================
745 {
746 if ( buckets == reinterpret_cast<FwdList*>( &detail::DUMMY_BUCKET ) )
747 return;
748
749 // destruct entry data and delete entry objects
750 for( uinteger bucketIdx= 0 ; bucketIdx < bucketCount ; ++bucketIdx )
751 {
752 Element* first= buckets[bucketIdx].first();
753 if ( first != nullptr )
754 recyclerType::DisposeList(first);
755 }
756
757 // free bucket array
758 recyclerType::template DisposeChunk<FwdList>(buckets, bucketCount );
759 }
760
761 // ###############################################################################################
762 // ### method implementations
763 // ###############################################################################################
764
765 //==============================================================================================
766 /// Destructs and removes all entries from this hash table.
767 //==============================================================================================
768 void clear()
769 {
770 if( size == 0 )
771 return;
772
773 // destruct and recycle entries
774 for( uinteger bucketIdx= 0 ; bucketIdx < bucketCount ; ++bucketIdx )
775 if ( buckets[bucketIdx].first() )
776 {
777 recyclerType::RecycleList( buckets[bucketIdx].first() );
778 buckets[bucketIdx].reset();
779 }
780
781 size= 0;
782 }
783
784
785 //==============================================================================================
786 /// Changes the maximum load factor value and invokes #rehash providing the actual bucket
787 /// count as the minimum bucket count that is to be chosen.
788 /// @param pMaxLoadFactor The maximum load factor used to determine the need of re-hashing.
789 //==============================================================================================
790 void setMaxLoadFactor( float pMaxLoadFactor )
791 {
792 maxLoadFactor= pMaxLoadFactor;
793 if( bucketCount > 1 )
795 }
796
797 //==============================================================================================
798 /// Changes the number of buckets to be at least the higher value of
799 /// a) the given \p{newMinBucketCount}, and<br>
800 /// b) the quotient of the current size and the maximum load factor.
801 ///
802 /// The result of the above, is increased to the next higher prime number.
803 /// Rehash is only performed if bucket size increases. It never is decreased.
804 ///
805 /// @param newMinBucketCount The minimum new bucket count requested.
806 //==============================================================================================
807 void rehash( uinteger newMinBucketCount )
808 {
809 // smaller than before?
810 if( newMinBucketCount <= bucketCount )
811 return;
812
813 const auto oldBucketCount= bucketCount;
814
815 // adjust requested bucket count to the maximum load factor
816 newMinBucketCount= (std::max)( newMinBucketCount, uinteger(float(size) / maxLoadFactor) );
817
818 // adjust requested bucket count to next higher prime value
819 {
820 int idx= 0;
821 while( detail::PRIME_NUMBERS[idx] < newMinBucketCount )
822 ++idx;
824 }
825
826 ALIB_ASSERT_ERROR( bucketCount > oldBucketCount, "MONOMEM/HASHTABLE",
827 "Internal error: Rehashing to equal or smaller bucket count." )
828
829 // store new rehash trigger
831
832 // collect elements
833 FwdList elements;
834 for( uinteger bucketIdx= 0 ; bucketIdx < oldBucketCount ; ++bucketIdx )
835 {
836 Element* first= buckets[bucketIdx].first();
837 if( first != nullptr )
838 elements.pushFront( first, buckets[bucketIdx].findLast() );
839 }
840
841
842 // create a new data array
843 FwdList* oldData = buckets;
844
845 buckets= base::AI().template NewArray<FwdList>(bucketCount);
846
847 // re-insert objects
848 Element* actual= elements.first();
849 while( actual != nullptr )
850 {
851 Element* next= actual->next();
852 insertInBucket( actual, getHashCode(actual) );
853 actual= next;
854 }
855
856 // recycle old array and data (make future nodes elements out of it)
857 // But this must only be done with MonoAllocator and if ALIB_DEBUG_MEMORY is not set.
858 // (This is ensured by 'TAllocator::allowsMemSplit()')
859 if ( oldData != reinterpret_cast<FwdList*>( &detail::DUMMY_BUCKET ) )
860 recyclerType::template RecycleChunk<FwdList>( oldData, oldBucketCount );
861 }
862
863 //==============================================================================================
864 /// Searches the first and last element stored according to given \p{key}.
865 /// Returns a pare of iterators that define a range containing all elements with key
866 /// \p{key} of the container.<br>
867 /// Parameter \p{resultStart} is set to the first element of the matching range and
868 /// parameter \p{resultEnd} is set to point past the last element of the range.
869 ///
870 /// If no element with key \p{key} is found, both iterators are set to \b end.
871 ///
872 /// @param key The <em>key-portion</em> of the elements to find.
873 /// @return A pair of iterators defining the range of elements with key \p{key}.
874 //==============================================================================================
875 std::pair<TIterator<T>,TIterator<T>> findRange( const TKey& key )
876 {
877 const auto hashCode= THash{}(key);
878 auto bucketIdx= hashCode % bucketCount;
879 Element* element= findElement( bucketIdx, key, hashCode );
880 if( element == nullptr )
881 return std::make_pair( TIterator<T>( this, bucketCount, nullptr ),
882 TIterator<T>( this, bucketCount, nullptr ) );
883
884 auto result= std::make_pair( TIterator<T>( this, bucketIdx, element ),
885 TIterator<T>( this, bucketIdx, element ) );
886 for(;;)
887 {
888 ++result.second;
889 if( result.second.element == nullptr
890 || !areEqual( result.second.element, key, hashCode ) )
891 return result;
892 }
893
894 }
895
896 //==============================================================================================
897 /// Searches (a first) element with the given key.
898 /// If not found, an invalid iterator to the bucket is returned with a nulled element pointer.
899 /// Before this counter #size is increased and, if a load limit is reached, a re-hash is
900 /// performed.
901 ///
902 /// If otherwise an element was found, its valid iterator is returned.
903 ///
904 /// Note: Used by \alib{containers;HashMap::EmplaceIfNotExistent}.
905 ///
906 /// @param key The key to the (first) element to find.
907 /// @param hashCode The hash code of parameter \p{key}.
908 /// @return A pair of an iterator referring to the found or inserted element and a boolean
909 /// that is \c true if the insertion took place and \c false nothing was changed.
910 //==============================================================================================
911 std::pair<TIterator<T>, bool> insertIfNotExists( const TKey& key, size_t hashCode )
912 {
913 auto bucketIdx= hashCode % bucketCount;
914 Element* element = findElement( bucketIdx, key, hashCode );
915 if (element != nullptr )
916 return std::make_pair(TIterator<T>( this, bucketIdx, element ), false);
917
918 bucketIdx= increaseSize( 1, hashCode );
919
920 Element* newElement= allocElement( hashCode );
921 buckets[bucketIdx].pushFront( newElement );
922 return std::make_pair(TIterator<T>( this, bucketIdx, newElement ) , true);
923 }
924
925 //==============================================================================================
926 /// Inserts the topmost recyclable element if no element with the same key-portion of its value
927 /// exists.
928 ///
929 /// @param key Pointer to the key to search elements for deletion.
930 /// @param hashCode The hash code of parameter \p{key}.
931 /// @return A pair containing an iterator referring to the element added.
932 /// The bool component is \c true if the insertion took place and \c false if a new
933 /// element was created.
934 //==============================================================================================
935 std::pair<TIterator<T>, bool> insertOrGet( const TKey& key, size_t hashCode )
936 {
937 // find (first) element with same key in bucket
938 auto bucketIdx= hashCode % bucketCount;
939 auto* elem= findElement( bucketIdx, key, hashCode );
940 if( elem != nullptr )
941 return std::make_pair( TIterator<T>( this, bucketIdx, elem ), false);
942
943 // create new element
944 bucketIdx= increaseSize( 1, hashCode );
945 Element* newElem= allocElement( hashCode );
946 buckets[bucketIdx].pushFront( newElem );
947 return std::make_pair(TIterator<T>( this, bucketIdx, newElem ), true);
948 }
949
950}; // HashTableBase
951
952} // namespace [alib::containers::detail]
TIterator()=default
Default constructor. Keeps everything uninitialized.
TIterator & operator=(const TIterator &other)=default
std::forward_iterator_tag iterator_category
Implementation of std::iterator_traits.
TMapped value_type
Implementation of std::iterator_traits.
TIterator(THashtable *pTable, uinteger pBbucketIx)
std::conditional_t< !std::is_const_v< TConstOrMutable >, HashTableBase, const HashTableBase > THashtable
Const or mutable version of HashTableBase.
TIterator(const TIterator &other)=default
TConstOrMutable * pointer
Implementation of std::iterator_traits.
TIterator(THashtable *pTable, uinteger pBbucketIx, Element *pElement)
THashtable * table
The pointer to the hash table.
Element * element
The pointer to the actual element.
void repair()
Moves an iterator with a nulled element pointer to the next element.
integer difference_type
Implementation of std::iterator_traits.
TConstOrMutable & reference
Implementation of std::iterator_traits.
TConstOrMutable value_type
Implementation of std::iterator_traits.
integer difference_type
Implementation of std::iterator_traits.
TLocalIterator & operator=(const TLocalIterator &other)=default
TLocalIterator(const TLocalIterator &other)=default
Element * element
The pointer to the actual element.
TConstOrMutable & reference
Implementation of std::iterator_traits.
uinteger bucketIdx
The index of the bucket that this iterator works on.
std::forward_iterator_tag iterator_category
Implementation of std::iterator_traits.
TLocalIterator(uinteger pBucketIdx, Element *pElement)
TConstOrMutable * pointer
Implementation of std::iterator_traits.
#define ALIB_DLL
Definition alib.inl:496
#define ALIB_EXPORT
Definition alib.inl:488
#define ALIB_ASSERT_ERROR(cond, domain,...)
Definition alib.inl:1049
static constexpr int PRIME_TABLE_SIZE
The size of the static table of prime numbers. Depends on the platform.
Detail namespace of module ALib Containers.
ALIB_DLL const uinteger PRIME_NUMBERS[PRIME_TABLE_SIZE]
ALIB_DLL void * DUMMY_BUCKET
A dummy bucket used for nulled hash tables to avoid otherwise necessary checks.
Caching
Denotes if a cache mechanism is enabled or disabled.
@ Enabled
Caching is enabled.
@ Auto
Auto/default mode.
containers::HashTable< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling > HashTable
Type alias in namespace alib. See type definition alib::containers::HashSet.
lang::integer integer
Type alias in namespace alib.
Definition integers.inl:149
lang::uinteger uinteger
Type alias in namespace alib.
Definition integers.inl:152
TStored value
The custom data stored in nodes of this table.
static constexpr bool CachedHashCodes
Denotes that hash codes are cached.
std::conditional_t< IsCachingHashes(), HTElementCached< typename TValueDescriptor::StoredType >, HTElementUncached< typename TValueDescriptor::StoredType > > Type
The type stored in a hash table's bucket list.
TStored value
The custom data stored in nodes of this table.
static constexpr bool CachedHashCodes
Denotes that hash codes are not cached.
float maxLoadFactor
The maximum quotient of size and bucketCount that triggers a rehash.
lang::SidiNodeBase< Element > Node
Type of a node in the List.
typename TValueDescriptor::KeyType TKey
Type definition publishing template parameter TKey.
void clear()
Destructs and removes all entries from this hash table.
void rehash(uinteger newMinBucketCount)
Element * allocElement(const size_t hashCode)
lang::SidiListHook< Element > FwdList
Type of a single linked node list.
bool areEqual(Element *lhs, Element *rhs) const
static size_t getHashCode(Element *elem)
typename HTElementSelector< TValueDescriptor, THashCaching >::Type Element
The type stored in the bucket of class HashTable.
uinteger insertInBucket(Element *element, const size_t hashCode)
integer size
The number of elements stored.
uinteger bucketCount
The number of buckets managed by this tree.
typename TValueDescriptor::MappedType TMapped
Type definition publishing template parameter TKey.
typename TValueDescriptor::StoredType T
Type definition publishing template parameter T.
void setMaxLoadFactor(float pMaxLoadFactor)
typename RecyclingSelector< TRecycling >::template Type< TAllocator, typename HTElementSelector< TValueDescriptor, THashCaching >::Type > base
Our base type.
HashTableBase(float pBaseLoadFactor, float pMaxLoadFactor)
float baseLoadFactor
The load factor that is set when the table is rehashed automatically.
std::pair< TIterator< T >, bool > insertOrGet(const TKey &key, size_t hashCode)
integer sizeLimitToRehash
Calculated once with rehash. Product of maxLoadFactor and bucketCount.
typename detail::RecyclingSelector< TRecycling > ::template HookType< TAllocator, typename HTElementSelector< TValueDescriptor, THashCaching >::Type > SharedRecyclerType
HashTableBase(TAllocator &pAllocator, float pBaseLoadFactor, float pMaxLoadFactor)
Node * findElementBefore(uinteger bucketIdx, size_t keyHashCode, const TKey &key) const
Element * findElement(uinteger bucketIdx, const TKey &key, size_t keyHashCode) const
typename RecyclingSelector< TRecycling >::template Type< TAllocator, typename HTElementSelector< TValueDescriptor, THashCaching >::Type > recyclerType
Type of a single linked node list.
HashTableBase(TSharedRecycler &pSharedRecycler, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0)
size_t increaseSize(integer increase, const size_t hashCode=0)
FwdList * buckets
The list of buckets.
std::pair< TIterator< T >, bool > insertIfNotExists(const TKey &key, size_t hashCode)
std::pair< TIterator< T >, TIterator< T > > findRange(const TKey &key)
bool areEqual(Element *elem, const TKey &key, size_t keyHashCode) const
TElement * first() const noexcept
Definition sidilist.inl:223
void pushFront(TElement *elem) noexcept
Definition sidilist.inl:227
TElement * addBehind(TElement *elem) noexcept
Definition sidilist.inl:144
void next(SidiNodeBase *p)
Definition sidilist.inl:95