Implement non-recursive node output

This makes node output 3% 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@1014 99668b35-9821-0410-8761-19e4c4f06640

1 files changed, 151 insertions, 95 deletions

diff --git a/src/pugixml.cpp b/src/pugixml.cpp
index 5888159..767fb48 100644
--- a/src/pugixml.cpp
+++ b/src/pugixml.cpp
@@ -3269,6 +3269,12 @@ PUGI__NS_BEGIN
 		while (*s);
 	}
 
+	PUGI__FN void text_output_indent(xml_buffered_writer& writer, const char_t* indent, unsigned int depth)
+	{
+		for (unsigned int i = 0; i < depth; ++i)
+			writer.write(indent);
+	}
+
 	PUGI__FN void node_output_attributes(xml_buffered_writer& writer, const xml_node& node, unsigned int flags)
 	{
 		const char_t* default_name = PUGIXML_TEXT(":anonymous");
@@ -3285,133 +3291,183 @@ PUGI__NS_BEGIN
 		}
 	}
 
-	PUGI__FN void node_output(xml_buffered_writer& writer, const xml_node& node, const char_t* indent, unsigned int flags, unsigned int depth)
+	PUGI__FN bool node_output_start(xml_buffered_writer& writer, const xml_node& node, unsigned int flags)
 	{
 		const char_t* default_name = PUGIXML_TEXT(":anonymous");
+		const char_t* name = node.name()[0] ? node.name() : default_name;
 
-		if ((flags & format_indent) != 0 && (flags & format_raw) == 0)
-			for (unsigned int i = 0; i < depth; ++i) writer.write(indent);
+		writer.write('<');
+		writer.write(name);
 
-		switch (node.type())
-		{
-		case node_document:
+		node_output_attributes(writer, node, flags);
+
+		if (flags & format_raw)
 		{
-			for (xml_node n = node.first_child(); n; n = n.next_sibling())
-				node_output(writer, n, indent, flags, depth);
-			break;
+			if (!node.first_child())
+				writer.write(' ', '/', '>');
+			else
+			{
+				writer.write('>');
+
+				return true;
+			}
 		}
-			
-		case node_element:
+		else if (!node.first_child())
+			writer.write(' ', '/', '>', '\n');
+		else if (node.first_child() == node.last_child() && (node.first_child().type() == node_pcdata || node.first_child().type() == node_cdata))
 		{
-			const char_t* name = node.name()[0] ? node.name() : default_name;
+			writer.write('>');
 
-			writer.write('<');
+			if (node.first_child().type() == node_pcdata)
+				text_output(writer, node.first_child().value(), ctx_special_pcdata, flags);
+			else
+				text_output_cdata(writer, node.first_child().value());
+
+			writer.write('<', '/');
 			writer.write(name);
+			writer.write('>', '\n');
+		}
+		else
+		{
+			writer.write('>', '\n');
 
-			node_output_attributes(writer, node, flags);
+			return true;
+		}
 
-			if (flags & format_raw)
-			{
-				if (!node.first_child())
-					writer.write(' ', '/', '>');
-				else
-				{
-					writer.write('>');
+		return false;
+	}
+
+	PUGI__FN void node_output_end(xml_buffered_writer& writer, const xml_node& node, unsigned int flags)
+	{
+		const char_t* default_name = PUGIXML_TEXT(":anonymous");
+		const char_t* name = node.name()[0] ? node.name() : default_name;
+
+		writer.write('<', '/');
+		writer.write(name);
+		writer.write('>');
+
+		if ((flags & format_raw) == 0)
+			writer.write('\n');
+	}
 
-					for (xml_node n = node.first_child(); n; n = n.next_sibling())
-						node_output(writer, n, indent, flags, depth + 1);
+	PUGI__FN void node_output_simple(xml_buffered_writer& writer, const xml_node& node, unsigned int flags)
+	{
+		const char_t* default_name = PUGIXML_TEXT(":anonymous");
+
+		switch (node.type())
+		{
+			case node_pcdata:
+				text_output(writer, node.value(), ctx_special_pcdata, flags);
+				if ((flags & format_raw) == 0) writer.write('\n');
+				break;
 
-					writer.write('<', '/');
-					writer.write(name);
-					writer.write('>');
+			case node_cdata:
+				text_output_cdata(writer, node.value());
+				if ((flags & format_raw) == 0) writer.write('\n');
+				break;
+
+			case node_comment:
+				writer.write('<', '!', '-', '-');
+				writer.write(node.value());
+				writer.write('-', '-', '>');
+				if ((flags & format_raw) == 0) writer.write('\n');
+				break;
+
+			case node_pi:
+			case node_declaration:
+				writer.write('<', '?');
+				writer.write(node.name()[0] ? node.name() : default_name);
+
+				if (node.type() == node_declaration)
+				{
+					node_output_attributes(writer, node, flags);
+				}
+				else if (node.value()[0])
+				{
+					writer.write(' ');
+					writer.write(node.value());
 				}
-			}
-			else if (!node.first_child())
-				writer.write(' ', '/', '>', '\n');
-			else if (node.first_child() == node.last_child() && (node.first_child().type() == node_pcdata || node.first_child().type() == node_cdata))
-			{
-				writer.write('>');
 
-				if (node.first_child().type() == node_pcdata)
-					text_output(writer, node.first_child().value(), ctx_special_pcdata, flags);
-				else
-					text_output_cdata(writer, node.first_child().value());
+				writer.write('?', '>');
+				if ((flags & format_raw) == 0) writer.write('\n');
+				break;
 
-				writer.write('<', '/');
-				writer.write(name);
-				writer.write('>', '\n');
-			}
-			else
-			{
-				writer.write('>', '\n');
-				
-				for (xml_node n = node.first_child(); n; n = n.next_sibling())
-					node_output(writer, n, indent, flags, depth + 1);
+			case node_doctype:
+				writer.write('<', '!', 'D', 'O', 'C');
+				writer.write('T', 'Y', 'P', 'E');
 
-				if ((flags & format_indent) != 0 && (flags & format_raw) == 0)
-					for (unsigned int i = 0; i < depth; ++i) writer.write(indent);
-				
-				writer.write('<', '/');
-				writer.write(name);
-				writer.write('>', '\n');
-			}
+				if (node.value()[0])
+				{
+					writer.write(' ');
+					writer.write(node.value());
+				}
 
-			break;
+				writer.write('>');
+				if ((flags & format_raw) == 0) writer.write('\n');
+				break;
+
+			default:
+				assert(!"Invalid node type");
 		}
-		
-		case node_pcdata:
-			text_output(writer, node.value(), ctx_special_pcdata, flags);
-			if ((flags & format_raw) == 0) writer.write('\n');
-			break;
+	}
 
-		case node_cdata:
-			text_output_cdata(writer, node.value());
-			if ((flags & format_raw) == 0) writer.write('\n');
-			break;
+	PUGI__FN void node_output(xml_buffered_writer& writer, const xml_node& root, const char_t* indent, unsigned int flags, unsigned int depth)
+	{
+		xml_node node = root;
 
-		case node_comment:
-			writer.write('<', '!', '-', '-');
-			writer.write(node.value());
-			writer.write('-', '-', '>');
-			if ((flags & format_raw) == 0) writer.write('\n');
-			break;
+		do
+		{
+			assert(node);
 
-		case node_pi:
-		case node_declaration:
-			writer.write('<', '?');
-			writer.write(node.name()[0] ? node.name() : default_name);
+			// begin writing current node
+			if ((flags & (format_indent | format_raw)) == format_indent)
+				text_output_indent(writer, indent, depth);
 
-			if (node.type() == node_declaration)
+			if (node.type() == node_element)
 			{
-				node_output_attributes(writer, node, flags);
+				if (node_output_start(writer, node, flags))
+				{
+					node = node.first_child();
+					depth++;
+					continue;
+				}
 			}
-			else if (node.value()[0])
+			else if (node.type() == node_document)
 			{
-				writer.write(' ');
-				writer.write(node.value());
+				if (node.first_child())
+				{
+					node = node.first_child();
+					continue;
+				}
 			}
-
-			writer.write('?', '>');
-			if ((flags & format_raw) == 0) writer.write('\n');
-			break;
-
-		case node_doctype:
-			writer.write('<', '!', 'D', 'O', 'C');
-			writer.write('T', 'Y', 'P', 'E');
-
-			if (node.value()[0])
+			else
 			{
-				writer.write(' ');
-				writer.write(node.value());
+				node_output_simple(writer, node, flags);
 			}
 
-			writer.write('>');
-			if ((flags & format_raw) == 0) writer.write('\n');
-			break;
+			// continue to the next node
+			while (node != root)
+			{
+				if (node.next_sibling())
+				{
+					node = node.next_sibling();
+					break;
+				}
 
-		default:
-			assert(!"Invalid node type");
+				node = node.parent();
+				depth--;
+
+				// write closing node
+				if (node.type() == node_element)
+				{
+					if ((flags & (format_indent | format_raw)) == format_indent)
+						text_output_indent(writer, indent, depth);
+
+					node_output_end(writer, node, flags);
+				}
+			}
 		}
+		while (node != root);
 	}
 
 	inline bool has_declaration(const xml_node& node)