9#if ALIB_SIZEOF_INTEGER == 4
11#elif ALIB_SIZEOF_INTEGER == 8
15 #error "Unknown size of integer"
20 template<
typename TAllocator,
21 typename TValueDescriptor,
40template<
typename TStored>
63template<
typename TStored>
86template<
typename TValueDescriptor, lang::Caching THashCaching>
94 && !std::is_arithmetic<typename TValueDescriptor::KeyType>::value );
99 HTElementCached <typename TValueDescriptor::StoredType>,
118template<
typename TAllocator,
119 typename TValueDescriptor,
126 typename HTElementSelector<TValueDescriptor, THashCaching>::Type >
133 using T =
typename TValueDescriptor::StoredType;
136 using TKey =
typename TValueDescriptor::KeyType;
139 using TMapped =
typename TValueDescriptor::MappedType;
169 :: template HookType<TAllocator,
189 if constexpr ( Element::CachedHashCodes )
190 return elem->getCached();
192 return THash{}( TValueDescriptor().Key( elem->value ) );
200 Element* elem= recyclerType::Get();
201 elem->fixHashCode( hashCode );
220 template<
typename TConstOrMutable>
225 friend class containers::HashTable<TAllocator, TValueDescriptor,THash,TEqual,THashCaching,TRecycling>;
229 using THashtable = std::conditional_t< !std::is_const_v< TConstOrMutable>,
258 if( !pTable->buckets[pBbucketIx].isEmpty() )
261 element = pTable->buckets[pBbucketIx].first();
311 template<
typename TMutable>
312 requires std::same_as<TMutable, TIterator<T>>
366 return !(*
this == other);
401 return TValueDescriptor().Key(
element->value );
410 return TValueDescriptor().Mapped(
element->value );
427 template<
typename TConstOrMutable>
432 friend class containers::HashTable<TAllocator,TValueDescriptor,THash,TEqual,THashCaching,TRecycling>;
461 template<
typename TMutable>
462 requires std::same_as<TMutable, TLocalIterator<T>>
515 return !(*
this == other);
549 return TValueDescriptor().Key(
element->value );
558 return TValueDescriptor().Mapped(
element->value );
596 && TEqual{}( TValueDescriptor().Key( lhs->value ),
597 TValueDescriptor().Key( rhs->value ) );
608 return ( !Element::CachedHashCodes || ( keyHashCode ==
getHashCode(elem) ) )
609 && TEqual{}( TValueDescriptor().Key( elem->value ), key );
624 return static_cast<Element*
>(result);
626 result= result->
next();
643 result= result->
next();
645 return result->
hasNext() ? result :
nullptr;
658 if( previous ==
nullptr )
687 float pBaseLoadFactor,
688 float pMaxLoadFactor )
706 float pMaxLoadFactor )
724 template<
typename TSharedRecycler= SharedRecyclerType>
725 requires (!std::same_as<TSharedRecycler , void>)
727 float pBaseLoadFactor = 1.0,
728 float pMaxLoadFactor = 2.0 )
753 if ( first !=
nullptr )
754 recyclerType::DisposeList(first);
775 if (
buckets[bucketIdx].first() )
777 recyclerType::RecycleList(
buckets[bucketIdx].first() );
827 "Internal error: Rehashing to equal or smaller bucket count." )
834 for(
uinteger bucketIdx= 0 ; bucketIdx < oldBucketCount ; ++bucketIdx )
837 if( first !=
nullptr )
849 while( actual !=
nullptr )
860 recyclerType::template RecycleChunk<FwdList>( oldData, oldBucketCount );
877 const auto hashCode= THash{}(key);
880 if( element ==
nullptr )
884 auto result= std::make_pair(
TIterator<T>(
this, bucketIdx, element ),
889 if( result.second.element ==
nullptr
890 || !
areEqual( result.second.element, key, hashCode ) )
915 if (element !=
nullptr )
916 return std::make_pair(
TIterator<T>(
this, bucketIdx, element ),
false);
921 buckets[bucketIdx].pushFront( newElement );
922 return std::make_pair(
TIterator<T>(
this, bucketIdx, newElement ) ,
true);
939 auto* elem=
findElement( bucketIdx, key, hashCode );
940 if( elem !=
nullptr )
941 return std::make_pair(
TIterator<T>(
this, bucketIdx, elem ),
false);
946 buckets[bucketIdx].pushFront( newElem );
947 return std::make_pair(
TIterator<T>(
this, bucketIdx, newElem ),
true);
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)
TConstOrMutable * operator->() const
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.
TConstOrMutable & Value() const
uinteger bucketIdx
The actual bucket index.
TIterator(THashtable *pTable, uinteger pBbucketIx, Element *pElement)
bool operator!=(TIterator other) const
TIterator(const TMutable &mutableIt)
TConstOrMutable & operator*() const
bool operator==(TIterator other) const
THashtable * table
The pointer to the hash table.
Element * element
The pointer to the actual element.
TIterator operator++(int)
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.
TConstOrMutable & operator*() const
integer difference_type
Implementation of std::iterator_traits.
TLocalIterator & operator++()
TLocalIterator & operator=(const TLocalIterator &other)=default
TLocalIterator operator++(int)
TLocalIterator(const TLocalIterator &other)=default
TConstOrMutable & Value() const
TConstOrMutable * operator->() const
Element * element
The pointer to the actual element.
bool operator==(TLocalIterator other) const
TConstOrMutable & reference
Implementation of std::iterator_traits.
bool operator!=(TLocalIterator other) const
TLocalIterator()
Default constructor.
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)
TLocalIterator(const TMutable &mutableIt)
TConstOrMutable * pointer
Implementation of std::iterator_traits.
#define ALIB_ASSERT_ERROR(cond, domain,...)
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.
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.
lang::uinteger uinteger
Type alias in namespace alib.
TStored value
The custom data stored in nodes of this table.
size_t hashCode
The cached hash code.
void fixHashCode(size_t pHashCode)
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.
static constexpr bool IsCachingHashes()
TStored value
The custom data stored in nodes of this table.
static constexpr bool CachedHashCodes
Denotes that hash codes are not cached.
void fixHashCode(size_t pHashCode)
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.
static constexpr bool IsCachingHashes()
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
void pushFront(TElement *elem) noexcept
TElement * addBehind(TElement *elem) noexcept
void next(SidiNodeBase *p)