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

Private Member Functions
void	check_tx_stage_work () const
	Private helper function. More...

template<typename K , typename pointer_type , typename comparator >
persistent_node_ptr	internal_find_position (size_type level, pointer_type &prev, const K &key, const comparator &cmp) const
	Finds position on the. More...

template<typename K >
void	find_insert_pos (prev_array_type &prev_nodes, next_array_type &next_nodes, const K &key)
	The method finds insert position for the given. More...

template<typename K , typename comparator >
void	fill_prev_next_arrays (prev_array_type &prev_nodes, next_array_type &next_nodes, const K &key, const comparator &cmp)
	The method finds successor and predecessor nodes on each level of the skip list for the given. More...

template<typename... Args>
std::pair< iterator, bool >	internal_unsafe_emplace (Args &&... args)
	Not thread-safe but can be called within a transaction. More...

template<typename K , typename... Args>
std::pair< iterator, bool >	internal_insert (const K &key, Args &&... args)
	Construct and insert new node to the skip list in a thread-safe way.

template<typename K , typename PrepareNode >
std::pair< iterator, bool >	internal_insert_node (const K &key, size_type height, PrepareNode &&prepare_new_node)
	Try to insert new node to the skip list in a thread-safe way.

template<typename PrepareNode >
node_ptr	try_insert_node (prev_array_type &prev_nodes, const next_array_type &next_nodes, size_type height, PrepareNode &&prepare_new_node)
	Try to insert new node to the skip list. More...

bool	check_prev_array (const prev_array_type &prevs, size_type height)
	Used only inside asserts. More...

template<typename K , typename comparator >
const_iterator	internal_get_bound (const K &key, const comparator &cmp) const
	Returns an iterator pointing to the first element from the list for which cmp(element, key) is false. More...

template<typename K , typename comparator >
iterator	internal_get_bound (const K &key, const comparator &cmp)
	Returns an iterator pointing to the first element from the list for which cmp(element, key) is false. More...

template<typename K , typename comparator >
const_iterator	internal_get_biggest_less_than (const K &key, const comparator &cmp) const
	Returns an iterator pointing to the last element from the list for which cmp(element, key) is true. More...

std::pair< persistent_node_ptr, persistent_node_ptr >	internal_extract (const_iterator it)

obj::pool_base	get_pool_base () const
	Get the persistent memory pool where hashmap resides. More...

size_type	random_level ()
	Generate random level.

template<typename... Args>
persistent_node_ptr	create_node (Args &&... args)
	Creates new node.

void	create_dummy_head ()
	Creates dummy head. More...

template<typename... Args>
persistent_node_ptr	creates_dummy_node (size_type height, Args &&... args)
	Creates new node, value_type should be constructed separately. More...

void	tls_restore ()
	Process any information which was saved to tls and clears tls.

Private Attributes
obj::p< size_type >	on_init_size
	This variable holds real size after the skip list is initialized. More...

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 concurrent skip list 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 >

bool pmem::detail::concurrent_skip_list< Traits >::check_prev_array	(	const prev_array_type &	prevs,
		size_type	height
	)

inlineprivate

Used only inside asserts.

Checks that prev_array is filled with correct values.

◆ check_tx_stage_work()

template<typename Traits >

void pmem::detail::concurrent_skip_list< Traits >::check_tx_stage_work ( ) const

inlineprivate

Private helper function.

Checks if current transaction stage is equal to TX_STAGE_WORK and throws an exception otherwise.

Exceptions

pmem::transaction_scope_error if current transaction stage is not equal to TX_STAGE_WORK.

◆ clear()

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.

◆ create_dummy_head()

template<typename Traits >

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

inlineprivate

Creates dummy head.

Precondition: Always called from ctor.

◆ creates_dummy_node()

template<typename Traits >

template<typename... Args>

persistent_node_ptr pmem::detail::concurrent_skip_list< Traits >::creates_dummy_node	(	size_type	height,
		Args &&...	args
	)

inlineprivate

Creates new node, value_type should be constructed separately.

Each node object has different size which depends on number of layers the node is linked. In this method we calculate the size of the new node based on the node height. Then required amount of bytes are allocated and casted to the persistent_node_ptr.

Precondition: Should be called inside transaction.

◆ 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.

◆ fill_prev_next_arrays()

template<typename Traits >

template<typename K , typename comparator >

void pmem::detail::concurrent_skip_list< Traits >::fill_prev_next_arrays	(	prev_array_type &	prev_nodes,
		next_array_type &	next_nodes,
		const K &	key,
		const comparator &	cmp
	)

inlineprivate

The method finds successor and predecessor nodes on each level of the skip list for the given.

key.

Parameters

[out]	prev_nodes	array of pointers to predecessor nodes on each level.
[out]	next_nodes	array of pointers to successor nodes on each level.
[in]	key	inserted key.
[in]	cmp	comparator functor used for the search.

◆ 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_insert_pos()

template<typename Traits >

template<typename K >

void pmem::detail::concurrent_skip_list< Traits >::find_insert_pos	(	prev_array_type &	prev_nodes,
		next_array_type &	next_nodes,
		const K &	key
	)

inlineprivate

The method finds insert position for the given.

key. It finds successor and predecessor nodes on each level of the skip list.

Parameters

[out]	prev_nodes	array of pointers to predecessor nodes on each level.
[out]	next_nodes	array of pointers to successor nodes on each level.
[in]	key	inserted key.

◆ 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.

◆ get_pool_base()

template<typename Traits >

obj::pool_base pmem::detail::concurrent_skip_list< Traits >::get_pool_base ( ) const

inlineprivate

Get the persistent memory pool where hashmap resides.

Returns: pmem::obj::pool_base object.

◆ 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.

◆ internal_extract()

template<typename Traits >

std::pair<persistent_node_ptr, persistent_node_ptr> pmem::detail::concurrent_skip_list< Traits >::internal_extract ( const_iterator it )

inlineprivate

Returns: a pointer to extracted node and a pointer to next node

◆ internal_find_position()

template<typename Traits >

template<typename K , typename pointer_type , typename comparator >

persistent_node_ptr pmem::detail::concurrent_skip_list< Traits >::internal_find_position	(	size_type	level,
		pointer_type &	prev,
		const K &	key,
		const comparator &	cmp
	)		const

inlineprivate

Finds position on the.

level using

cmp

Parameters

level	- on which level search prev node
prev	- pointer to the start node to search
key	- key to search
cmp	- callable object to compare two objects (_compare member is default comparator)

Returns: pointer to the node which is not satisfy the comparison with

key

◆ internal_get_biggest_less_than()

template<typename Traits >

template<typename K , typename comparator >

const_iterator pmem::detail::concurrent_skip_list< Traits >::internal_get_biggest_less_than	(	const K &	key,
		const comparator &	cmp
	)		const

inlineprivate

Returns an iterator pointing to the last element from the list for which cmp(element, key) is true.

Parameters

[in]	key	key value to compare the elements to.
[in]	cmp	comparator functor used for the search.

Returns: Iterator pointing to the first element for which cmp(element, key) is false. If no such element is found, a past-the-end iterator is returned.

◆ internal_get_bound() [1/2]

template<typename Traits >

template<typename K , typename comparator >

iterator pmem::detail::concurrent_skip_list< Traits >::internal_get_bound	(	const K &	key,
		const comparator &	cmp
	)

inlineprivate

Returns an iterator pointing to the first element from the list for which cmp(element, key) is false.

Parameters

[in]	key	key value to compare the elements to.
[in]	cmp	comparator functor used for the search.

Returns: Iterator pointing to the first element for which cmp(element, key) is false. If no such element is found, a past-the-end iterator is returned.

◆ internal_get_bound() [2/2]

template<typename Traits >

template<typename K , typename comparator >

const_iterator pmem::detail::concurrent_skip_list< Traits >::internal_get_bound	(	const K &	key,
		const comparator &	cmp
	)		const

inlineprivate

Returns an iterator pointing to the first element from the list for which cmp(element, key) is false.

Parameters

[in]	key	key value to compare the elements to.
[in]	cmp	comparator functor used for the search.

Returns: Iterator pointing to the first element for which cmp(element, key) is false. If no such element is found, a past-the-end iterator is returned.

◆ internal_unsafe_emplace()

template<typename Traits >

template<typename... Args>

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

inlineprivate

Not thread-safe but can be called within a transaction.

XXX: Need to optimize for single-threaded case.

◆ 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.

◆ try_insert_node()

template<typename Traits >

template<typename PrepareNode >

node_ptr pmem::detail::concurrent_skip_list< Traits >::try_insert_node	(	prev_array_type &	prev_nodes,
		const next_array_type &	next_nodes,
		size_type	height,
		PrepareNode &&	prepare_new_node
	)

inlineprivate

Try to insert new node to the skip list.

Returns: pointer to the new node if it was inserted. Otherwise, returns nullptr.

◆ 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

◆ on_init_size

template<typename Traits >

obj::p<size_type> pmem::detail::concurrent_skip_list< Traits >::on_init_size

private

This variable holds real size after the skip list is initialized.

It holds real value of size only after initialization (before any insert/remove).

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

libpmemobj++/container/detail/concurrent_skip_list_impl.hpp

Public Member Functions

Private Member Functions

Private 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()

◆ check_prev_array()

◆ check_tx_stage_work()

◆ clear()

◆ contains() [1/2]

◆ contains() [2/2]

◆ count() [1/2]

◆ count() [2/2]

◆ create_dummy_head()

◆ creates_dummy_node()

◆ 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]

◆ fill_prev_next_arrays()

◆ 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_insert_pos()

◆ 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()

◆ get_pool_base()

◆ insert() [1/7]

◆ insert() [2/7]

◆ insert() [3/7]

◆ insert() [4/7]

◆ insert() [5/7]

◆ insert() [6/7]

◆ insert() [7/7]

◆ internal_extract()

◆ internal_find_position()

◆ internal_get_biggest_less_than()

◆ internal_get_bound() [1/2]

◆ internal_get_bound() [2/2]

◆ internal_unsafe_emplace()

◆ key_comp() [1/2]

◆ key_comp() [2/2]

◆ lower_bound() [1/4]

◆ lower_bound() [2/4]

◆ lower_bound() [3/4]

◆ lower_bound() [4/4]

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