added iOS source code

[wl-app.git] / iOS / Pods / Realm / include / core / realm / bptree.hpp

/*************************************************************************
 *
 * Copyright 2016 Realm Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 **************************************************************************/

#ifndef REALM_BPTREE_HPP
#define REALM_BPTREE_HPP

#include <memory> // std::unique_ptr
#include <realm/array.hpp>
#include <realm/array_basic.hpp>
#include <realm/column_type_traits.hpp>
#include <realm/impl/destroy_guard.hpp>
#include <realm/impl/output_stream.hpp>

namespace realm {

/// Specialize BpTree to implement column types.
template <class T>
class BpTree;

class ArrayInteger;
class ArrayIntNull;

class BpTreeNode : public Array {
public:
    using Array::Array;
    /// Get the number of elements in the B+-tree rooted at this array
    /// node. The root must not be a leaf.
    ///
    /// Please avoid using this function (consider it deprecated). It
    /// will have to be removed if we choose to get rid of the last
    /// element of the main array of an inner B+-tree node that stores
    /// the total number of elements in the subtree. The motivation
    /// for removing it, is that it will significantly improve the
    /// efficiency when inserting after, and erasing the last element.
    size_t get_bptree_size() const noexcept;

    /// The root must not be a leaf.
    static size_t get_bptree_size_from_header(const char* root_header) noexcept;


    /// Find the leaf node corresponding to the specified element
    /// index index. The specified element index must refer to an
    /// element that exists in the tree. This function must be called
    /// on an inner B+-tree node, never a leaf. Note that according to
    /// invar:bptree-nonempty-inner and invar:bptree-nonempty-leaf, an
    /// inner B+-tree node can never be empty.
    ///
    /// This function is not obliged to instantiate intermediate array
    /// accessors. For this reason, this function cannot be used for
    /// operations that modify the tree, as that requires an unbroken
    /// chain of parent array accessors between the root and the
    /// leaf. Thus, despite the fact that the returned MemRef object
    /// appears to allow modification of the referenced memory, the
    /// caller must handle the memory reference as if it was
    /// const-qualified.
    ///
    /// \return (`leaf_header`, `ndx_in_leaf`) where `leaf_header`
    /// points to the the header of the located leaf, and
    /// `ndx_in_leaf` is the local index within that leaf
    /// corresponding to the specified element index.
    std::pair<MemRef, size_t> get_bptree_leaf(size_t elem_ndx) const noexcept;


    class NodeInfo;
    class VisitHandler;

    /// Visit leaves of the B+-tree rooted at this inner node,
    /// starting with the leaf that contains the element at the
    /// specified element index start offset, and ending when the
    /// handler returns false. The specified element index offset must
    /// refer to an element that exists in the tree. This function
    /// must be called on an inner B+-tree node, never a leaf. Note
    /// that according to invar:bptree-nonempty-inner and
    /// invar:bptree-nonempty-leaf, an inner B+-tree node can never be
    /// empty.
    ///
    /// \param elem_ndx_offset The start position (must be valid).
    ///
    /// \param elems_in_tree The total number of elements in the tree.
    ///
    /// \param handler The callback which will get called for each leaf.
    ///
    /// \return True if, and only if the handler has returned true for
    /// all visited leafs.
    bool visit_bptree_leaves(size_t elem_ndx_offset, size_t elems_in_tree, VisitHandler& handler);


    class UpdateHandler;

    /// Call the handler for every leaf. This function must be called
    /// on an inner B+-tree node, never a leaf.
    void update_bptree_leaves(UpdateHandler&);

    /// Call the handler for the leaf that contains the element at the
    /// specified index. This function must be called on an inner
    /// B+-tree node, never a leaf.
    void update_bptree_elem(size_t elem_ndx, UpdateHandler&);


    class EraseHandler;

    /// Erase the element at the specified index in the B+-tree with
    /// the specified root. When erasing the last element, you must
    /// pass npos in place of the index. This function must be called
    /// with a root that is an inner B+-tree node, never a leaf.
    ///
    /// This function is guaranteed to succeed (not throw) if the
    /// specified element was inserted during the current transaction,
    /// and no other modifying operation has been carried out since
    /// then (noexcept:bptree-erase-alt).
    ///
    /// FIXME: ExceptionSafety: The exception guarantee explained
    /// above is not as powerfull as we would like it to be. Here is
    /// what we would like: This function is guaranteed to succeed
    /// (not throw) if the specified element was inserted during the
    /// current transaction (noexcept:bptree-erase). This must be true
    /// even if the element is modified after insertion, and/or if
    /// other elements are inserted or erased around it. There are two
    /// aspects of the current design that stand in the way of this
    /// guarantee: (A) The fact that the node accessor, that is cached
    /// in the column accessor, has to be reallocated/reinstantiated
    /// when the root switches between being a leaf and an inner
    /// node. This problem would go away if we always cached the last
    /// used leaf accessor in the column accessor instead. (B) The
    /// fact that replacing one child ref with another can fail,
    /// because it may require reallocation of memory to expand the
    /// bit-width. This can be fixed in two ways: Either have the
    /// inner B+-tree nodes always have a bit-width of 64, or allow
    /// the root node to be discarded and the column ref to be set to
    /// zero in Table::m_columns.
    static void erase_bptree_elem(BpTreeNode* root, size_t elem_ndx, EraseHandler&);

    template <class TreeTraits>
    struct TreeInsert : TreeInsertBase {
        typename TreeTraits::value_type m_value;
        bool m_nullable;
    };

    /// Same as bptree_insert() but insert after the last element.
    template <class TreeTraits>
    ref_type bptree_append(TreeInsert<TreeTraits>& state);

    /// Insert an element into the B+-subtree rooted at this array
    /// node. The element is inserted before the specified element
    /// index. This function must be called on an inner B+-tree node,
    /// never a leaf. If this inner node had to be split, this
    /// function returns the `ref` of the new sibling.
    template <class TreeTraits>
    ref_type bptree_insert(size_t elem_ndx, TreeInsert<TreeTraits>& state);

protected:
    /// Insert a new child after original. If the parent has to be
    /// split, this function returns the `ref` of the new parent node.
    ref_type insert_bptree_child(Array& offsets, size_t orig_child_ndx, ref_type new_sibling_ref,
                                 TreeInsertBase& state);

    void ensure_bptree_offsets(Array& offsets);
    void create_bptree_offsets(Array& offsets, int_fast64_t first_value);

    bool do_erase_bptree_elem(size_t elem_ndx, EraseHandler&);
};

class BpTreeBase {
public:
    struct unattached_tag {
    };

    // Disable copying, this is not allowed.
    BpTreeBase& operator=(const BpTreeBase&) = delete;
    BpTreeBase(const BpTreeBase&) = delete;

    // Accessor concept:
    Allocator& get_alloc() const noexcept;
    void destroy() noexcept;
    void detach();
    bool is_attached() const noexcept;
    void set_parent(ArrayParent* parent, size_t ndx_in_parent) noexcept;
    size_t get_ndx_in_parent() const noexcept;
    void set_ndx_in_parent(size_t ndx) noexcept;
    void update_from_parent(size_t old_baseline) noexcept;
    MemRef clone_deep(Allocator& alloc) const;

    // BpTree interface:
    const Array& root() const noexcept;
    Array& root() noexcept;
    bool root_is_leaf() const noexcept;
    BpTreeNode& root_as_node();
    const BpTreeNode& root_as_node() const;
    void introduce_new_root(ref_type new_sibling_ref, TreeInsertBase& state, bool is_append);
    void replace_root(std::unique_ptr<Array> leaf);

protected:
    explicit BpTreeBase(std::unique_ptr<Array> root);
    explicit BpTreeBase(BpTreeBase&&) = default;
    BpTreeBase& operator=(BpTreeBase&&) = default;
    std::unique_ptr<Array> m_root;

    struct SliceHandler {
        virtual MemRef slice_leaf(MemRef leaf_mem, size_t offset, size_t size, Allocator& target_alloc) = 0;
        ~SliceHandler() noexcept
        {
        }
    };
    static ref_type write_subtree(const BpTreeNode& root, size_t slice_offset, size_t slice_size, size_t table_size,
                                  SliceHandler&, _impl::OutputStream&);
    friend class ColumnBase;
    friend class ColumnBaseSimple;

private:
    struct WriteSliceHandler;

    // FIXME: Move B+Tree functionality from Array to this class.
};


// Default implementation of BpTree. This should work for all types that have monomorphic
// leaves (i.e. all leaves are of the same type).
template <class T>
class BpTree : public BpTreeBase {
public:
    using value_type = T;
    using LeafType = typename ColumnTypeTraits<T>::leaf_type;

    /// LeafInfo is used by get_leaf() to provide access to a leaf
    /// without instantiating unnecessary nodes along the way.
    /// Upon return, out_leaf with hold a pointer to the leaf containing
    /// the index given to get_leaf(). If the index happens to be
    /// in the root node (i.e., the root is a leaf), it will point
    /// to the root node.
    /// If the index isn't in the root node, fallback will be initialized
    /// to represent the leaf holding the node, and out_leaf will be set
    /// to point to fallback.
    struct LeafInfo {
        const LeafType** out_leaf;
        LeafType* fallback;
    };

    BpTree();
    explicit BpTree(BpTreeBase::unattached_tag);
    explicit BpTree(Allocator& alloc);
    REALM_DEPRECATED("Initialize with MemRef instead")
    explicit BpTree(std::unique_ptr<Array> init_root)
        : BpTreeBase(std::move(init_root))
    {
    }
    explicit BpTree(Allocator& alloc, MemRef mem)
        : BpTreeBase(std::unique_ptr<Array>(new LeafType(alloc)))
    {
        init_from_mem(alloc, mem);
    }
    BpTree(BpTree&&) = default;
    BpTree& operator=(BpTree&&) = default;

    // Disable copying, this is not allowed.
    BpTree& operator=(const BpTree&) = delete;
    BpTree(const BpTree&) = delete;

    void init_from_ref(Allocator& alloc, ref_type ref);
    void init_from_mem(Allocator& alloc, MemRef mem);
    void init_from_parent();

    size_t size() const noexcept;
    bool is_empty() const noexcept
    {
        return size() == 0;
    }

    T get(size_t ndx) const noexcept;
    bool is_null(size_t ndx) const noexcept;
    void set(size_t, T value);
    void set_null(size_t);
    void insert(size_t ndx, T value, size_t num_rows = 1);
    void erase(size_t ndx, bool is_last = false);
    void move_last_over(size_t ndx, size_t last_row_ndx);
    void clear();
    T front() const noexcept;
    T back() const noexcept;

    size_t find_first(T value, size_t begin = 0, size_t end = npos) const;
    void find_all(IntegerColumn& out_indices, T value, size_t begin = 0, size_t end = npos) const;

    static MemRef create_leaf(Array::Type leaf_type, size_t size, T value, Allocator&);

    /// See LeafInfo for information about what to put in the inout_leaf
    /// parameter.
    ///
    /// This function cannot be used for modifying operations as it
    /// does not ensure the presence of an unbroken chain of parent
    /// accessors. For this reason, the identified leaf should always
    /// be accessed through the returned const-qualified reference,
    /// and never directly through the specfied fallback accessor.
    void get_leaf(size_t ndx, size_t& out_ndx_in_leaf, LeafInfo& inout_leaf) const noexcept;

    void update_each(BpTreeNode::UpdateHandler&);
    void update_elem(size_t, BpTreeNode::UpdateHandler&);

    void adjust(size_t ndx, T diff);
    void adjust(T diff);
    void adjust_ge(T limit, T diff);

    ref_type write(size_t slice_offset, size_t slice_size, size_t table_size, _impl::OutputStream& out) const;

#if defined(REALM_DEBUG)
    void verify() const;
    static size_t verify_leaf(MemRef mem, Allocator& alloc);
#endif
    static void leaf_to_dot(MemRef mem, ArrayParent* parent, size_t ndx_in_parent, std::ostream& out,
                            Allocator& alloc);

private:
    LeafType& root_as_leaf();
    const LeafType& root_as_leaf() const;

    std::unique_ptr<Array> create_root_from_ref(Allocator& alloc, ref_type ref);
    std::unique_ptr<Array> create_root_from_mem(Allocator& alloc, MemRef mem);

    struct EraseHandler;
    struct UpdateHandler;
    struct SetNullHandler;
    struct SliceHandler;
    struct AdjustHandler;
    struct AdjustGEHandler;

    struct LeafValueInserter;
    struct LeafNullInserter;

    template <class TreeTraits>
    void bptree_insert(size_t row_ndx, BpTreeNode::TreeInsert<TreeTraits>& state, size_t num_rows);
};


class BpTreeNode::NodeInfo {
public:
    MemRef m_mem;
    Array* m_parent;
    size_t m_ndx_in_parent;
    size_t m_offset, m_size;
};

class BpTreeNode::VisitHandler {
public:
    virtual bool visit(const NodeInfo& leaf_info) = 0;
    virtual ~VisitHandler() noexcept
    {
    }
};


class BpTreeNode::UpdateHandler {
public:
    virtual void update(MemRef, ArrayParent*, size_t leaf_ndx_in_parent, size_t elem_ndx_in_leaf) = 0;
    virtual ~UpdateHandler() noexcept
    {
    }
};


class BpTreeNode::EraseHandler {
public:
    /// If the specified leaf has more than one element, this function
    /// must erase the specified element from the leaf and return
    /// false. Otherwise, when the leaf has a single element, this
    /// function must return true without modifying the leaf. If \a
    /// elem_ndx_in_leaf is `npos`, it refers to the last element in
    /// the leaf. The implementation of this function must be
    /// exception safe. This function is guaranteed to be called at
    /// most once during each execution of Array::erase_bptree_elem(),
    /// and *exactly* once during each *successful* execution of
    /// Array::erase_bptree_elem().
    virtual bool erase_leaf_elem(MemRef, ArrayParent*, size_t leaf_ndx_in_parent, size_t elem_ndx_in_leaf) = 0;

    virtual void destroy_leaf(MemRef leaf_mem) noexcept = 0;

    /// Must replace the current root with the specified leaf. The
    /// implementation of this function must not destroy the
    /// underlying root node, or any of its children, as that will be
    /// done by Array::erase_bptree_elem(). The implementation of this
    /// function must be exception safe.
    virtual void replace_root_by_leaf(MemRef leaf_mem) = 0;

    /// Same as replace_root_by_leaf(), but must replace the root with
    /// an empty leaf. Also, if this function is called during an
    /// execution of Array::erase_bptree_elem(), it is guaranteed that
    /// it will be preceeded by a call to erase_leaf_elem().
    virtual void replace_root_by_empty_leaf() = 0;

    virtual ~EraseHandler() noexcept
    {
    }
};


/// Implementation:

inline BpTreeBase::BpTreeBase(std::unique_ptr<Array> init_root)
    : m_root(std::move(init_root))
{
}

inline Allocator& BpTreeBase::get_alloc() const noexcept
{
    return m_root->get_alloc();
}

inline void BpTreeBase::destroy() noexcept
{
    if (m_root)
        m_root->destroy_deep();
}

inline void BpTreeBase::detach()
{
    m_root->detach();
}

inline bool BpTreeBase::is_attached() const noexcept
{
    return m_root->is_attached();
}

inline bool BpTreeBase::root_is_leaf() const noexcept
{
    return !m_root->is_inner_bptree_node();
}

inline BpTreeNode& BpTreeBase::root_as_node()
{
    REALM_ASSERT_DEBUG(!root_is_leaf());
    REALM_ASSERT_DEBUG(dynamic_cast<BpTreeNode*>(m_root.get()) != nullptr);
    return static_cast<BpTreeNode&>(root());
}

inline const BpTreeNode& BpTreeBase::root_as_node() const
{
    Array* arr = m_root.get();
    REALM_ASSERT_DEBUG(!root_is_leaf());
    REALM_ASSERT_DEBUG(dynamic_cast<const BpTreeNode*>(arr) != nullptr);
    return static_cast<const BpTreeNode&>(*arr);
}

inline void BpTreeBase::set_parent(ArrayParent* parent, size_t ndx_in_parent) noexcept
{
    m_root->set_parent(parent, ndx_in_parent);
}

inline size_t BpTreeBase::get_ndx_in_parent() const noexcept
{
    return m_root->get_ndx_in_parent();
}

inline void BpTreeBase::set_ndx_in_parent(size_t ndx) noexcept
{
    m_root->set_ndx_in_parent(ndx);
}

inline void BpTreeBase::update_from_parent(size_t old_baseline) noexcept
{
    m_root->update_from_parent(old_baseline);
}

inline MemRef BpTreeBase::clone_deep(Allocator& alloc) const
{
    return m_root->clone_deep(alloc);
}

inline const Array& BpTreeBase::root() const noexcept
{
    return *m_root;
}

inline Array& BpTreeBase::root() noexcept
{
    return *m_root;
}

inline size_t BpTreeNode::get_bptree_size() const noexcept
{
    REALM_ASSERT_DEBUG(is_inner_bptree_node());
    int_fast64_t v = back();
    return size_t(v / 2); // v = 1 + 2*total_elems_in_tree
}

inline size_t BpTreeNode::get_bptree_size_from_header(const char* root_header) noexcept
{
    REALM_ASSERT_DEBUG(get_is_inner_bptree_node_from_header(root_header));
    size_t root_size = get_size_from_header(root_header);
    int_fast64_t v = get(root_header, root_size - 1);
    return size_t(v / 2); // v = 1 + 2*total_elems_in_tree
}

inline void BpTreeNode::ensure_bptree_offsets(Array& offsets)
{
    int_fast64_t first_value = get(0);
    if (first_value % 2 == 0) {
        offsets.init_from_ref(to_ref(first_value));
    }
    else {
        create_bptree_offsets(offsets, first_value); // Throws
    }
    offsets.set_parent(this, 0);
}


template <class TreeTraits>
ref_type BpTreeNode::bptree_append(TreeInsert<TreeTraits>& state)
{
    // FIXME: Consider exception safety. Especially, how can the split
    // be carried out in an exception safe manner?
    //
    // Can split be done as a separate preparation step, such that if
    // the actual insert fails, the split will still have occured.
    //
    // Unfortunately, it requires a rather significant rearrangement
    // of the insertion flow. Instead of returning the sibling ref
    // from insert functions, the leaf-insert functions must instead
    // call the special bptree_insert() function on the parent, which
    // will then cascade the split towards the root as required.
    //
    // At each level where a split is required (starting at the leaf):
    //
    //  1. Create the new sibling.
    //
    //  2. Copy relevant entries over such that new sibling is in
    //     its final state.
    //
    //  3. Call Array::bptree_insert() on parent with sibling ref.
    //
    //  4. Rearrange entries in original sibling and truncate as
    //     required (must not throw).
    //
    // What about the 'offsets' array? It will always be
    // present. Consider this carefully.

    REALM_ASSERT_DEBUG(size() >= 1 + 1 + 1); // At least one child

    ArrayParent& childs_parent = *this;
    size_t child_ref_ndx = size() - 2;
    ref_type child_ref = get_as_ref(child_ref_ndx), new_sibling_ref;
    char* child_header = static_cast<char*>(m_alloc.translate(child_ref));

    bool child_is_leaf = !get_is_inner_bptree_node_from_header(child_header);
    if (child_is_leaf) {
        size_t elem_ndx_in_child = npos; // Append
        new_sibling_ref = TreeTraits::leaf_insert(MemRef(child_header, child_ref, m_alloc), childs_parent,
                                                  child_ref_ndx, m_alloc, elem_ndx_in_child, state); // Throws
    }
    else {
        BpTreeNode child(m_alloc);
        child.init_from_mem(MemRef(child_header, child_ref, m_alloc));
        child.set_parent(&childs_parent, child_ref_ndx);
        new_sibling_ref = child.bptree_append(state); // Throws
    }

    if (REALM_LIKELY(!new_sibling_ref)) {
        // +2 because stored value is 1 + 2*total_elems_in_subtree
        adjust(size() - 1, +2); // Throws
        return 0;               // Child was not split, so parent was not split either
    }

    Array offsets(m_alloc);
    int_fast64_t first_value = get(0);
    if (first_value % 2 == 0) {
        // Offsets array is present (general form)
        offsets.init_from_ref(to_ref(first_value));
        offsets.set_parent(this, 0);
    }
    size_t child_ndx = child_ref_ndx - 1;
    return insert_bptree_child(offsets, child_ndx, new_sibling_ref, state); // Throws
}


template <class TreeTraits>
ref_type BpTreeNode::bptree_insert(size_t elem_ndx, TreeInsert<TreeTraits>& state)
{
    REALM_ASSERT_3(size(), >=, 1 + 1 + 1); // At least one child

    // Conversion to general form if in compact form. Since this
    // conversion will occur from root to leaf, it will maintain
    // invar:bptree-node-form.
    Array offsets(m_alloc);
    ensure_bptree_offsets(offsets); // Throws

    size_t child_ndx, elem_ndx_in_child;
    if (elem_ndx == 0) {
        // Optimization for prepend
        child_ndx = 0;
        elem_ndx_in_child = 0;
    }
    else {
        // There is a choice to be made when the element is to be
        // inserted between two subtrees. It can either be appended to
        // the first subtree, or it can be prepended to the second
        // one. We currently always append to the first subtree. It is
        // essentially a matter of using the lower vs. the upper bound
        // when searching through the offsets array.
        child_ndx = offsets.lower_bound_int(elem_ndx);
        REALM_ASSERT_3(child_ndx, <, size() - 2);
        size_t elem_ndx_offset = child_ndx == 0 ? 0 : to_size_t(offsets.get(child_ndx - 1));
        elem_ndx_in_child = elem_ndx - elem_ndx_offset;
    }

    ArrayParent& childs_parent = *this;
    size_t child_ref_ndx = child_ndx + 1;
    ref_type child_ref = get_as_ref(child_ref_ndx), new_sibling_ref;
    char* child_header = static_cast<char*>(m_alloc.translate(child_ref));
    bool child_is_leaf = !get_is_inner_bptree_node_from_header(child_header);
    if (child_is_leaf) {
        REALM_ASSERT_3(elem_ndx_in_child, <=, REALM_MAX_BPNODE_SIZE);
        new_sibling_ref = TreeTraits::leaf_insert(MemRef(child_header, child_ref, m_alloc), childs_parent,
                                                  child_ref_ndx, m_alloc, elem_ndx_in_child, state); // Throws
    }
    else {
        BpTreeNode child(m_alloc);
        child.init_from_mem(MemRef(child_header, child_ref, m_alloc));
        child.set_parent(&childs_parent, child_ref_ndx);
        new_sibling_ref = child.bptree_insert(elem_ndx_in_child, state); // Throws
    }

    if (REALM_LIKELY(!new_sibling_ref)) {
        // +2 because stored value is 1 + 2*total_elems_in_subtree
        adjust(size() - 1, +2); // Throws
        offsets.adjust(child_ndx, offsets.size(), +1);
        return 0; // Child was not split, so parent was not split either
    }

    return insert_bptree_child(offsets, child_ndx, new_sibling_ref, state); // Throws
}

template <class T>
BpTree<T>::BpTree()
    : BpTree(Allocator::get_default())
{
}

template <class T>
BpTree<T>::BpTree(Allocator& alloc)
    : BpTreeBase(std::unique_ptr<Array>(new LeafType(alloc)))
{
}

template <class T>
BpTree<T>::BpTree(BpTreeBase::unattached_tag)
    : BpTreeBase(nullptr)
{
}

template <class T>
std::unique_ptr<Array> BpTree<T>::create_root_from_mem(Allocator& alloc, MemRef mem)
{
    const char* header = mem.get_addr();
    std::unique_ptr<Array> new_root;
    bool is_inner_bptree_node = Array::get_is_inner_bptree_node_from_header(header);

    bool can_reuse_root_accessor =
        m_root && &m_root->get_alloc() == &alloc && m_root->is_inner_bptree_node() == is_inner_bptree_node;
    if (can_reuse_root_accessor) {
        if (is_inner_bptree_node) {
            m_root->init_from_mem(mem);
        }
        else {
            static_cast<LeafType&>(*m_root).init_from_mem(mem);
        }
        return std::move(m_root); // Same root will be reinstalled.
    }

    // Not reusing root note, allocating a new one.
    if (is_inner_bptree_node) {
        new_root.reset(new BpTreeNode{alloc});
        new_root->init_from_mem(mem);
    }
    else {
        std::unique_ptr<LeafType> leaf{new LeafType{alloc}};
        leaf->init_from_mem(mem);
        new_root = std::move(leaf);
    }
    return new_root;
}

template <class T>
std::unique_ptr<Array> BpTree<T>::create_root_from_ref(Allocator& alloc, ref_type ref)
{
    MemRef mem = MemRef{alloc.translate(ref), ref, alloc};
    return create_root_from_mem(alloc, mem);
}

template <class T>
void BpTree<T>::init_from_ref(Allocator& alloc, ref_type ref)
{
    auto new_root = create_root_from_ref(alloc, ref);
    replace_root(std::move(new_root));
}

template <class T>
void BpTree<T>::init_from_mem(Allocator& alloc, MemRef mem)
{
    auto new_root = create_root_from_mem(alloc, mem);
    replace_root(std::move(new_root));
}

template <class T>
void BpTree<T>::init_from_parent()
{
    ref_type ref = root().get_ref_from_parent();
    if (ref) {
        ArrayParent* parent = m_root->get_parent();
        size_t ndx_in_parent = m_root->get_ndx_in_parent();
        auto new_root = create_root_from_ref(get_alloc(), ref);
        new_root->set_parent(parent, ndx_in_parent);
        m_root = std::move(new_root);
    }
    else {
        m_root->detach();
    }
}

template <class T>
typename BpTree<T>::LeafType& BpTree<T>::root_as_leaf()
{
    REALM_ASSERT_DEBUG(root_is_leaf());
    REALM_ASSERT_DEBUG(dynamic_cast<LeafType*>(m_root.get()) != nullptr);
    return static_cast<LeafType&>(root());
}

template <class T>
const typename BpTree<T>::LeafType& BpTree<T>::root_as_leaf() const
{
    REALM_ASSERT_DEBUG(root_is_leaf());
    REALM_ASSERT_DEBUG(dynamic_cast<const LeafType*>(m_root.get()) != nullptr);
    return static_cast<const LeafType&>(root());
}

template <class T>
size_t BpTree<T>::size() const noexcept
{
    if (root_is_leaf()) {
        return root_as_leaf().size();
    }
    return root_as_node().get_bptree_size();
}

template <class T>
T BpTree<T>::back() const noexcept
{
    // FIXME: slow
    return get(size() - 1);
}

namespace _impl {

// NullableOrNothing encapsulates the behavior of nullable and
// non-nullable leaf types, so that non-nullable leaf types
// don't have to implement is_null/set_null but BpTree can still
// support the interface (and return false / assert when null
// is not supported).
template <class Leaf>
struct NullableOrNothing {
    static bool is_null(const Leaf& leaf, size_t ndx)
    {
        return leaf.is_null(ndx);
    }
    static void set_null(Leaf& leaf, size_t ndx)
    {
        leaf.set_null(ndx);
    }
};
template <>
struct NullableOrNothing<ArrayInteger> {
    static bool is_null(const ArrayInteger&, size_t)
    {
        return false;
    }
    static void set_null(ArrayInteger&, size_t)
    {
        REALM_ASSERT_RELEASE(false);
    }
};
}

template <class T>
bool BpTree<T>::is_null(size_t ndx) const noexcept
{
    if (root_is_leaf()) {
        return _impl::NullableOrNothing<LeafType>::is_null(root_as_leaf(), ndx);
    }
    LeafType fallback(get_alloc());
    const LeafType* leaf;
    LeafInfo leaf_info{&leaf, &fallback};
    size_t ndx_in_leaf;
    get_leaf(ndx, ndx_in_leaf, leaf_info);
    return _impl::NullableOrNothing<LeafType>::is_null(*leaf, ndx_in_leaf);
}

template <class T>
T BpTree<T>::get(size_t ndx) const noexcept
{
    REALM_ASSERT_DEBUG_EX(ndx < size(), ndx, size());
    if (root_is_leaf()) {
        return root_as_leaf().get(ndx);
    }

    // Use direct getter to avoid initializing leaf array:
    std::pair<MemRef, size_t> p = root_as_node().get_bptree_leaf(ndx);
    const char* leaf_header = p.first.get_addr();
    size_t ndx_in_leaf = p.second;
    return LeafType::get(leaf_header, ndx_in_leaf);
}

template <class T>
template <class TreeTraits>
void BpTree<T>::bptree_insert(size_t row_ndx, BpTreeNode::TreeInsert<TreeTraits>& state, size_t num_rows)
{
    ref_type new_sibling_ref;
    for (size_t i = 0; i < num_rows; ++i) {
        size_t row_ndx_2 = row_ndx == realm::npos ? realm::npos : row_ndx + i;
        if (root_is_leaf()) {
            REALM_ASSERT_DEBUG(row_ndx_2 == realm::npos || row_ndx_2 < REALM_MAX_BPNODE_SIZE);
            new_sibling_ref = root_as_leaf().bptree_leaf_insert(row_ndx_2, state.m_value, state);
        }
        else {
            if (row_ndx_2 == realm::npos) {
                new_sibling_ref = root_as_node().bptree_append(state); // Throws
            }
            else {
                new_sibling_ref = root_as_node().bptree_insert(row_ndx_2, state); // Throws
            }
        }

        if (REALM_UNLIKELY(new_sibling_ref)) {
            bool is_append = row_ndx_2 == realm::npos;
            introduce_new_root(new_sibling_ref, state, is_append);
        }
    }
}

template <class T>
struct BpTree<T>::LeafValueInserter {
    using value_type = T;
    T m_value;
    LeafValueInserter(T value)
        : m_value(std::move(value))
    {
    }

    // TreeTraits concept:
    static ref_type leaf_insert(MemRef leaf_mem, ArrayParent& parent, size_t ndx_in_parent, Allocator& alloc,
                                size_t ndx_in_leaf, BpTreeNode::TreeInsert<LeafValueInserter>& state)
    {
        LeafType leaf{alloc};
        leaf.init_from_mem(leaf_mem);
        leaf.set_parent(&parent, ndx_in_parent);
        // Should not move out of m_value, because the same inserter may be used to perform
        // multiple insertions (for example, if num_rows > 1).
        return leaf.bptree_leaf_insert(ndx_in_leaf, state.m_value, state);
    }
};

template <class T>
struct BpTree<T>::LeafNullInserter {
    using value_type = null;
    // TreeTraits concept:
    static ref_type leaf_insert(MemRef leaf_mem, ArrayParent& parent, size_t ndx_in_parent, Allocator& alloc,
                                size_t ndx_in_leaf, BpTreeNode::TreeInsert<LeafNullInserter>& state)
    {
        LeafType leaf{alloc};
        leaf.init_from_mem(leaf_mem);
        leaf.set_parent(&parent, ndx_in_parent);
        return leaf.bptree_leaf_insert(ndx_in_leaf, null{}, state);
    }
};

template <class T>
void BpTree<T>::insert(size_t row_ndx, T value, size_t num_rows)
{
    REALM_ASSERT_DEBUG(row_ndx == npos || row_ndx < size());
    BpTreeNode::TreeInsert<LeafValueInserter> inserter;
    inserter.m_value = std::move(value);
    inserter.m_nullable = std::is_same<T, util::Optional<int64_t>>::value; // FIXME
    bptree_insert(row_ndx, inserter, num_rows);                            // Throws
}

template <class T>
struct BpTree<T>::UpdateHandler : BpTreeNode::UpdateHandler {
    LeafType m_leaf;
    const T m_value;
    UpdateHandler(BpTreeBase& tree, T value) noexcept
        : m_leaf(tree.get_alloc())
        , m_value(std::move(value))
    {
    }
    void update(MemRef mem, ArrayParent* parent, size_t ndx_in_parent, size_t elem_ndx_in_leaf) override
    {
        m_leaf.init_from_mem(mem);
        m_leaf.set_parent(parent, ndx_in_parent);
        m_leaf.set(elem_ndx_in_leaf, m_value); // Throws
    }
};

template <class T>
struct BpTree<T>::SetNullHandler : BpTreeNode::UpdateHandler {
    LeafType m_leaf;
    SetNullHandler(BpTreeBase& tree) noexcept
        : m_leaf(tree.get_alloc())
    {
    }
    void update(MemRef mem, ArrayParent* parent, size_t ndx_in_parent, size_t elem_ndx_in_leaf) override
    {
        m_leaf.init_from_mem(mem);
        m_leaf.set_parent(parent, ndx_in_parent);
        _impl::NullableOrNothing<LeafType>::set_null(m_leaf, elem_ndx_in_leaf); // Throws
    }
};

template <class T>
void BpTree<T>::set(size_t ndx, T value)
{
    if (root_is_leaf()) {
        root_as_leaf().set(ndx, std::move(value));
    }
    else {
        UpdateHandler set_leaf_elem(*this, std::move(value));
        static_cast<BpTreeNode*>(m_root.get())->update_bptree_elem(ndx, set_leaf_elem); // Throws
    }
}

template <class T>
void BpTree<T>::set_null(size_t ndx)
{
    if (root_is_leaf()) {
        _impl::NullableOrNothing<LeafType>::set_null(root_as_leaf(), ndx);
    }
    else {
        SetNullHandler set_leaf_elem(*this);
        static_cast<BpTreeNode*>(m_root.get())->update_bptree_elem(ndx, set_leaf_elem); // Throws;
    }
}

template <class T>
struct BpTree<T>::EraseHandler : BpTreeNode::EraseHandler {
    BpTreeBase& m_tree;
    LeafType m_leaf;
    bool m_leaves_have_refs; // FIXME: Should be able to eliminate this.
    EraseHandler(BpTreeBase& tree) noexcept
        : m_tree(tree)
        , m_leaf(tree.get_alloc())
        , m_leaves_have_refs(false)
    {
    }
    bool erase_leaf_elem(MemRef leaf_mem, ArrayParent* parent, size_t leaf_ndx_in_parent,
                         size_t elem_ndx_in_leaf) override
    {
        m_leaf.init_from_mem(leaf_mem);
        REALM_ASSERT_3(m_leaf.size(), >=, 1);
        size_t last_ndx = m_leaf.size() - 1;
        if (last_ndx == 0) {
            m_leaves_have_refs = m_leaf.has_refs();
            return true;
        }
        m_leaf.set_parent(parent, leaf_ndx_in_parent);
        size_t ndx = elem_ndx_in_leaf;
        if (ndx == npos)
            ndx = last_ndx;
        m_leaf.erase(ndx); // Throws
        return false;
    }
    void destroy_leaf(MemRef leaf_mem) noexcept override
    {
        // FIXME: Seems like this would cause file space leaks if
        // m_leaves_have_refs is true, but consider carefully how
        // m_leaves_have_refs get its value.
        m_tree.get_alloc().free_(leaf_mem);
    }
    void replace_root_by_leaf(MemRef leaf_mem) override
    {
        std::unique_ptr<LeafType> leaf{new LeafType(m_tree.get_alloc())}; // Throws
        leaf->init_from_mem(leaf_mem);
        m_tree.replace_root(std::move(leaf)); // Throws
    }
    void replace_root_by_empty_leaf() override
    {
        std::unique_ptr<LeafType> leaf{new LeafType(m_tree.get_alloc())};            // Throws
        leaf->create(m_leaves_have_refs ? Array::type_HasRefs : Array::type_Normal); // Throws
        m_tree.replace_root(std::move(leaf));                                        // Throws
    }
};

template <class T>
void BpTree<T>::erase(size_t ndx, bool is_last)
{
    REALM_ASSERT_DEBUG_EX(ndx < size(), ndx, size());
    REALM_ASSERT_DEBUG(is_last == (ndx == size() - 1));
    if (root_is_leaf()) {
        root_as_leaf().erase(ndx);
    }
    else {
        size_t ndx_2 = is_last ? npos : ndx;
        EraseHandler handler(*this);
        BpTreeNode::erase_bptree_elem(&root_as_node(), ndx_2, handler);
    }
}

template <class T>
void BpTree<T>::move_last_over(size_t row_ndx, size_t last_row_ndx)
{
    // Copy value from last row over
    T value = get(last_row_ndx);
    set(row_ndx, value);
    erase(last_row_ndx, true);
}

template <class T>
void BpTree<T>::clear()
{
    if (root_is_leaf()) {
        if (std::is_same<T, int64_t>::value && root().get_type() == Array::type_HasRefs) {
            // FIXME: This is because some column types rely on integer columns
            // to contain refs.
            root().clear_and_destroy_children();
        }
        else {
            root_as_leaf().clear();
        }
    }
    else {
        Allocator& alloc = get_alloc();
        root().destroy_deep();

        std::unique_ptr<LeafType> new_root(new LeafType(alloc));
        new_root->create();
        replace_root(std::move(new_root));
    }
}


template <class T>
struct BpTree<T>::AdjustHandler : BpTreeNode::UpdateHandler {
    LeafType m_leaf;
    const T m_diff;
    AdjustHandler(BpTreeBase& tree, T diff)
        : m_leaf(tree.get_alloc())
        , m_diff(diff)
    {
    }

    void update(MemRef mem, ArrayParent* parent, size_t ndx_in_parent, size_t) final
    {
        m_leaf.init_from_mem(mem);
        m_leaf.set_parent(parent, ndx_in_parent);
        m_leaf.adjust(0, m_leaf.size(), m_diff);
    }
};

template <class T>
void BpTree<T>::adjust(T diff)
{
    if (root_is_leaf()) {
        root_as_leaf().adjust(0, m_root->size(), std::move(diff)); // Throws
    }
    else {
        AdjustHandler adjust_leaf_elem(*this, std::move(diff));
        root_as_node().update_bptree_leaves(adjust_leaf_elem); // Throws
    }
}

template <class T>
void BpTree<T>::adjust(size_t ndx, T diff)
{
    static_assert(std::is_arithmetic<T>::value, "adjust is undefined for non-arithmetic trees");
    set(ndx, get(ndx) + diff);
}

template <class T>
struct BpTree<T>::AdjustGEHandler : BpTreeNode::UpdateHandler {
    LeafType m_leaf;
    const T m_limit, m_diff;

    AdjustGEHandler(BpTreeBase& tree, T limit, T diff)
        : m_leaf(tree.get_alloc())
        , m_limit(limit)
        , m_diff(diff)
    {
    }

    void update(MemRef mem, ArrayParent* parent, size_t ndx_in_parent, size_t) final
    {
        m_leaf.init_from_mem(mem);
        m_leaf.set_parent(parent, ndx_in_parent);
        m_leaf.adjust_ge(m_limit, m_diff);
    }
};

template <class T>
void BpTree<T>::adjust_ge(T limit, T diff)
{
    if (root_is_leaf()) {
        root_as_leaf().adjust_ge(std::move(limit), std::move(diff)); // Throws
    }
    else {
        AdjustGEHandler adjust_leaf_elem(*this, std::move(limit), std::move(diff));
        root_as_node().update_bptree_leaves(adjust_leaf_elem); // Throws
    }
}

template <class T>
struct BpTree<T>::SliceHandler : public BpTreeBase::SliceHandler {
public:
    SliceHandler(Allocator& alloc)
        : m_leaf(alloc)
    {
    }
    MemRef slice_leaf(MemRef leaf_mem, size_t offset, size_t size, Allocator& target_alloc) override
    {
        m_leaf.init_from_mem(leaf_mem);
        return m_leaf.slice_and_clone_children(offset, size, target_alloc); // Throws
    }

private:
    LeafType m_leaf;
};

template <class T>
ref_type BpTree<T>::write(size_t slice_offset, size_t slice_size, size_t table_size, _impl::OutputStream& out) const
{
    ref_type ref;
    if (root_is_leaf()) {
        Allocator& alloc = Allocator::get_default();
        MemRef mem = root_as_leaf().slice_and_clone_children(slice_offset, slice_size, alloc); // Throws
        Array slice(alloc);
        _impl::DeepArrayDestroyGuard dg(&slice);
        slice.init_from_mem(mem);
        bool deep = true;
        bool only_when_modified = false;
        ref = slice.write(out, deep, only_when_modified); // Throws
    }
    else {
        SliceHandler handler(get_alloc());
        ref = write_subtree(root_as_node(), slice_offset, slice_size, table_size, handler, out); // Throws
    }
    return ref;
}

template <class T>
MemRef BpTree<T>::create_leaf(Array::Type leaf_type, size_t size, T value, Allocator& alloc)
{
    bool context_flag = false;
    MemRef mem = LeafType::create_array(leaf_type, context_flag, size, std::move(value), alloc);
    return mem;
}

template <class T>
void BpTree<T>::get_leaf(size_t ndx, size_t& ndx_in_leaf, LeafInfo& inout_leaf_info) const noexcept
{
    if (root_is_leaf()) {
        ndx_in_leaf = ndx;
        *inout_leaf_info.out_leaf = &root_as_leaf();
        return;
    }
    std::pair<MemRef, size_t> p = root_as_node().get_bptree_leaf(ndx);
    inout_leaf_info.fallback->init_from_mem(p.first);
    ndx_in_leaf = p.second;
    *inout_leaf_info.out_leaf = inout_leaf_info.fallback;
}

template <class T>
size_t BpTree<T>::find_first(T value, size_t begin, size_t end) const
{
    if (root_is_leaf()) {
        return root_as_leaf().find_first(value, begin, end);
    }

    // FIXME: It would be better to always require that 'end' is
    // specified explicitly, since Table has the size readily
    // available, and Array::get_bptree_size() is deprecated.
    if (end == npos)
        end = size();

    LeafType leaf_cache(get_alloc());
    size_t ndx_in_tree = begin;
    while (ndx_in_tree < end) {
        const LeafType* leaf;
        LeafInfo leaf_info{&leaf, &leaf_cache};
        size_t ndx_in_leaf;
        get_leaf(ndx_in_tree, ndx_in_leaf, leaf_info);
        size_t leaf_offset = ndx_in_tree - ndx_in_leaf;
        size_t end_in_leaf = std::min(leaf->size(), end - leaf_offset);
        size_t ndx = leaf->find_first(value, ndx_in_leaf, end_in_leaf); // Throws (maybe)
        if (ndx != not_found)
            return leaf_offset + ndx;
        ndx_in_tree = leaf_offset + end_in_leaf;
    }

    return not_found;
}

template <class T>
void BpTree<T>::find_all(IntegerColumn& result, T value, size_t begin, size_t end) const
{
    if (root_is_leaf()) {
        root_as_leaf().find_all(&result, value, 0, begin, end); // Throws
        return;
    }

    // FIXME: It would be better to always require that 'end' is
    // specified explicitely, since Table has the size readily
    // available, and Array::get_bptree_size() is deprecated.
    if (end == npos)
        end = size();

    LeafType leaf_cache(get_alloc());
    size_t ndx_in_tree = begin;
    while (ndx_in_tree < end) {
        const LeafType* leaf;
        LeafInfo leaf_info{&leaf, &leaf_cache};
        size_t ndx_in_leaf;
        get_leaf(ndx_in_tree, ndx_in_leaf, leaf_info);
        size_t leaf_offset = ndx_in_tree - ndx_in_leaf;
        size_t end_in_leaf = std::min(leaf->size(), end - leaf_offset);
        leaf->find_all(&result, value, leaf_offset, ndx_in_leaf, end_in_leaf); // Throws
        ndx_in_tree = leaf_offset + end_in_leaf;
    }
}

#if defined(REALM_DEBUG)
template <class T>
size_t BpTree<T>::verify_leaf(MemRef mem, Allocator& alloc)
{
    LeafType leaf(alloc);
    leaf.init_from_mem(mem);
    leaf.verify();
    return leaf.size();
}

template <class T>
void BpTree<T>::verify() const
{
    if (root_is_leaf()) {
        root_as_leaf().verify();
    }
    else {
        root().verify_bptree(&verify_leaf);
    }
}
#endif // REALM_DEBUG

template <class T>
void BpTree<T>::leaf_to_dot(MemRef leaf_mem, ArrayParent* parent, size_t ndx_in_parent, std::ostream& out,
                            Allocator& alloc)
{
    LeafType leaf(alloc);
    leaf.init_from_mem(leaf_mem);
    leaf.set_parent(parent, ndx_in_parent);
    leaf.to_dot(out);
}

} // namespace realm

#endif // REALM_BPTREE_HPP