PMDK C++ bindings  1.13.0-git23.gf49772ac
This is the C++ bindings documentation for PMDK's libpmemobj.
Classes | Public Member Functions | Private Member Functions | List of all members
pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode > Class Template Reference

Radix tree is an associative, ordered container. More...

#include <libpmemobj++/experimental/radix_tree.hpp>

Classes

struct  leaf
 This is the structure which 'holds' key/value pair. More...
 
struct  node
 This is internal node. More...
 
struct  radix_tree_iterator
 Radix tree iterator supports multipass and bidirectional iteration. More...
 

Public Member Functions

 radix_tree ()
 Default radix tree constructor. More...
 
template<class InputIt >
 radix_tree (InputIt first, InputIt last)
 Constructs the container with the contents of the range [first, last). More...
 
 radix_tree (const radix_tree &m)
 Copy constructor. More...
 
 radix_tree (radix_tree &&m)
 Move constructor. More...
 
 radix_tree (std::initializer_list< value_type > il)
 Constructs the container with the contents of the initializer list init. More...
 
radix_treeoperator= (const radix_tree &m)
 Copy assignment operator. More...
 
radix_treeoperator= (radix_tree &&m)
 Move assignment operator. More...
 
radix_treeoperator= (std::initializer_list< value_type > ilist)
 Replaces the contents with those identified by initializer list ilist transactionally. More...
 
 ~radix_tree ()
 Destructor.
 
std::pair< iterator, bool > insert (const value_type &v)
 Inserts element if the tree doesn't already contain an element with an equivalent key. More...
 
std::pair< iterator, bool > insert (value_type &&v)
 Inserts element using move semantic if the tree doesn't already contain an element with an equivalent key. More...
 
template<class InputIterator >
void insert (InputIterator first, InputIterator last)
 Inserts elements from range [first, last). More...
 
void insert (std::initializer_list< value_type > il)
 Inserts elements from initializer list il. More...
 
template<typename K , typename BV = BytesView, class... Args>
auto try_emplace (K &&k, Args &&... args) -> typename std::enable_if< detail::has_is_transparent< BV >::value &&!std::is_same< typename std::remove_const< typename std::remove_reference< K >::type >::type, key_type >::value, std::pair< iterator, bool >>::type
 If a key equivalent to k already exists in the container, does nothing. More...
 
iterator erase (const_iterator pos)
 Removes the element at pos from the container. More...
 
iterator 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 erase (const key_type &k)
 Removes the element (if one exists) with the key equivalent to key. More...
 
template<typename K , typename = typename std::enable_if< detail::has_is_transparent<BytesView>::value && !std::is_same<K, iterator>::value && !std::is_same<K, const_iterator>::value, K>::type>
size_type erase (const K &k)
 Removes the element (if one exists) with the key equivalent to key. More...
 
void clear ()
 Erases all elements from the container transactionally. More...
 
size_type count (const key_type &k) const
 Returns the number of elements with key that compares equivalent to the specified argument. More...
 
template<typename K , typename = typename std::enable_if< detail::has_is_transparent<BytesView>::value, K>::type>
size_type count (const K &k) const
 Returns the number of elements with key that compares equivalent to the specified argument. More...
 
iterator find (const key_type &k)
 Finds an element with key equivalent to key. More...
 
const_iterator find (const key_type &k) const
 Finds an element with key equivalent to key. More...
 
template<typename K , typename = typename std::enable_if< detail::has_is_transparent<BytesView>::value, K>::type>
iterator find (const K &k)
 Finds an element with key equivalent to key. More...
 
template<typename K , typename = typename std::enable_if< detail::has_is_transparent<BytesView>::value, K>::type>
const_iterator find (const K &k) const
 Finds an element with key equivalent to key. More...
 
iterator lower_bound (const key_type &k)
 Returns an iterator pointing to the first element that is not less than (i.e. More...
 
const_iterator lower_bound (const key_type &k) 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< detail::has_is_transparent<BytesView>::value, K>::type>
iterator lower_bound (const K &k)
 Returns an iterator pointing to the first element that is not less than (i.e. More...
 
template<typename K , typename = typename std::enable_if< detail::has_is_transparent<BytesView>::value, K>::type>
const_iterator lower_bound (const K &k) const
 Returns an iterator pointing to the first element that is not less than (i.e. More...
 
iterator upper_bound (const key_type &k)
 Returns an iterator pointing to the first element that is greater than key. More...
 
const_iterator upper_bound (const key_type &k) const
 Returns an iterator pointing to the first element that is greater than key. More...
 
template<typename K , typename = typename std::enable_if< detail::has_is_transparent<BytesView>::value, K>::type>
iterator upper_bound (const K &k)
 Returns an iterator pointing to the first element that is greater than key. More...
 
template<typename K , typename = typename std::enable_if< detail::has_is_transparent<BytesView>::value, K>::type>
const_iterator upper_bound (const K &k) const
 Returns an iterator pointing to the first element that is greater than key. More...
 
iterator begin ()
 Returns an iterator to the first element of the container. More...
 
iterator end ()
 Returns an iterator to the element following the last element of the map. More...
 
const_iterator cbegin () const
 Returns a const iterator to the first element of the container. More...
 
const_iterator cend () const
 Returns a const iterator to the element following the last element of the map. More...
 
const_iterator begin () const
 Returns a const iterator to the first element of the container. More...
 
const_iterator end () const
 Returns a const iterator to the element following the last element of the map. More...
 
reverse_iterator rbegin ()
 Returns a reverse iterator to the beginning. More...
 
reverse_iterator rend ()
 Returns a reverse iterator to the end. More...
 
const_reverse_iterator crbegin () const
 Returns a const, reverse iterator to the beginning. More...
 
const_reverse_iterator crend () const
 Returns a const, reverse iterator to the end. More...
 
bool empty () const noexcept
 Checks whether the container is empty. More...
 
size_type max_size () const noexcept
 
uint64_t size () const noexcept
 
void swap (radix_tree &rhs)
 Member swap. More...
 
template<bool Mt = MtMode, typename Enable = typename std::enable_if<Mt>::type>
void garbage_collect ()
 Tries to collect and free some garbage produced by erase, clear, insert_or_assign or assign_val in concurrent mode (if MtMode == true). More...
 
template<bool Mt = MtMode, typename Enable = typename std::enable_if<Mt>::type>
void garbage_collect_force ()
 Performs full epochs synchronisation. More...
 
template<bool Mt = MtMode, typename Enable = typename std::enable_if<Mt>::type>
void runtime_initialize_mt (ebr *e=new ebr())
 If MtMode == true, this function must be called after each application restart. More...
 
template<bool Mt = MtMode, typename Enable = typename std::enable_if<Mt>::type>
void runtime_finalize_mt ()
 If MtMode == true, this function must be called before each application close and before calling radix destructor or there will be possible a memory leak.
 
template<bool Mt = MtMode, typename Enable = typename std::enable_if<Mt>::type>
worker_type register_worker ()
 Registers and returns a new worker, which can perform critical operations (accessing some shared data that can be removed in other threads). More...
 
template<class... Args>
std::pair< typename radix_tree< Key, Value, BytesView, MtMode >::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<class... Args>
std::pair< typename radix_tree< Key, Value, BytesView, MtMode >::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 P , typename >
std::pair< typename radix_tree< Key, Value, BytesView, MtMode >::iterator, bool > insert (P &&p)
 Inserts element if the tree doesn't already contain an element with an equivalent key. More...
 
template<class... Args>
std::pair< typename radix_tree< Key, Value, BytesView, MtMode >::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 M >
std::pair< typename radix_tree< Key, Value, BytesView, MtMode >::iterator, bool > insert_or_assign (const key_type &k, M &&obj)
 If a key equivalent to k already exists in the container, assigns std::forward<M>(obj) to the mapped_type corresponding to the key k. More...
 
template<typename M >
std::pair< typename radix_tree< Key, Value, BytesView, MtMode >::iterator, bool > insert_or_assign (key_type &&k, M &&obj)
 If a key equivalent to k already exists in the container, assigns std::forward<M>(obj) to the mapped_type corresponding to the key k. More...
 
template<typename M , typename K , typename >
std::pair< typename radix_tree< Key, Value, BytesView, MtMode >::iterator, bool > insert_or_assign (K &&k, M &&obj)
 If a key equivalent to k already exists in the container, assigns std::forward<M>(obj) to the mapped_type corresponding to the key k. More...
 

Private Member Functions

template<bool Lower, typename K >
bool validate_bound (const_iterator it, const K &key) const
 Checks if iterator points to element which compares bigger (or equal) to key.
 
template<bool Mt = MtMode>
std::enable_if< Mt, bool >::type validate_path (const path_type &path) const
 Checks if any node in the. More...
 
template<typename T >
void free (persistent_ptr< T > ptr)
 Deletes node/leaf pointed by ptr. More...
 
void check_pmem ()
 Private helper function. More...
 
void check_tx_stage_work ()
 Private helper function. More...
 

Detailed Description

template<typename Key, typename Value, typename BytesView = bytes_view<Key>, bool MtMode = false>
class pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >

Radix tree is an associative, ordered container.

Its API is similar to the API of std::map.

Unlike std::map radix tree does not use comparison (std::less or equivalent) to locate elements. Instead, keys are mapped to a sequence of bytes using user-provided BytesView type. The key's bytes uniquely define the position of an element. In some way, it is similar to a hash table (BytesView can be treated as a hash function) but with sorted elements.

The elements' ordering is defined based on the BytesView mapping. The byte sequences are compared using a function equivalent to std::string::compare.

BytesView should accept a pointer to the key type in a constructor and provide operator[] (should return a byte at the specified position in the byte representation of value) and size (should return size of value in bytes) method. The declaration should be as following:

struct BytesView {
BytesView(const Type* t);
char operator[](size_t pos) const; // Must be const!
size_t size() const; // Must be const!
};
uint64_t size() const noexcept
Definition: radix_tree.hpp:961

By default, implementation for pmem::obj::basic_inline_string<CharT, Traits> and unsigned integral types is provided. Note that integral types are assumed to be in little-endian.

Iterators and references are stable (are not invalidated by inserts or erases of other elements nor by assigning to the value) for all value types except basic_inline_string<CharT, Traits>.

In case of basic_inline_string<CharT, Traits>, iterators and references are not invalidated by other inserts or erases, but might be invalidated by assigning new value to the element. Using find(K).assign_val("new_value") may invalidate other iterators and references to the element with key K.

swap() invalidates all references and iterators.

MtMode enables single-writer multiple-readers concurrency with read uncommitted isolation. In this, mode user HAS TO call runtime_initialize_mt after each application restart and runtime_finalize_mt before destroying radix tree.

Enabling MtMode has the following effects:

By default, concurrency is not enabled (it is not allowed to perform concurrent operations on radix tree).

An example of custom BytesView implementation:

struct custom_key {
int x;
int y;
};
struct custom_bytes_view {
custom_bytes_view(const custom_key *k)
{
auto *x = reinterpret_cast<const char *>(&k->x);
auto *y = reinterpret_cast<const char *>(&k->y);
for (int i = 0; i < 4; i++)
bytes[i] = x[sizeof(int) - i - 1];
for (int i = 0; i < 4; i++)
bytes[i + 4] = y[sizeof(int) - i - 1];
}
/* Note that this function MUST be marked as const */
char operator[](size_t pos) const
{
return bytes[pos];
}
/* Note that this function MUST be marked as const */
size_t
size() const
{
return sizeof(custom_key);
}
char bytes[sizeof(custom_key)];
};

Constructor & Destructor Documentation

◆ radix_tree() [1/5]

template<typename Key , typename Value , typename BytesView , bool MtMode>
pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::radix_tree

Default radix tree constructor.

Constructs an empty 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.

◆ radix_tree() [2/5]

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<class InputIt >
pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::radix_tree ( InputIt  first,
InputIt  last 
)

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.

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.

◆ radix_tree() [3/5]

template<typename Key , typename Value , typename BytesView , bool MtMode>
pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::radix_tree ( const radix_tree< Key, Value, BytesView, MtMode > &  m)

Copy constructor.

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

Parameters
[in]mreference to the radix_tree to be copied.
Precondition
must be called in transaction scope.
Exceptions
pmem::pool_errorif an object is not in persistent memory.
pmem::transaction_alloc_errorwhen allocating memory in transaction failed.
pmem::transaction_scope_errorif constructor wasn't called in transaction.
rethrowselement constructor exception.

◆ radix_tree() [4/5]

template<typename Key , typename Value , typename BytesView , bool MtMode>
pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::radix_tree ( radix_tree< Key, Value, BytesView, MtMode > &&  m)

Move constructor.

Constructs the container with the contents of other using move semantics. After the move, other is guaranteed to be empty().

Parameters
[in]mrvalue reference to the radix_tree to be moved from.
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.

◆ radix_tree() [5/5]

template<typename Key , typename Value , typename BytesView , bool MtMode>
pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::radix_tree ( std::initializer_list< value_type >  il)

Constructs the container with the contents of the initializer list init.

Parameters
[in]ilinitializer list with content to be constructed.
Precondition
must be called in transaction scope.
Exceptions
pmem::pool_errorif an object is not in persistent memory.
pmem::transaction_alloc_errorwhen allocating memory in transaction failed.
pmem::transaction_scope_errorif constructor wasn't called in transaction.
rethrowselement constructor exception.

Member Function Documentation

◆ begin() [1/2]

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::begin

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 Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::begin

Returns a const iterator to the first element of the container.

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

Returns
const iterator to the first element.

◆ cbegin()

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::cbegin

Returns a const iterator to the first element of the container.

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

Returns
const iterator to the first element.

◆ cend()

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::cend

Returns a const 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
const iterator to the element following the last element.

◆ check_pmem()

template<typename Key , typename Value , typename BytesView , bool MtMode>
void pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::check_pmem
private

Private helper function.

Checks if radix tree resides on pmem and throws an exception if not.

Exceptions
pool_errorif radix tree doesn't reside on pmem.

◆ check_tx_stage_work()

template<typename Key , typename Value , typename BytesView , bool MtMode>
void pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::check_tx_stage_work
private

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 Key , typename Value , typename BytesView , bool MtMode>
void pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::clear

Erases all elements from the container transactionally.

Postcondition
size() == 0
Exceptions
pmem::transaction_errorwhen snapshotting failed.

◆ count() [1/2]

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<typename K , typename >
radix_tree< Key, Value, BytesView, MtMode >::size_type pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::count ( const K &  k) const

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

This overload only participates in overload resolution if BytesView struct has a type member named is_transparent.

Parameters
[in]kkey value of the element to count.
Returns
Number of elements with key that compares equivalent to the specified argument.

◆ count() [2/2]

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::size_type pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::count ( const key_type &  k) const

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

Parameters
[in]kkey value of the element to count.
Returns
Number of elements with key that compares equivalent to the specified argument.

◆ crbegin()

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::const_reverse_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::crbegin

Returns a const, reverse iterator to the beginning.

Using reverse iterators in concurrent environment is not safe.

Returns
const_reverse_iterator pointing to the last element in the vector.

◆ crend()

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::const_reverse_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::crend

Returns a const, reverse iterator to the end.

Using reverse iterators in concurrent environment is not safe.

Returns
const_reverse_iterator pointing to the theoretical element preceding the first element in the vector.

◆ emplace()

template<typename Key , typename Value , typename BytesView = bytes_view<Key>, bool MtMode = false>
template<class... Args>
std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool> pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::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.

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

◆ empty()

template<typename Key , typename Value , typename BytesView , bool MtMode>
bool pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::empty
noexcept

Checks whether the container is empty.

Returns
true if container is empty, false otherwise.

◆ end() [1/2]

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::end

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 Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::end

Returns a const 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
const iterator to the element following the last element.

◆ erase() [1/4]

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<typename K , typename >
radix_tree< Key, Value, BytesView, MtMode >::size_type pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::erase ( const K &  k)

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 BytesView struct has a type member named is_transparent.

Parameters
[in]kkey value of the elements to remove
Returns
Number of elements removed.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
rethrowsdestructor exception.

◆ erase() [2/4]

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::size_type pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::erase ( const key_type &  k)

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]kkey value of the elements to remove.
Returns
Number of elements removed.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
rethrowsdestructor exception.

◆ erase() [3/4]

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::erase ( const_iterator  first,
const_iterator  last 
)

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.

◆ erase() [4/4]

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::erase ( const_iterator  pos)

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.

◆ find() [1/4]

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<typename K , typename >
radix_tree< Key, Value, BytesView, MtMode >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::find ( const K &  k)

Finds an element with key equivalent to key.

This overload only participates in overload resolution if BytesView struct has a type member named is_transparent.

Parameters
[in]kkey 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() [2/4]

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<typename K , typename >
radix_tree< Key, Value, BytesView, MtMode >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::find ( const K &  k) const

Finds an element with key equivalent to key.

This overload only participates in overload resolution if BytesView struct has a type member named is_transparent.

Parameters
[in]kkey value of the element to search for.
Returns
Const 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 Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::find ( const key_type &  k)

Finds an element with key equivalent to key.

Parameters
[in]kkey 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 Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::find ( const key_type &  k) const

Finds an element with key equivalent to key.

Parameters
[in]kkey value of the element to search for.
Returns
Const iterator to an element with key equivalent to key. If no such element is found, past-the-end iterator is returned.

◆ free()

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<typename T >
void pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::free ( persistent_ptr< T >  ptr)
private

Deletes node/leaf pointed by ptr.

If concurrent mode is used, adds element to the garbage list. Otherwise, frees the element immediately.

◆ garbage_collect()

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<bool Mt, typename Enable >
void pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::garbage_collect

Tries to collect and free some garbage produced by erase, clear, insert_or_assign or assign_val in concurrent mode (if MtMode == true).

It is not guaranteed that this method will free any memory. It depends on operations currently performed by other threads.

Garbage is not automatically collected on move/copy ctor/assignment.

Exceptions
pmem::transaction_errorwhen snapshotting failed.

◆ garbage_collect_force()

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<bool Mt, typename Enable >
void pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::garbage_collect_force

Performs full epochs synchronisation.

Transactionally collects and frees all garbage produced by erase, clear, insert_or_assign or assign_val in concurrent mode (if MtMode == true).

Garbage is not automatically collected on move/copy ctor/assignment.

Exceptions
pmem::transaction_errorwhen snapshotting failed.

◆ insert() [1/5]

template<typename Key , typename Value , typename BytesView , bool MtMode>
std::pair< typename radix_tree< Key, Value, BytesView, MtMode >::iterator, bool > pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::insert ( const value_type &  v)

Inserts element if the tree doesn't already contain an element with an equivalent key.

Parameters
[in]velement 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.
rethrowsconstructor exception.

◆ insert() [2/5]

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<typename InputIterator >
void pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::insert ( InputIterator  first,
InputIterator  last 
)

Inserts elements from range [first, last).

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

◆ insert() [3/5]

template<typename Key , typename Value , typename BytesView = bytes_view<Key>, bool MtMode = false>
template<typename P , typename >
std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool> pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::insert ( P &&  p)

Inserts element if the tree doesn't already contain an element with an equivalent key.

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]pelement 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.
rethrowsconstructor exception.

◆ insert() [4/5]

template<typename Key , typename Value , typename BytesView , bool MtMode>
void pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::insert ( std::initializer_list< value_type >  il)

Inserts elements from initializer list il.

Parameters
[in]ilinitializer list to insert the values from.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
rethrowsconstructor exception.

◆ insert() [5/5]

template<typename Key , typename Value , typename BytesView , bool MtMode>
std::pair< typename radix_tree< Key, Value, BytesView, MtMode >::iterator, bool > pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::insert ( value_type &&  v)

Inserts element using move semantic if the tree doesn't already contain an element with an equivalent key.

Parameters
[in]velement 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.
rethrowsconstructor exception.

◆ insert_or_assign() [1/3]

template<typename Key , typename Value , typename BytesView = bytes_view<Key>, bool MtMode = false>
template<typename M >
std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool> pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::insert_or_assign ( const key_type &  k,
M &&  obj 
)

If a key equivalent to k already exists in the container, assigns std::forward<M>(obj) to the mapped_type corresponding to the key k.

If the key does not exist, inserts the new value as if by insert, constructing it from value_type(k, std::forward<M>(obj)).

Parameters
[in]kthe key used both to look up and to insert if not found.
[in]objthe value to insert or assign.
Returns
std::pair<iterator,bool> The bool component is true if the insertion took place and false if the assignment took place. The iterator component is pointing at the element that was inserted or updated.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
rethrowsconstructor exception.

◆ insert_or_assign() [2/3]

template<typename Key , typename Value , typename BytesView = bytes_view<Key>, bool MtMode = false>
template<typename M , typename K , typename >
std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool> pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::insert_or_assign ( K &&  k,
M &&  obj 
)

If a key equivalent to k already exists in the container, assigns std::forward<M>(obj) to the mapped_type corresponding to the key k.

If the key does not exist, inserts the new value as if by insert, constructing it from value_type(std::forward<K>(k), std::forward<M>(obj)).

This overload only participates in overload resolution if BytesView struct has a type member named is_transparent.

Parameters
[in]kthe key used both to look up and to insert if not found.
[in]objthe value to insert or assign.
Returns
std::pair<iterator,bool> The bool component is true if the insertion took place and false if the assignment took place. The iterator component is pointing at the element that was inserted or updated.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
rethrowsconstructor exception.

◆ insert_or_assign() [3/3]

template<typename Key , typename Value , typename BytesView = bytes_view<Key>, bool MtMode = false>
template<typename M >
std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool> pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::insert_or_assign ( key_type &&  k,
M &&  obj 
)

If a key equivalent to k already exists in the container, assigns std::forward<M>(obj) to the mapped_type corresponding to the key k.

If the key does not exist, inserts the new value as if by insert, constructing it from value_type(std::move(k), std::forward<M>(obj))

Parameters
[in]kthe key used both to look up and to insert if not found
[in]objthe value to insert or assign
Returns
std::pair<iterator,bool> The bool component is true if the insertion took place and false if the assignment took place. The iterator component is pointing at the element that was inserted or updated.
Exceptions
pmem::transaction_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
rethrowsconstructor exception.

◆ lower_bound() [1/4]

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<typename K , typename >
radix_tree< Key, Value, BytesView, MtMode >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::lower_bound ( const K &  k)

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

greater or equal to) key.

This overload only participates in overload resolution if BytesView struct has a type member named is_transparent.

Parameters
[in]kkey 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() [2/4]

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<typename K , typename >
radix_tree< Key, Value, BytesView, MtMode >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::lower_bound ( const K &  k) const

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

greater or equal to) key.

This overload only participates in overload resolution if BytesView struct has a type member named is_transparent.

Parameters
[in]kkey value to compare the elements to.
Returns
Const 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 Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::lower_bound ( const key_type &  k)

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

greater or equal to) key.

Parameters
[in]kkey 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 Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::lower_bound ( const key_type &  k) const

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

greater or equal to) key.

Parameters
[in]kkey value to compare the elements to.
Returns
Const 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 Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::size_type pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::max_size
noexcept
Returns
maximum number of elements the container is able to hold

◆ operator=() [1/3]

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode > & pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::operator= ( const radix_tree< Key, Value, BytesView, MtMode > &  other)

Copy assignment operator.

Replaces the contents with a copy of the contents of other transactionally.

Exceptions
pmem::pool_errorif an object is not in persistent memory.
pmem::transaction_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.
rethrowsconstructor's exception.

◆ operator=() [2/3]

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode > & pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::operator= ( radix_tree< Key, Value, BytesView, MtMode > &&  other)

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) transactionally. Other is in a valid but empty state afterwards.

Exceptions
pmem::pool_errorif an object is not in persistent memory.
pmem::transaction_errorwhen snapshotting failed.

◆ operator=() [3/3]

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode > & pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::operator= ( std::initializer_list< value_type >  ilist)

Replaces the contents with those identified by initializer list ilist transactionally.

Parameters
[in]ilistinitializer list to use as data source.
Exceptions
pmem::pool_errorif an object is not in persistent memory.
pmem::transaction_errorwhen snapshotting failed.
pmem::transaction_alloc_errorwhen allocating new memory failed.

◆ rbegin()

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::reverse_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::rbegin

Returns a reverse iterator to the beginning.

Using reverse iterators in concurrent environment is not safe.

Returns
reverse_iterator pointing to the last element in the vector.

◆ register_worker()

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<bool Mt, typename Enable >
radix_tree< Key, Value, BytesView, MtMode >::worker_type pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::register_worker

Registers and returns a new worker, which can perform critical operations (accessing some shared data that can be removed in other threads).

There can be only one worker per thread. The worker will be automatically unregistered in the destructor.

Returns
new registered worker.

◆ rend()

template<typename Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::reverse_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::rend

Returns a reverse iterator to the end.

Using reverse iterators in concurrent environment is not safe.

Returns
reverse_iterator pointing to the theoretical element preceding the first element in the vector.

◆ runtime_initialize_mt()

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<bool Mt, typename Enable >
void pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::runtime_initialize_mt ( ebr e = new ebr())

If MtMode == true, this function must be called after each application restart.

It is necessary to call runtime_finalize_mt() before closing the application.

Parameters
[in]epointer to already created ebr, default it will be created automatically.

◆ size()

template<typename Key , typename Value , typename BytesView , bool MtMode>
uint64_t pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::size
noexcept
Returns
number of elements.

◆ swap()

template<typename Key , typename Value , typename BytesView , bool MtMode>
void pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::swap ( radix_tree< Key, Value, BytesView, MtMode > &  rhs)

Member swap.

Exchanges *this with

Parameters
rhs

◆ try_emplace() [1/3]

template<typename Key , typename Value , typename BytesView = bytes_view<Key>, bool MtMode = false>
template<class... Args>
std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool> pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::try_emplace ( const key_type &  k,
Args &&...  args 
)

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

Unlike insert or emplace, this method do not move from rvalue arguments if the insertion does not happen, which makes it easy to manipulate maps whose values are move-only types. In addition, try_emplace treats the key and the arguments to the mapped_type separately, unlike emplace, which requires the arguments to construct a value_type (that is, a std::pair).

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() [2/3]

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<typename K , typename BV , class... Args>
auto pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::try_emplace ( K &&  k,
Args &&...  args 
) -> typename std::enable_if< detail::has_is_transparent<BV>::value && !std::is_same<typename std::remove_const< typename std::remove_reference< K>::type>::type, key_type>::value, std::pair<iterator, bool>>::type

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::forward<K>(k)), std::forward_as_tuple(std::forward<Args>(args)...)).

Unlike insert or emplace, this method do not move from rvalue arguments if the insertion does not happen, which makes it easy to manipulate maps whose values are move-only types. In addition, try_emplace treats the key and the arguments to the mapped_type separately, unlike emplace, which requires the arguments to construct a value_type (that is, a std::pair).

This overload only participates in overload resolution if BytesView struct has a type member named is_transparent.

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 Key , typename Value , typename BytesView = bytes_view<Key>, bool MtMode = false>
template<class... Args>
std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool> pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::try_emplace ( key_type &&  k,
Args &&...  args 
)

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

Unlike insert or emplace, this method do not move from rvalue arguments if the insertion does not happen, which makes it easy to manipulate maps whose values are move-only types. In addition, try_emplace treats the key and the arguments to the mapped_type separately, unlike emplace, which requires the arguments to construct a value_type (that is, a std::pair).

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.

◆ upper_bound() [1/4]

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<typename K , typename >
radix_tree< Key, Value, BytesView, MtMode >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::upper_bound ( const K &  k)

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

This overload only participates in overload resolution if BytesView struct has a type member named is_transparent.

Parameters
[in]kkey 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() [2/4]

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<typename K , typename >
radix_tree< Key, Value, BytesView, MtMode >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::upper_bound ( const K &  k) const

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

This overload only participates in overload resolution if BytesView struct has a type member named is_transparent.

Parameters
[in]kkey value to compare the elements to.
Returns
Const 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 Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::upper_bound ( const key_type &  k)

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

Parameters
[in]kkey 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 Key , typename Value , typename BytesView , bool MtMode>
radix_tree< Key, Value, BytesView, MtMode >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::upper_bound ( const key_type &  k) const

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

Parameters
[in]kkey value to compare the elements to.
Returns
Const iterator pointing to the first element that is greater than key. If no such element is found, a past-the-end iterator is returned.

◆ validate_path()

template<typename Key , typename Value , typename BytesView , bool MtMode>
template<bool Mt>
std::enable_if<!Mt, bool >::type pmem::obj::experimental::radix_tree< Key, Value, BytesView, MtMode >::validate_path ( const path_type &  path) const
private

Checks if any node in the.

Parameters
pathwas modified.

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