From a15efb2def59dd3e9f8c88ff2f2167482b47a380 Mon Sep 17 00:00:00 2001 From: Arseny Kapoulkine Date: Sun, 10 Aug 2014 23:52:49 +0000 Subject: Implement node moving functions. The operations itself are O(1) since they just rearrange pointers. However, the validation step is O(logN) due to a sanity check to prevent recursive trees. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1002 99668b35-9821-0410-8761-19e4c4f06640 --- src/pugixml.cpp | 98 ++++++++++++++++++++++++++++++++++++++++++++++++--------- src/pugixml.hpp | 6 ++++ 2 files changed, 90 insertions(+), 14 deletions(-) (limited to 'src') diff --git a/src/pugixml.cpp b/src/pugixml.cpp index b6559e7..cc19c8a 100644 --- a/src/pugixml.cpp +++ b/src/pugixml.cpp @@ -621,6 +621,8 @@ PUGI__NS_BEGIN node->first_child = child; child->prev_sibling_c = child; } + + child->next_sibling = 0; } inline void prepend_node(xml_node_struct* child, xml_node_struct* node) @@ -641,38 +643,38 @@ PUGI__NS_BEGIN node->first_child = child; } - inline void insert_node_before(xml_node_struct* child, xml_node_struct* node) + inline void insert_node_after(xml_node_struct* child, xml_node_struct* node) { xml_node_struct* parent = node->parent; child->parent = parent; - if (node->prev_sibling_c->next_sibling) - node->prev_sibling_c->next_sibling = child; + if (node->next_sibling) + node->next_sibling->prev_sibling_c = child; else - parent->first_child = child; + parent->first_child->prev_sibling_c = child; - child->prev_sibling_c = node->prev_sibling_c; - child->next_sibling = node; + child->next_sibling = node->next_sibling; + child->prev_sibling_c = node; - node->prev_sibling_c = child; + node->next_sibling = child; } - inline void insert_node_after(xml_node_struct* child, xml_node_struct* node) + inline void insert_node_before(xml_node_struct* child, xml_node_struct* node) { xml_node_struct* parent = node->parent; child->parent = parent; - if (node->next_sibling) - node->next_sibling->prev_sibling_c = child; + if (node->prev_sibling_c->next_sibling) + node->prev_sibling_c->next_sibling = child; else - parent->first_child->prev_sibling_c = child; + parent->first_child = child; - child->next_sibling = node->next_sibling; - child->prev_sibling_c = node; + child->prev_sibling_c = node->prev_sibling_c; + child->next_sibling = node; - node->next_sibling = child; + node->prev_sibling_c = child; } inline void remove_node(xml_node_struct* node) @@ -3428,6 +3430,30 @@ PUGI__NS_BEGIN return true; } + PUGI__FN bool allow_move(const xml_node& parent, const xml_node& child) + { + // check that child can be a child of parent + if (!allow_insert_child(parent.type(), child.type())) + return false; + + // check that node is not moved between documents + if (parent.root() != child.root()) + return false; + + // check that new parent is not in the child subtree + xml_node cur = parent; + + while (cur) + { + if (cur == child) + return false; + + cur = cur.parent(); + } + + return true; + } + PUGI__FN void recursive_copy_skip(xml_node& dest, const xml_node& source, const xml_node& skip) { assert(dest.type() == source.type()); @@ -4823,6 +4849,50 @@ namespace pugi return result; } + PUGI__FN xml_node xml_node::append_move(const xml_node& moved) + { + if (!impl::allow_move(*this, moved)) return xml_node(); + + impl::remove_node(moved._root); + impl::append_node(moved._root, _root); + + return moved; + } + + PUGI__FN xml_node xml_node::prepend_move(const xml_node& moved) + { + if (!impl::allow_move(*this, moved)) return xml_node(); + + impl::remove_node(moved._root); + impl::prepend_node(moved._root, _root); + + return moved; + } + + PUGI__FN xml_node xml_node::insert_move_after(const xml_node& moved, const xml_node& node) + { + if (!impl::allow_move(*this, moved)) return xml_node(); + if (!node._root || node._root->parent != _root) return xml_node(); + if (moved._root == node._root) return xml_node(); + + impl::remove_node(moved._root); + impl::insert_node_after(moved._root, node._root); + + return moved; + } + + PUGI__FN xml_node xml_node::insert_move_before(const xml_node& moved, const xml_node& node) + { + if (!impl::allow_move(*this, moved)) return xml_node(); + if (!node._root || node._root->parent != _root) return xml_node(); + if (moved._root == node._root) return xml_node(); + + impl::remove_node(moved._root); + impl::insert_node_before(moved._root, node._root); + + return moved; + } + PUGI__FN bool xml_node::remove_attribute(const char_t* name_) { return remove_attribute(attribute(name_)); diff --git a/src/pugixml.hpp b/src/pugixml.hpp index c15e5a1..69b2cb2 100644 --- a/src/pugixml.hpp +++ b/src/pugixml.hpp @@ -501,6 +501,12 @@ namespace pugi xml_node insert_copy_after(const xml_node& proto, const xml_node& node); xml_node insert_copy_before(const xml_node& proto, const xml_node& node); + // Move the specified node to become a child of this node. Returns moved node, or empty node on errors. + xml_node append_move(const xml_node& moved); + xml_node prepend_move(const xml_node& moved); + xml_node insert_move_after(const xml_node& moved, const xml_node& node); + xml_node insert_move_before(const xml_node& moved, const xml_node& node); + // Remove specified attribute bool remove_attribute(const xml_attribute& a); bool remove_attribute(const char_t* name); -- cgit v1.2.3