PMDK C++ bindings  1.13.0-git85.g2ab46040
This is the C++ bindings documentation for PMDK's libpmemobj.
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 ()
 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_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...
 

Static Public Attributes

static constexpr bool allow_multimapping
 

Protected Types

using traits_type = Traits
 
using key_type = typename traits_type::key_type
 
using mapped_type = typename traits_type::mapped_type
 
using value_type = typename traits_type::value_type
 
using size_type = std::size_t
 
using difference_type = std::ptrdiff_t
 
using key_compare = typename traits_type::compare_type
 
using allocator_type = typename traits_type::allocator_type
 
using allocator_traits_type = std::allocator_traits< allocator_type >
 
using reference = value_type &
 
using const_reference = const value_type &
 
using pointer = typename allocator_traits_type::pointer
 
using const_pointer = typename allocator_traits_type::const_pointer
 
using list_node_type = skip_list_node< value_type >
 
using iterator = skip_list_iterator< list_node_type, false >
 
using const_iterator = skip_list_iterator< list_node_type, true >
 
using random_level_generator_type = geometric_level_generator< typename traits_type::random_generator_type, MAX_LEVEL >
 
using node_allocator_type = typename std::allocator_traits< allocator_type >::template rebind_alloc< uint8_t >
 
using node_allocator_traits = typename std::allocator_traits< allocator_type >::template rebind_traits< uint8_t >
 
using node_ptr = list_node_type *
 
using const_node_ptr = const list_node_type *
 
using persistent_node_ptr = obj::experimental::self_relative_ptr< list_node_type >
 
using prev_array_type = std::array< node_ptr, MAX_LEVEL >
 
using next_array_type = std::array< persistent_node_ptr, MAX_LEVEL >
 
using node_lock_type = typename list_node_type::lock_type
 
using lock_array = std::array< node_lock_type, MAX_LEVEL >
 

Static Protected Attributes

static constexpr size_type MAX_LEVEL = traits_type::max_level
 

Detailed Description

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

Persistent memory aware implementation of the concurrent skip list.

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

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

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

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

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

Constructor & Destructor Documentation

◆ concurrent_skip_list() [1/7]

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

Default constructor.

Construct empty skip list.

Precondition
must be called in transaction scope.
Exceptions
pmem::pool_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.

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

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

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

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

◆ 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

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

◆ 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

◆ allow_multimapping

template<typename Traits >
constexpr bool pmem::detail::concurrent_skip_list< Traits >::allow_multimapping
staticconstexpr
Initial value:
=
traits_type::allow_multimapping

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