radix_tree.hpp

Go to the documentation of this file.

// SPDX-License-Identifier: BSD-3-Clause
/* Copyright 2020-2022, Intel Corporation */
 
#ifndef LIBPMEMOBJ_CPP_RADIX_HPP
#define LIBPMEMOBJ_CPP_RADIX_HPP
 
#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>
#if __cpp_lib_endian
#include <bit>
#endif
 
#include <libpmemobj++/detail/common.hpp>
#include <libpmemobj++/detail/integer_sequence.hpp>
 
namespace pmem
{
 
namespace detail
{
template <typename T, typename Enable = void>
struct bytes_view;
}
 
namespace obj
{
 
namespace experimental
{
 
template <typename Key, typename Value,
      typename BytesView = detail::bytes_view<Key>>
class radix_tree {
    template <bool IsConst>
    struct radix_tree_iterator;
 
public:
    using key_type = Key;
    using mapped_type = Value;
    using value_type = detail::pair<const key_type, mapped_type>;
    using size_type = std::size_t;
    using reference = value_type &;
    using const_reference = const value_type &;
    using iterator = radix_tree_iterator<false>;
    using const_iterator = radix_tree_iterator<true>;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
    using difference_type = std::ptrdiff_t;
 
    radix_tree();
 
    template <class InputIt>
    radix_tree(InputIt first, InputIt last);
    radix_tree(const radix_tree &m);
    radix_tree(radix_tree &&m);
    radix_tree(std::initializer_list<value_type> il);
 
    radix_tree &operator=(const radix_tree &m);
    radix_tree &operator=(radix_tree &&m);
    radix_tree &operator=(std::initializer_list<value_type> ilist);
 
    ~radix_tree();
 
    template <class... Args>
    std::pair<iterator, bool> emplace(Args &&... args);
 
    std::pair<iterator, bool> insert(const value_type &v);
    std::pair<iterator, bool> insert(value_type &&v);
    template <typename P,
          typename = typename std::enable_if<
              std::is_constructible<value_type, P &&>::value,
              P>::type>
    std::pair<iterator, bool> insert(P &&p);
    /* iterator insert(const_iterator position, const value_type &v); */
    /* iterator insert(const_iterator position, value_type &&v); */
    /* template <
        typename P,
        typename = typename std::enable_if<
            detail::has_is_transparent<BytesView>::value, P>::type>
    iterator insert(const_iterator position, P &&p); */
    template <class InputIterator>
    void insert(InputIterator first, InputIterator last);
    void insert(std::initializer_list<value_type> il);
    // insert_return_type insert(node_type&& nh);
    // iterator insert(const_iterator hint, node_type&& nh);
 
    template <class... Args>
    std::pair<iterator, bool> try_emplace(const key_type &k,
                          Args &&... args);
    template <class... Args>
    std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args);
    /*template <class... Args>
    iterator try_emplace(const_iterator hint, const key_type &k,
                 Args &&... args);*/
    /*template <class... Args>
    iterator try_emplace(const_iterator hint, key_type &&k,
                 Args &&... args);*/
    /* https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96976 */
    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;
 
    template <typename M>
    std::pair<iterator, bool> insert_or_assign(const key_type &k, M &&obj);
    template <typename M>
    std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj);
    /*template <typename M>
    iterator insert_or_assign(const_iterator hint, const key_type &k,
                  M &&obj);*/
    /*template <typename M>
    iterator insert_or_assign(const_iterator hint, key_type &&k, M &&obj);*/
    template <
        typename M, typename K,
        typename = typename std::enable_if<
            detail::has_is_transparent<BytesView>::value, K>::type>
    std::pair<iterator, bool> insert_or_assign(K &&k, M &&obj);
 
    iterator erase(const_iterator pos);
    iterator erase(const_iterator first, const_iterator last);
    size_type erase(const key_type &k);
    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);
 
    void clear();
 
    size_type count(const key_type &k) const;
    template <
        typename K,
        typename = typename std::enable_if<
            detail::has_is_transparent<BytesView>::value, K>::type>
    size_type count(const K &k) const;
 
    iterator find(const key_type &k);
    const_iterator find(const key_type &k) const;
    template <
        typename K,
        typename = typename std::enable_if<
            detail::has_is_transparent<BytesView>::value, K>::type>
    iterator find(const K &k);
    template <
        typename K,
        typename = typename std::enable_if<
            detail::has_is_transparent<BytesView>::value, K>::type>
    const_iterator find(const K &k) const;
 
    iterator lower_bound(const key_type &k);
    const_iterator lower_bound(const key_type &k) const;
    template <
        typename K,
        typename = typename std::enable_if<
            detail::has_is_transparent<BytesView>::value, K>::type>
    iterator lower_bound(const K &k);
    template <
        typename K,
        typename = typename std::enable_if<
            detail::has_is_transparent<BytesView>::value, K>::type>
    const_iterator lower_bound(const K &k) const;
 
    iterator upper_bound(const key_type &k);
    const_iterator upper_bound(const key_type &k) const;
    template <
        typename K,
        typename = typename std::enable_if<
            detail::has_is_transparent<BytesView>::value, K>::type>
    iterator upper_bound(const K &k);
    template <
        typename K,
        typename = typename std::enable_if<
            detail::has_is_transparent<BytesView>::value, K>::type>
    const_iterator upper_bound(const K &k) const;
 
    iterator begin();
    iterator end();
    const_iterator cbegin() const;
    const_iterator cend() const;
    const_iterator begin() const;
    const_iterator end() const;
 
    reverse_iterator rbegin();
    reverse_iterator rend();
    const_reverse_iterator crbegin() const;
    const_reverse_iterator crend() const;
    const_reverse_iterator rbegin() const;
    const_reverse_iterator rend() const;
 
    /* capacity: */
    bool empty() const noexcept;
    size_type max_size() const noexcept;
    uint64_t size() const noexcept;
 
    void swap(radix_tree &rhs);
 
    template <typename K, typename V, typename BV>
    friend std::ostream &operator<<(std::ostream &os,
                    const radix_tree<K, V, BV> &tree);
 
private:
    using byten_t = uint64_t;
    using bitn_t = uint8_t;
 
    /* Size of a chunk which differentiates subtrees of a node */
    static constexpr std::size_t SLICE = 4;
    /* Mask for SLICE */
    static constexpr std::size_t NIB = ((1ULL << SLICE) - 1);
    /* Number of children in internal nodes */
    static constexpr std::size_t SLNODES = (1 << SLICE);
    /* Mask for SLICE */
    static constexpr bitn_t SLICE_MASK = (bitn_t) ~(SLICE - 1);
    /* Position of the first SLICE */
    static constexpr bitn_t FIRST_NIB = 8 - SLICE;
 
    struct tagged_node_ptr;
    struct leaf;
    struct node;
 
    /*** pmem members ***/
    tagged_node_ptr root;
    p<uint64_t> size_;
 
    /* helper functions */
    template <typename K, typename F, class... Args>
    std::pair<iterator, bool> internal_emplace(const K &, F &&);
    template <typename K>
    leaf *internal_find(const K &k) const;
 
    static tagged_node_ptr &parent_ref(tagged_node_ptr n);
    template <typename K1, typename K2>
    static bool keys_equal(const K1 &k1, const K2 &k2);
    template <typename K1, typename K2>
    static int compare(const K1 &k1, const K2 &k2, byten_t offset = 0);
    template <bool Direction, typename Iterator>
    static leaf *next_leaf(Iterator child, tagged_node_ptr parent);
    template <bool Direction>
    static leaf *find_leaf(tagged_node_ptr n);
    static unsigned slice_index(char k, uint8_t shift);
    template <typename K1, typename K2>
    static byten_t prefix_diff(const K1 &lhs, const K2 &rhs,
                   byten_t offset = 0);
    leaf *any_leftmost_leaf(tagged_node_ptr n, size_type min_depth) const;
    template <typename K1, typename K2>
    static bitn_t bit_diff(const K1 &leaf_key, const K2 &key, byten_t diff);
    template <typename K>
    leaf *common_prefix_leaf(const K &key) const;
    static void print_rec(std::ostream &os, radix_tree::tagged_node_ptr n);
    template <typename K>
    static BytesView bytes_view(const K &k);
    static string_view bytes_view(string_view s);
    static bool path_length_equal(size_t key_size, tagged_node_ptr n);
    template <typename K>
    std::tuple<const tagged_node_ptr *, tagged_node_ptr>
    descend(const K &k, byten_t diff, bitn_t sh) const;
    template <typename K>
    std::tuple<tagged_node_ptr *, tagged_node_ptr>
    descend(const K &k, byten_t diff, bitn_t sh);
    template <bool Lower, typename K>
    const_iterator internal_bound(const K &k) const;
 
    void check_pmem();
    void check_tx_stage_work();
 
    static_assert(sizeof(node) == 256,
              "Internal node should have size equal to 256 bytes.");
};
 
template <typename Key, typename Value, typename BytesView>
void swap(radix_tree<Key, Value, BytesView> &lhs,
      radix_tree<Key, Value, BytesView> &rhs);
 
template <typename Key, typename Value, typename BytesView>
struct radix_tree<Key, Value, BytesView>::tagged_node_ptr {
    tagged_node_ptr() = default;
    tagged_node_ptr(const tagged_node_ptr &rhs) = default;
 
    tagged_node_ptr(std::nullptr_t);
    tagged_node_ptr(const persistent_ptr<leaf> &ptr);
    tagged_node_ptr(const persistent_ptr<node> &ptr);
 
    tagged_node_ptr &operator=(const tagged_node_ptr &rhs) = default;
 
    tagged_node_ptr &operator=(std::nullptr_t);
    tagged_node_ptr &operator=(const persistent_ptr<leaf> &rhs);
    tagged_node_ptr &operator=(const persistent_ptr<node> &rhs);
 
    bool operator==(const tagged_node_ptr &rhs) const;
    bool operator!=(const tagged_node_ptr &rhs) const;
 
    bool operator==(const radix_tree::leaf *rhs) const;
    bool operator!=(const radix_tree::leaf *rhs) const;
 
    void swap(tagged_node_ptr &rhs);
 
    bool is_leaf() const;
 
    radix_tree::leaf *get_leaf() const;
    radix_tree::node *get_node() const;
 
    radix_tree::node *operator->() const noexcept;
 
    explicit operator bool() const noexcept;
 
private:
    static constexpr uintptr_t IS_LEAF = 1;
    void *add_tag(radix_tree::leaf *ptr) const;
    void *remove_tag(void *ptr) const;
 
    self_relative_ptr_base ptr;
};
 
template <typename Key, typename Value, typename BytesView>
struct radix_tree<Key, Value, BytesView>::leaf {
    using tree_type = radix_tree<Key, Value, BytesView>;
 
    leaf(const leaf &) = delete;
    leaf(leaf &&) = delete;
 
    leaf &operator=(const leaf &) = delete;
    leaf &operator=(leaf &&) = delete;
 
    ~leaf();
 
    Key &key();
    Value &value();
 
    const Key &key() const;
    const Value &value() const;
 
    static persistent_ptr<leaf> make(tagged_node_ptr parent);
 
    template <typename... Args1, typename... Args2>
    static persistent_ptr<leaf>
    make(tagged_node_ptr parent, std::piecewise_construct_t pc,
         std::tuple<Args1...> first_args, std::tuple<Args2...> second_args);
    template <typename K, typename V>
    static persistent_ptr<leaf> make(tagged_node_ptr parent, K &&k, V &&v);
    static persistent_ptr<leaf> make(tagged_node_ptr parent, const Key &k,
                     const Value &v);
    template <typename K, typename... Args>
    static persistent_ptr<leaf> make_key_args(tagged_node_ptr parent, K &&k,
                          Args &&... args);
    template <typename K, typename V>
    static persistent_ptr<leaf> make(tagged_node_ptr parent,
                     detail::pair<K, V> &&p);
    template <typename K, typename V>
    static persistent_ptr<leaf> make(tagged_node_ptr parent,
                     const detail::pair<K, V> &p);
    template <typename K, typename V>
    static persistent_ptr<leaf> make(tagged_node_ptr parent,
                     std::pair<K, V> &&p);
    template <typename K, typename V>
    static persistent_ptr<leaf> make(tagged_node_ptr parent,
                     const std::pair<K, V> &p);
    static persistent_ptr<leaf> make(tagged_node_ptr parent,
                     const leaf &other);
 
private:
    friend class radix_tree<Key, Value, BytesView>;
 
    leaf() = default;
 
    template <typename... Args1, typename... Args2, size_t... I1,
          size_t... I2>
    static persistent_ptr<leaf>
    make(tagged_node_ptr parent, std::piecewise_construct_t,
         std::tuple<Args1...> &first_args,
         std::tuple<Args2...> &second_args, detail::index_sequence<I1...>,
         detail::index_sequence<I2...>);
 
    tagged_node_ptr parent = nullptr;
};
 
template <typename Key, typename Value, typename BytesView>
struct radix_tree<Key, Value, BytesView>::node {
    node(tagged_node_ptr parent, byten_t byte, bitn_t bit);
 
    tagged_node_ptr parent;
 
    tagged_node_ptr embedded_entry;
 
    /* Children can be both leaves and internal nodes. */
    tagged_node_ptr child[SLNODES];
 
    byten_t byte;
    bitn_t bit;
 
    struct direction {
        static constexpr bool Forward = 0;
        static constexpr bool Reverse = 1;
    };
 
    struct forward_iterator;
    using reverse_iterator = std::reverse_iterator<forward_iterator>;
 
    template <bool Direction>
    using iterator =
        typename std::conditional<Direction == direction::Forward,
                      forward_iterator,
                      reverse_iterator>::type;
 
    template <bool Direction = direction::Forward>
    typename std::enable_if<
        Direction ==
            radix_tree<Key, Value,
                   BytesView>::node::direction::Forward,
        typename radix_tree<Key, Value,
                    BytesView>::node::forward_iterator>::type
    begin() const;
 
    template <bool Direction = direction::Forward>
    typename std::enable_if<
        Direction ==
            radix_tree<Key, Value,
                   BytesView>::node::direction::Forward,
        typename radix_tree<Key, Value,
                    BytesView>::node::forward_iterator>::type
    end() const;
 
    /* rbegin */
    template <bool Direction = direction::Forward>
    typename std::enable_if<
        Direction ==
            radix_tree<Key, Value,
                   BytesView>::node::direction::Reverse,
        typename radix_tree<Key, Value,
                    BytesView>::node::reverse_iterator>::type
    begin() const;
 
    /* rend */
    template <bool Direction = direction::Forward>
    typename std::enable_if<
        Direction ==
            radix_tree<Key, Value,
                   BytesView>::node::direction::Reverse,
        typename radix_tree<Key, Value,
                    BytesView>::node::reverse_iterator>::type
    end() const;
 
    template <bool Direction = direction::Forward, typename Ptr>
    iterator<Direction> find_child(const Ptr &n) const;
 
    template <bool Direction = direction::Forward,
          typename Enable = typename std::enable_if<
              Direction == direction::Forward>::type>
    iterator<Direction> make_iterator(const tagged_node_ptr *ptr) const;
 
    uint8_t padding[256 - sizeof(parent) - sizeof(leaf) - sizeof(child) -
            sizeof(byte) - sizeof(bit)];
};
 
template <typename Key, typename Value, typename BytesView>
template <bool IsConst>
struct radix_tree<Key, Value, BytesView>::radix_tree_iterator {
private:
    using leaf_ptr =
        typename std::conditional<IsConst, const leaf *, leaf *>::type;
    using node_ptr =
        typename std::conditional<IsConst, const tagged_node_ptr *,
                      tagged_node_ptr *>::type;
    friend struct radix_tree_iterator<true>;
 
public:
    using difference_type = std::ptrdiff_t;
    using value_type = radix_tree::leaf;
    using reference = typename std::conditional<IsConst, const value_type &,
                            value_type &>::type;
    using pointer = typename std::conditional<IsConst, value_type const *,
                          value_type *>::type;
    using iterator_category = std::bidirectional_iterator_tag;
 
    radix_tree_iterator() = default;
    radix_tree_iterator(leaf_ptr leaf_, node_ptr root);
    radix_tree_iterator(const radix_tree_iterator &rhs) = default;
 
    template <bool C = IsConst,
          typename Enable = typename std::enable_if<C>::type>
    radix_tree_iterator(const radix_tree_iterator<false> &rhs);
 
    radix_tree_iterator &
    operator=(const radix_tree_iterator &rhs) = default;
 
    reference operator*() const;
    pointer operator->() const;
 
    template <typename V = Value,
          typename Enable = typename std::enable_if<
              detail::is_inline_string<V>::value>::type>
    void assign_val(basic_string_view<typename V::value_type,
                      typename V::traits_type>
                rhs);
 
    template <typename T, typename V = Value,
          typename Enable = typename std::enable_if<
              !detail::is_inline_string<V>::value>::type>
    void assign_val(T &&rhs);
 
    radix_tree_iterator &operator++();
    radix_tree_iterator &operator--();
 
    radix_tree_iterator operator++(int);
    radix_tree_iterator operator--(int);
 
    template <bool C>
    bool operator!=(const radix_tree_iterator<C> &rhs) const;
 
    template <bool C>
    bool operator==(const radix_tree_iterator<C> &rhs) const;
 
private:
    friend class radix_tree;
 
    leaf_ptr leaf_ = nullptr;
    node_ptr root = nullptr;
};
 
template <typename Key, typename Value, typename BytesView>
struct radix_tree<Key, Value, BytesView>::node::forward_iterator {
    using difference_type = std::ptrdiff_t;
    using value_type = tagged_node_ptr;
    using pointer = const value_type *;
    using reference = const value_type &;
    using iterator_category = std::forward_iterator_tag;
 
    forward_iterator(pointer child, const node *node);
 
    forward_iterator operator++();
    forward_iterator operator++(int);
 
    forward_iterator operator--();
 
    reference operator*() const;
    pointer operator->() const;
 
    pointer get_node() const;
 
    bool operator!=(const forward_iterator &rhs) const;
    bool operator==(const forward_iterator &rhs) const;
 
private:
    pointer child;
    const node *n;
};
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView>::radix_tree() : root(nullptr), size_(0)
{
    check_pmem();
    check_tx_stage_work();
}
 
template <typename Key, typename Value, typename BytesView>
template <class InputIt>
radix_tree<Key, Value, BytesView>::radix_tree(InputIt first, InputIt last)
    : root(nullptr), size_(0)
{
    check_pmem();
    check_tx_stage_work();
 
    for (auto it = first; it != last; it++)
        emplace(*it);
}
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView>::radix_tree(const radix_tree &m)
{
    check_pmem();
    check_tx_stage_work();
 
    root = nullptr;
    size_ = 0;
 
    for (auto it = m.cbegin(); it != m.cend(); it++)
        emplace(*it);
}
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView>::radix_tree(radix_tree &&m)
{
    check_pmem();
    check_tx_stage_work();
 
    root = m.root;
    size_ = m.size_;
    m.root = nullptr;
    m.size_ = 0;
}
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView>::radix_tree(
    std::initializer_list<value_type> il)
    : radix_tree(il.begin(), il.end())
{
}
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView> &
radix_tree<Key, Value, BytesView>::operator=(const radix_tree &other)
{
    check_pmem();
 
    auto pop = pool_by_vptr(this);
 
    if (this != &other) {
        flat_transaction::run(pop, [&] {
            clear();
 
            this->root = nullptr;
            this->size_ = 0;
 
            for (auto it = other.cbegin(); it != other.cend(); it++)
                emplace(*it);
        });
    }
 
    return *this;
}
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView> &
radix_tree<Key, Value, BytesView>::operator=(radix_tree &&other)
{
    check_pmem();
 
    auto pop = pool_by_vptr(this);
 
    if (this != &other) {
        flat_transaction::run(pop, [&] {
            clear();
 
            this->root = other.root;
            this->size_ = other.size_;
            other.root = nullptr;
            other.size_ = 0;
        });
    }
 
    return *this;
}
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView> &
radix_tree<Key, Value, BytesView>::operator=(
    std::initializer_list<value_type> ilist)
{
    check_pmem();
 
    auto pop = pool_by_vptr(this);
 
    transaction::run(pop, [&] {
        clear();
 
        this->root = nullptr;
        this->size_ = 0;
 
        for (auto it = ilist.begin(); it != ilist.end(); it++)
            emplace(*it);
    });
 
    return *this;
}
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView>::~radix_tree()
{
    try {
        clear();
    } catch (...) {
        std::terminate();
    }
}
 
template <typename Key, typename Value, typename BytesView>
bool
radix_tree<Key, Value, BytesView>::empty() const noexcept
{
    return size_ == 0;
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::size_type
radix_tree<Key, Value, BytesView>::max_size() const noexcept
{
    return std::numeric_limits<difference_type>::max();
}
 
template <typename Key, typename Value, typename BytesView>
uint64_t
radix_tree<Key, Value, BytesView>::size() const noexcept
{
    return this->size_;
}
 
template <typename Key, typename Value, typename BytesView>
void
radix_tree<Key, Value, BytesView>::swap(radix_tree &rhs)
{
    auto pop = pool_by_vptr(this);
 
    flat_transaction::run(pop, [&] {
        this->size_.swap(rhs.size_);
        this->root.swap(rhs.root);
    });
}
 
/*
 * Returns reference to n->parent (handles both internal and leaf nodes).
 */
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
radix_tree<Key, Value, BytesView>::parent_ref(tagged_node_ptr n)
{
    if (n.is_leaf())
        return n.get_leaf()->parent;
 
    return n->parent;
}
 
/*
 * Find a leftmost leaf in a subtree of @param n.
 *
 * @param min_depth specifies minimum depth of the leaf. If the
 * tree is shorter than min_depth, a bottom leaf is returned.
 */
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::leaf *
radix_tree<Key, Value, BytesView>::any_leftmost_leaf(
    typename radix_tree<Key, Value, BytesView>::tagged_node_ptr n,
    size_type min_depth) const
{
    assert(n);
 
    while (!n.is_leaf()) {
        if (n->embedded_entry && n->byte >= min_depth)
            return n->embedded_entry.get_leaf();
 
        for (size_t i = 0; i < SLNODES; i++) {
            tagged_node_ptr m;
            if ((m = n->child[i])) {
                n = m;
                break;
            }
        }
    }
 
    return n.get_leaf();
}
 
/*
 * Descends to the leaf that shares a common prefix with the key.
 */
template <typename Key, typename Value, typename BytesView>
template <typename K>
typename radix_tree<Key, Value, BytesView>::leaf *
radix_tree<Key, Value, BytesView>::common_prefix_leaf(const K &key) const
{
    auto n = root;
 
    while (n && !n.is_leaf() && n->byte < key.size()) {
        auto nn = n->child[slice_index(key[n->byte], n->bit)];
 
        if (nn)
            n = nn;
        else {
            n = any_leftmost_leaf(n, key.size());
            break;
        }
    }
 
    /* This can happen when key is a prefix of some leaf or when the node at
     * which the keys diverge isn't a leaf */
    if (!n.is_leaf())
        n = any_leftmost_leaf(n, key.size());
 
    return n.get_leaf();
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K>
BytesView
radix_tree<Key, Value, BytesView>::bytes_view(const K &key)
{
    /* bytes_view accepts const pointer instead of reference to make sure
     * there is no implicit conversion to a temporary type (and hence
     * dangling references). */
    return BytesView(&key);
}
 
template <typename Key, typename Value, typename BytesView>
string_view
radix_tree<Key, Value, BytesView>::bytes_view(string_view key)
{
    return key;
}
 
/*
 * Checks for key equality.
 */
template <typename Key, typename Value, typename BytesView>
template <typename K1, typename K2>
bool
radix_tree<Key, Value, BytesView>::keys_equal(const K1 &k1, const K2 &k2)
{
    return k1.size() == k2.size() && compare(k1, k2) == 0;
}
 
/*
 * Checks for key equality.
 */
template <typename Key, typename Value, typename BytesView>
template <typename K1, typename K2>
int
radix_tree<Key, Value, BytesView>::compare(const K1 &k1, const K2 &k2,
                       byten_t offset)
{
    auto ret = prefix_diff(k1, k2, offset);
 
    if (ret != (std::min)(k1.size(), k2.size()))
        return (unsigned char)(k1[ret]) - (unsigned char)(k2[ret]);
 
    return k1.size() - k2.size();
}
 
/*
 * Returns length of common prefix of lhs and rhs.
 */
template <typename Key, typename Value, typename BytesView>
template <typename K1, typename K2>
typename radix_tree<Key, Value, BytesView>::byten_t
radix_tree<Key, Value, BytesView>::prefix_diff(const K1 &lhs, const K2 &rhs,
                           byten_t offset)
{
    byten_t diff;
    for (diff = offset; diff < (std::min)(lhs.size(), rhs.size()); diff++) {
        if (lhs[diff] != rhs[diff])
            return diff;
    }
 
    return diff;
}
 
/*
 * Checks whether length of the path from root to n is equal
 * to key_size.
 */
template <typename Key, typename Value, typename BytesView>
bool
radix_tree<Key, Value, BytesView>::path_length_equal(size_t key_size,
                             tagged_node_ptr n)
{
    return n->byte == key_size && n->bit == bitn_t(FIRST_NIB);
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K1, typename K2>
typename radix_tree<Key, Value, BytesView>::bitn_t
radix_tree<Key, Value, BytesView>::bit_diff(const K1 &leaf_key, const K2 &key,
                        byten_t diff)
{
    auto min_key_len = (std::min)(leaf_key.size(), key.size());
    bitn_t sh = 8;
 
    /* If key differs from leaf_key at some point (neither is a prefix of
     * another) we will descend to the point of divergence. Otherwise we
     * will look for a node which represents the prefix. */
    if (diff < min_key_len) {
        auto at =
            static_cast<unsigned char>(leaf_key[diff] ^ key[diff]);
        sh = pmem::detail::mssb_index((uint32_t)at) & SLICE_MASK;
    }
 
    return sh;
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K>
std::tuple<const typename radix_tree<Key, Value, BytesView>::tagged_node_ptr *,
       typename radix_tree<Key, Value, BytesView>::tagged_node_ptr>
radix_tree<Key, Value, BytesView>::descend(const K &key, byten_t diff,
                       bitn_t sh) const
{
    auto n = root;
    auto prev = n;
    auto slot = &root;
 
    while (n && !n.is_leaf() &&
           (n->byte < diff || (n->byte == diff && n->bit >= sh))) {
        prev = n;
        slot = &n->child[slice_index(key[n->byte], n->bit)];
        n = *slot;
    }
 
    return {slot, prev};
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K>
std::tuple<typename radix_tree<Key, Value, BytesView>::tagged_node_ptr *,
       typename radix_tree<Key, Value, BytesView>::tagged_node_ptr>
radix_tree<Key, Value, BytesView>::descend(const K &key, byten_t diff,
                       bitn_t sh)
{
    const tagged_node_ptr *slot;
    tagged_node_ptr prev;
 
    std::tie(slot, prev) =
        const_cast<const radix_tree *>(this)->descend(key, diff, sh);
 
    return {const_cast<tagged_node_ptr *>(slot), prev};
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename F, class... Args>
std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
radix_tree<Key, Value, BytesView>::internal_emplace(const K &k, F &&make_leaf)
{
    auto key = bytes_view(k);
    auto pop = pool_base(pmemobj_pool_by_ptr(this));
 
    if (!root) {
        flat_transaction::run(pop,
                      [&] { this->root = make_leaf(nullptr); });
        return {iterator(root.get_leaf(), &root), true};
    }
 
    /*
     * Need to descend the tree twice. First to find a leaf that
     * represents a subtree that shares a common prefix with the key.
     * This is needed to find out the actual labels between nodes (they
     * are not known due to a possible path compression). Second time to
     * find the place for the new element.
     */
    auto leaf = common_prefix_leaf(key);
    auto leaf_key = bytes_view(leaf->key());
    auto diff = prefix_diff(key, leaf_key);
    auto sh = bit_diff(leaf_key, key, diff);
 
    /* Key exists. */
    if (diff == key.size() && leaf_key.size() == key.size())
        return {iterator(leaf, &root), false};
 
    /* Descend into the tree again. */
    tagged_node_ptr *slot;
    tagged_node_ptr prev;
    std::tie(slot, prev) = descend(key, diff, sh);
 
    auto n = *slot;
 
    /*
     * If the divergence point is at same nib as an existing node, and
     * the subtree there is empty, just place our leaf there and we're
     * done.  Obviously this can't happen if SLICE == 1.
     */
    if (!n) {
        assert(diff < (std::min)(leaf_key.size(), key.size()));
 
        flat_transaction::run(pop, [&] { *slot = make_leaf(prev); });
        return {iterator(slot->get_leaf(), &root), true};
    }
 
    /* New key is a prefix of the leaf key or they are equal. We need to add
     * leaf ptr to internal node. */
    if (diff == key.size()) {
        if (!n.is_leaf() && path_length_equal(key.size(), n)) {
            assert(!n->embedded_entry);
 
            flat_transaction::run(
                pop, [&] { n->embedded_entry = make_leaf(n); });
 
            return {iterator(n->embedded_entry.get_leaf(), &root),
                true};
        }
 
        /* Path length from root to n is longer than key.size().
         * We have to allocate new internal node above n. */
        tagged_node_ptr node;
        flat_transaction::run(pop, [&] {
            node = make_persistent<radix_tree::node>(
                parent_ref(n), diff, bitn_t(FIRST_NIB));
            node->embedded_entry = make_leaf(node);
            node->child[slice_index(leaf_key[diff],
                        bitn_t(FIRST_NIB))] = n;
 
            parent_ref(n) = node;
            *slot = node;
        });
 
        return {iterator(node->embedded_entry.get_leaf(), &root), true};
    }
 
    if (diff == leaf_key.size()) {
        /* Leaf key is a prefix of the new key. We need to convert leaf
         * to a node. */
        tagged_node_ptr node;
        flat_transaction::run(pop, [&] {
            /* We have to add new node at the edge from parent to n
             */
            node = make_persistent<radix_tree::node>(
                parent_ref(n), diff, bitn_t(FIRST_NIB));
            node->embedded_entry = n;
            node->child[slice_index(key[diff], bitn_t(FIRST_NIB))] =
                make_leaf(node);
 
            parent_ref(n) = node;
            *slot = node;
        });
 
        return {iterator(node->child[slice_index(key[diff],
                             bitn_t(FIRST_NIB))]
                     .get_leaf(),
                 &root),
            true};
    }
 
    /* There is already a subtree at the divergence point
     * (slice_index(key[diff], sh)). This means that a tree is vertically
     * compressed and we have to "break" this compression and add a new
     * node. */
    tagged_node_ptr node;
    flat_transaction::run(pop, [&] {
        node = make_persistent<radix_tree::node>(parent_ref(n), diff,
                             sh);
        node->child[slice_index(leaf_key[diff], sh)] = n;
        node->child[slice_index(key[diff], sh)] = make_leaf(node);
 
        parent_ref(n) = node;
        *slot = node;
    });
 
    return {iterator(node->child[slice_index(key[diff], sh)].get_leaf(),
             &root),
        true};
}
 
template <typename Key, typename Value, typename BytesView>
template <class... Args>
std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
radix_tree<Key, Value, BytesView>::try_emplace(const key_type &k,
                           Args &&... args)
{
    return internal_emplace(k, [&](tagged_node_ptr parent) {
        size_++;
        return leaf::make_key_args(parent, k,
                       std::forward<Args>(args)...);
    });
}
 
template <typename Key, typename Value, typename BytesView>
template <class... Args>
std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
radix_tree<Key, Value, BytesView>::emplace(Args &&... args)
{
    auto pop = pool_base(pmemobj_pool_by_ptr(this));
    std::pair<iterator, bool> ret;
 
    flat_transaction::run(pop, [&] {
        auto leaf_ = leaf::make(nullptr, std::forward<Args>(args)...);
        auto make_leaf = [&](tagged_node_ptr parent) {
            leaf_->parent = parent;
            size_++;
            return leaf_;
        };
 
        ret = internal_emplace(leaf_->key(), make_leaf);
 
        if (!ret.second)
            delete_persistent<leaf>(leaf_);
    });
 
    return ret;
}
 
template <typename Key, typename Value, typename BytesView>
std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
radix_tree<Key, Value, BytesView>::insert(const value_type &v)
{
    return try_emplace(v.first, v.second);
}
 
template <typename Key, typename Value, typename BytesView>
std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
radix_tree<Key, Value, BytesView>::insert(value_type &&v)
{
    return try_emplace(std::move(v.first), std::move(v.second));
}
 
template <typename Key, typename Value, typename BytesView>
template <typename P, typename>
std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
radix_tree<Key, Value, BytesView>::insert(P &&p)
{
    return emplace(std::forward<P>(p));
}
 
template <typename Key, typename Value, typename BytesView>
template <typename InputIterator>
void
radix_tree<Key, Value, BytesView>::insert(InputIterator first,
                      InputIterator last)
{
    for (auto it = first; it != last; it++)
        try_emplace((*it).first, (*it).second);
}
 
template <typename Key, typename Value, typename BytesView>
void
radix_tree<Key, Value, BytesView>::insert(std::initializer_list<value_type> il)
{
    insert(il.begin(), il.end());
}
 
template <typename Key, typename Value, typename BytesView>
template <class... Args>
std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
radix_tree<Key, Value, BytesView>::try_emplace(key_type &&k, Args &&... args)
{
    return internal_emplace(k, [&](tagged_node_ptr parent) {
        size_++;
        return leaf::make_key_args(parent, std::move(k),
                       std::forward<Args>(args)...);
    });
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename BV, class... Args>
auto
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<typename radix_tree<Key, Value, BytesView>::iterator,
              bool>>::type
 
{
    return internal_emplace(k, [&](tagged_node_ptr parent) {
        size_++;
        return leaf::make_key_args(parent, std::forward<K>(k),
                       std::forward<Args>(args)...);
    });
}
 
template <typename Key, typename Value, typename BytesView>
template <typename M>
std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
radix_tree<Key, Value, BytesView>::insert_or_assign(const key_type &k, M &&obj)
{
    auto ret = try_emplace(k, std::forward<M>(obj));
    if (!ret.second)
        ret.first.assign_val(std::forward<M>(obj));
    return ret;
}
 
template <typename Key, typename Value, typename BytesView>
template <typename M>
std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
radix_tree<Key, Value, BytesView>::insert_or_assign(key_type &&k, M &&obj)
{
    auto ret = try_emplace(std::move(k), std::forward<M>(obj));
    if (!ret.second)
        ret.first.assign_val(std::forward<M>(obj));
    return ret;
}
 
template <typename Key, typename Value, typename BytesView>
template <typename M, typename K, typename>
std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
radix_tree<Key, Value, BytesView>::insert_or_assign(K &&k, M &&obj)
{
    auto ret = try_emplace(std::forward<K>(k), std::forward<M>(obj));
    if (!ret.second)
        ret.first.assign_val(std::forward<M>(obj));
    return ret;
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::size_type
radix_tree<Key, Value, BytesView>::count(const key_type &k) const
{
    return internal_find(k) != nullptr ? 1 : 0;
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename>
typename radix_tree<Key, Value, BytesView>::size_type
radix_tree<Key, Value, BytesView>::count(const K &k) const
{
    return internal_find(k) != nullptr ? 1 : 0;
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::iterator
radix_tree<Key, Value, BytesView>::find(const key_type &k)
{
    return iterator(internal_find(k), &root);
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::const_iterator
radix_tree<Key, Value, BytesView>::find(const key_type &k) const
{
    return const_iterator(internal_find(k), &root);
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename>
typename radix_tree<Key, Value, BytesView>::iterator
radix_tree<Key, Value, BytesView>::find(const K &k)
{
    return iterator(internal_find(k), &root);
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename>
typename radix_tree<Key, Value, BytesView>::const_iterator
radix_tree<Key, Value, BytesView>::find(const K &k) const
{
    return const_iterator(internal_find(k), &root);
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K>
typename radix_tree<Key, Value, BytesView>::leaf *
radix_tree<Key, Value, BytesView>::internal_find(const K &k) const
{
    auto key = bytes_view(k);
 
    auto n = root;
    while (n && !n.is_leaf()) {
        if (path_length_equal(key.size(), n))
            n = n->embedded_entry;
        else if (n->byte >= key.size())
            return nullptr;
        else
            n = n->child[slice_index(key[n->byte], n->bit)];
    }
 
    if (!n)
        return nullptr;
 
    if (!keys_equal(key, bytes_view(n.get_leaf()->key())))
        return nullptr;
 
    return n.get_leaf();
}
 
template <typename Key, typename Value, typename BytesView>
void
radix_tree<Key, Value, BytesView>::clear()
{
    if (size() != 0)
        erase(begin(), end());
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::iterator
radix_tree<Key, Value, BytesView>::erase(const_iterator pos)
{
    auto pop = pool_base(pmemobj_pool_by_ptr(this));
 
    flat_transaction::run(pop, [&] {
        auto *leaf = pos.leaf_;
        auto parent = leaf->parent;
 
        /* there are more elements in the container */
        if (parent)
            ++pos;
 
        delete_persistent<radix_tree::leaf>(
            persistent_ptr<radix_tree::leaf>(leaf));
 
        size_--;
 
        /* was root */
        if (!parent) {
            this->root = nullptr;
            pos = begin();
            return;
        }
 
        /* It's safe to cast because we're inside non-const method. */
        const_cast<tagged_node_ptr &>(*parent->find_child(leaf)) =
            nullptr;
 
        /* Compress the tree vertically. */
        auto n = parent;
        parent = n->parent;
        tagged_node_ptr only_child = nullptr;
        for (size_t i = 0; i < SLNODES; i++) {
            if (n->child[i]) {
                if (only_child) {
                    /* more than one child */
                    return;
                }
                only_child = n->child[i];
            }
        }
 
        if (only_child && n->embedded_entry) {
            /* There are actually 2 "children" so we can't compress.
             */
            return;
        } else if (n->embedded_entry) {
            only_child = n->embedded_entry;
        }
 
        assert(only_child);
        parent_ref(only_child) = n->parent;
 
        auto *child_slot = parent
            ? const_cast<tagged_node_ptr *>(&*parent->find_child(n))
            : &root;
        *child_slot = only_child;
 
        delete_persistent<radix_tree::node>(n.get_node());
    });
 
    return iterator(const_cast<typename iterator::leaf_ptr>(pos.leaf_),
            &root);
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::iterator
radix_tree<Key, Value, BytesView>::erase(const_iterator first,
                     const_iterator last)
{
    auto pop = pool_base(pmemobj_pool_by_ptr(this));
 
    flat_transaction::run(pop, [&] {
        while (first != last)
            first = erase(first);
    });
 
    return iterator(const_cast<typename iterator::leaf_ptr>(first.leaf_),
            &root);
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::size_type
radix_tree<Key, Value, BytesView>::erase(const key_type &k)
{
    auto it = const_iterator(internal_find(k), &root);
 
    if (it == end())
        return 0;
 
    erase(it);
 
    return 1;
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename>
typename radix_tree<Key, Value, BytesView>::size_type
radix_tree<Key, Value, BytesView>::erase(const K &k)
{
    auto it = const_iterator(internal_find(k), &root);
 
    if (it == end())
        return 0;
 
    erase(it);
 
    return 1;
}
 
template <typename Key, typename Value, typename BytesView>
template <bool Lower, typename K>
typename radix_tree<Key, Value, BytesView>::const_iterator
radix_tree<Key, Value, BytesView>::internal_bound(const K &k) const
{
    auto key = bytes_view(k);
    auto pop = pool_base(pmemobj_pool_by_ptr(this));
 
    if (!root)
        return end();
 
    /*
     * Need to descend the tree twice. First to find a leaf that
     * represents a subtree that shares a common prefix with the key.
     * This is needed to find out the actual labels between nodes (they
     * are not known due to a possible path compression). Second time to
     * get the actual element.
     */
    auto leaf = common_prefix_leaf(key);
    auto leaf_key = bytes_view(leaf->key());
    auto diff = prefix_diff(key, leaf_key);
    auto sh = bit_diff(leaf_key, key, diff);
 
    /* Key exists. */
    if (diff == key.size() && leaf_key.size() == key.size()) {
        if (Lower)
            return const_iterator(leaf, &root);
        else
            return ++const_iterator(leaf, &root);
    }
 
    /* Descend into the tree again. */
    const tagged_node_ptr *slot;
    tagged_node_ptr prev;
    std::tie(slot, prev) = descend(key, diff, sh);
 
    if (!*slot) {
        leaf = next_leaf<node::direction::Forward>(
            prev->template make_iterator<node::direction::Forward>(
                slot),
            prev);
 
        return const_iterator(leaf, &root);
    }
 
    /* The looked-for key is a prefix of the leaf key. The target node must
     * be the smallest leaf within *slot subtree. Key represented by a path
     * from root to n is larger than the looked-for key. Additionally keys
     * under right siblings of *slot are > key and keys under left siblings
     * are < key. */
    if (diff == key.size()) {
        leaf = find_leaf<node::direction::Forward>(*slot);
        return const_iterator(leaf, &root);
    }
 
    /* Leaf's key is a prefix of the looked-for key. Leaf's key is the
     * biggest key less than the looked-for key.
     * The target node must be the next leaf. */
    if (diff == leaf_key.size())
        return ++const_iterator(leaf, &root);
 
    /* *slot is the point of divergence. */
    assert(diff < leaf_key.size() && diff < key.size());
 
    /* The target node must be within *slot subtree. The left siblings
     * of *slot are all less than the looked-for key. */
    if (compare(key, leaf_key, diff) < 0) {
        leaf = find_leaf<node::direction::Forward>(*slot);
        return const_iterator(leaf, &root);
    }
 
    if (slot == &root) {
        return const_iterator(nullptr, &root);
    }
 
    /* Since looked-for key is larger than *slot, the target node must be
     * within subtree of a right sibling of *slot. */
    leaf = next_leaf<node::direction::Forward>(
        prev->template make_iterator<node::direction::Forward>(slot),
        prev);
 
    return const_iterator(leaf, &root);
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::const_iterator
radix_tree<Key, Value, BytesView>::lower_bound(const key_type &k) const
{
    return internal_bound<true>(k);
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::iterator
radix_tree<Key, Value, BytesView>::lower_bound(const key_type &k)
{
    auto it = const_cast<const radix_tree *>(this)->lower_bound(k);
    return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
            &root);
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename>
typename radix_tree<Key, Value, BytesView>::iterator
radix_tree<Key, Value, BytesView>::lower_bound(const K &k)
{
    auto it = const_cast<const radix_tree *>(this)->lower_bound(k);
    return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
            &root);
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename>
typename radix_tree<Key, Value, BytesView>::const_iterator
radix_tree<Key, Value, BytesView>::lower_bound(const K &k) const
{
    return internal_bound<true>(k);
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::const_iterator
radix_tree<Key, Value, BytesView>::upper_bound(const key_type &k) const
{
    return internal_bound<false>(k);
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::iterator
radix_tree<Key, Value, BytesView>::upper_bound(const key_type &k)
{
    auto it = const_cast<const radix_tree *>(this)->upper_bound(k);
    return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
            &root);
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename>
typename radix_tree<Key, Value, BytesView>::iterator
radix_tree<Key, Value, BytesView>::upper_bound(const K &k)
{
    auto it = const_cast<const radix_tree *>(this)->upper_bound(k);
    return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
            &root);
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename>
typename radix_tree<Key, Value, BytesView>::const_iterator
radix_tree<Key, Value, BytesView>::upper_bound(const K &k) const
{
    return internal_bound<false>(k);
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::iterator
radix_tree<Key, Value, BytesView>::begin()
{
    auto const_begin = const_cast<const radix_tree *>(this)->begin();
    return iterator(
        const_cast<typename iterator::leaf_ptr>(const_begin.leaf_),
        &root);
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::iterator
radix_tree<Key, Value, BytesView>::end()
{
    auto const_end = const_cast<const radix_tree *>(this)->end();
    return iterator(
        const_cast<typename iterator::leaf_ptr>(const_end.leaf_),
        &root);
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::const_iterator
radix_tree<Key, Value, BytesView>::cbegin() const
{
    if (!root)
        return const_iterator(nullptr, &root);
 
    return const_iterator(
        radix_tree::find_leaf<radix_tree::node::direction::Forward>(
            root),
        &root);
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::const_iterator
radix_tree<Key, Value, BytesView>::cend() const
{
    return const_iterator(nullptr, &root);
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::const_iterator
radix_tree<Key, Value, BytesView>::begin() const
{
    return cbegin();
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::const_iterator
radix_tree<Key, Value, BytesView>::end() const
{
    return cend();
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::reverse_iterator
radix_tree<Key, Value, BytesView>::rbegin()
{
    return reverse_iterator(end());
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::reverse_iterator
radix_tree<Key, Value, BytesView>::rend()
{
    return reverse_iterator(begin());
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
radix_tree<Key, Value, BytesView>::crbegin() const
{
    return const_reverse_iterator(cend());
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
radix_tree<Key, Value, BytesView>::crend() const
{
    return const_reverse_iterator(cbegin());
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
radix_tree<Key, Value, BytesView>::rbegin() const
{
    return const_reverse_iterator(cend());
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
radix_tree<Key, Value, BytesView>::rend() const
{
    return const_reverse_iterator(cbegin());
}
 
template <typename Key, typename Value, typename BytesView>
void
radix_tree<Key, Value, BytesView>::print_rec(std::ostream &os,
                         radix_tree::tagged_node_ptr n)
{
    if (!n.is_leaf()) {
        os << "\"" << n.get_node() << "\""
           << " [style=filled,color=\"blue\"]" << std::endl;
        os << "\"" << n.get_node() << "\" [label=\"byte:" << n->byte
           << ", bit:" << int(n->bit) << "\"]" << std::endl;
 
        auto parent = n->parent ? n->parent.get_node() : 0;
        os << "\"" << n.get_node() << "\" -> "
           << "\"" << parent << "\" [label=\"parent\"]" << std::endl;
 
        for (auto it = n->begin(); it != n->end(); ++it) {
            if (!(*it))
                continue;
 
            auto ch = it->is_leaf() ? (void *)it->get_leaf()
                        : (void *)it->get_node();
 
            os << "\"" << n.get_node() << "\" -> \"" << ch << "\""
               << std::endl;
            print_rec(os, *it);
        }
    } else {
        auto bv = bytes_view(n.get_leaf()->key());
 
        os << "\"" << n.get_leaf()
           << "\" [style=filled,color=\"green\"]" << std::endl;
        os << "\"" << n.get_leaf() << "\" [label=\"key:";
 
        for (size_t i = 0; i < bv.size(); i++)
            os << bv[i];
 
        os << "\"]" << std::endl;
 
        auto parent = n.get_leaf()->parent
            ? n.get_leaf()->parent.get_node()
            : nullptr;
 
        os << "\"" << n.get_leaf() << "\" -> \"" << parent
           << "\" [label=\"parent\"]" << std::endl;
 
        if (parent && n == parent->embedded_entry) {
            os << "{rank=same;\"" << parent << "\";\""
               << n.get_leaf() << "\"}" << std::endl;
        }
    }
}
 
template <typename K, typename V, typename BV>
std::ostream &
operator<<(std::ostream &os, const radix_tree<K, V, BV> &tree)
{
    os << "digraph Radix {" << std::endl;
 
    if (tree.root)
        radix_tree<K, V, BV>::print_rec(os, tree.root);
 
    os << "}" << std::endl;
 
    return os;
}
 
/*
 * internal: slice_index -- return index of child at the given nib
 */
template <typename Key, typename Value, typename BytesView>
unsigned
radix_tree<Key, Value, BytesView>::slice_index(char b, uint8_t bit)
{
    return static_cast<unsigned>(b >> bit) & NIB;
}
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
    std::nullptr_t)
    : ptr(nullptr)
{
    assert(!(bool)*this);
}
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
    const persistent_ptr<leaf> &ptr)
    : ptr(add_tag(ptr.get()))
{
    assert(get_leaf() == ptr.get());
}
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
    const persistent_ptr<node> &ptr)
    : ptr(ptr.get())
{
    assert(get_node() == ptr.get());
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
    radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
        std::nullptr_t)
{
    ptr = nullptr;
    assert(!(bool)*this);
 
    return *this;
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
    const persistent_ptr<leaf> &rhs)
{
    ptr = add_tag(rhs.get());
    assert(get_leaf() == rhs.get());
 
    return *this;
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
    const persistent_ptr<node> &rhs)
{
    ptr = rhs.get();
    assert(get_node() == rhs.get());
 
    return *this;
}
 
template <typename Key, typename Value, typename BytesView>
bool
radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator==(
    const radix_tree::tagged_node_ptr &rhs) const
{
    return ptr.to_byte_pointer() == rhs.ptr.to_byte_pointer();
}
 
template <typename Key, typename Value, typename BytesView>
bool
radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator!=(
    const radix_tree::tagged_node_ptr &rhs) const
{
    return !(*this == rhs);
}
 
template <typename Key, typename Value, typename BytesView>
bool
radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator==(
    const radix_tree::leaf *rhs) const
{
    return is_leaf() && get_leaf() == rhs;
}
 
template <typename Key, typename Value, typename BytesView>
bool
radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator!=(
    const radix_tree::leaf *rhs) const
{
    return !(*this == rhs);
}
 
template <typename Key, typename Value, typename BytesView>
void
radix_tree<Key, Value, BytesView>::tagged_node_ptr::swap(tagged_node_ptr &rhs)
{
    ptr.swap(rhs.ptr);
}
 
template <typename Key, typename Value, typename BytesView>
void *
radix_tree<Key, Value, BytesView>::tagged_node_ptr::add_tag(
    radix_tree::leaf *ptr) const
{
    auto tagged = reinterpret_cast<uintptr_t>(ptr) | uintptr_t(IS_LEAF);
    return reinterpret_cast<radix_tree::leaf *>(tagged);
}
 
template <typename Key, typename Value, typename BytesView>
void *
radix_tree<Key, Value, BytesView>::tagged_node_ptr::remove_tag(void *ptr) const
{
    auto untagged = reinterpret_cast<uintptr_t>(ptr) & ~uintptr_t(IS_LEAF);
    return reinterpret_cast<void *>(untagged);
}
 
template <typename Key, typename Value, typename BytesView>
bool
radix_tree<Key, Value, BytesView>::tagged_node_ptr::is_leaf() const
{
    auto value = reinterpret_cast<uintptr_t>(ptr.to_void_pointer());
    return value & uintptr_t(IS_LEAF);
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::leaf *
radix_tree<Key, Value, BytesView>::tagged_node_ptr::get_leaf() const
{
    assert(is_leaf());
    return static_cast<radix_tree::leaf *>(
        remove_tag(ptr.to_void_pointer()));
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::node *
radix_tree<Key, Value, BytesView>::tagged_node_ptr::get_node() const
{
    assert(!is_leaf());
    return static_cast<radix_tree::node *>(ptr.to_void_pointer());
}
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator bool() const
    noexcept
{
    return remove_tag(ptr.to_void_pointer()) != nullptr;
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::node *
    radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator->() const
    noexcept
{
    return get_node();
}
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView>::node::forward_iterator::forward_iterator(
    pointer child, const node *n)
    : child(child), n(n)
{
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::node::forward_iterator
radix_tree<Key, Value, BytesView>::node::forward_iterator::operator++()
{
    if (child == &n->embedded_entry)
        child = &n->child[0];
    else
        child++;
 
    return *this;
}
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView>::node::node(tagged_node_ptr parent,
                          byten_t byte, bitn_t bit)
    : parent(parent), byte(byte), bit(bit)
{
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::node::forward_iterator
radix_tree<Key, Value, BytesView>::node::forward_iterator::operator--()
{
    if (child == &n->child[0])
        child = &n->embedded_entry;
    else
        child--;
 
    return *this;
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::node::forward_iterator
radix_tree<Key, Value, BytesView>::node::forward_iterator::operator++(int)
{
    forward_iterator tmp(child, n);
    operator++();
    return tmp;
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::node::forward_iterator::reference
    radix_tree<Key, Value, BytesView>::node::forward_iterator::operator*()
        const
{
    return *child;
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::node::forward_iterator::pointer
    radix_tree<Key, Value, BytesView>::node::forward_iterator::operator->()
        const
{
    return child;
}
 
template <typename Key, typename Value, typename BytesView>
typename radix_tree<Key, Value, BytesView>::node::forward_iterator::pointer
radix_tree<Key, Value, BytesView>::node::forward_iterator::get_node() const
{
    return n;
}
 
template <typename Key, typename Value, typename BytesView>
bool
radix_tree<Key, Value, BytesView>::node::forward_iterator::operator==(
    const forward_iterator &rhs) const
{
    return child == rhs.child && n == rhs.n;
}
 
template <typename Key, typename Value, typename BytesView>
bool
radix_tree<Key, Value, BytesView>::node::forward_iterator::operator!=(
    const forward_iterator &rhs) const
{
    return child != rhs.child || n != rhs.n;
}
 
template <typename Key, typename Value, typename BytesView>
template <bool Direction>
typename std::enable_if<
    Direction ==
        radix_tree<Key, Value, BytesView>::node::direction::Forward,
    typename radix_tree<Key, Value,
                BytesView>::node::forward_iterator>::type
radix_tree<Key, Value, BytesView>::node::begin() const
{
    return forward_iterator(&embedded_entry, this);
}
 
template <typename Key, typename Value, typename BytesView>
template <bool Direction>
typename std::enable_if<
    Direction ==
        radix_tree<Key, Value, BytesView>::node::direction::Forward,
    typename radix_tree<Key, Value,
                BytesView>::node::forward_iterator>::type
radix_tree<Key, Value, BytesView>::node::end() const
{
    return forward_iterator(&child[SLNODES], this);
}
 
template <typename Key, typename Value, typename BytesView>
template <bool Direction>
typename std::enable_if<
    Direction ==
        radix_tree<Key, Value, BytesView>::node::direction::Reverse,
    typename radix_tree<Key, Value,
                BytesView>::node::reverse_iterator>::type
radix_tree<Key, Value, BytesView>::node::begin() const
{
    return reverse_iterator(end<direction::Forward>());
}
 
template <typename Key, typename Value, typename BytesView>
template <bool Direction>
typename std::enable_if<
    Direction ==
        radix_tree<Key, Value, BytesView>::node::direction::Reverse,
    typename radix_tree<Key, Value,
                BytesView>::node::reverse_iterator>::type
radix_tree<Key, Value, BytesView>::node::end() const
{
    return reverse_iterator(begin<direction::Forward>());
}
 
template <typename Key, typename Value, typename BytesView>
template <bool Direction, typename Ptr>
typename radix_tree<Key, Value, BytesView>::node::template iterator<Direction>
radix_tree<Key, Value, BytesView>::node::find_child(const Ptr &n) const
{
    return std::find(begin<Direction>(), end<Direction>(), n);
}
 
template <typename Key, typename Value, typename BytesView>
template <bool Direction, typename Enable>
typename radix_tree<Key, Value, BytesView>::node::template iterator<Direction>
radix_tree<Key, Value, BytesView>::node::make_iterator(
    const tagged_node_ptr *ptr) const
{
    return forward_iterator(ptr, this);
}
 
template <typename Key, typename Value, typename BytesView>
template <bool IsConst>
radix_tree<Key, Value, BytesView>::radix_tree_iterator<
    IsConst>::radix_tree_iterator(leaf_ptr leaf_, node_ptr root)
    : leaf_(leaf_), root(root)
{
}
 
template <typename Key, typename Value, typename BytesView>
template <bool IsConst>
template <bool C, typename Enable>
radix_tree<Key, Value, BytesView>::radix_tree_iterator<
    IsConst>::radix_tree_iterator(const radix_tree_iterator<false> &rhs)
    : leaf_(rhs.leaf_)
{
}
 
template <typename Key, typename Value, typename BytesView>
template <bool IsConst>
typename radix_tree<Key, Value,
            BytesView>::template radix_tree_iterator<IsConst>::reference
    radix_tree<Key, Value,
           BytesView>::radix_tree_iterator<IsConst>::operator*() const
{
    assert(leaf_);
    return *leaf_;
}
 
template <typename Key, typename Value, typename BytesView>
template <bool IsConst>
typename radix_tree<Key, Value,
            BytesView>::template radix_tree_iterator<IsConst>::pointer
    radix_tree<Key, Value,
           BytesView>::radix_tree_iterator<IsConst>::operator->() const
{
    assert(leaf_);
    return leaf_;
}
 
template <typename Key, typename Value, typename BytesView>
template <bool IsConst>
template <typename V, typename Enable>
void
radix_tree<Key, Value, BytesView>::radix_tree_iterator<IsConst>::assign_val(
    basic_string_view<typename V::value_type, typename V::traits_type> rhs)
{
    auto pop = pool_base(pmemobj_pool_by_ptr(leaf_));
 
    if (rhs.size() <= leaf_->value().capacity()) {
        flat_transaction::run(pop, [&] { leaf_->value() = rhs; });
    } else {
        tagged_node_ptr *slot;
 
        if (!leaf_->parent) {
            assert(root->get_leaf() == leaf_);
            slot = root;
        } else {
            slot = const_cast<tagged_node_ptr *>(
                &*leaf_->parent->find_child(leaf_));
        }
 
        auto old_leaf = leaf_;
 
        flat_transaction::run(pop, [&] {
            *slot = leaf::make_key_args(old_leaf->parent,
                            old_leaf->key(), rhs);
            delete_persistent<typename radix_tree::leaf>(old_leaf);
        });
 
        leaf_ = slot->get_leaf();
    }
}
 
template <typename Key, typename Value, typename BytesView>
template <bool IsConst>
template <typename T, typename V, typename Enable>
void
radix_tree<Key, Value, BytesView>::radix_tree_iterator<IsConst>::assign_val(
    T &&rhs)
{
    auto pop = pool_base(pmemobj_pool_by_ptr(leaf_));
 
    flat_transaction::run(pop,
                  [&] { leaf_->value() = std::forward<T>(rhs); });
}
 
template <typename Key, typename Value, typename BytesView>
template <bool IsConst>
typename radix_tree<Key, Value,
            BytesView>::template radix_tree_iterator<IsConst> &
radix_tree<Key, Value, BytesView>::radix_tree_iterator<IsConst>::operator++()
{
    assert(leaf_);
 
    /* leaf is root, there is no other leaf in the tree */
    if (!leaf_->parent)
        leaf_ = nullptr;
    else {
        auto it = leaf_->parent->template find_child<
            radix_tree::node::direction::Forward>(leaf_);
 
        leaf_ = const_cast<leaf_ptr>(
            next_leaf<radix_tree::node::direction::Forward>(
                it, leaf_->parent));
    }
 
    return *this;
}
 
template <typename Key, typename Value, typename BytesView>
template <bool IsConst>
typename radix_tree<Key, Value,
            BytesView>::template radix_tree_iterator<IsConst> &
radix_tree<Key, Value, BytesView>::radix_tree_iterator<IsConst>::operator--()
{
    if (!leaf_) {
        /* this == end() */
        leaf_ = const_cast<leaf_ptr>(
            radix_tree::find_leaf<
                radix_tree::node::direction::Reverse>(*root));
    } else {
        /* Iterator must be decrementable. */
        assert(leaf_->parent);
 
        auto it = leaf_->parent->template find_child<
            radix_tree::node::direction::Reverse>(leaf_);
 
        leaf_ = const_cast<leaf_ptr>(
            next_leaf<radix_tree::node::direction::Reverse>(
                it, leaf_->parent));
    }
 
    return *this;
}
 
template <typename Key, typename Value, typename BytesView>
template <bool IsConst>
typename radix_tree<Key, Value,
            BytesView>::template radix_tree_iterator<IsConst>
radix_tree<Key, Value, BytesView>::radix_tree_iterator<IsConst>::operator++(int)
{
    auto tmp = *this;
 
    ++(*this);
 
    return tmp;
}
 
template <typename Key, typename Value, typename BytesView>
template <bool IsConst>
typename radix_tree<Key, Value,
            BytesView>::template radix_tree_iterator<IsConst>
radix_tree<Key, Value, BytesView>::radix_tree_iterator<IsConst>::operator--(int)
{
    auto tmp = *this;
 
    --(*this);
 
    return tmp;
}
 
template <typename Key, typename Value, typename BytesView>
template <bool IsConst>
template <bool C>
bool
radix_tree<Key, Value, BytesView>::radix_tree_iterator<IsConst>::operator!=(
    const radix_tree_iterator<C> &rhs) const
{
    return leaf_ != rhs.leaf_;
}
 
template <typename Key, typename Value, typename BytesView>
template <bool IsConst>
template <bool C>
bool
radix_tree<Key, Value, BytesView>::radix_tree_iterator<IsConst>::operator==(
    const radix_tree_iterator<C> &rhs) const
{
    return !(*this != rhs);
}
 
/*
 * Returns next leaf (either with smaller or larger key, depending on
 * ChildIterator type). This function might need to traverse the
 * tree upwards.
 */
template <typename Key, typename Value, typename BytesView>
template <bool Direction, typename Iterator>
typename radix_tree<Key, Value, BytesView>::leaf *
radix_tree<Key, Value, BytesView>::next_leaf(Iterator node,
                         tagged_node_ptr parent)
{
    do {
        ++node;
    } while (node != parent->template end<Direction>() && !(*node));
 
    /* No more children on this level, need to go up. */
    if (node == parent->template end<Direction>()) {
        auto p = parent->parent;
        if (!p) // parent == root
            return nullptr;
 
        auto p_it = p->template find_child<Direction>(parent);
        return next_leaf<Direction>(p_it, p);
    }
 
    return find_leaf<Direction>(*node);
}
 
/*
 * Returns smallest (or biggest, depending on ChildIterator) leaf
 * in a subtree.
 */
template <typename Key, typename Value, typename BytesView>
template <bool Direction>
typename radix_tree<Key, Value, BytesView>::leaf *
radix_tree<Key, Value, BytesView>::find_leaf(
    typename radix_tree<Key, Value, BytesView>::tagged_node_ptr n)
{
    assert(n);
 
    if (n.is_leaf())
        return n.get_leaf();
 
    for (auto it = n->template begin<Direction>();
         it != n->template end<Direction>(); ++it) {
        if (*it)
            return find_leaf<Direction>(*it);
    }
 
    /* There must be at least one leaf at the bottom. */
    std::abort();
}
 
template <typename Key, typename Value, typename BytesView>
Key &
radix_tree<Key, Value, BytesView>::leaf::key()
{
    return *reinterpret_cast<Key *>(this + 1);
}
 
template <typename Key, typename Value, typename BytesView>
Value &
radix_tree<Key, Value, BytesView>::leaf::value()
{
    auto key_dst = reinterpret_cast<char *>(this + 1);
    auto val_dst = reinterpret_cast<Value *>(
        key_dst + total_sizeof<Key>::value(key()));
 
    return *reinterpret_cast<Value *>(val_dst);
}
 
template <typename Key, typename Value, typename BytesView>
const Key &
radix_tree<Key, Value, BytesView>::leaf::key() const
{
    return *reinterpret_cast<const Key *>(this + 1);
}
 
template <typename Key, typename Value, typename BytesView>
const Value &
radix_tree<Key, Value, BytesView>::leaf::value() const
{
    auto key_dst = reinterpret_cast<const char *>(this + 1);
    auto val_dst = reinterpret_cast<const Value *>(
        key_dst + total_sizeof<Key>::value(key()));
 
    return *reinterpret_cast<const Value *>(val_dst);
}
 
template <typename Key, typename Value, typename BytesView>
radix_tree<Key, Value, BytesView>::leaf::~leaf()
{
    detail::destroy<Key>(key());
    detail::destroy<Value>(value());
}
 
template <typename Key, typename Value, typename BytesView>
persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent)
{
    auto t = std::make_tuple();
    return make(parent, std::piecewise_construct, t, t,
            typename detail::make_index_sequence<>::type{},
            typename detail::make_index_sequence<>::type{});
}
 
template <typename Key, typename Value, typename BytesView>
template <typename... Args1, typename... Args2>
persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
                          std::piecewise_construct_t pc,
                          std::tuple<Args1...> first_args,
                          std::tuple<Args2...> second_args)
{
    return make(parent, pc, first_args, second_args,
            typename detail::make_index_sequence<Args1...>::type{},
            typename detail::make_index_sequence<Args2...>::type{});
}
 
template <typename Key, typename Value, typename BytesView>
persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
                          const Key &k, const Value &v)
{
    return make(parent, std::piecewise_construct, std::forward_as_tuple(k),
            std::forward_as_tuple(v));
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename V>
persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent, K &&k,
                          V &&v)
{
    return make(parent, std::piecewise_construct,
            std::forward_as_tuple(std::forward<K>(k)),
            std::forward_as_tuple(std::forward<V>(v)));
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename... Args>
persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
radix_tree<Key, Value, BytesView>::leaf::make_key_args(tagged_node_ptr parent,
                               K &&k, Args &&... args)
{
    return make(parent, std::piecewise_construct,
            std::forward_as_tuple(std::forward<K>(k)),
            std::forward_as_tuple(std::forward<Args>(args)...));
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename V>
persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
                          detail::pair<K, V> &&p)
{
    return make(parent, std::piecewise_construct,
            std::forward_as_tuple(std::move(p.first)),
            std::forward_as_tuple(std::move(p.second)));
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename V>
persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
                          const detail::pair<K, V> &p)
{
    return make(parent, std::piecewise_construct,
            std::forward_as_tuple(p.first),
            std::forward_as_tuple(p.second));
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename V>
persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
                          std::pair<K, V> &&p)
{
    return make(parent, std::piecewise_construct,
            std::forward_as_tuple(std::move(p.first)),
            std::forward_as_tuple(std::move(p.second)));
}
 
template <typename Key, typename Value, typename BytesView>
template <typename K, typename V>
persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
                          const std::pair<K, V> &p)
{
    return make(parent, std::piecewise_construct,
            std::forward_as_tuple(p.first),
            std::forward_as_tuple(p.second));
}
 
template <typename Key, typename Value, typename BytesView>
template <typename... Args1, typename... Args2, size_t... I1, size_t... I2>
persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
                          std::piecewise_construct_t,
                          std::tuple<Args1...> &first_args,
                          std::tuple<Args2...> &second_args,
                          detail::index_sequence<I1...>,
                          detail::index_sequence<I2...>)
{
    standard_alloc_policy<void> a;
    auto key_size = total_sizeof<Key>::value(std::get<I1>(first_args)...);
    auto val_size =
        total_sizeof<Value>::value(std::get<I2>(second_args)...);
    auto ptr = static_cast<persistent_ptr<leaf>>(
        a.allocate(sizeof(leaf) + key_size + val_size));
 
    auto key_dst = reinterpret_cast<Key *>(ptr.get() + 1);
    auto val_dst = reinterpret_cast<Value *>(
        reinterpret_cast<char *>(key_dst) + key_size);
 
    new (ptr.get()) leaf();
    new (key_dst) Key(std::forward<Args1>(std::get<I1>(first_args))...);
    new (val_dst) Value(std::forward<Args2>(std::get<I2>(second_args))...);
 
    ptr->parent = parent;
 
    return ptr;
}
 
template <typename Key, typename Value, typename BytesView>
persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
                          const leaf &other)
{
    return make(parent, other.key(), other.value());
}
 
template <typename Key, typename Value, typename BytesView>
void
radix_tree<Key, Value, BytesView>::check_pmem()
{
    if (nullptr == pmemobj_pool_by_ptr(this))
        throw pmem::pool_error("Invalid pool handle.");
}
 
template <typename Key, typename Value, typename BytesView>
void
radix_tree<Key, Value, BytesView>::check_tx_stage_work()
{
    if (pmemobj_tx_stage() != TX_STAGE_WORK)
        throw pmem::transaction_scope_error(
            "Function called out of transaction scope.");
}
 
template <typename Key, typename Value, typename BytesView>
void
swap(radix_tree<Key, Value, BytesView> &lhs,
     radix_tree<Key, Value, BytesView> &rhs)
{
    lhs.swap(rhs);
}
 
} /* namespace experimental */
} /* namespace obj */
 
namespace detail
{
/* Check if type is pmem::obj::basic_string or
 * pmem::obj::basic_inline_string */
template <typename>
struct is_string : std::false_type {
};
 
template <typename CharT, typename Traits>
struct is_string<obj::basic_string<CharT, Traits>> : std::true_type {
};
 
template <typename CharT, typename Traits>
struct is_string<obj::experimental::basic_inline_string<CharT, Traits>>
    : std::true_type {
};
 
template <typename T>
struct bytes_view<T, typename std::enable_if<is_string<T>::value>::type> {
    using CharT = typename T::value_type;
    using Traits = typename T::traits_type;
 
    template <
        typename C,
        typename Enable = typename std::enable_if<std::is_constructible<
            obj::basic_string_view<CharT, Traits>, C>::value>::type>
    bytes_view(const C *s) : s(*s)
    {
    }
 
    char operator[](std::size_t p) const
    {
        return reinterpret_cast<const char *>(s.data())[p];
    }
 
    size_t
    size() const
    {
        return s.size() * sizeof(CharT);
    }
 
    obj::basic_string_view<CharT, Traits> s;
 
    using is_transparent = void;
};
 
template <typename T>
struct bytes_view<T,
          typename std::enable_if<std::is_integral<T>::value &&
                      !std::is_signed<T>::value>::type> {
    bytes_view(const T *k) : k(k)
    {
#if __cpp_lib_endian
        static_assert(
            std::endian::native == std::endian::little,
            "Scalar type are not little endian on this platform!");
#elif !defined(NDEBUG)
        /* Assert little endian is used. */
        uint16_t word = (2 << 8) + 1;
        assert(((char *)&word)[0] == 1);
#endif
    }
 
    char operator[](std::size_t p) const
    {
        return reinterpret_cast<const char *>(k)[size() - p - 1];
    }
 
    constexpr size_t
    size() const
    {
        return sizeof(T);
    }
 
    const T *k;
};
} /* namespace detail */
 
} /* namespace pmem */
 
#endif /* LIBPMEMOBJ_CPP_RADIX_HPP */