#include <robin_growth_policy.h>

Public Member Functions
std::size_t	bucket_for_hash (std::size_t hash) const noexcept

void	clear () noexcept

std::size_t	max_bucket_count () const

std::size_t	next_bucket_count () const

	prime_growth_policy (std::size_t &min_bucket_count_in_out)

Private Attributes
unsigned int	m_iprime

Detailed Description

Grow the hash table by using prime numbers as bucket count. Slower than tsl::rh::power_of_two_growth_policy in general but will probably distribute the values around better in the buckets with a poor hash function.

To allow the compiler to optimize the modulo operation, a lookup table is used with constant primes numbers.

With a switch the code would look like:

switch(iprime) { // iprime is the current prime of the hash table
    case 0: hash % 5ul;
            break;
    case 1: hash % 17ul;
            break;
    case 2: hash % 29ul;
            break;
    ...
}

Due to the constant variable in the modulo the compiler is able to optimize the operation by a series of multiplications, substractions and shifts.

The 'hash % 5' could become something like 'hash - (hash * 0xCCCCCCCD) >> 34)

5' in a 64 bits environment.

Definition at line 369 of file robin_growth_policy.h.

Constructor & Destructor Documentation

◆ prime_growth_policy()

tsl::rh::prime_growth_policy::prime_growth_policy ( std::size_t & min_bucket_count_in_out )

inlineexplicit

Definition at line 371 of file robin_growth_policy.h.

Member Function Documentation

◆ bucket_for_hash()

std::size_t tsl::rh::prime_growth_policy::bucket_for_hash ( std::size_t hash ) const

inlinenoexcept

Definition at line 388 of file robin_growth_policy.h.

◆ clear()

void tsl::rh::prime_growth_policy::clear ( )

inlinenoexcept

Definition at line 403 of file robin_growth_policy.h.

◆ max_bucket_count()

std::size_t tsl::rh::prime_growth_policy::max_bucket_count ( ) const

inline

Definition at line 401 of file robin_growth_policy.h.

◆ next_bucket_count()

std::size_t tsl::rh::prime_growth_policy::next_bucket_count ( ) const

inline

Definition at line 392 of file robin_growth_policy.h.

Member Data Documentation

◆ m_iprime

unsigned int tsl::rh::prime_growth_policy::m_iprime

private

Definition at line 406 of file robin_growth_policy.h.

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

robin_growth_policy.h

Public Member Functions

Private Attributes