xenium::harris_michael_list_based_set< Key, Policies > Class Template Reference

A lock-free container that contains a sorted set of unique objects of type Key. More...

#include <harris_michael_list_based_set.hpp>

Classes
class	iterator
	A ForwardIterator to safely iterate the list. 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...
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...
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... Policies>
class xenium::harris_michael_list_based_set< Key, Policies >

A lock-free container that contains a sorted set of unique objects of type Key.

This container is implemented as a sorted singly linked list. All operations have a runtime complexity linear in the size of the list (in the absence of conflicting operations).

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::compare
    Defines the comparison function that is used to order the list. (optional; defaults to std::less<Key>)
  • xenium::policy::backoff
    Defines the backoff strategy. (optional; defaults to xenium::no_backoff)

Template Parameters

Key	type of the stored elements.
Policies	list of policies to customize the behaviour

Member Function Documentation

begin()

template<class Key , class... Policies>

auto xenium::harris_michael_list_based_set< Key, Policies >::begin

Returns an iterator to the first element of the container.

Returns

iterator to the first element

contains()

template<class Key , class... Policies>

bool xenium::harris_michael_list_based_set< Key, 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... Policies>

template<class... Args>

bool xenium::harris_michael_list_based_set< Key, 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... Policies>

template<class... Args>

std::pair<iterator, bool> xenium::harris_michael_list_based_set< Key, 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... Policies>

auto xenium::harris_michael_list_based_set< Key, 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... Policies>

bool xenium::harris_michael_list_based_set< Key, 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... Policies>

auto xenium::harris_michael_list_based_set< Key, 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... Policies>

auto xenium::harris_michael_list_based_set< Key, 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