radix_tree.hpp File Reference

Implementation of persistent radix tree. More...

#include <libpmemobj++/allocator.hpp>
#include <libpmemobj++/container/string.hpp>
#include <libpmemobj++/detail/pair.hpp>
#include <libpmemobj++/detail/template_helpers.hpp>
#include <libpmemobj++/experimental/inline_string.hpp>
#include <libpmemobj++/experimental/self_relative_ptr.hpp>
#include <libpmemobj++/make_persistent.hpp>
#include <libpmemobj++/p.hpp>
#include <libpmemobj++/persistent_ptr.hpp>
#include <libpmemobj++/pext.hpp>
#include <libpmemobj++/pool.hpp>
#include <libpmemobj++/string_view.hpp>
#include <libpmemobj++/transaction.hpp>
#include <libpmemobj++/utils.hpp>
#include <algorithm>
#include <iostream>
#include <string>
#include <libpmemobj++/detail/common.hpp>
#include <libpmemobj++/detail/integer_sequence.hpp>

Go to the source code of this file.

Classes
class	pmem::obj::experimental::radix_tree< Key, Value, BytesView >
	Radix tree is an associative, ordered container. More...
struct	pmem::obj::experimental::radix_tree< Key, Value, BytesView >::leaf
	This is the structure which 'holds' key/value pair. More...
struct	pmem::obj::experimental::radix_tree< Key, Value, BytesView >::node
	This is internal node. More...
struct	pmem::obj::experimental::radix_tree< Key, Value, BytesView >::radix_tree_iterator< IsConst >
	Radix tree iterator supports multipass and bidirectional iteration. More...

Namespaces
	pmem
	Persistent memory namespace.
	pmem::detail
	Implementation details.
	pmem::obj
	Main libpmemobj namespace.
	pmem::obj::experimental
	Experimental implementations.

Functions
template<typename Key , typename Value , typename BytesView >
void	pmem::obj::experimental::swap (radix_tree< Key, Value, BytesView > &lhs, radix_tree< Key, Value, BytesView > &rhs)
	Non-member swap.
template<typename K , typename V , typename BV >
std::ostream &	pmem::obj::experimental::operator<< (std::ostream &os, const radix_tree< K, V, BV > &tree)
	Prints tree in DOT format. More...

Detailed Description

Implementation of persistent radix tree.

Based on: https://github.com/pmem/vmemcache/blob/master/src/critnib.h

The implementation is a variation of a PATRICIA trie - the internal nodes do not store the path explicitly, but only a position at which the keys differ. Keys are stored entirely in leaves.

More info about radix tree: https://en.wikipedia.org/wiki/Radix_tree