Persistent memory aware implementation of the concurrent skip list. More...

#include <libpmemobj++/container/detail/concurrent_skip_list_impl.hpp>

Public Member Functions
	concurrent_skip_list ()
	Default constructor. More...

	concurrent_skip_list (const key_compare &comp, const allocator_type &alloc=allocator_type())
	Constructs an empty container. More...

template<class InputIt >
	concurrent_skip_list (InputIt first, InputIt last, const key_compare &comp=key_compare(), const allocator_type &alloc=allocator_type())
	Constructs the container with the contents of the range [first, last). More...

	concurrent_skip_list (const concurrent_skip_list &other)
	Copy constructor. More...

	concurrent_skip_list (const concurrent_skip_list &other, const allocator_type &alloc)
	Copy constructor. More...

	concurrent_skip_list (concurrent_skip_list &&other)
	Move constructor. More...

	concurrent_skip_list (concurrent_skip_list &&other, const allocator_type &alloc)
	Move constructor. More...

void	runtime_initialize ()
	Initialize concurrent_skip_list after process restart. More...

void	free_data ()
	Should be called before concurrent_skip_list destructor is called. More...

	~concurrent_skip_list ()
	Destructor. More...

concurrent_skip_list &	operator= (const concurrent_skip_list &other)
	Copy assignment operator. More...

concurrent_skip_list &	operator= (concurrent_skip_list &&other)
	Move assignment operator. More...

concurrent_skip_list &	operator= (std::initializer_list< value_type > il)
	Replaces the contents with those identified by initializer list il. More...

std::pair< iterator, bool >	insert (const value_type &value)
	Inserts value in a thread-safe way. More...

template<typename P , typename std::enable_if< std::is_constructible< value_type, P && >::value >::type >
std::pair< iterator, bool >	insert (P &&value)
	Inserts value. More...

std::pair< iterator, bool >	insert (value_type &&value)
	Inserts value using move semantic. More...

iterator	insert (const_iterator hint, const_reference value)
	Inserts value in the position as close as possible, just prior to hint. More...

template<typename P , typename std::enable_if< std::is_constructible< value_type, P && >::value >::type >
iterator	insert (const_iterator hint, P &&value)
	Inserts value in the position as close as possible, just prior to hint. More...

template<typename InputIterator >
void	insert (InputIterator first, InputIterator last)
	Inserts elements from range [first, last). More...

void	insert (std::initializer_list< value_type > ilist)
	Inserts elements from initializer list ilist. More...

template<typename... Args>
std::pair< iterator, bool >	emplace (Args &&... args)
	Inserts a new element into the container constructed in-place with the given args if there is no element with the key in the container. More...

template<typename... Args>
iterator	emplace_hint (const_iterator hint, Args &&... args)
	Inserts a new element to the container as close as possible to the position just before hint. More...

template<typename... Args>
std::pair< iterator, bool >	try_emplace (const key_type &k, Args &&... args)
	If a key equivalent to k already exists in the container, does nothing. More...

template<typename... Args>
std::pair< iterator, bool >	try_emplace (key_type &&k, Args &&... args)
	If a key equivalent to k already exists in the container, does nothing. More...

template<typename K , typename... Args>
std::enable_if< has_is_transparent< key_compare >::value &&std::is_constructible< key_type, K && >::value, std::pair< iterator, bool > >::type	try_emplace (K &&k, Args &&... args)
	If a key equivalent to k already exists in the container, does nothing. More...

iterator	unsafe_erase (iterator pos)
	Removes the element at pos from the container. More...

iterator	unsafe_erase (const_iterator pos)
	Removes the element at pos from the container. More...

iterator	unsafe_erase (const_iterator first, const_iterator last)
	Removes the elements in the range [first; last), which must be a valid range in *this. More...

size_type	unsafe_erase (const key_type &key)
	Removes the element (if one exists) with the key equivalent to key. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value && !std::is_convertible<K, iterator>::value && !std::is_convertible<K, const_iterator>::value, K>::type>
size_type	unsafe_erase (const K &key)
	Removes the element (if one exists) with the key equivalent to key. More...

iterator	lower_bound (const key_type &key)
	Returns an iterator pointing to the first element that is not less than (i.e. More...

const_iterator	lower_bound (const key_type &key) const
	Returns an iterator pointing to the first element that is not less than (i.e. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
iterator	lower_bound (const K &x)
	Returns an iterator pointing to the first element that compares not less (i.e. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
const_iterator	lower_bound (const K &x) const
	Returns an iterator pointing to the first element that compares not less (i.e. More...

iterator	find_higher_eq (const key_type &key)
	Returns an iterator pointing to the first element that is not less than (i.e. More...

const_iterator	find_higher_eq (const key_type &key) const
	Returns an iterator pointing to the first element that is not less than (i.e. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
iterator	find_higher_eq (const K &x)
	Returns an iterator pointing to the first element that compares not less (i.e. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
const_iterator	find_higher_eq (const K &x) const
	Returns an iterator pointing to the first element that compares not less (i.e. More...

iterator	upper_bound (const key_type &key)
	Returns an iterator pointing to the first element that is greater than key. More...

const_iterator	upper_bound (const key_type &key) const
	Returns an iterator pointing to the first element that is greater than key. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
iterator	upper_bound (const K &x)
	Returns an iterator pointing to the first element that compares greater to the value x. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
const_iterator	upper_bound (const K &x) const
	Returns an iterator pointing to the first element that compares greater to the value x. More...

iterator	find_higher (const key_type &key)
	Returns an iterator pointing to the first element that is greater than key. More...

const_iterator	find_higher (const key_type &key) const
	Returns an iterator pointing to the first element that is greater than key. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
iterator	find_higher (const K &x)
	Returns an iterator pointing to the first element that compares greater to the value x. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
const_iterator	find_higher (const K &x) const
	Returns an iterator pointing to the first element that compares greater to the value x. More...

iterator	find_lower (const key_type &key)
	Returns an iterator pointing to the biggest element that is less than key. More...

const_iterator	find_lower (const key_type &key) const
	Returns a const iterator pointing to the biggest element that is less than key. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
iterator	find_lower (const K &key)
	Returns an iterator pointing to the biggest element that is less than key. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
const_iterator	find_lower (const K &key) const
	Returns a const iterator pointing to the biggest element that is less than key. More...

iterator	find_lower_eq (const key_type &key)
	Returns an iterator pointing to the biggest element that is less than or equal to key. More...

const_iterator	find_lower_eq (const key_type &key) const
	Returns a const iterator pointing to the biggest element that is less than or equal to key. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
iterator	find_lower_eq (const K &key)
	Returns an iterator pointing to the biggest element that is less than or equal to key. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
const_iterator	find_lower_eq (const K &key) const
	Returns a const iterator pointing to the biggest element that is less than or equal to key. More...

iterator	find (const key_type &key)
	Finds an element with key equivalent to key. More...

const_iterator	find (const key_type &key) const
	Finds an element with key equivalent to key. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
iterator	find (const K &x)
	Finds an element with key that compares equivalent to the value x. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
const_iterator	find (const K &x) const
	Finds an element with key that compares equivalent to the value x. More...

size_type	count (const key_type &key) const
	Returns the number of elements with key that compares equivalent to the specified argument. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
size_type	count (const K &key) const
	Returns the number of elements with key that compares equivalent to the specified argument. More...

bool	contains (const key_type &key) const
	Checks if there is an element with key equivalent to key in the container. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
bool	contains (const K &x) const
	Checks if there is an element with key that compares equivalent to the value x. More...

void	clear ()
	Erases all elements from the container transactionally. More...

iterator	begin ()
	Returns an iterator to the first element of the container. More...

const_iterator	begin () const
	Returns an iterator to the first element of the container. More...

const_iterator	cbegin () const
	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 map. More...

const_iterator	end () const
	Returns an iterator to the element following the last element of the map. More...

const_iterator	cend () const
	Returns an iterator to the element following the last element of the map. More...

size_type	size () const
	Returns the number of elements in the container, i.e. More...

size_type	max_size () const
	Returns the maximum number of elements the container is able to hold due to system or library implementation limitations, i.e. More...

bool	empty () const
	Checks if the container has no elements, i.e. More...

void	swap (concurrent_skip_list &other)
	XXX: Implement get_allocator() interface. More...

std::pair< iterator, iterator >	equal_range (const key_type &key)
	Returns a range containing all elements with the given key in the container. More...

std::pair< const_iterator, const_iterator >	equal_range (const key_type &key) const
	Returns a range containing all elements with the given key in the container. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
std::pair< iterator, iterator >	equal_range (const K &x)
	Returns a range containing all elements with the given key in the container. More...

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>
std::pair< const_iterator, const_iterator >	equal_range (const K &key) const
	Returns a range containing all elements with the given key in the container. More...

const key_compare &	key_comp () const
	Returns a const reference to the object that compares the keys. More...

key_compare &	key_comp ()
	Returns a reference to the object that compares the keys. More...

Static Public Attributes
static constexpr bool	allow_multimapping

Protected Types
using	traits_type = Traits

using	key_type = typename traits_type::key_type

using	mapped_type = typename traits_type::mapped_type

using	value_type = typename traits_type::value_type

using	size_type = std::size_t

using	difference_type = std::ptrdiff_t

using	key_compare = typename traits_type::compare_type

using	allocator_type = typename traits_type::allocator_type

using	allocator_traits_type = std::allocator_traits< allocator_type >

using	reference = value_type &

using	const_reference = const value_type &

using	pointer = typename allocator_traits_type::pointer

using	const_pointer = typename allocator_traits_type::const_pointer

using	list_node_type = skip_list_node< value_type >

using	iterator = skip_list_iterator< list_node_type, false >

using	const_iterator = skip_list_iterator< list_node_type, true >

using	random_level_generator_type = geometric_level_generator< typename traits_type::random_generator_type, MAX_LEVEL >

using	node_allocator_type = typename std::allocator_traits< allocator_type >::template rebind_alloc< uint8_t >

using	node_allocator_traits = typename std::allocator_traits< allocator_type >::template rebind_traits< uint8_t >

using	node_ptr = list_node_type *

using	const_node_ptr = const list_node_type *

using	persistent_node_ptr = obj::experimental::self_relative_ptr< list_node_type >

using	prev_array_type = std::array< node_ptr, MAX_LEVEL >

using	next_array_type = std::array< persistent_node_ptr, MAX_LEVEL >

using	node_lock_type = typename list_node_type::lock_type

using	lock_array = std::array< node_lock_type, MAX_LEVEL >

Static Protected Attributes
static constexpr size_type	MAX_LEVEL = traits_type::max_level

Detailed Description

template<typename Traits>
class pmem::detail::concurrent_skip_list< Traits >

Persistent memory aware implementation of the concurrent skip list.

The implementation is based on the lock-based algorithm described in https://www.cs.tau.ac.il/~shanir/nir-pubs-web/Papers/OPODIS2006-BA.pdf.

Our concurrent skip list implementation supports concurrent insertion and traversal, but not concurrent erasure. The erase method is prefixed with unsafe_, to indicate that there is no concurrency safety.

Each time, the pool with concurrent_skip_list is being opened, the concurrent_skip_list requires runtime_initialize() to be called in order to restore the state after process restart.

Traits template parameter allows to specify properties of the concurrent_ski_list. The Traits type should has the following member types:

key_type - type of the key
mapped_type - type of the mapped_value
value_type - type of the value stored inside the skip list node (e.g. pair<const key_type, mapped_type>).
compare_type - The comparison functor used to sort elements in the skip list.
allocator_type - The type of allocator used by the skip list.
max_level - The constant value which specify the number of layers in the skip list.
random_generator_type - The type of random generator used by the skip list. It should be thread-safe.

Constructor & Destructor Documentation

◆ concurrent_skip_list() [1/7]

template<typename Traits >

pmem::detail::concurrent_skip_list< Traits >::concurrent_skip_list ( )

inline

Default constructor.

Construct empty skip list.

Precondition: must be called in transaction scope.

Exceptions

pmem::pool_error	if an object is not in persistent memory.
pmem::transaction_scope_error	if constructor wasn't called in transaction.

◆ concurrent_skip_list() [2/7]

template<typename Traits >

pmem::detail::concurrent_skip_list< Traits >::concurrent_skip_list	(	const key_compare &	comp,
		const allocator_type &	alloc = `allocator_type()`
	)

inlineexplicit

Constructs an empty container.

Parameters

[in]	comp	comparison function object to use for all comparisons of keys.
[in]	alloc	allocator to use for all memory allocations of this container.

Precondition: must be called in transaction scope.

Exceptions

pmem::pool_error	if an object is not in persistent memory.
pmem::transaction_scope_error	if constructor wasn't called in transaction.
pmem::transaction_alloc_error	when allocating memory for inserted elements in transaction failed.

◆ concurrent_skip_list() [3/7]

template<typename Traits >

template<class InputIt >

pmem::detail::concurrent_skip_list< Traits >::concurrent_skip_list	(	InputIt	first,
		InputIt	last,
		const key_compare &	comp = `key_compare()`,
		const allocator_type &	alloc = `allocator_type()`
	)

inline

Constructs the container with the contents of the range [first, last).

If multiple elements in the range have keys that compare equivalent, the first element is inserted.

Parameters

[in]	first	first iterator of inserted range.
[in]	last	last iterator of inserted range.
[in]	comp	comparison function object to use for all comparisons of keys.
[in]	alloc	allocator to use for all memory allocations of this container.

InputIt must meet the requirements of LegacyInputIterator.

Precondition: must be called in transaction scope.

Exceptions

pmem::pool_error	if an object is not in persistent memory.
pmem::transaction_scope_error	if constructor wasn't called in transaction.
pmem::transaction_alloc_error	when allocating memory for inserted elements in transaction failed.
rethrows	element constructor exception.

◆ concurrent_skip_list() [4/7]

template<typename Traits >

pmem::detail::concurrent_skip_list< Traits >::concurrent_skip_list ( const concurrent_skip_list< Traits > & other )

inline

Copy constructor.

Constructs the container with the copy of the contents of other.

Parameters

[in] other reference to the concurrent_skip_list to be copied.

Precondition: must be called in transaction scope.

Postcondition: size() == other.size()

Exceptions

pmem::pool_error	if an object is not in persistent memory.
pmem::transaction_alloc_error	when allocating memory for copied elements in transaction failed.
pmem::transaction_scope_error	if constructor wasn't called in transaction.
rethrows	element constructor exception.

◆ concurrent_skip_list() [5/7]

template<typename Traits >

pmem::detail::concurrent_skip_list< Traits >::concurrent_skip_list	(	const concurrent_skip_list< Traits > &	other,
		const allocator_type &	alloc
	)

inline

Copy constructor.

Constructs the container with the copy of the contents of other.

Parameters

[in]	other	reference to the concurrent_skip_list to be copied.
[in]	alloc	allocator to use for all memory allocations of this container.

Precondition: must be called in transaction scope.

Postcondition: size() == other.size()

Exceptions

pmem::pool_error	if an object is not in persistent memory.
pmem::transaction_alloc_error	when allocating memory for copied elements in transaction failed.
pmem::transaction_scope_error	if constructor wasn't called in transaction.
rethrows	element constructor exception.

◆ concurrent_skip_list() [6/7]

template<typename Traits >

pmem::detail::concurrent_skip_list< Traits >::concurrent_skip_list ( concurrent_skip_list< Traits > && other )

inline

Move constructor.

Constructs the container with the contents of other using move semantics. Allocator is obtained by move-construction from the allocator belonging to other

Parameters

[in] other reference to the concurrent_skip_list to be copied.

Precondition: must be called in transaction scope.

Postcondition: size() == other.size()

Exceptions

pmem::pool_error	if an object is not in persistent memory.
pmem::transaction_alloc_error	when allocating memory for copied elements in transaction failed.
pmem::transaction_scope_error	if constructor wasn't called in transaction.
rethrows	element constructor exception.

◆ concurrent_skip_list() [7/7]

template<typename Traits >

pmem::detail::concurrent_skip_list< Traits >::concurrent_skip_list	(	concurrent_skip_list< Traits > &&	other,
		const allocator_type &	alloc
	)

inline

Move constructor.

Constructs the container with the contents of other using move semantics.

Parameters

[in]	other	reference to the concurrent_skip_list to be copied.
[in]	alloc	allocator to use for all memory allocations of this container.

Precondition: must be called in transaction scope.

Postcondition: size() == other.size()

Exceptions

pmem::pool_error	if an object is not in persistent memory.
pmem::transaction_alloc_error	when allocating memory for copied elements in transaction failed.
pmem::transaction_scope_error	if constructor wasn't called in transaction.
rethrows	element constructor exception.

◆ ~concurrent_skip_list()

template<typename Traits >

template<typename Traits >

void pmem::detail::concurrent_skip_list< Traits >::clear ( )

inline

Erases all elements from the container transactionally.

Postcondition: size() == 0

Exceptions

pmem::transaction_error	when snapshotting failed.
rethrows	destructor exception.

◆ contains() [1/2]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

bool pmem::detail::concurrent_skip_list< Traits >::contains ( const K & x ) const

inline

Checks if there is an element with key that compares equivalent to the value x.

This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. It allows calling this function without constructing an instance of Key.

Parameters

[in] x a value of any type that can be transparently compared with a key.

Returns: true if there is such an element, otherwise false.

◆ contains() [2/2]

template<typename Traits >

bool pmem::detail::concurrent_skip_list< Traits >::contains ( const key_type & key ) const

inline

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

Parameters

[in] key key value of the element to search for.

Returns: true if there is such an element, otherwise false.

◆ count() [1/2]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

size_type pmem::detail::concurrent_skip_list< Traits >::count ( const K & key ) const

inline

Returns the number of elements with key that compares equivalent to the specified argument.

This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key.

Parameters

[in] key alternative value to compare to the keys.

Returns: Number of elements with key that compares equivalent to the specified argument.

◆ count() [2/2]

template<typename Traits >

size_type pmem::detail::concurrent_skip_list< Traits >::count ( const key_type & key ) const

inline

Returns the number of elements with key that compares equivalent to the specified argument.

Parameters

[in] key key value of the element to count.

Returns: Number of elements with key that compares equivalent to the specified argument.

◆ emplace()

template<typename Traits >

template<typename... Args>

std::pair<iterator, bool> pmem::detail::concurrent_skip_list< Traits >::emplace ( Args &&... args )

inline

Inserts a new element into the container constructed in-place with the given args if there is no element with the key in the container.

Careful use of emplace allows the new element to be constructed while avoiding unnecessary copy or move operations. The constructor of the new element (i.e. std::pair<const Key, T>) is called with exactly the same arguments as supplied to emplace, forwarded via 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.

Parameters

[in] args arguments to forward to the constructor of the element

Returns: a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place.

Exceptions

pmem::transaction_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
pmem::transaction_scope_error	if called inside transaction.
rethrows	constructor exception.

◆ emplace_hint()

template<typename Traits >

template<typename... Args>

iterator pmem::detail::concurrent_skip_list< Traits >::emplace_hint	(	const_iterator	hint,
		Args &&...	args
	)

inline

Inserts a new element to the container as close as possible to the position just before hint.

The element is constructed in-place, i.e. no copy or move operations are performed.

The constructor of the element type (value_type, that is, std::pair<const Key, T>) is called with exactly the same arguments as supplied to the function, forwarded with std::forward<Args>(args)...

No iterators or references are invalidated.

Parameters

[in]	hint	iterator to the position before which the new element will be inserted.
[in]	args	arguments to forward to the constructor of the element.

Returns: Returns an iterator to the newly inserted element.

If the insertion failed because the element already exists, returns an iterator to the already existing element with the equivalent key.

Returns: an iterator to the inserted element, or to the element that prevented the insertion.

Exceptions

pmem::transaction_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
pmem::transaction_scope_error	if called inside transaction.
rethrows	constructor exception.

◆ empty()

template<typename Traits >

bool pmem::detail::concurrent_skip_list< Traits >::empty ( ) const

inline

Checks if the container has no elements, i.e.

whether begin() == end().

Returns: true if the container is empty, false otherwise.

◆ end() [1/2]

template<typename Traits >

iterator pmem::detail::concurrent_skip_list< Traits >::end ( )

inline

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

This element acts as a placeholder; attempting to access it results in undefined behavior.

Returns: Iterator to the element following the last element.

◆ end() [2/2]

template<typename Traits >

const_iterator pmem::detail::concurrent_skip_list< Traits >::end ( ) const

inline

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

This element acts as a placeholder; attempting to access it results in undefined behavior.

Returns: Iterator to the element following the last element.

◆ equal_range() [1/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

std::pair<const_iterator, const_iterator> pmem::detail::concurrent_skip_list< Traits >::equal_range ( const K & key ) const

inline

Returns a range containing all elements with the given key in the container.

The range is defined by two iterators, one pointing to the first element that is not less than key and another pointing to the first element greater than key. Alternatively, the first iterator may be obtained with lower_bound(), and the second with upper_bound().

Compares the keys to the value x. This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key.

Parameters

[in] key alternative value that can be compared to Key.

Returns: std::pair containing a pair of iterators defining the wanted range: the first pointing to the first element that is not less than key and the second pointing to the first element greater than key. If there are no elements not less than key, past-the-end (see end()) iterator is returned as the first element. Similarly if there are no elements greater than key, past-the-end iterator is returned as the second element.

◆ equal_range() [2/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

std::pair<iterator, iterator> pmem::detail::concurrent_skip_list< Traits >::equal_range ( const K & x )

inline

Returns a range containing all elements with the given key in the container.

The range is defined by two iterators, one pointing to the first element that is not less than key and another pointing to the first element greater than key. Alternatively, the first iterator may be obtained with lower_bound(), and the second with upper_bound().

Compares the keys to the value x. This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key.

Parameters

[in] x alternative value that can be compared to Key.

Returns: std::pair containing a pair of iterators defining the wanted range: the first pointing to the first element that is not less than key and the second pointing to the first element greater than key. If there are no elements not less than key, past-the-end (see end()) iterator is returned as the first element. Similarly if there are no elements greater than key, past-the-end iterator is returned as the second element.

◆ equal_range() [3/4]

template<typename Traits >

std::pair<iterator, iterator> pmem::detail::concurrent_skip_list< Traits >::equal_range ( const key_type & key )

inline

Returns a range containing all elements with the given key in the container.

The range is defined by two iterators, one pointing to the first element that is not less than key and another pointing to the first element greater than key. Alternatively, the first iterator may be obtained with lower_bound(), and the second with upper_bound().

Compares the keys to key.

Parameters

[in] key key value to compare the elements to.

Returns: std::pair containing a pair of iterators defining the wanted range: the first pointing to the first element that is not less than key and the second pointing to the first element greater than key. If there are no elements not less than key, past-the-end (see end()) iterator is returned as the first element. Similarly if there are no elements greater than key, past-the-end iterator is returned as the second element.

◆ equal_range() [4/4]

template<typename Traits >

std::pair<const_iterator, const_iterator> pmem::detail::concurrent_skip_list< Traits >::equal_range ( const key_type & key ) const

inline

Returns a range containing all elements with the given key in the container.

The range is defined by two iterators, one pointing to the first element that is not less than key and another pointing to the first element greater than key. Alternatively, the first iterator may be obtained with lower_bound(), and the second with upper_bound().

Compares the keys to key.

Parameters

[in] key key value to compare the elements to.

Returns: std::pair containing a pair of iterators defining the wanted range: the first pointing to the first element that is not less than key and the second pointing to the first element greater than key. If there are no elements not less than key, past-the-end (see end()) iterator is returned as the first element. Similarly if there are no elements greater than key, past-the-end iterator is returned as the second element.

◆ find() [1/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

iterator pmem::detail::concurrent_skip_list< Traits >::find ( const K & x )

inline

Finds an element with key that compares equivalent to the value x.

This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. It allows calling this function without constructing an instance of Key.

Parameters

[in] x a value of any type that can be transparently compared with a key.

Returns: Iterator to an element with key equivalent to key. If no such element is found, past-the-end iterator is returned.

◆ find() [2/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

const_iterator pmem::detail::concurrent_skip_list< Traits >::find ( const K & x ) const

inline

Finds an element with key that compares equivalent to the value x.

This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. It allows calling this function without constructing an instance of Key.

Parameters

[in] x a value of any type that can be transparently compared with a key.

Returns: Iterator to an element with key equivalent to key. If no such element is found, past-the-end iterator is returned.

◆ find() [3/4]

template<typename Traits >

iterator pmem::detail::concurrent_skip_list< Traits >::find ( const key_type & key )

inline

Finds an element with key equivalent to key.

Parameters

[in] key key value of the element to search for.

Returns: Iterator to an element with key equivalent to key. If no such element is found, past-the-end iterator is returned.

◆ find() [4/4]

template<typename Traits >

const_iterator pmem::detail::concurrent_skip_list< Traits >::find ( const key_type & key ) const

inline

Finds an element with key equivalent to key.

Parameters

[in] key key value of the element to search for.

Returns: Iterator to an element with key equivalent to key. If no such element is found, past-the-end iterator is returned.

◆ find_higher() [1/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

iterator pmem::detail::concurrent_skip_list< Traits >::find_higher ( const K & x )

inline

Returns an iterator pointing to the first element that compares greater to the value x.

This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key. Equivalent of upper_bound.

Parameters

[in] x alternative value that can be compared to Key.

Returns: Iterator pointing to the first element that is greater than key. If no such element is found, a past-the-end iterator is returned.

◆ find_higher() [2/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

const_iterator pmem::detail::concurrent_skip_list< Traits >::find_higher ( const K & x ) const

inline

Returns an iterator pointing to the first element that compares greater to the value x.

This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key. Equivalent of upper_bound.

Parameters

[in] x alternative value that can be compared to Key.

Returns: Iterator pointing to the first element that is greater than key. If no such element is found, a past-the-end iterator is returned.

◆ find_higher() [3/4]

template<typename Traits >

iterator pmem::detail::concurrent_skip_list< Traits >::find_higher ( const key_type & key )

inline

Returns an iterator pointing to the first element that is greater than key.

Equivalent of upper_bound.

Parameters

[in] key key value to compare the elements to.

Returns: Iterator pointing to the first element that is greater than key. If no such element is found, a past-the-end iterator is returned.

◆ find_higher() [4/4]

template<typename Traits >

const_iterator pmem::detail::concurrent_skip_list< Traits >::find_higher ( const key_type & key ) const

inline

Returns an iterator pointing to the first element that is greater than key.

Equivalent of upper_bound.

Parameters

[in] key key value to compare the elements to.

Returns: Iterator pointing to the first element that is greater than key. If no such element is found, a past-the-end iterator is returned.

◆ find_higher_eq() [1/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

iterator pmem::detail::concurrent_skip_list< Traits >::find_higher_eq ( const K & x )

inline

Returns an iterator pointing to the first element that compares not less (i.e.

greater or equal) to the value x. This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key. Equivalent of lower_bound.

Parameters

[in] x alternative value that can be compared to Key.

Returns: Iterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator is returned.

◆ find_higher_eq() [2/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

const_iterator pmem::detail::concurrent_skip_list< Traits >::find_higher_eq ( const K & x ) const

inline

Returns an iterator pointing to the first element that compares not less (i.e.

greater or equal) to the value x. This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key. Equivalent of lower_bound.

Parameters

[in] x alternative value that can be compared to Key.

Returns: Iterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator is returned.

◆ find_higher_eq() [3/4]

template<typename Traits >

iterator pmem::detail::concurrent_skip_list< Traits >::find_higher_eq ( const key_type & key )

inline

Returns an iterator pointing to the first element that is not less than (i.e.

greater or equal to) key. Equivalent of lower_bound.

Parameters

[in] key key value to compare the elements to.

Returns: Iterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator is returned.

◆ find_higher_eq() [4/4]

template<typename Traits >

const_iterator pmem::detail::concurrent_skip_list< Traits >::find_higher_eq ( const key_type & key ) const

inline

Returns an iterator pointing to the first element that is not less than (i.e.

greater or equal to) key. Equivalent of lower_bound.

Parameters

[in] key key value to compare the elements to.

Returns: Iterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator is returned.

◆ find_lower() [1/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

iterator pmem::detail::concurrent_skip_list< Traits >::find_lower ( const K & key )

inline

Returns an iterator pointing to the biggest element that is less than key.

This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key.

Parameters

[in] key alternative value that can be compared to Key.

Returns: Iterator pointing to the biggest element that is less than key. If no such element is found, a past-the-end iterator is returned.

◆ find_lower() [2/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

const_iterator pmem::detail::concurrent_skip_list< Traits >::find_lower ( const K & key ) const

inline

Returns a const iterator pointing to the biggest element that is less than key.

This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key.

Parameters

[in] key alternative value that can be compared to Key.

Returns: Const iterator pointing to the biggest element that is less than key. If no such element is found, a past-the-end iterator is returned.

◆ find_lower() [3/4]

template<typename Traits >

iterator pmem::detail::concurrent_skip_list< Traits >::find_lower ( const key_type & key )

inline

Returns an iterator pointing to the biggest element that is less than key.

Parameters

[in] key key value to compare the elements to.

Returns: Iterator pointing to the biggest element that is less than key. If no such element is found, a past-the-end iterator is returned.

◆ find_lower() [4/4]

template<typename Traits >

const_iterator pmem::detail::concurrent_skip_list< Traits >::find_lower ( const key_type & key ) const

inline

Returns a const iterator pointing to the biggest element that is less than key.

Parameters

[in] key key value to compare the elements to.

Returns: Const iterator pointing to the biggest element that is less than key. If no such element is found, a past-the-end iterator is returned.

◆ find_lower_eq() [1/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

iterator pmem::detail::concurrent_skip_list< Traits >::find_lower_eq ( const K & key )

inline

Returns an iterator pointing to the biggest element that is less than or equal to key.

This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key.

Parameters

[in] key alternative value that can be compared to Key.

Returns: Iterator pointing to the biggest element that is less than or equal to key. If no such element is found, a past-the-end iterator is returned.

◆ find_lower_eq() [2/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

const_iterator pmem::detail::concurrent_skip_list< Traits >::find_lower_eq ( const K & key ) const

inline

Returns a const iterator pointing to the biggest element that is less than or equal to key.

This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key.

Parameters

[in] key alternative value that can be compared to Key.

Returns: Const iterator pointing to the biggest element that is less than or equal to key. If no such element is found, a past-the-end iterator is returned.

◆ find_lower_eq() [3/4]

template<typename Traits >

iterator pmem::detail::concurrent_skip_list< Traits >::find_lower_eq ( const key_type & key )

inline

Returns an iterator pointing to the biggest element that is less than or equal to key.

Parameters

[in] key key value to compare the elements to.

Returns: Iterator pointing to the biggest element that is less than or equal to key. If no such element is found, a past-the-end iterator is returned.

◆ find_lower_eq() [4/4]

template<typename Traits >

const_iterator pmem::detail::concurrent_skip_list< Traits >::find_lower_eq ( const key_type & key ) const

inline

Returns a const iterator pointing to the biggest element that is less than or equal to key.

Parameters

[in] key key value to compare the elements to.

Returns: Const iterator pointing to the biggest element that is less than or equal to key. If no such element is found, a past-the-end iterator is returned.

◆ free_data()

template<typename Traits >

void pmem::detail::concurrent_skip_list< Traits >::free_data ( )

inline

Should be called before concurrent_skip_list destructor is called.

Otherwise, program can terminate if an exception occurs while freeing memory inside dtor.

The skip list map can NOT be used after free_data() was called (unless it was called in a transaction and that transaction aborted).

Exceptions

std::transaction_error	in case of PMDK transaction failure
pmem::transaction_free_error	when freeing underlying memory failed.

◆ insert() [1/7]

template<typename Traits >

std::pair<iterator, bool> pmem::detail::concurrent_skip_list< Traits >::insert ( const value_type & value )

inline

Inserts value in a thread-safe way.

No iterators or references are invalidated.

Parameters

[in] value element value to insert.

Returns: a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place.

Exceptions

pmem::transaction_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
pmem::transaction_scope_error	if called inside transaction.
rethrows	constructor exception.

◆ insert() [2/7]

template<typename Traits >

iterator pmem::detail::concurrent_skip_list< Traits >::insert	(	const_iterator	hint,
		const_reference	value
	)

inline

Inserts value in the position as close as possible, just prior to hint.

No iterators or references are invalidated.

Parameters

[in]	hint	iterator to the position before which the new element will be inserted.
[in]	value	element value to insert.

Returns: an iterator to the inserted element, or to the element that prevented the insertion.

Exceptions

pmem::transaction_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
pmem::transaction_scope_error	if called inside transaction.
rethrows	constructor exception.

◆ insert() [3/7]

template<typename Traits >

template<typename P , typename std::enable_if< std::is_constructible< value_type, P && >::value >::type >

iterator pmem::detail::concurrent_skip_list< Traits >::insert	(	const_iterator	hint,
		P &&	value
	)

inline

Inserts value in the position as close as possible, just prior to hint.

No iterators or references are invalidated. This overload is equivalent to emplace_hint(hint, std::forward<P>(value)) and only participates in overload resolution if std::is_constructible<value_type, P&&>::value == true.

Parameters

[in]	hint	iterator to the position before which the new element will be inserted.
[in]	value	element value to insert.

Returns: an iterator to the inserted element, or to the element that prevented the insertion.

Exceptions

pmem::transaction_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
pmem::transaction_scope_error	if called inside transaction.
rethrows	constructor exception.

◆ insert() [4/7]

template<typename Traits >

template<typename InputIterator >

void pmem::detail::concurrent_skip_list< Traits >::insert	(	InputIterator	first,
		InputIterator	last
	)

inline

Inserts elements from range [first, last).

If multiple elements in the range have keys that compare equivalent, the first one is inserted.

Parameters

[in]	first	first iterator of inserted range.
[in]	last	last iterator of inserted range.

Exceptions

pmem::transaction_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
pmem::transaction_scope_error	if called inside transaction.
rethrows	constructor exception.

◆ insert() [5/7]

template<typename Traits >

template<typename P , typename std::enable_if< std::is_constructible< value_type, P && >::value >::type >

std::pair<iterator, bool> pmem::detail::concurrent_skip_list< Traits >::insert ( P && value )

inline

Inserts value.

No iterators or references are invalidated. This overload is equivalent to emplace(std::forward<P>(value)) and only participates in overload resolution if std::is_constructible<value_type, P&&>::value == true.

Parameters

[in] value element value to insert.

Returns: a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place.

Exceptions

pmem::transaction_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
pmem::transaction_scope_error	if called inside transaction.
rethrows	constructor exception.

◆ insert() [6/7]

template<typename Traits >

void pmem::detail::concurrent_skip_list< Traits >::insert ( std::initializer_list< value_type > ilist )

inline

Inserts elements from initializer list ilist.

If multiple elements in the range have keys that compare equivalent, the first one is inserted.

Parameters

[in] ilist first initializer list to insert the values from.

Exceptions

pmem::transaction_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
pmem::transaction_scope_error	if called inside transaction.
rethrows	constructor exception.

◆ insert() [7/7]

template<typename Traits >

std::pair<iterator, bool> pmem::detail::concurrent_skip_list< Traits >::insert ( value_type && value )

inline

Inserts value using move semantic.

No iterators or references are invalidated.

Parameters

[in] value element value to insert.

Returns: a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place.

Exceptions

pmem::transaction_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
pmem::transaction_scope_error	if called inside transaction.
rethrows	constructor exception.

◆ key_comp() [1/2]

template<typename Traits >

key_compare& pmem::detail::concurrent_skip_list< Traits >::key_comp ( )

inline

Returns a reference to the object that compares the keys.

Returns: Reference to the key comparison function object.

◆ key_comp() [2/2]

template<typename Traits >

const key_compare& pmem::detail::concurrent_skip_list< Traits >::key_comp ( ) const

inline

Returns a const reference to the object that compares the keys.

Returns: Const reference to the key comparison function object.

◆ lower_bound() [1/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

iterator pmem::detail::concurrent_skip_list< Traits >::lower_bound ( const K & x )

inline

Returns an iterator pointing to the first element that compares not less (i.e.

greater or equal) to the value x. This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key.

Parameters

[in] x alternative value that can be compared to Key.

Returns: Iterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator is returned.

◆ lower_bound() [2/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

const_iterator pmem::detail::concurrent_skip_list< Traits >::lower_bound ( const K & x ) const

inline

Returns an iterator pointing to the first element that compares not less (i.e.

greater or equal) to the value x. This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key.

Parameters

[in] x alternative value that can be compared to Key.

Returns: Iterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator is returned.

◆ lower_bound() [3/4]

template<typename Traits >

iterator pmem::detail::concurrent_skip_list< Traits >::lower_bound ( const key_type & key )

inline

Returns an iterator pointing to the first element that is not less than (i.e.

greater or equal to) key.

Parameters

[in] key key value to compare the elements to.

Returns: Iterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator is returned.

◆ lower_bound() [4/4]

template<typename Traits >

const_iterator pmem::detail::concurrent_skip_list< Traits >::lower_bound ( const key_type & key ) const

inline

Returns an iterator pointing to the first element that is not less than (i.e.

greater or equal to) key.

Parameters

[in] key key value to compare the elements to.

Returns: Iterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator is returned.

◆ max_size()

template<typename Traits >

size_type pmem::detail::concurrent_skip_list< Traits >::max_size ( ) const

inline

Returns the maximum number of elements the container is able to hold due to system or library implementation limitations, i.e.

std::distance(begin(), end()) for the largest container.

Returns: Maximum number of elements.

◆ operator=() [1/3]

template<typename Traits >

concurrent_skip_list& pmem::detail::concurrent_skip_list< Traits >::operator= ( concurrent_skip_list< Traits > && other )

inline

Move assignment operator.

Replaces the contents with those of other using move semantics (i.e. the data in other is moved from other into this container). other is in a valid but unspecified state afterwards. If std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value is true, the target allocator is replaced by a copy of the source allocator. If it is false and the source and the target allocators do not compare equal, the target cannot take ownership of the source memory and must move-assign each element individually, allocating additional memory using its own allocator as needed. In any case, all elements originally present in *this are either destroyed or replaced by elementwise move-assignment.

Exceptions

pmem::transaction_alloc_error	when allocating new memory failed.
pmem::transaction_free_error	when freeing old existing elements failed.
rethrows	constructor exception.

◆ operator=() [2/3]

template<typename Traits >

concurrent_skip_list& pmem::detail::concurrent_skip_list< Traits >::operator= ( const concurrent_skip_list< Traits > & other )

inline

Copy assignment operator.

Replaces the contents with a copy of the contents of other transactionally. If std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value is true, the target allocator is replaced by a copy of the source allocator.

Postcondition: size() == other.size()

Exceptions

pmem::transaction_alloc_error	when allocating new memory failed.
pmem::transaction_free_error	when freeing old existing elements failed.
rethrows	constructor exception.

◆ operator=() [3/3]

template<typename Traits >

concurrent_skip_list& pmem::detail::concurrent_skip_list< Traits >::operator= ( std::initializer_list< value_type > il )

inline

Replaces the contents with those identified by initializer list il.

Parameters

[in] il initializer list to use as data source

Exceptions

pmem::transaction_alloc_error	when allocating new memory failed.
pmem::transaction_free_error	when freeing old existing elements failed.
rethrows	constructor exception.

◆ runtime_initialize()

template<typename Traits >

void pmem::detail::concurrent_skip_list< Traits >::runtime_initialize ( )

inline

Initialize concurrent_skip_list after process restart.

MUST be called every time after process restart. Not thread safe.

◆ size()

template<typename Traits >

size_type pmem::detail::concurrent_skip_list< Traits >::size ( ) const

inline

Returns the number of elements in the container, i.e.

std::distance(begin(), end()).

Returns: The number of elements in the container.

◆ swap()

template<typename Traits >

void pmem::detail::concurrent_skip_list< Traits >::swap ( concurrent_skip_list< Traits > & other )

inline

XXX: Implement get_allocator() interface.

Related with: https://github.com/pmem/libpmemobj-cpp/issues/827 Exchanges the contents of the container with those of other transactionally. Does not invoke any move, copy, or swap operations on individual elements.

Exceptions

pmem::transaction_error when snapshotting failed.

◆ try_emplace() [1/3]

template<typename Traits >

template<typename... Args>

std::pair<iterator, bool> pmem::detail::concurrent_skip_list< Traits >::try_emplace	(	const key_type &	k,
		Args &&...	args
	)

inline

If a key equivalent to k already exists in the container, does nothing.

Otherwise, behaves like emplace except that the element is constructed as value_type(std::piecewise_construct, std::forward_as_tuple(k), std::forward_as_tuple(std::forward<Args>(args)...))

No iterators or references are invalidated.

Parameters

[in]	k	the key used both to look up and to insert if not found.
[in]	args	arguments to forward to the constructor of the element.

Returns: a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place.

Exceptions

pmem::transaction_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
pmem::transaction_scope_error	if called inside transaction.
rethrows	constructor exception.

◆ try_emplace() [2/3]

template<typename Traits >

template<typename K , typename... Args>

std::enable_if< has_is_transparent<key_compare>::value && std::is_constructible<key_type, K &&>::value, std::pair<iterator, bool> >::type pmem::detail::concurrent_skip_list< Traits >::try_emplace	(	K &&	k,
		Args &&...	args
	)

inline

If a key equivalent to k already exists in the container, does nothing.

Otherwise, behaves like emplace except that the element is constructed as value_type(std::piecewise_construct, std::forward_as_tuple(std::move(k)), std::forward_as_tuple(std::forward<Args>(args)...)). This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type and std::is_constructible<Key, K &&>::value == true . It allows calling this function without constructing an instance of Key.

No iterators or references are invalidated.

Parameters

[in]	k	the key used both to look up and to insert if not found.
[in]	args	arguments to forward to the constructor of the element.

Returns: a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place.

Exceptions

pmem::transaction_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
rethrows	constructor exception.

◆ try_emplace() [3/3]

template<typename Traits >

template<typename... Args>

std::pair<iterator, bool> pmem::detail::concurrent_skip_list< Traits >::try_emplace	(	key_type &&	k,
		Args &&...	args
	)

inline

If a key equivalent to k already exists in the container, does nothing.

Otherwise, behaves like emplace except that the element is constructed as value_type(std::piecewise_construct, std::forward_as_tuple(std::move(k)), std::forward_as_tuple(std::forward<Args>(args)...)).

No iterators or references are invalidated.

Parameters

[in]	k	the key used both to look up and to insert if not found.
[in]	args	arguments to forward to the constructor of the element.

Returns: a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place.

Exceptions

pmem::transaction_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
pmem::transaction_scope_error	if called inside transaction.
rethrows	constructor exception.

◆ unsafe_erase() [1/5]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value && !std::is_convertible<K, iterator>::value && !std::is_convertible<K, const_iterator>::value, K>::type>

size_type pmem::detail::concurrent_skip_list< Traits >::unsafe_erase ( const K & key )

inline

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

References and iterators to the erased elements are invalidated. Other references and iterators are not affected. This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type and std::is_convertible<K, iterator>::value != true && std::is_convertible<K, const_iterator>::value != true. It allows calling this function without constructing an instance of Key.

Parameters

[in] key key value of the elements to remove.

Returns: Number of elements removed.

Exceptions

pmem::transaction_error	when snapshotting failed.
rethrows	destructor exception.

◆ unsafe_erase() [2/5]

template<typename Traits >

size_type pmem::detail::concurrent_skip_list< Traits >::unsafe_erase ( const key_type & key )

inline

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

References and iterators to the erased elements are invalidated. Other references and iterators are not affected.

Parameters

[in] key key value of the elements to remove.

Returns: Number of elements removed.

Exceptions

pmem::transaction_error	when snapshotting failed.
rethrows	destructor exception.

◆ unsafe_erase() [3/5]

template<typename Traits >

iterator pmem::detail::concurrent_skip_list< Traits >::unsafe_erase	(	const_iterator	first,
		const_iterator	last
	)

inline

Removes the elements in the range [first; last), which must be a valid range in *this.

References and iterators to the erased elements are invalidated. Other references and iterators are not affected.

Parameters

[in]	first	first iterator in the range of elements to remove.
[in]	last	last iterator in the range of elements to remove.

Returns: iterator following the last removed element.

Exceptions

pmem::transaction_error	when snapshotting failed.
rethrows	destructor exception.

◆ unsafe_erase() [4/5]

template<typename Traits >

iterator pmem::detail::concurrent_skip_list< Traits >::unsafe_erase ( const_iterator pos )

inline

Removes the element at pos from the container.

References and iterators to the erased elements are invalidated. Other references and iterators are not affected.

Precondition: The iterator pos must be valid and dereferenceable. Thus the end() iterator (which is valid, but is not dereferenceable) cannot be used as a value for pos.

Parameters

[in] pos iterator to the element to remove.

Returns: iterator following the removed element.

Exceptions

pmem::transaction_error	when snapshotting failed.
rethrows	destructor exception.

◆ unsafe_erase() [5/5]

template<typename Traits >

iterator pmem::detail::concurrent_skip_list< Traits >::unsafe_erase ( iterator pos )

inline

Removes the element at pos from the container.

References and iterators to the erased elements are invalidated. Other references and iterators are not affected.

Precondition: The iterator pos must be valid and dereferenceable. Thus the end() iterator (which is valid, but is not dereferenceable) cannot be used as a value for pos.

Parameters

[in] pos iterator to the element to remove.

Returns: iterator following the removed element.

Exceptions

pmem::transaction_error	when snapshotting failed.
rethrows	destructor exception.

◆ upper_bound() [1/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

iterator pmem::detail::concurrent_skip_list< Traits >::upper_bound ( const K & x )

inline

Returns an iterator pointing to the first element that compares greater to the value x.

This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key.

Parameters

[in] x alternative value that can be compared to Key.

Returns: Iterator pointing to the first element that is greater than key. If no such element is found, a past-the-end iterator is returned.

◆ upper_bound() [2/4]

template<typename Traits >

template<typename K , typename = typename std::enable_if< has_is_transparent<key_compare>::value, K>::type>

const_iterator pmem::detail::concurrent_skip_list< Traits >::upper_bound ( const K & x ) const

inline

Returns an iterator pointing to the first element that compares greater to the value x.

This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key.

Parameters

[in] x alternative value that can be compared to Key.

Returns: Iterator pointing to the first element that is greater than key. If no such element is found, a past-the-end iterator is returned.

◆ upper_bound() [3/4]

template<typename Traits >

iterator pmem::detail::concurrent_skip_list< Traits >::upper_bound ( const key_type & key )

inline

Returns an iterator pointing to the first element that is greater than key.

Parameters

[in] key key value to compare the elements to.

Returns: Iterator pointing to the first element that is greater than key. If no such element is found, a past-the-end iterator is returned.

◆ upper_bound() [4/4]

template<typename Traits >

const_iterator pmem::detail::concurrent_skip_list< Traits >::upper_bound ( const key_type & key ) const

inline

Returns an iterator pointing to the first element that is greater than key.

Parameters

[in] key key value to compare the elements to.

Returns: Iterator pointing to the first element that is greater than key. If no such element is found, a past-the-end iterator is returned.

Member Data Documentation

◆ allow_multimapping

template<typename Traits >

constexpr bool pmem::detail::concurrent_skip_list< Traits >::allow_multimapping

staticconstexpr

Initial value:

=

traits_type::allow_multimapping

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

libpmemobj++/container/detail/concurrent_skip_list_impl.hpp

Public Member Functions

Static Public Attributes

Protected Types

Static Protected Attributes

Detailed Description

template<typename Traits> class pmem::detail::concurrent_skip_list< Traits >

Constructor & Destructor Documentation

◆ concurrent_skip_list() [1/7]

◆ concurrent_skip_list() [2/7]

◆ concurrent_skip_list() [3/7]

◆ concurrent_skip_list() [4/7]

◆ concurrent_skip_list() [5/7]

◆ concurrent_skip_list() [6/7]

◆ concurrent_skip_list() [7/7]

◆ ~concurrent_skip_list()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ clear()

◆ contains() [1/2]

◆ contains() [2/2]

◆ count() [1/2]

◆ count() [2/2]

◆ emplace()

◆ emplace_hint()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ equal_range() [1/4]

◆ equal_range() [2/4]

◆ equal_range() [3/4]

◆ equal_range() [4/4]

◆ find() [1/4]

◆ find() [2/4]

◆ find() [3/4]

◆ find() [4/4]

◆ find_higher() [1/4]

◆ find_higher() [2/4]

◆ find_higher() [3/4]

◆ find_higher() [4/4]

◆ find_higher_eq() [1/4]

◆ find_higher_eq() [2/4]

◆ find_higher_eq() [3/4]

◆ find_higher_eq() [4/4]

◆ find_lower() [1/4]

◆ find_lower() [2/4]

◆ find_lower() [3/4]

◆ find_lower() [4/4]

◆ find_lower_eq() [1/4]

◆ find_lower_eq() [2/4]

◆ find_lower_eq() [3/4]

◆ find_lower_eq() [4/4]

◆ free_data()

◆ insert() [1/7]

◆ insert() [2/7]

◆ insert() [3/7]

◆ insert() [4/7]

◆ insert() [5/7]

◆ insert() [6/7]

◆ insert() [7/7]

◆ key_comp() [1/2]

◆ key_comp() [2/2]

◆ lower_bound() [1/4]

◆ lower_bound() [2/4]

◆ lower_bound() [3/4]

◆ lower_bound() [4/4]

◆ max_size()

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ runtime_initialize()

◆ size()

◆ swap()

◆ try_emplace() [1/3]

◆ try_emplace() [2/3]

◆ try_emplace() [3/3]

◆ unsafe_erase() [1/5]

◆ unsafe_erase() [2/5]

template<typename Traits>
class pmem::detail::concurrent_skip_list< Traits >