PMDK C++ bindings  1.11
This is the C++ bindings documentation for PMDK's libpmemobj.
Public Member Functions | Private Member Functions | Private Attributes | List of all members
pmem::detail::concurrent_skip_list< Traits > Class Template Reference

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 ()
 Intialize 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_listoperator= (const concurrent_skip_list &other)
 Copy assignment operator. More...
 
concurrent_skip_listoperator= (concurrent_skip_list &&other)
 Move assignment operator. More...
 
concurrent_skip_listoperator= (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_ptrinternal_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:

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_errorif an object is not in persistent memory.
pmem::transaction_scope_errorif 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]compcomparison function object to use for all comparisons of keys.
[in]allocallocator to use for all memory allocations of this container.
Precondition
must be called in transaction scope.
Exceptions
pmem::pool_errorif an object is not in persistent memory.
pmem::transaction_scope_errorif constructor wasn't called in transaction.
pmem::transaction_alloc_errorwhen 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]firstfirst iterator of inserted range.
[in]lastlast iterator of inserted range.
[in]compcomparison function object to use for all comparisons of keys.
[in]allocallocator 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_errorif an object is not in persistent memory.
pmem::transaction_scope_errorif constructor wasn't called in transaction.
pmem::transaction_alloc_errorwhen allocating memory for inserted elements in transaction failed.
rethrowselement 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]otherreference to the concurrent_skip_list to be copied.
Precondition
must be called in transaction scope.
Postcondition
size() == other.size()
Exceptions
pmem::pool_errorif an object is not in persistent memory.
pmem::transaction_alloc_errorwhen allocating memory for copied elements in transaction failed.
pmem::transaction_scope_errorif constructor wasn't called in transaction.
rethrowselement 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]otherreference to the concurrent_skip_list to be copied.
[in]allocallocator to use for all memory allocations of this container.
Precondition
must be called in transaction scope.
Postcondition
size() == other.size()
Exceptions
pmem::pool_errorif an object is not in persistent memory.
pmem::transaction_alloc_errorwhen allocating memory for copied elements in transaction failed.
pmem::transaction_scope_errorif constructor wasn't called in transaction.
rethrowselement 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]otherreference to the concurrent_skip_list to be copied.
Precondition
must be called in transaction scope.
Postcondition
size() == other.size()
Exceptions
pmem::pool_errorif an object is not in persistent memory.
pmem::transaction_alloc_errorwhen allocating memory for copied elements in transaction failed.
pmem::transaction_scope_errorif constructor wasn't called in transaction.
rethrowselement 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]otherreference to the concurrent_skip_list to be copied.
[in]allocallocator to use for all memory allocations of this container.
Precondition
must be called in transaction scope.
Postcondition
size() == other.size()
Exceptions
pmem::pool_errorif an object is not in persistent memory.
pmem::transaction_alloc_errorwhen allocating memory for copied elements in transaction failed.
pmem::transaction_scope_errorif constructor wasn't called in transaction.
rethrowselement constructor exception.

◆ ~concurrent_skip_list()

template<typename Traits >
pmem::detail::concurrent_skip_list< Traits >::~concurrent_skip_list ( )
inline

Destructor.

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

Member Function Documentation

◆ begin() [1/2]

template<typename Traits >
iterator pmem::detail::concurrent_skip_list< Traits >::begin ( )
inline

Returns an iterator to the first element of the container.

If the map is empty, the returned iterator will be equal to end().

Returns
Iterator to the first element.

◆ begin() [2/2]

template<typename Traits >
const_iterator pmem::detail::concurrent_skip_list< Traits >::begin ( ) const
inline

Returns an iterator to the first element of the container.

If the map is empty, the returned iterator will be equal to end().

Returns
Iterator to the first element.

◆ cbegin()

template<typename Traits >
const_iterator pmem::detail::concurrent_skip_list< Traits >::cbegin ( ) const
inline

Returns an iterator to the first element of the container.

If the map is empty, the returned iterator will be equal to end().

Returns
Iterator to the first element.

◆ cend()

template<typename Traits >
const_iterator pmem::detail::concurrent_skip_list< Traits >::cend ( ) 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.

◆ check_prev_array()

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_errorif 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_errorwhen snapshotting failed.
rethrowsdestructor 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]xa 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]keykey 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]keyalternative 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]keykey 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 allcoated 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]argsarguments 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_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
pmem::transaction_scope_errorif called inside transaction.
rethrowsconstructor 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]hintiterator to the position before which the new element will be inserted.
[in]argsarguments 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_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
pmem::transaction_scope_errorif called inside transaction.
rethrowsconstructor 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]keyalternative 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]xalternative 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]keykey 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]keykey 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_nodesarray of pointers to predecessor nodes on each level.
[out]next_nodesarray of pointers to successor nodes on each level.
[in]keyinserted key.
[in]cmpcomparator 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]xa 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]xa 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]keykey 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]keykey 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]xalternative 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]xalternative 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]keykey 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]keykey 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]xalternative 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]xalternative 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]keykey 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]keykey 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_nodesarray of pointers to predecessor nodes on each level.
[out]next_nodesarray of pointers to successor nodes on each level.
[in]keyinserted 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]keyalternative 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]keyalternative 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]keykey 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]keykey 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]keyalternative 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]keyalternative 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]keykey 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]keykey 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_errorin case of PMDK transaction failure
pmem::transaction_free_errorwhen 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]valueelement 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_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
pmem::transaction_scope_errorif called inside transaction.
rethrowsconstructor 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]hintiterator to the position before which the new element will be inserted.
[in]valueelement value to insert.
Returns
an iterator to the inserted element, or to the element that prevented the insertion.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
pmem::transaction_scope_errorif called inside transaction.
rethrowsconstructor 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]hintiterator to the position before which the new element will be inserted.
[in]valueelement value to insert.
Returns
an iterator to the inserted element, or to the element that prevented the insertion.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
pmem::transaction_scope_errorif called inside transaction.
rethrowsconstructor 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]firstfirst iterator of inserted range.
[in]lastlast iterator of inserted range.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
pmem::transaction_scope_errorif called inside transaction.
rethrowsconstructor 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]valueelement 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_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
pmem::transaction_scope_errorif called inside transaction.
rethrowsconstructor 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]ilistfirst initializer list to insert the values from.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
pmem::transaction_scope_errorif called inside transaction.
rethrowsconstructor 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]valueelement 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_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
pmem::transaction_scope_errorif called inside transaction.
rethrowsconstructor 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]keykey value to compare the elements to.
[in]cmpcomparator 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]keykey value to compare the elements to.
[in]cmpcomparator 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]keykey value to compare the elements to.
[in]cmpcomparator 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]xalternative 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]xalternative 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]keykey 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]keykey 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_errorwhen allocating new memory failed.
pmem::transaction_free_errorwhen freeing old existing elements failed.
rethrowsconstructor 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_errorwhen allocating new memory failed.
pmem::transaction_free_errorwhen freeing old existing elements failed.
rethrowsconstructor 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]ilinitializer list to use as data source
Exceptions
pmem::transaction_alloc_errorwhen allocating new memory failed.
pmem::transaction_free_errorwhen freeing old existing elements failed.
rethrowsconstructor exception.

◆ runtime_initialize()

template<typename Traits >
void pmem::detail::concurrent_skip_list< Traits >::runtime_initialize ( )
inline

Intialize concurrent_skip_list after process restart.

MUST be called everytime 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_errorwhen 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]kthe key used both to look up and to insert if not found.
[in]argsarguments 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_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
pmem::transaction_scope_errorif called inside transaction.
rethrowsconstructor 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]kthe key used both to look up and to insert if not found.
[in]argsarguments 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_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
rethrowsconstructor 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]kthe key used both to look up and to insert if not found.
[in]argsarguments 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_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
pmem::transaction_scope_errorif called inside transaction.
rethrowsconstructor 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]keykey value of the elements to remove.
Returns
Number of elements removed.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
rethrowsdestructor 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]keykey value of the elements to remove.
Returns
Number of elements removed.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
rethrowsdestructor 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]firstfirst iterator in the range of elements to remove.
[in]lastlast iterator in the range of elements to remove.
Returns
iterator following the last removed element.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
rethrowsdestructor 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]positerator to the element to remove.
Returns
iterator following the removed element.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
rethrowsdestructor 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]positerator to the element to remove.
Returns
iterator following the removed element.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
rethrowsdestructor 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]xalternative 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]xalternative 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]keykey 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]keykey 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: