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_tree &	operator= (const radix_tree &m)
	Copy assignment operator. More...

radix_tree &	operator= (radix_tree &&m)
	Move assignment operator. More...

radix_tree &	operator= (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<class... Args>
std::pair< typename radix_tree< Key, Value, BytesView >::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 >::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 >::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 >::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 >::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 >::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 >::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
void	check_pmem ()
	Private helper function. More...

void	check_tx_stage_work ()
	Private helper function. More...

Friends
template<typename K , typename V , typename BV >
std::ostream &	operator<< (std::ostream &os, const radix_tree< K, V, BV > &tree)
	Prints tree in DOT format. More...

Detailed Description

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

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!
};

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.

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 >

pmem::obj::experimental::radix_tree< Key, Value, BytesView >::radix_tree

Default radix tree constructor.

Constructs an empty container.

Precondition: must be called in transaction scope.

Exceptions

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

◆ radix_tree() [2/5]

template<typename Key , typename Value , typename BytesView >

template<class InputIt >

pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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]	first	first iterator of inserted range.
[in]	last	last iterator of inserted range.

InputIt must meet the requirements of LegacyInputIterator.

Precondition: must be called in transaction scope.

Exceptions

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

◆ radix_tree() [3/5]

template<typename Key , typename Value , typename BytesView >

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

Copy constructor.

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

Parameters

[in] m reference to the radix_tree to be copied.

Precondition: must be called in transaction scope.

Exceptions

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

◆ radix_tree() [4/5]

template<typename Key , typename Value , typename BytesView >

pmem::obj::experimental::radix_tree< Key, Value, BytesView >::radix_tree ( radix_tree< Key, Value, BytesView > && 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] m rvalue reference to the radix_tree to be moved from.

Precondition: must be called in transaction scope.

Exceptions

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

◆ radix_tree() [5/5]

template<typename Key , typename Value , typename BytesView >

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

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

Parameters

[in] il initializer list with content to be constructed.

Precondition: must be called in transaction scope.

Exceptions

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

Member Function Documentation

◆ begin() [1/2]

template<typename Key , typename Value , typename BytesView >

radix_tree< Key, Value, BytesView >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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 >

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

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

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

void pmem::obj::experimental::radix_tree< Key, Value, BytesView >::check_pmem

private

Private helper function.

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

Exceptions

pool_error if radix tree doesn't reside on pmem.

◆ check_tx_stage_work()

template<typename Key , typename Value , typename BytesView >

void pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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_error if current transaction stage is not equal to TX_STAGE_WORK.

◆ clear()

template<typename Key , typename Value , typename BytesView >

void pmem::obj::experimental::radix_tree< Key, Value, BytesView >::clear

Erases all elements from the container transactionally.

Postcondition: size() == 0

Exceptions

pmem::transaction_error when snapshotting failed.

◆ count() [1/2]

template<typename Key , typename Value , typename BytesView >

template<typename K , typename >

radix_tree< Key, Value, BytesView >::size_type pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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] k key 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 >

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

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

Parameters

[in] k key 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 >

radix_tree< Key, Value, BytesView >::const_reverse_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::crbegin

Returns a const, reverse iterator to the beginning.

Returns: const_reverse_iterator pointing to the last element in the vector.

◆ crend()

template<typename Key , typename Value , typename BytesView >

radix_tree< Key, Value, BytesView >::const_reverse_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::crend

Returns a const, reverse iterator to the end.

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

◆ emplace()

template<typename Key , typename Value , typename BytesView = detail::bytes_view<Key>>

template<class... Args>

std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool> pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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] args arguments to forward to the constructor of the element

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

Exceptions

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

◆ empty()

template<typename Key , typename Value , typename BytesView >

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

radix_tree< Key, Value, BytesView >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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 >

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

template<typename K , typename >

radix_tree< Key, Value, BytesView >::size_type pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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] k key value of the elements to remove.

Returns: Number of elements removed.

Exceptions

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

◆ erase() [2/4]

template<typename Key , typename Value , typename BytesView >

radix_tree< Key, Value, BytesView >::size_type pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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] k key value of the elements to remove.

Returns: Number of elements removed.

Exceptions

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

◆ erase() [3/4]

template<typename Key , typename Value , typename BytesView >

radix_tree< Key, Value, BytesView >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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]	first	first iterator in the range of elements to remove.
[in]	last	last iterator in the range of elements to remove.

Returns: iterator following the last removed element.

Exceptions

pmem::transaction_error when snapshotting failed.

◆ erase() [4/4]

template<typename Key , typename Value , typename BytesView >

radix_tree< Key, Value, BytesView >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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] pos iterator to the element to remove.

Returns: iterator following the removed element.

Exceptions

pmem::transaction_error when snapshotting failed.

◆ find() [1/4]

template<typename Key , typename Value , typename BytesView >

template<typename K , typename >

radix_tree< Key, Value, BytesView >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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] k key value of the element to search for.

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

◆ find() [2/4]

template<typename Key , typename Value , typename BytesView >

template<typename K , typename >

radix_tree< Key, Value, BytesView >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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] k key 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 >

radix_tree< Key, Value, BytesView >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::find ( const key_type & k )

Finds an element with key equivalent to key.

Parameters

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

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

◆ find() [4/4]

template<typename Key , typename Value , typename BytesView >

radix_tree< Key, Value, BytesView >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::find ( const key_type & k ) const

Finds an element with key equivalent to key.

Parameters

[in] k key 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.

◆ insert() [1/5]

template<typename Key , typename Value , typename BytesView >

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

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

Parameters

[in] v element value to insert.

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

Exceptions

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

◆ insert() [2/5]

template<typename Key , typename Value , typename BytesView >

template<typename InputIterator >

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

Inserts elements from range [first, last).

Parameters

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

Exceptions

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

◆ insert() [3/5]

template<typename Key , typename Value , typename BytesView = detail::bytes_view<Key>>

template<typename P , typename >

std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool> pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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] p element value to insert.

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

Exceptions

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

◆ insert() [4/5]

template<typename Key , typename Value , typename BytesView >

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

Inserts elements from initializer list il.

Parameters

[in] il initializer list to insert the values from.

Exceptions

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

◆ insert() [5/5]

template<typename Key , typename Value , typename BytesView >

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

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

Parameters

[in] v element value to insert.

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

Exceptions

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

◆ insert_or_assign() [1/3]

template<typename Key , typename Value , typename BytesView = detail::bytes_view<Key>>

template<typename M >

std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool> pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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]	k	the key used both to look up and to insert if not found.
[in]	obj	the 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_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
rethrows	constructor exception.

◆ insert_or_assign() [2/3]

template<typename Key , typename Value , typename BytesView = detail::bytes_view<Key>>

template<typename M , typename K , typename >

std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool> pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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]	k	the key used both to look up and to insert if not found.
[in]	obj	the 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_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
rethrows	constructor exception.

◆ insert_or_assign() [3/3]

template<typename Key , typename Value , typename BytesView = detail::bytes_view<Key>>

template<typename M >

std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool> pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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]	k	the key used both to look up and to insert if not found
[in]	obj	the 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_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
rethrows	constructor exception.

◆ lower_bound() [1/4]

template<typename Key , typename Value , typename BytesView >

template<typename K , typename >

radix_tree< Key, Value, BytesView >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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] k key value to compare the elements to.

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

◆ lower_bound() [2/4]

template<typename Key , typename Value , typename BytesView >

template<typename K , typename >

radix_tree< Key, Value, BytesView >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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] k key 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 >

radix_tree< Key, Value, BytesView >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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] k key value to compare the elements to.

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

◆ lower_bound() [4/4]

template<typename Key , typename Value , typename BytesView >

radix_tree< Key, Value, BytesView >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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] k key 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 >

radix_tree< Key, Value, BytesView >::size_type pmem::obj::experimental::radix_tree< Key, Value, BytesView >::max_size

noexcept

Returns: maximum number of elements the container is able to hold

◆ operator=() [1/3]

template<typename Key , typename Value , typename BytesView >

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

Copy assignment operator.

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

Exceptions

pmem::pool_error	if an object is not in persistent memory.
pmem::transaction_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.
rethrows	constructor's exception.

◆ operator=() [2/3]

template<typename Key , typename Value , typename BytesView >

radix_tree< Key, Value, BytesView > & pmem::obj::experimental::radix_tree< Key, Value, BytesView >::operator= ( radix_tree< Key, Value, BytesView > && 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_error	if an object is not in persistent memory.
pmem::transaction_error	when snapshotting failed.

◆ operator=() [3/3]

template<typename Key , typename Value , typename BytesView >

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

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

Parameters

[in] ilist initializer list to use as data source.

Exceptions

pmem::pool_error	if an object is not in persistent memory.
pmem::transaction_error	when snapshotting failed.
pmem::transaction_alloc_error	when allocating new memory failed.

◆ rbegin()

template<typename Key , typename Value , typename BytesView >

radix_tree< Key, Value, BytesView >::reverse_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::rbegin

Returns a reverse iterator to the beginning.

Returns: reverse_iterator pointing to the last element in the vector.

◆ rend()

template<typename Key , typename Value , typename BytesView >

radix_tree< Key, Value, BytesView >::reverse_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::rend

Returns a reverse iterator to the end.

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

◆ size()

template<typename Key , typename Value , typename BytesView >

uint64_t pmem::obj::experimental::radix_tree< Key, Value, BytesView >::size

noexcept

Returns: number of elements.

◆ swap()

template<typename Key , typename Value , typename BytesView >

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

Member swap.

Exchanges *this with

Parameters

rhs

◆ try_emplace() [1/3]

template<typename Key , typename Value , typename BytesView = detail::bytes_view<Key>>

template<class... Args>

std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool> pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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]	k	the key used both to look up and to insert if not found.
[in]	args	arguments to forward to the constructor of the element.

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

Exceptions

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

◆ try_emplace() [2/3]

template<typename Key , typename Value , typename BytesView >

template<typename K , typename BV , class... Args>

auto pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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]	k	the key used both to look up and to insert if not found.
[in]	args	arguments to forward to the constructor of the element.

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

Exceptions

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

◆ try_emplace() [3/3]

template<typename Key , typename Value , typename BytesView = detail::bytes_view<Key>>

template<class... Args>

std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool> pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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]	k	the key used both to look up and to insert if not found.
[in]	args	arguments to forward to the constructor of the element.

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

Exceptions

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

◆ upper_bound() [1/4]

template<typename Key , typename Value , typename BytesView >

template<typename K , typename >

radix_tree< Key, Value, BytesView >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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] k key value to compare the elements to.

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

◆ upper_bound() [2/4]

template<typename Key , typename Value , typename BytesView >

template<typename K , typename >

radix_tree< Key, Value, BytesView >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::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] k key 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 >

radix_tree< Key, Value, BytesView >::iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::upper_bound ( const key_type & k )

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

Parameters

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

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

◆ upper_bound() [4/4]

template<typename Key , typename Value , typename BytesView >

radix_tree< Key, Value, BytesView >::const_iterator pmem::obj::experimental::radix_tree< Key, Value, BytesView >::upper_bound ( const key_type & k ) const

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

Parameters

[in] k key 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.

Friends And Related Function Documentation

◆ operator<<

template<typename Key , typename Value , typename BytesView = detail::bytes_view<Key>>

template<typename K , typename V , typename BV >

std::ostream& operator<<	(	std::ostream &	os,
		const radix_tree< K, V, BV > &	tree
	)

friend

Prints tree in DOT format.

Used for debugging.

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

libpmemobj++/experimental/radix_tree.hpp

Classes

Public Member Functions

Private Member Functions

Friends

Detailed Description

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

Constructor & Destructor Documentation

◆ radix_tree() [1/5]

◆ radix_tree() [2/5]

◆ radix_tree() [3/5]

◆ radix_tree() [4/5]

◆ radix_tree() [5/5]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ check_pmem()

◆ check_tx_stage_work()

◆ clear()

◆ count() [1/2]

◆ count() [2/2]

◆ crbegin()

◆ crend()

◆ emplace()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/4]

◆ erase() [2/4]

◆ erase() [3/4]

◆ erase() [4/4]

◆ find() [1/4]

◆ find() [2/4]

◆ find() [3/4]

◆ find() [4/4]

◆ insert() [1/5]

◆ insert() [2/5]

◆ insert() [3/5]

◆ insert() [4/5]

◆ insert() [5/5]

◆ insert_or_assign() [1/3]

◆ insert_or_assign() [2/3]

◆ insert_or_assign() [3/3]

◆ lower_bound() [1/4]

◆ lower_bound() [2/4]

◆ lower_bound() [3/4]

◆ lower_bound() [4/4]

◆ max_size()

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ rbegin()

◆ rend()

◆ size()

◆ swap()

◆ try_emplace() [1/3]

◆ try_emplace() [2/3]

◆ try_emplace() [3/3]

◆ upper_bound() [1/4]

◆ upper_bound() [2/4]

◆ upper_bound() [3/4]

◆ upper_bound() [4/4]

Friends And Related Function Documentation

◆ operator<<

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