Class Tree

Synopsis

#include <src/c4/yml/tree.hpp>

class Tree

Description

No description yet.

Mentioned in

Construction and assignment

Tree overload
~Tree
operator= overload

Memory and sizing

reserve
clearclear the tree and zero every node
clear_arena
empty overloadtrue when name and value are empty, and has no children
size

Mentioned in

capacity
slack
arena_size
arena_capacity
arena_slack
allocator

Node getters

id
get overloadwith the get() method, i can be NONE, in which case a nullptr is returned
root_id overloadGet the id of the root node.
rootref overloadGet the root as a NodeRef.
operator[] overloadfind a root child by name, return it as a NodeRef
operator[] overloadfind a root child by index: return the root node's i-th child as a NodeRef

Node property getters

type
type_str
key
key_tag
key_ref
key_anchor
keysc
val
val_tag
val_ref
val_anchor
valsc

Node predicates

is_root
is_stream
is_doc
is_container
is_map
is_seq
has_val
has_key
is_val
is_keyval
has_key_tag
has_val_tag
has_key_anchor
has_val_anchor
is_key_ref
is_val_ref
is_ref
is_anchor
parent_is_seq
parent_is_map
has_anchortrue when the node has an anchor named a

Hierarchy predicates

has_parent
has_child overload
has_children
has_sibling overload
has_siblingscounts with *this
has_other_siblingsdoes not count with *this

Hierarchy getters

parent
prev_sibling
next_sibling
num_childrenO(num_children)
child_pos
first_child
last_child
child
find_child

Mentioned in

num_siblingsO(num_siblings) counts with this
num_other_siblingsdoes not count with this
sibling_pos
first_sibling
last_sibling
sibling
find_sibling

Node modifiers

to_keyval
to_map overload
to_seq overload
to_val
to_doc
to_stream
set_key
set_val
set_key_tag
set_val_tag
set_key_anchor
set_val_anchor
set_key_ref
set_val_ref
rem_key_anchor
rem_val_anchor
rem_key_ref
rem_val_ref
rem_anchor_ref

Tree modifiers

reorderreorder the tree in memory so that all the nodes are stored in a linear sequence when visited in depth-first order
resolveResolve references (aliases <- anchors) in the tree.

Modifying hierarchy

insert_childcreate and insert a new child of "parent"
prepend_child
append_child
insert_siblingcreate and insert a new sibling of n. insert after "after"
prepend_sibling
append_sibling
removeremove an entire branch at once: ie remove the children and the node itself
remove_childrenremove all the node's children, but keep the node itself
move overloadchange the node's position in the parent
move overloadchange the node's parent and position
move overloadchange the node's parent and position to a different tree
duplicate overloadrecursively duplicate a node from this tree into a new parent, placing it after one of its children
duplicate overloadrecursively duplicate a node from a different tree into a new parent, placing it after one of its children
duplicate_children overloadrecursively duplicate the node's children (but not the node)
duplicate_children overloadrecursively duplicate the node's children (but not the node), where the node is from a different tree
duplicate_contents overload
duplicate_children_no_rep overloadduplicate the node's children (but not the node) in a new parent, but omit repetitions where a duplicated node has the same key (in maps) or value (in seqs)
merge_with

Internal string arena

arena_posget the current size of the tree's internal arena
arenaget the current arena
in_arenareturn true if the given substring is part of the tree's string arena
to_arenaserialize the given variable to the tree's arena, growing it as needed to accomodate the serialization to fit.
copy_to_arenacopy the given substr to the tree's arena, growing it by the required size
alloc_arenagrow the tree's string arena by the given size and return a substr of the added portion
reserve_arenaensure the tree's internal string arena is at least the given capacity

Lookup

lookup_pathfor example foo.bar[0].baz
lookup_path_or_modifydefaulted lookup: lookup path; if the lookup fails, recursively modify the tree so that the corresponding lookup_path() would return the default value

Other Types

lookup_result

Source

Lines 412-1239 in src/c4/yml/tree.hpp.

class Tree
{
public:

    /** @name construction and assignment */
    /** @{ */

    Tree(Allocator const& cb);
    Tree() : Tree(Allocator()) {}
    Tree(size_t node_capacity, size_t arena_capacity=0, Allocator const& cb={});

    ~Tree();

    Tree(Tree const& that) noexcept;
    Tree(Tree     && that) noexcept;

    Tree& operator= (Tree const& that) noexcept;
    Tree& operator= (Tree     && that) noexcept;

    /** @} */

public:

    /** @name memory and sizing */
    /** @{ */

    void reserve(size_t node_capacity);

    /** clear the tree and zero every node
     * @note does NOT clear the arena
     * @see clear_arena() */
    void clear();
    inline void clear_arena() { m_arena_pos = 0; }

    inline bool   empty() const { return m_size == 0; }

    inline size_t size () const { return m_size; }
    inline size_t capacity() const { return m_cap; }
    inline size_t slack() const { RYML_ASSERT(m_cap >= m_size); return m_cap - m_size; }

    inline size_t arena_size() const { return m_arena_pos; }
    inline size_t arena_capacity() const { return m_arena.len; }
    inline size_t arena_slack() const { RYML_ASSERT(m_arena.len >= m_arena_pos); return m_arena.len - m_arena_pos; }

    Allocator const& allocator() const { return m_alloc; }

    /** @} */

public:

    /** @name node getters */
    /** @{ */

    size_t id(NodeData const* n) const
    {
        if( ! n)
        {
            return NONE;
        }
        RYML_ASSERT(n >= m_buf && n < m_buf + m_cap);
        return static_cast<size_t>(n - m_buf);
    }

    // with the get() method, i can be NONE, in which case a nullptr is returned
    inline NodeData *get(size_t i)
    {
        if(i == NONE)
        {
            return nullptr;
        }
        RYML_ASSERT(i >= 0 && i < m_cap);
        return m_buf + i;
    }
    inline NodeData const *get(size_t i) const
    {
        if(i == NONE)
        {
            return nullptr;
        }
        RYML_ASSERT(i >= 0 && i < m_cap);
        return m_buf + i;
    }

    // these next two functions are implementation only; use at your
    // own risk.

    // An if-less form of get() that demands a valid node index
    inline NodeData       * _p(size_t i)       { RYML_ASSERT(i != NONE && i >= 0 && i < m_cap); return m_buf + i; }
    // An if-less form of get() that demands a valid node index
    inline NodeData const * _p(size_t i) const { RYML_ASSERT(i != NONE && i >= 0 && i < m_cap); return m_buf + i; }

    //! Get the id of the root node
    size_t root_id()       { if(m_cap == 0) { reserve(16); } RYML_ASSERT(m_cap > 0 && m_size > 0); return 0; }
    //! Get the id of the root node
    size_t root_id() const {                                 RYML_ASSERT(m_cap > 0 && m_size > 0); return 0; }

    //! Get the root as a NodeRef
    NodeRef       rootref();
    //! Get the root as a NodeRef
    NodeRef const rootref() const;

    //! find a root child by name, return it as a NodeRef
    //! @note requires the root to be a map.
    NodeRef       operator[] (csubstr key);
    //! find a root child by name, return it as a NodeRef
    //! @note requires the root to be a map.
    NodeRef const operator[] (csubstr key) const;

    //! find a root child by index: return the root node's @p i-th child as a NodeRef
    //! @note @i is NOT the node id, but the child's position
    NodeRef       operator[] (size_t i);
    //! find a root child by index: return the root node's @p i-th child as a NodeRef
    //! @note @i is NOT the node id, but the child's position
    NodeRef const operator[] (size_t i) const;

    /** @} */

public:

    /** @name node property getters */
    /** @{ */

    NodeType_e  type(size_t node) const { return (NodeType_e)(_p(node)->m_type & _TYMASK); }
    const char* type_str(size_t node) const { return NodeType::type_str(_p(node)->m_type); }

    csubstr    const& key       (size_t node) const { RYML_ASSERT(has_key(node)); return _p(node)->m_key.scalar; }
    csubstr    const& key_tag   (size_t node) const { RYML_ASSERT(has_key_tag(node)); return _p(node)->m_key.tag; }
    csubstr    const& key_ref   (size_t node) const { RYML_ASSERT(is_key_ref(node) && ! has_key_anchor(node)); return _p(node)->m_key.anchor; }
    csubstr    const& key_anchor(size_t node) const { RYML_ASSERT( ! is_key_ref(node) && has_key_anchor(node)); return _p(node)->m_key.anchor; }
    NodeScalar const& keysc     (size_t node) const { RYML_ASSERT(has_key(node)); return _p(node)->m_key; }

    csubstr    const& val       (size_t node) const { RYML_ASSERT(has_val(node)); return _p(node)->m_val.scalar; }
    csubstr    const& val_tag   (size_t node) const { RYML_ASSERT(has_val_tag(node)); return _p(node)->m_val.tag; }
    csubstr    const& val_ref   (size_t node) const { RYML_ASSERT(is_val_ref(node) && ! has_val_anchor(node)); return _p(node)->m_val.anchor; }
    csubstr    const& val_anchor(size_t node) const { RYML_ASSERT( ! is_val_ref(node) && has_val_anchor(node)); return _p(node)->m_val.anchor; }
    NodeScalar const& valsc     (size_t node) const { RYML_ASSERT(has_val(node)); return _p(node)->m_val; }

    /** @} */

public:

    /** @name node predicates */
    /** @{ */

    bool is_root(size_t node) const { RYML_ASSERT(_p(node)->m_parent != NONE || node == 0); return _p(node)->m_parent == NONE; }
    bool is_stream(size_t node) const { return (_p(node)->m_type & STREAM) == STREAM; }
    bool is_doc(size_t node) const { return (_p(node)->m_type & DOC) != 0; }
    bool is_container(size_t node) const { return (_p(node)->m_type & (MAP|SEQ|STREAM|DOC)) != 0; }
    bool is_map(size_t node) const { return (_p(node)->m_type & MAP) != 0; }
    bool is_seq(size_t node) const { return (_p(node)->m_type & SEQ) != 0; }
    bool has_val(size_t node) const { return (_p(node)->m_type & VAL) != 0; }
    bool has_key(size_t node) const { return (_p(node)->m_type & KEY) != 0; }
    bool is_val(size_t node) const { return (_p(node)->m_type & KEYVAL) == VAL; }
    bool is_keyval(size_t node) const { return (_p(node)->m_type & KEYVAL) == KEYVAL; }
    bool has_key_tag(size_t node) const { return (_p(node)->m_type & (KEY|KEYTAG)) == (KEY|KEYTAG); }
    bool has_val_tag(size_t node) const { return ((_p(node)->m_type & (VALTAG)) && (_p(node)->m_type & (VAL|MAP|SEQ))); }
    bool has_key_anchor(size_t node) const { return (_p(node)->m_type & KEYANCH) != 0; }
    bool has_val_anchor(size_t node) const { return (_p(node)->m_type & VALANCH) != 0; }
    bool is_key_ref(size_t node) const { return (_p(node)->m_type & KEYREF) != 0; }
    bool is_val_ref(size_t node) const { return (_p(node)->m_type & VALREF) != 0; }
    bool is_ref(size_t node) const { return (_p(node)->m_type & (KEYREF|VALREF)) != 0; }
    bool is_anchor(size_t node) const { return (_p(node)->m_type & (KEYANCH|VALANCH)) != 0; }

    bool parent_is_seq(size_t node) const { RYML_ASSERT(has_parent(node)); return is_seq(_p(node)->m_parent); }
    bool parent_is_map(size_t node) const { RYML_ASSERT(has_parent(node)); return is_map(_p(node)->m_parent); }

    /** true when name and value are empty, and has no children */
    bool empty(size_t node) const { return ! has_children(node) && _p(node)->m_key.empty() && (( ! (_p(node)->m_type & VAL)) || _p(node)->m_val.empty()); }
    /** true when the node has an anchor named a */
    bool has_anchor(size_t node, csubstr a) const { return _p(node)->m_key.anchor == a || _p(node)->m_val.anchor == a; }

    /** @} */

public:

    /** @name hierarchy predicates */
    /** @{ */

    bool has_parent(size_t node) const { return _p(node)->m_parent != NONE; }

    bool has_child(size_t node, csubstr key) const { return find_child(node, key) != npos; }
    bool has_child(size_t node, size_t ch) const { return child_pos(node, ch) != npos; }
    bool has_children(size_t node) const { return _p(node)->m_first_child != NONE; }

    bool has_sibling(size_t node, size_t sib) const { return is_root(node) ? sib==node : child_pos(_p(node)->m_parent, sib) != npos; }
    bool has_sibling(size_t node, csubstr key) const { return find_sibling(node, key) != npos; }
    /** counts with *this */
    bool has_siblings(size_t /*node*/) const { return true; }
    /** does not count with *this */
    bool has_other_siblings(size_t node) const { return is_root(node) ? false : (_p(_p(node)->m_parent)->m_first_child != _p(_p(node)->m_parent)->m_last_child); }

    /** @} */

public:

    /** @name hierarchy getters */
    /** @{ */

    size_t parent(size_t node) const { return _p(node)->m_parent; }

    size_t prev_sibling(size_t node) const { return _p(node)->m_prev_sibling; }
    size_t next_sibling(size_t node) const { return _p(node)->m_next_sibling; }

    /** O(#num_children) */
    size_t num_children(size_t node) const;
    size_t child_pos(size_t node, size_t ch) const;
    size_t first_child(size_t node) const { return _p(node)->m_first_child; }
    size_t last_child(size_t node) const { return _p(node)->m_last_child; }
    size_t child(size_t node, size_t pos) const;
    size_t find_child(size_t node, csubstr const& key) const;

    /** O(#num_siblings) */
    /** counts with this */
    size_t num_siblings(size_t node) const { return is_root(node) ? 1 : num_children(_p(node)->m_parent); }
    /** does not count with this */
    size_t num_other_siblings(size_t node) const { size_t ns = num_siblings(node); RYML_ASSERT(ns > 0); return ns-1; }
    size_t sibling_pos(size_t node, size_t sib) const { RYML_ASSERT( ! is_root(node) || node == root_id()); return child_pos(_p(node)->m_parent, sib); }
    size_t first_sibling(size_t node) const { return is_root(node) ? node : _p(_p(node)->m_parent)->m_first_child; }
    size_t last_sibling(size_t node) const { return is_root(node) ? node : _p(_p(node)->m_parent)->m_last_child; }
    size_t sibling(size_t node, size_t pos) const { return child(_p(node)->m_parent, pos); }
    size_t find_sibling(size_t node, csubstr const& key) const { return find_child(_p(node)->m_parent, key); }

    /** @} */

public:

    /** @name node modifiers */
    /** @{ */

    void to_keyval(size_t node, csubstr const& key, csubstr const& val, type_bits more_flags=0);
    void to_map(size_t node, csubstr const& key, type_bits more_flags=0);
    void to_seq(size_t node, csubstr const& key, type_bits more_flags=0);
    void to_val(size_t node, csubstr const& val, type_bits more_flags=0);
    void to_map(size_t node, type_bits more_flags=0);
    void to_seq(size_t node, type_bits more_flags=0);
    void to_doc(size_t node, type_bits more_flags=0);
    void to_stream(size_t node, type_bits more_flags=0);

    void set_key(size_t node, csubstr key) { RYML_ASSERT(has_key(node)); _p(node)->m_key.scalar = key; }
    void set_val(size_t node, csubstr val) { RYML_ASSERT(has_val(node)); _p(node)->m_val.scalar = val; }

    void set_key_tag(size_t node, csubstr tag) { RYML_ASSERT(has_key(node)); _p(node)->m_key.tag = tag; _add_flags(node, KEYTAG); }
    void set_val_tag(size_t node, csubstr tag) { RYML_ASSERT(has_val(node) || is_container(node)); _p(node)->m_val.tag = tag; _add_flags(node, VALTAG); }

    void set_key_anchor(size_t node, csubstr anchor) { RYML_ASSERT( ! is_key_ref(node)); _p(node)->m_key.anchor = anchor; _add_flags(node, KEYANCH); }
    void set_val_anchor(size_t node, csubstr anchor) { RYML_ASSERT( ! is_val_ref(node)); _p(node)->m_val.anchor = anchor; _add_flags(node, VALANCH); }
    void set_key_ref   (size_t node, csubstr ref   ) { RYML_ASSERT( ! has_key_anchor(node)); _p(node)->m_key.anchor = ref; _add_flags(node, KEYREF); }
    void set_val_ref   (size_t node, csubstr ref   ) { RYML_ASSERT( ! has_val_anchor(node)); _p(node)->m_val.anchor = ref; _add_flags(node, VALREF); }

    void rem_key_anchor(size_t node) { _p(node)->m_key.anchor.clear(); _rem_flags(node, KEYANCH); }
    void rem_val_anchor(size_t node) { _p(node)->m_val.anchor.clear(); _rem_flags(node, VALANCH); }
    void rem_key_ref   (size_t node) { _p(node)->m_key.anchor.clear(); _rem_flags(node, KEYREF); }
    void rem_val_ref   (size_t node) { _p(node)->m_val.anchor.clear(); _rem_flags(node, VALREF); }
    void rem_anchor_ref(size_t node) { _p(node)->m_key.anchor.clear(); _p(node)->m_val.anchor.clear(); _rem_flags(node, KEYANCH|VALANCH|KEYREF|VALREF); }

    /** @} */

public:

    /** @name tree modifiers */
    /** @{ */

    /** reorder the tree in memory so that all the nodes are stored
     * in a linear sequence when visited in depth-first order.
     * This will invalidate existing ids, since the node id is its
     * position in the node array. */
    void reorder();

    /** Resolve references (aliases <- anchors) in the tree.
     *
     * Dereferencing is opt-in; after parsing, Tree::resolve()
     * has to be called explicitly for obtaining resolved references in the
     * tree. This method will resolve all references and substitute the
     * anchored values in place of the reference.
     *
     * This method first does a full traversal of the tree to gather all
     * anchors and references in a separate collection, then it goes through
     * that collection to locate the names, which it does by obeying the YAML
     * standard diktat that "an alias node refers to the most recent node in
     * the serialization having the specified anchor"
     *
     * So, depending on the number of anchor/alias nodes, this is a
     * potentially expensive operation, with a best-case linear complexity
     * (from the initial traversal). This potential cost is the reason for
     * requiring an explicit call.
     */
    void resolve();

    /** @} */

public:

    /** @name modifying hierarchy */
    /** @{ */

    /** create and insert a new child of "parent". insert after the (to-be)
     * sibling "after", which must be a child of "parent". To insert as the
     * first child, set after to NONE */
    inline size_t insert_child(size_t parent, size_t after)
    {
        RYML_ASSERT(parent != NONE);
        RYML_ASSERT(is_container(parent) || is_root(parent));
        RYML_ASSERT(after == NONE || has_child(parent, after));
        size_t child = _claim();
        _set_hierarchy(child, parent, after);
        return child;
    }
    inline size_t prepend_child(size_t parent) { return insert_child(parent, NONE); }
    inline size_t  append_child(size_t parent) { return insert_child(parent, last_child(parent)); }

public:

    #if defined(__clang__)
    #   pragma clang diagnostic push
    #   pragma clang diagnostic ignored "-Wnull-dereference"
    #elif defined(__GNUC__)
    #   pragma GCC diagnostic push
    #   if __GNUC__ >= 6
    #       pragma GCC diagnostic ignored "-Wnull-dereference"
    #   endif
    #endif

    //! create and insert a new sibling of n. insert after "after"
    inline size_t insert_sibling(size_t node, size_t after)
    {
        RYML_ASSERT(node != NONE);
        RYML_ASSERT( ! is_root(node));
        RYML_ASSERT(parent(node) != NONE);
        RYML_ASSERT(after == NONE || (has_sibling(node, after) && has_sibling(after, node)));
        RYML_ASSERT(get(node) != nullptr);
        return insert_child(get(node)->m_parent, after);
    }
    inline size_t prepend_sibling(size_t node) { return insert_sibling(node, NONE); }
    inline size_t  append_sibling(size_t node) { return insert_sibling(node, last_sibling(node)); }

public:

    //! remove an entire branch at once: ie remove the children and the node itself
    inline void remove(size_t node)
    {
        remove_children(node);
        _release(node);
    }

    //! remove all the node's children, but keep the node itself
    void remove_children(size_t node)
    {
        RYML_ASSERT(get(node) != nullptr);
        size_t ich = get(node)->m_first_child;
        while(ich != NONE)
        {
            remove_children(ich);
            RYML_ASSERT(get(ich) != nullptr);
            size_t next = get(ich)->m_next_sibling;
            _release(ich);
            if(ich == get(node)->m_last_child) break;
            ich = next;
        }
    }

    #if defined(__clang__)
    #   pragma clang diagnostic pop
    #elif defined(__GNUC__)
    #   pragma GCC diagnostic pop
    #endif

public:

    /** change the node's position in the parent */
    void move(size_t node, size_t after);

    /** change the node's parent and position */
    void move(size_t node, size_t new_parent, size_t after);

    /** change the node's parent and position to a different tree
     * @return the index of the new node in the destination tree */
    size_t move(Tree * src, size_t node, size_t new_parent, size_t after);

public:

    /** recursively duplicate a node from this tree into a new parent,
     * placing it after one of its children
     * @return the index of the copy */
    size_t duplicate(size_t node, size_t new_parent, size_t after);
    /** recursively duplicate a node from a different tree into a new parent,
     * placing it after one of its children
     * @return the index of the copy */
    size_t duplicate(Tree const* src, size_t node, size_t new_parent, size_t after);

    /** recursively duplicate the node's children (but not the node)
     * @return the index of the last duplicated child */
    size_t duplicate_children(size_t node, size_t parent, size_t after);
    /** recursively duplicate the node's children (but not the node), where
     * the node is from a different tree
     * @return the index of the last duplicated child */
    size_t duplicate_children(Tree const* src, size_t node, size_t parent, size_t after);

    void duplicate_contents(size_t node, size_t where);
    void duplicate_contents(Tree const* src, size_t node, size_t where);

    /** duplicate the node's children (but not the node) in a new parent, but
     * omit repetitions where a duplicated node has the same key (in maps) or
     * value (in seqs). If one of the duplicated children has the same key
     * (in maps) or value (in seqs) as one of the parent's children, the one
     * that is placed closest to the end will prevail. */
    size_t duplicate_children_no_rep(size_t node, size_t parent, size_t after);
    size_t duplicate_children_no_rep(Tree const* src, size_t node, size_t parent, size_t after);

public:

    void merge_with(Tree const* src, size_t src_node=NONE, size_t dst_root=NONE);

    /** @} */

public:

    /** @name internal string arena */
    /** @{ */

    /** get the current size of the tree's internal arena */
    size_t arena_pos() const { return m_arena_pos; }

    /** get the current arena */
    substr arena() const { return m_arena.first(m_arena_pos); }

    /** return true if the given substring is part of the tree's string arena */
    bool in_arena(csubstr s) const
    {
        return m_arena.is_super(s);
    }

    /** serialize the given variable to the tree's arena, growing it as
     * needed to accomodate the serialization to fit.
     * @note Growing the arena may cause relocation of the entire
     * existing arena, and thus change the contents of individual nodes.
     * @see alloc_arena() */
    template<class T>
    csubstr to_arena(T const& a)
    {
        substr rem(m_arena.sub(m_arena_pos));
        size_t num = to_chars(rem, a);
        if(num > rem.len)
        {
            rem = _grow_arena(num);
            num = to_chars(rem, a);
            RYML_ASSERT(num <= rem.len);
        }
        rem = _request_span(num);
        return rem;
    }

    /** copy the given substr to the tree's arena, growing it by the required size
     * @note Growing the arena may cause relocation of the entire
     * existing arena, and thus change the contents of individual nodes.
     * @see alloc_arena() */
    substr copy_to_arena(csubstr s)
    {
        substr cp = alloc_arena(s.len);
        RYML_ASSERT(cp.len == s.len);
        RYML_ASSERT(!s.overlaps(cp));
        #if defined(__clang__)
        #elif defined(__GNUC__)
        #   pragma GCC diagnostic push
        #   if __GNUC__ >= 10
        #       pragma GCC diagnostic ignored "-Wstringop-overflow=" // no need for terminating \0
        #       pragma GCC diagnostic ignored "-Wrestrict" // there's an assert above covering violation of restrict behavior
        #   endif
        #endif
        memcpy(cp.str, s.str, s.len);
        #if defined(__clang__)
        #elif defined(__GNUC__)
        #   pragma GCC diagnostic pop
        #endif
        return cp;
    }

    /** grow the tree's string arena by the given size and return a substr
     * of the added portion
     * @note Growing the arena may cause relocation of the entire
     * existing arena, and thus change the contents of individual nodes. */
    substr alloc_arena(size_t sz)
    {
        if(sz >= arena_slack())
        {
            _grow_arena(sz - arena_slack());
        }
        substr s = _request_span(sz);
        return s;
    }

    /** ensure the tree's internal string arena is at least the given capacity
     * @note Growing the arena may cause relocation of the entire
     * existing arena, and thus change the contents of individual nodes. */
    void reserve_arena(size_t arena_cap)
    {
        if(arena_cap > m_arena.len)
        {
            substr buf;
            buf.str = (char*) m_alloc.allocate(arena_cap, m_arena.str);
            buf.len = arena_cap;
            if(m_arena.str)
            {
                RYML_ASSERT(m_arena.len >= 0);
                _relocate(buf); // does a memcpy and changes nodes using the arena
                m_alloc.free(m_arena.str, m_arena.len);
            }
            m_arena = buf;
        }
    }

    /** @} */

private:

    substr _grow_arena(size_t more)
    {
        size_t cap = m_arena_pos + more;
        cap = cap < 2 * m_arena.len ? 2 * m_arena.len : cap;
        cap = cap < 64 ? 64 : cap;
        reserve_arena(cap);
        return m_arena.sub(m_arena_pos);
    }

    substr _request_span(size_t sz)
    {
        substr s;
        s = m_arena.sub(m_arena_pos, sz);
        m_arena_pos += sz;
        return s;
    }

    substr _relocated(csubstr s, substr next_arena) const
    {
        RYML_ASSERT(m_arena.is_super(s));
        RYML_ASSERT(m_arena.sub(0, m_arena_pos).is_super(s));
        auto pos = (s.str - m_arena.str);
        substr r(next_arena.str + pos, s.len);
        RYML_ASSERT(r.str - next_arena.str == pos);
        RYML_ASSERT(next_arena.sub(0, m_arena_pos).is_super(r));
        return r;
    }

public:

    /** @name lookup */
    /** @{ */

    struct lookup_result
    {
        size_t  target;
        size_t  closest;
        size_t  path_pos;
        csubstr path;

        inline operator bool() const { return target != NONE; }

        lookup_result() : target(NONE), closest(NONE), path_pos(0), path() {}
        lookup_result(csubstr path_, size_t start) : target(NONE), closest(start), path_pos(0), path(path_) {}

        csubstr resolved() const;
        csubstr unresolved() const;
    };

    /** for example foo.bar[0].baz */
    lookup_result lookup_path(csubstr path, size_t start=NONE) const;

    /** defaulted lookup: lookup path; if the lookup fails, recursively modify
     * the tree so that the corresponding lookup_path() would return the 
     * default value */
    size_t lookup_path_or_modify(csubstr default_value, csubstr path, size_t start=NONE);

    /** @} */

private:

    struct _lookup_path_token
    {
        csubstr value;
        NodeType type;
        _lookup_path_token() : value(), type() {}
        _lookup_path_token(csubstr v, NodeType t) : value(v), type(t) {}
        inline operator bool() const { return type != NOTYPE; }
        bool is_index() const { return value.begins_with('[') && value.ends_with(']'); }
    };

    void _lookup_path(lookup_result *r, bool modify);
    size_t _next_node(lookup_result *r, bool modify, _lookup_path_token *parent);
    _lookup_path_token _next_token(lookup_result *r, _lookup_path_token const& parent);
    void _advance(lookup_result *r, size_t more);

private:

    void _clear();
    void _free();
    void _copy(Tree const& that);
    void _move(Tree      & that);

    void _relocate(substr next_arena);

public:

    #if ! RYML_USE_ASSERT
    #define _check_next_flags(node, f)
    #else
    inline void _check_next_flags(size_t node, type_bits f)
    {
        auto n = _p(node);
        type_bits o = n->m_type; // old
        C4_UNUSED(o);
        if(f & MAP)
        {
            RYML_ASSERT_MSG((f & SEQ) == 0, "cannot mark simultaneously as map and seq");
            RYML_ASSERT_MSG((f & VAL) == 0, "cannot mark simultaneously as map and val");
            RYML_ASSERT_MSG((o & SEQ) == 0, "cannot turn a seq into a map; clear first");
            RYML_ASSERT_MSG((o & VAL) == 0, "cannot turn a val into a map; clear first");
        }
        else if(f & SEQ)
        {
            RYML_ASSERT_MSG((f & MAP) == 0, "cannot mark simultaneously as seq and map");
            RYML_ASSERT_MSG((f & VAL) == 0, "cannot mark simultaneously as seq and val");
            RYML_ASSERT_MSG((o & MAP) == 0, "cannot turn a map into a seq; clear first");
            RYML_ASSERT_MSG((o & VAL) == 0, "cannot turn a val into a seq; clear first");
        }
        if(f & KEY)
        {
            RYML_ASSERT(!is_root(node));
            auto pid = parent(node); C4_UNUSED(pid);
            RYML_ASSERT(is_map(pid));
        }
        if(f & VAL)
        {
            RYML_ASSERT(!is_root(node));
            auto pid = parent(node); C4_UNUSED(pid);
            RYML_ASSERT(is_map(pid) || is_seq(pid));
        }
    }
    #endif

    inline void _set_flags(size_t node, NodeType_e f) { _check_next_flags(node, f); _p(node)->m_type = f; }
    inline void _set_flags(size_t node, type_bits  f) { _check_next_flags(node, f); _p(node)->m_type = f; }

    inline void _add_flags(size_t node, NodeType_e f) { NodeData *d = _p(node); type_bits fb = f |  d->m_type; _check_next_flags(node, fb); d->m_type = (NodeType_e) fb; }
    inline void _add_flags(size_t node, type_bits  f) { NodeData *d = _p(node);                f |= d->m_type; _check_next_flags(node,  f); d->m_type = f; }

    inline void _rem_flags(size_t node, NodeType_e f) { NodeData *d = _p(node); type_bits fb = d->m_type & ~f; _check_next_flags(node, fb); d->m_type = (NodeType_e) fb; }
    inline void _rem_flags(size_t node, type_bits  f) { NodeData *d = _p(node);            f = d->m_type & ~f; _check_next_flags(node,  f); d->m_type = f; }

    void _set_key(size_t node, csubstr const& key, type_bits more_flags=0)
    {
        _p(node)->m_key.scalar = key;
        _add_flags(node, KEY|more_flags);
    }
    void _set_key(size_t node, NodeScalar const& key, type_bits more_flags=0)
    {
        _p(node)->m_key = key;
        _add_flags(node, KEY|more_flags);
    }

    void _set_val(size_t node, csubstr const& val, type_bits more_flags=0)
    {
        RYML_ASSERT(num_children(node) == 0);
        RYML_ASSERT( ! is_container(node));
        _p(node)->m_val.scalar = val;
        _add_flags(node, VAL|more_flags);
    }
    void _set_val(size_t node, NodeScalar const& val, type_bits more_flags=0)
    {
        RYML_ASSERT(num_children(node) == 0);
        RYML_ASSERT( ! is_container(node));
        _p(node)->m_val = val;
        _add_flags(node, VAL|more_flags);
    }

    void _set(size_t node, NodeInit const& i)
    {
        RYML_ASSERT(i._check());
        NodeData *n = _p(node);
        RYML_ASSERT(n->m_key.scalar.empty() || i.key.scalar.empty() || i.key.scalar == n->m_key.scalar);
        _add_flags(node, i.type);
        if(n->m_key.scalar.empty())
        {
            if( ! i.key.scalar.empty())
            {
                _set_key(node, i.key.scalar);
            }
        }
        n->m_key.tag = i.key.tag;
        n->m_val = i.val;
    }

    void _set_parent_as_container_if_needed(size_t in)
    {
        NodeData const* n = _p(in);
        size_t ip = parent(in);
        if(ip != NONE)
        {
            if( ! (is_seq(ip) || is_map(ip)))
            {
                if((in == first_child(ip)) && (in == last_child(ip)))
                {
                    if( ! n->m_key.empty() || n->has_key())
                    {
                        _add_flags(ip, MAP);
                    }
                    else
                    {
                        _add_flags(ip, SEQ);
                    }
                }
            }
        }
    }

    void _seq2map(size_t node)
    {
        RYML_ASSERT(is_seq(node));
        for(size_t i = first_child(node); i != NONE; i = next_sibling(i))
        {
            NodeData *C4_RESTRICT ch = _p(i);
            if(ch->m_type.is_keyval()) continue;
            ch->m_type.add(KEY);
            ch->m_key = ch->m_val;
        }
        auto *C4_RESTRICT n = _p(node);
        n->m_type.rem(SEQ);
        n->m_type.add(MAP);
    }

    size_t _do_reorder(size_t *node, size_t count);

    void _swap(size_t n_, size_t m_);
    void _swap_props(size_t n_, size_t m_);
    void _swap_hierarchy(size_t n_, size_t m_);
    void _copy_hierarchy(size_t dst_, size_t src_);

    void _copy_props(size_t dst_, size_t src_)
    {
        auto      & C4_RESTRICT dst = *_p(dst_);
        auto const& C4_RESTRICT src = *_p(src_);
        dst.m_type = src.m_type;
        dst.m_key  = src.m_key;
        dst.m_val  = src.m_val;
    }

    void _copy_props_wo_key(size_t dst_, size_t src_)
    {
        auto      & C4_RESTRICT dst = *_p(dst_);
        auto const& C4_RESTRICT src = *_p(src_);
        dst.m_type = src.m_type;
        dst.m_val  = src.m_val;
    }

    void _copy_props(size_t dst_, Tree const* that_tree, size_t src_)
    {
        auto      & C4_RESTRICT dst = *_p(dst_);
        auto const& C4_RESTRICT src = *that_tree->_p(src_);
        dst.m_type = src.m_type;
        dst.m_key  = src.m_key;
        dst.m_val  = src.m_val;
    }

    void _copy_props_wo_key(size_t dst_, Tree const* that_tree, size_t src_)
    {
        auto      & C4_RESTRICT dst = *_p(dst_);
        auto const& C4_RESTRICT src = *that_tree->_p(src_);
        dst.m_type = src.m_type;
        dst.m_val  = src.m_val;
    }

    inline void _clear_type(size_t node)
    {
        _p(node)->m_type = NOTYPE;
    }

    inline void _clear(size_t node)
    {
        auto *C4_RESTRICT n = _p(node);
        n->m_type = NOTYPE;
        n->m_key.clear();
        n->m_val.clear();
        n->m_parent = NONE;
        n->m_first_child = NONE;
        n->m_last_child = NONE;
    }

    inline void _clear_key(size_t node)
    {
        _p(node)->m_key.clear();
        _rem_flags(node, KEY);
    }

    inline void _clear_val(size_t node)
    {
        _p(node)->m_key.clear();
        _rem_flags(node, VAL);
    }

private:

    void _clear_range(size_t first, size_t num);

    size_t _claim();
    void   _claim_root();
    void   _release(size_t node);
    void   _free_list_add(size_t node);
    void   _free_list_rem(size_t node);

    void _set_hierarchy(size_t node, size_t parent, size_t after_sibling);
    void _rem_hierarchy(size_t node);

public:

    // members are exposed, but you should NOT access them directly

    NodeData * m_buf;
    size_t m_cap;

    size_t m_size;

    size_t m_free_head;
    size_t m_free_tail;

    substr m_arena;
    size_t m_arena_pos;

    Allocator m_alloc;

};





Add Discussion as Guest

Log in