template class tsl::detail_robin_hash::bucket_entry

Overview

Each bucket entry has:

• A value of type ValueType.

• An integer to store how far the value of the bucket, if any, is from its ideal bucket (ex: if the current bucket 5 has the value ‘foo’ and hash(‘foo) % nb_buckets == 3, dist_from_ideal_bucket() ` will return 2 as the current value of the bucket is two buckets away from its ideal bucket) If there is no value in the bucket (i.e. empty() is true) dist_from_ideal_bucket() will be < 0.

• A marker which tells us if the bucket is the last bucket of the bucket array (useful for the iterator of the hash table).

• If StoreHash is true, 32 bits of the hash of the value, if any, are also stored in the bucket. If the size of the hash is more than 32 bits, it is truncated. We don’t store the full hash as storing the hash is a potential opportunity to use the unused space due to the alignment of the bucket_entry structure. We can thus potentially store the hash without any extra space (which would not be possible with 64 bits of the hash).

#include <robin_hash.h>

template <typename ValueType, bool StoreHash>
class bucket_entry: public tsl::detail_robin_hash::bucket_entry_hash
{
public:
    // typedefs

    typedef ValueType value_type;
    typedef std::int16_t distance_type;

    // fields

    static const distance_type EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1;
    static const distance_type DIST_FROM_IDEAL_BUCKET_LIMIT = 8192;

    // construction

    bucket_entry();
    bucket_entry(bool last_bucket);
    bucket_entry(const bucket_entry& other);
    bucket_entry(bucket_entry&& other);

    // methods

    bucket_entry& operator = (const bucket_entry& other);
    bucket_entry& operator = (bucket_entry&&);
    void clear();
    bool empty() const;
    value_type& value();
    const value_type& value() const;
    distance_type dist_from_ideal_bucket() const;
    bool last_bucket() const;
    void set_as_last_bucket();

    template <typename... Args>
    void set_value_of_empty_bucket(
        distance_type dist_from_ideal_bucket,
        truncated_hash_type hash,
        Args&&... value_type_args
        );

    void swap_with_value_in_bucket(
        distance_type& dist_from_ideal_bucket,
        truncated_hash_type& hash,
        value_type& value
        );

    static truncated_hash_type truncate_hash(std::size_t hash);
};

Inherited Members

public:
    // methods

    bool bucket_hash_equal(std::size_t) const;
    truncated_hash_type truncated_hash() const;

Construction

bucket_entry(bucket_entry&& other)

Never really used, but still necessary as we must call resize on an empty std::vector<bucket_entry>. and we need to support move-only types. See robin_hash constructor for details.