xenium::harris_michael_hash_map< Key, Value, Policies > Class Template Reference

A generic lock-free hash-map. More...

#include <harris_michael_hash_map.hpp>

Classes
class	accessor
	An accessor to safely access the value of an element. More...
class	iterator
	A ForwardIterator to safely iterate the hash-map. More...

Public Member Functions
template<class... Args>
bool	emplace (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 constructed in-place with the given args. More...
template<class... Args>
std::pair< iterator, bool >	emplace_or_get (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 constructed in-place with the given args. More...
template<class... Args>
std::pair< iterator, bool >	get_or_emplace (Key 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 constructed as value_type(std::piecewise_construct, std::forward_as_tuple(k), std::forward_as_tuple(std::forward<Args>(args)...)). More...
template<class Factory >
std::pair< iterator, bool >	get_or_emplace_lazy (Key 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	erase (const Key &key)
	Removes the element with the key equivalent to key (if one exists). More...
iterator	erase (iterator pos)
	Removes the specified element from the container. More...
iterator	find (const Key &key)
	Finds an element with key equivalent to key. More...
bool	contains (const Key &key)
	Checks if there is an element with key equivalent to key in the container. More...
accessor	operator[] (const Key &key)
	The accessor 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>
class xenium::harris_michael_hash_map< Key, Value, Policies >

A generic lock-free hash-map.

This hash-map consists of a fixed number of buckets were each bucket is essentially a harris_michael_list_based_set instance. The number of buckets is fixed, so the hash-map does not support dynamic resizing.

This hash-map is less efficient than many other available concurrent hash-maps, but it is lock-free and fully generic, i.e., it supports arbitrary types for Key and Value.

This data structure is based on the solution proposed by Michael [Mic02] which builds upon the original proposal by Harris [Har01].

Supported policies:

• xenium::policy::reclaimer
  Defines the reclamation scheme to be used for internal nodes. (required)
• xenium::policy::hash
  Defines the hash function. (optional; defaults to xenium::hash<Key>)
• xenium::policy::map_to_bucket
  Defines the function that is used to map the calculated hash to a bucket. (optional; defaults to xenium::utils::modulo<std::size_t>)
• xenium::policy::backoff
  Defines the backoff strategy. (optional; defaults to xenium::no_backoff)
• xenium::policy::buckets
  Defines the number of buckets. (optional; defaults to 512)
• xenium::policy::memoize_hash
  Defines whether the hash should be stored and used during lookup operations. (optional; defaults to false for scalar Key types; otherwise true)

Template Parameters

Key
Value
Policies	list of policies to customize the behaviour

Member Function Documentation

begin()

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

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

Returns an iterator to the first element of the container.

Returns

iterator to the first element

contains()

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

bool xenium::harris_michael_hash_map< Key, Value, Policies >::contains

(

const Key &

key

)

Checks if there is an element with key equivalent to key in the container.

Progress guarantees: lock-free

Parameters

key	key of the element to search for

Returns

true if there is such an element, otherwise false

emplace()

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

template<class... Args>

bool xenium::harris_michael_hash_map< Key, Value, Policies >::emplace

(

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 constructed in-place with the given args.

The element is always constructed. If there already is an element with the key in the container, the newly constructed element will be destroyed immediately.

No iterators or references are invalidated.

Progress guarantees: lock-free

Parameters

args	arguments to forward to the constructor of the element

Returns

true if an element was inserted, otherwise false

emplace_or_get()

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

template<class... Args>

std::pair<iterator, bool> xenium::harris_michael_hash_map< Key, Value, Policies >::emplace_or_get

(

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 constructed in-place with the given args.

The element is always constructed. If there already is an element with the key in the container, the newly constructed element will be destroyed immediately.

No iterators or references are invalidated.

Progress guarantees: lock-free

Parameters

args	arguments to forward to the constructor of the element

Returns

a pair consisting of an iterator 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

end()

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

auto xenium::harris_michael_hash_map< Key, Value, Policies >::end

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.

Returns

iterator to the element following the last element.

erase() [1/2]

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

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

(

const Key &

key

)

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

No iterators or references are invalidated.

Progress guarantees: lock-free

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>

auto xenium::harris_michael_hash_map< Key, Value, Policies >::erase

(

iterator

pos

)

Removes the specified element from the container.

No iterators or references are invalidated.

Progress guarantees: lock-free

Parameters

pos	the iterator identifying the element to remove

Returns

iterator following the last removed element

find()

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

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

(

const Key &

key

)

Finds an element with key equivalent to key.

Progress guarantees: lock-free

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<iterator, bool> xenium::harris_michael_hash_map< Key, Value, Policies >::get_or_emplace	(	Key	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 constructed as value_type(std::piecewise_construct, std::forward_as_tuple(k), std::forward_as_tuple(std::forward<Args>(args)...)).

The element may be constructed even if there already is an element with the key in the container, in which case the newly constructed element will be destroyed immediately.

No iterators or references are invalidated. Progress guarantees: lock-free

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 iterator 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<iterator, bool> xenium::harris_michael_hash_map< Key, Value, Policies >::get_or_emplace_lazy	(	Key	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 may be constructed even if there already is an element with the key in the container, in which case the newly constructed element will be destroyed immediately.

No iterators or references are invalidated. Progress guarantees: lock-free

Template Parameters

Func

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 iterator 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

operator[]()

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

auto xenium::harris_michael_hash_map< Key, Value, Policies >::operator[]

(

const Key &

key

)

The accessor

Parameters

key

Returns

an accessor to the element's value