xenium::vyukov_hash_map< Key, Value, Policies > Struct Template Reference

A concurrent hash-map that uses fine-grained locking. More...

#include <vyukov_hash_map.hpp>

Classes
class	iterator
	A ForwardIterator to safely iterate vyukov_hash_map. More...

Public Member Functions
bool	emplace (key_type key, value_type value)
	Inserts a new element into the container if the container doesn't already contain an element with an equivalent key. More...
template<class... Args>
std::pair< accessor, bool >	get_or_emplace (key_type key, Args &&... args)
	Inserts a new element into the container if the container doesn't already contain an element with an equivalent key. More...
template<class Factory >
std::pair< accessor, bool >	get_or_emplace_lazy (key_type key, Factory &&factory)
	Inserts a new element into the container if the container doesn't already contain an element with an equivalent key. The value for the newly constructed element is created by calling value_factory. More...
bool	extract (const key_type &key, accessor &accessor)
	Removes the element with the key equivalent to key (if one exists), and provides an accessor to the removed value. More...
bool	erase (const key_type &key)
	Removes the element with the key equivalent to key (if one exists). More...
void	erase (iterator &pos)
	Removes the specified element from the container. More...
bool	try_get_value (const key_type &key, accessor &result) const
	Provides an accessor to the value associated with the specified key, if such an element exists in the map. More...
iterator	find (const key_type &key)
	Finds an element with key equivalent to key. More...
iterator	begin ()
	Returns an iterator to the first element of the container. More...
iterator	end ()
	Returns an iterator to the element following the last element of the container. More...

Detailed Description

template<class Key, class Value, class... Policies>
struct xenium::vyukov_hash_map< Key, Value, Policies >

A concurrent hash-map that uses fine-grained locking.

This is a preliminary version; the interface might be subject to change.

This hash-map is heavily inspired by the hash-map presented by Vyukov [Vyu08]. It uses bucket-level locking for update operations (emplace/erase); however, read-only operations (try_get_value) are lock-free. Buckets are cacheline aligned to reduce false sharing and minimize cache thrashing.

There are two ways to access values of entries: via iterator or via accessor. An iterator can be used to iterate the map, providing access to the current key/value pair. An iterator keeps a lock on the currently iterated bucket, preventing concurrent update operations on that bucket. In contrast, an accessor provides safe access to a single value, but without holding any lock. The entry can safely be removed from the map even though some other thread may have an accessor to its value.

Some parts of the interface depend on whether the key/value types are trivially copyable and have a size of 4 or 8 bytes (e.g., raw pointers, integers); such types are further simply referred to as "trivial".

In addition to the distinction between trivial and non-trivial key/value types, it is possible to specify a managed_ptr instantiation as value type.

Based on these possibilities the class behaves as follows:

• trivial key, trivial value:
  • key/value are stored in separate atomics
  • accessor is a thin wrapper around a Value copy. Since the accessor contains a copy of the value it is limited to read-only access.
  • iterator dereferentiation returns a temporary std::pair<const Key, Value> object; the operator-> is therefore not supported.
• trivial key, managed_ptr with type T and reclaimer R:
  • T has to derive from R::enable_concurrent_ptr<T>
  • key is stored in an atomic, value is storend in a concurrent_ptr<T>
  • accessor is a thin wrapper around a guard_ptr<T>.
  • iterator dereferentiation returns a temporary std::pair<const Key, T*> object; the operator-> is therefore not supported.
• non-trivial key, managed_ptr with type T and reclaimer R:
  • T has to derive from R::enable_concurrent_ptr<T>
  • key and value are is stored in an internally allocated node
  • accessor is a thin wrapper containing a guard_ptr to the internal node, as well as a guard_ptr<T>.
  • iterator dereferentiation returns a temporary std::pair<const Key&, T*> object; the operator-> is therefore not supported.
• trivial key, non-trivial value
  • key is stored in an atomic, values are stored in internally allocated nodes. The lifetime of these nodes is managed via the specified the reclamation scheme (see xenium::policy::value_reclaimer).
  • accessor is a thin wrapper around a guard_ptr to the value's internal node
  • iterator dereferentiation returns a temporary std::pair<const Key, Value&> object; the operator-> is therefore not supported.
• non-trivial key, non-trivial value
  • key and value are stored in a std::pair in an internally allocated node
  • the key's hash value is memoized in an atomic in the bucket to ensure fast comparison
  • accessor is a thin wrapper around a guard_ptr to the internal node
  • iterator dereferentiation returns a reference to the node's std::pair object; this is the only configuration that supports the operator->.

Supported policies:

• xenium::policy::reclaimer
  Defines the reclamation scheme to be used for internal allocations. (required)
• xenium::policy::hash
  Defines the hash function. (optional; defaults to xenium::hash<Key>)
• xenium::policy::backoff
  Defines the backoff strategy. (optional; defaults to xenium::no_backoff)

Template Parameters

Key
Value
Policies

Member Function Documentation

begin()

template<class Key , class Value , class... Policies>

auto xenium::vyukov_hash_map< Key, Value, Policies >::begin

Returns an iterator to the first element of the container.

Progress guarantees: blocking

Returns

iterator to the first element

emplace()

template<class Key , class Value , class... Policies>

bool xenium::vyukov_hash_map< Key, Value, Policies >::emplace	(	key_type	key,
		value_type	value
	)

Inserts a new element into the container if the container doesn't already contain an element with an equivalent key.

The element is only constructed if no element with the key exists in the container. No iterators or accessors are invalidated.

Progress guarantees: blocking

Parameters

key	the key of element to be inserted.
value	the value of the element to be inserted

Returns

true if an element was inserted, otherwise false

end()

template<class Key , class Value , class... Policies>

iterator xenium::vyukov_hash_map< Key, Value, Policies >::end ( )

inline

Returns an iterator to the element following the last element of the container.

This element acts as a placeholder; attempting to access it results in undefined behavior. Progress guarantees: wait-free

Returns

iterator to the element following the last element.

erase() [1/2]

template<class Key , class Value , class... Policies>

bool xenium::vyukov_hash_map< Key, Value, Policies >::erase

(

const key_type &

key

)

Removes the element with the key equivalent to key (if one exists).

No iterators or accessors are invalidated.

Progress guarantees: blocking

Parameters

key	key of the element to remove

Returns

true if an element was removed, otherwise false

erase() [2/2]

template<class Key , class Value , class... Policies>

void xenium::vyukov_hash_map< Key, Value, Policies >::erase

(

iterator &

pos

)

Removes the specified element from the container.

No iterators or accessors are invalidated.

Progress guarantees: blocking

Parameters

pos	the iterator identifying the element to remove; pos is implicitly updated to refer to the next element.

extract()

template<class Key , class Value , class... Policies>

bool xenium::vyukov_hash_map< Key, Value, Policies >::extract	(	const key_type &	key,
		accessor &	accessor
	)

Removes the element with the key equivalent to key (if one exists), and provides an accessor to the removed value.

No iterators or accessors are invalidated.

Progress guarantees: blocking

Parameters

key	key of the element to remove
accessor	reference to an accessor to be set in case an element is removed.

Returns

true if an element was removed, otherwise false

find()

template<class Key , class Value , class... Policies>

auto xenium::vyukov_hash_map< Key, Value, Policies >::find

(

const key_type &

key

)

Finds an element with key equivalent to key.

Progress guarantees: blocking

Parameters

key	key of the element to search for

Returns

iterator to an element with key equivalent to key if such element is found, otherwise past-the-end iterator

get_or_emplace()

template<class Key , class Value , class... Policies>

template<class... Args>

std::pair<accessor, bool> xenium::vyukov_hash_map< Key, Value, Policies >::get_or_emplace	(	key_type	key,
		Args &&...	args
	)

Inserts a new element into the container if the container doesn't already contain an element with an equivalent key.

The element is only constructed if no element with the key exists in the container. No iterators or accessors are invalidated.

Progress guarantees: blocking

Parameters

key	the key of element to be inserted.
args	arguments to forward to the constructor of the element

Returns

a pair consisting of an accessor to the inserted element, or the already-existing element if no insertion happened, and a bool denoting whether the insertion took place; true if an element was inserted, otherwise false

get_or_emplace_lazy()

template<class Key , class Value , class... Policies>

template<class Factory >

std::pair<accessor, bool> xenium::vyukov_hash_map< Key, Value, Policies >::get_or_emplace_lazy	(	key_type	key,
		Factory &&	factory
	)

Inserts a new element into the container if the container doesn't already contain an element with an equivalent key. The value for the newly constructed element is created by calling value_factory.

The element is only constructed if no element with the key exists in the container. No iterators or accessors are invalidated.

Progress guarantees: blocking

Template Parameters

Factory

Parameters

key	the key of element to be inserted.
factory	a functor that is used to create the Value instance when constructing the new element to be inserted.

Returns

a pair consisting of an accessor to the inserted element, or the already-existing element if no insertion happened, and a bool denoting whether the insertion took place; true if an element was inserted, otherwise false

try_get_value()

template<class Key , class Value , class... Policies>

bool xenium::vyukov_hash_map< Key, Value, Policies >::try_get_value	(	const key_type &	key,
		accessor &	result
	)		const

Provides an accessor to the value associated with the specified key, if such an element exists in the map.

No iterators or accessors are invalidated.

Progress guarantees: lock-free

Parameters

key	key of the element to search for
result	reference to an accessor to be set if a matching element is found

Returns

true if an element was found, otherwise false