FeldmanHashMap traits More...

#include <cds/container/details/feldman_hashmap_base.h>

Public Types
typedef opt::none	hash
	Hash functor, default is `opt::none`. More...

typedef cds::opt::none	hash_splitter
	Hash splitter. More...

typedef cds::opt::none	compare
	Hash comparing functor. More...

typedef cds::opt::none	less
	Specifies binary predicate used for hash compare. More...

typedef cds::atomicity::item_counter	item_counter
	Item counter. More...

typedef CDS_DEFAULT_ALLOCATOR	allocator
	Item allocator. More...

typedef CDS_DEFAULT_ALLOCATOR	node_allocator
	Array node allocator. More...

typedef cds::opt::v::relaxed_ordering	memory_model
	C++ memory ordering model. More...

typedef cds::backoff::Default	back_off
	Back-off strategy.

typedef empty_stat	stat
	Internal statistics. More...

typedef cds::opt::v::rcu_throw_deadlock	rcu_check_deadlock
	RCU deadlock checking policy (only for RCU-based FeldmanHashMap) More...

Static Public Attributes
static constexpr size_t const	hash_size = 0
	The size of hash value in bytes. More...

Detailed Description

FeldmanHashMap traits

Member Typedef Documentation

◆ allocator

typedef CDS_DEFAULT_ALLOCATOR cds::container::feldman_hashmap::traits::allocator

Item allocator.

Default is CDS_DEFAULT_ALLOCATOR

◆ compare

typedef cds::opt::none cds::container::feldman_hashmap::traits::compare

Hash comparing functor.

No default functor is provided. If the option is not specified, the less option is used.

◆ hash

typedef opt::none cds::container::feldman_hashmap::traits::hash

Hash functor, default is opt::none.

FeldmanHashMap may use any hash functor converting a key to fixed-sized bit-string, for example, SHA1, SHA2, MurmurHash, CityHash or its successor FarmHash.

If you use a fixed-sized key you can use it directly instead of a hash. In such case traits::hash should be specified as opt::none. However, if you want to use the hash values or if your key type is not fixed-sized you must specify a proper hash functor in your traits. For example: fixed-sized key - IP4 address map

// Key - IP address
struct ip4_address {
    uint8_t ip[4];
};
// IP compare
struct ip4_cmp {
    int operator()( ip4_address const& lhs, ip4_address const& rhs ) const
    {
        return memcmp( &lhs, &rhs, sizeof(lhs));
    }
};
// Value - statistics for the IP address
struct statistics {
    // ...
};
// Traits
// Key type (ip4_addr) is fixed-sized so we may use the map without any hash functor
struct ip4_map_traits: public cds::container::multilevl_hashmap::traits
{
    typedef ip4_cmp  compare;
};
// IP4 address - statistics map
typedef cds::container::FeldmanHashMap< cds::gc::HP, ip4_address, statistics, ip4_map_traits > ip4_map;

variable-size key requires a hash functor: URL map

// Value - statistics for the URL
struct statistics {
    // ...
};
// Traits
// Key type (std::string) is variable-sized so we must provide a hash functor in our traits
// We do not specify any comparing predicate (less or compare) so <tt> std::less<std::string> </tt> will be used by default
struct url_map_traits: public cds::container::multilevl_hashmap::traits
{
    typedef std::hash<std::string> hash;
};
// URL statistics map
typedef cds::container::FeldmanHashMap< cds::gc::HP, std::string, statistics, url_map_traits > url_map;

◆ hash_splitter

typedef cds::opt::none cds::container::feldman_hashmap::traits::hash_splitter

Hash splitter.

This trait specifies hash bit-string splitter algorithm. By default, cds::algo::number_splitter is used if HashType is a number, cds::algo::split_bitstring otherwise.

◆ item_counter

typedef cds::atomicity::item_counter cds::container::feldman_hashmap::traits::item_counter

Item counter.

The item counting is an important part of FeldmanHashSet algorithm: the empty() member function depends on correct item counting. Therefore, atomicity::empty_item_counter is not allowed as a type of the option.

Default is atomicity::item_counter. To avoid false sharing you can aldo use atomicity::cache_friendly_item_counter

◆ less

typedef cds::opt::none cds::container::feldman_hashmap::traits::less

Specifies binary predicate used for hash compare.

If less and compare are not specified, memcmp() -like bit-wise hash comparator is used because the hash value is treated as fixed-sized bit-string.

◆ memory_model

typedef cds::opt::v::relaxed_ordering cds::container::feldman_hashmap::traits::memory_model

C++ memory ordering model.

Can be opt::v::relaxed_ordering (relaxed memory model, the default) or opt::v::sequential_consistent (sequentially consisnent memory model).

◆ node_allocator

typedef CDS_DEFAULT_ALLOCATOR cds::container::feldman_hashmap::traits::node_allocator

Array node allocator.

Allocator for array nodes. The allocator is used for creating headNode and arrayNode when the set grows. Default is CDS_DEFAULT_ALLOCATOR

◆ rcu_check_deadlock

typedef cds::opt::v::rcu_throw_deadlock cds::container::feldman_hashmap::traits::rcu_check_deadlock

RCU deadlock checking policy (only for RCU-based FeldmanHashMap)

List of available policy see opt::rcu_check_deadlock

◆ stat

typedef empty_stat cds::container::feldman_hashmap::traits::stat

Internal statistics.

By default, internal statistics is disabled (feldman_hashset::empty_stat). Use feldman_hashset::stat to enable it.

Field Documentation

◆ hash_size

constexpr size_t const cds::container::feldman_hashmap::traits::hash_size = 0

static

The size of hash value in bytes.

By default, the size of hash value is sizeof( hash_type ) where hash_type is type of hash() result or sizeof( key ) if you use fixed-sized key.

Sometimes that size is wrong, for example, for that 6-byte key:

struct key_type {
    uint32_t    key;
    uint16_t    subkey;
};
static_assert( sizeof( key_type ) == 6, "Key type size mismatch" );

Here sizeof( key_type ) == 8 so static_assert will be thrown.

For that case you can specify hash_size explicitly.

Value 0 means auto-calculated sizeof( key_type ).

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

cds/container/details/feldman_hashmap_base.h

Public Types

Static Public Attributes