Implement non-recursive node copying

This makes node copying 6% faster, prevents it from ever running out of
stack space and makes the profiling results more actionable for profilers
that can't merge information from recursive calls.

git-svn-id: https://pugixml.googlecode.com/svn/trunk@1027 99668b35-9821-0410-8761-19e4c4f06640

1 files changed, 43 insertions, 24 deletions

diff --git a/src/pugixml.cpp b/src/pugixml.cpp
index fa0f34c..492948a 100644
--- a/src/pugixml.cpp
+++ b/src/pugixml.cpp
@@ -3602,29 +3602,19 @@ PUGI__NS_BEGIN
 		return true;
 	}
 
-	PUGI__FN void recursive_copy_skip(xml_node& dest, const xml_node& source, const xml_node& skip)
+	PUGI__FN void node_copy_contents(xml_node dest, xml_node source)
 	{
 		assert(dest.type() == source.type());
 
 		switch (source.type())
 		{
 		case node_element:
+		case node_declaration:
 		{
 			dest.set_name(source.name());
 
 			for (xml_attribute a = source.first_attribute(); a; a = a.next_attribute())
 				dest.append_attribute(a.name()).set_value(a.value());
-
-			for (xml_node c = source.first_child(); c; c = c.next_sibling())
-			{
-				if (c == skip) continue;
-
-				xml_node cc = dest.append_child(c.type());
-				assert(cc);
-
-				recursive_copy_skip(cc, c, skip);
-			}
-
 			break;
 		}
 
@@ -3640,18 +3630,47 @@ PUGI__NS_BEGIN
 			dest.set_value(source.value());
 			break;
 
-		case node_declaration:
+		default:
+			assert(!"Invalid node type");
+		}
+	}
+
+	PUGI__FN void node_copy_tree(xml_node dest, xml_node source)
+	{
+		node_copy_contents(dest, source);
+
+		xml_node destit = dest;
+		xml_node sourceit = source.first_child();
+
+		while (sourceit && sourceit != source)
 		{
-			dest.set_name(source.name());
+			if (sourceit != dest)
+			{
+				xml_node copy = destit.append_child(sourceit.type());
 
-			for (xml_attribute a = source.first_attribute(); a; a = a.next_attribute())
-				dest.append_attribute(a.name()).set_value(a.value());
+				node_copy_contents(copy, sourceit);
 
-			break;
-		}
+				if (sourceit.first_child())
+				{
+					destit = copy;
+					sourceit = sourceit.first_child();
+					continue;
+				}
+			}
 
-		default:
-			assert(!"Invalid node type");
+			// continue to the next node
+			do
+			{
+				if (sourceit.next_sibling())
+				{
+					sourceit = sourceit.next_sibling();
+					break;
+				}
+
+				sourceit = sourceit.parent();
+				destit = destit.parent();
+			}
+			while (sourceit != source);
 		}
 	}
 
@@ -4965,7 +4984,7 @@ namespace pugi
 	{
 		xml_node result = append_child(proto.type());
 
-		if (result) impl::recursive_copy_skip(result, proto, result);
+		if (result) impl::node_copy_tree(result, proto);
 
 		return result;
 	}
@@ -4974,7 +4993,7 @@ namespace pugi
 	{
 		xml_node result = prepend_child(proto.type());
 
-		if (result) impl::recursive_copy_skip(result, proto, result);
+		if (result) impl::node_copy_tree(result, proto);
 
 		return result;
 	}
@@ -4983,7 +5002,7 @@ namespace pugi
 	{
 		xml_node result = insert_child_after(proto.type(), node);
 
-		if (result) impl::recursive_copy_skip(result, proto, result);
+		if (result) impl::node_copy_tree(result, proto);
 
 		return result;
 	}
@@ -4992,7 +5011,7 @@ namespace pugi
 	{
 		xml_node result = insert_child_before(proto.type(), node);
 
-		if (result) impl::recursive_copy_skip(result, proto, result);
+		if (result) impl::node_copy_tree(result, proto);
 
 		return result;
 	}