From a15efb2def59dd3e9f8c88ff2f2167482b47a380 Mon Sep 17 00:00:00 2001
From: Arseny Kapoulkine <arseny.kapoulkine@gmail.com>
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(-)
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