template class tsl::rh::power_of_two_growth_policy

Overview

Grow the hash table by a factor of GrowthFactor keeping the bucket count to a power of two. It allows the table to use a mask operation instead of a modulo operation to map a hash to a bucket.

GrowthFactor must be a power of two >= 2.

#include <robin_growth_policy.h>

template <std::size_t GrowthFactor>
class power_of_two_growth_policy
{
public:
    // construction

    power_of_two_growth_policy(std::size_t& min_bucket_count_in_out);

    // methods

    std::size_t bucket_for_hash(std::size_t hash) const;
    std::size_t next_bucket_count() const;
    std::size_t max_bucket_count() const;
    void clear();
};

Construction

power_of_two_growth_policy(std::size_t& min_bucket_count_in_out)

Called on the hash table creation and on rehash. The number of buckets for the table is passed in parameter. This number is a minimum, the policy may update this value with a higher value if needed (but not lower).

If 0 is given, min_bucket_count_in_out must still be 0 after the policy creation and bucket_for_hash must always return 0 in this case.

Methods

std::size_t bucket_for_hash(std::size_t hash) const

Return the bucket [0, bucket_count()) to which the hash belongs. If bucket_count() is 0, it must always return 0.

std::size_t next_bucket_count() const

Return the number of buckets that should be used on next growth.

std::size_t max_bucket_count() const

Return the maximum number of buckets supported by the policy.

void clear()

Reset the growth policy as if it was created with a bucket count of 0. After a clear, the policy must always return 0 when bucket_for_hash is called.