Optimize XPath document order comparator

Node ancestor search now terminates early if ancestor is found before the
document root (only happens if nodes were at the same depth).

Sibling search now steps synchronously for left and right nodes to avoid
worst-case performance when we go in the wrong direction and have to scan
a big list (this comes at the cost of average performance since in the
best case we do 2x more operations).

Node comparison is now done using node pointers to elide some null
comparisons since the structure of the search guarantees that they are
handled properly.

All of the above results in ~2x faster document order comparison on
complex documents.

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

1 files changed, 57 insertions, 31 deletions

diff --git a/src/pugixml.cpp b/src/pugixml.cpp
index 94073f3..8417c44 100644
--- a/src/pugixml.cpp
+++ b/src/pugixml.cpp
@@ -6808,44 +6808,71 @@ PUGI__NS_BEGIN
 		}
 	}
 	
-	PUGI__FN unsigned int node_height(xml_node n)
+	PUGI__FN bool node_is_before_sibling(xml_node_struct* ln, xml_node_struct* rn)
 	{
-		unsigned int result = 0;
-		
-		while (n)
+		assert(ln->parent == rn->parent);
+
+		// there is no common ancestor (the shared parent is null), nodes are from different documents
+		if (!ln->parent) return ln < rn;
+
+		// determine sibling order
+		xml_node_struct* ls = ln;
+		xml_node_struct* rs = rn;
+
+		while (ls && rs)
 		{
-			++result;
-			n = n.parent();
+			if (ls == rn) return true;
+			if (rs == ln) return false;
+
+			ls = ls->next_sibling;
+			rs = rs->next_sibling;
 		}
-		
-		return result;
+
+		// if rn sibling chain ended ln must be before rn
+		return !rs;
 	}
 	
-	PUGI__FN bool node_is_before(xml_node ln, unsigned int lh, xml_node rn, unsigned int rh)
+	PUGI__FN bool node_is_before(xml_node_struct* ln, xml_node_struct* rn)
 	{
-		// normalize heights
-		for (unsigned int i = rh; i < lh; i++) ln = ln.parent();
-		for (unsigned int j = lh; j < rh; j++) rn = rn.parent();
-		
-		// one node is the ancestor of the other
-		if (ln == rn) return lh < rh;
-		
-		// find common ancestor
-		while (ln.parent() != rn.parent())
+		// find common ancestor at the same depth, if any
+		xml_node_struct* lp = ln;
+		xml_node_struct* rp = rn;
+
+		while (lp && rp && lp->parent != rp->parent)
 		{
-			ln = ln.parent();
-			rn = rn.parent();
+			lp = lp->parent;
+			rp = rp->parent;
 		}
 
-		// there is no common ancestor (the shared parent is null), nodes are from different documents
-		if (!ln.parent()) return ln < rn;
+		// parents are the same!
+		if (lp && rp) return node_is_before_sibling(lp, rp);
 
-		// determine sibling order
-		for (; ln; ln = ln.next_sibling())
-			if (ln == rn)
-				return true;
+		// nodes are at different depths, need to normalize heights
+		bool left_higher = !lp;
 
-		return false;
+		while (lp)
+		{
+			lp = lp->parent;
+			ln = ln->parent;
+		}
+
+		while (rp)
+		{
+			rp = rp->parent;
+			rn = rn->parent;
+		}
+
+		// one node is the ancestor of the other
+		if (ln == rn) return left_higher;
+
+		// find common ancestor... again
+		while (ln->parent != rn->parent)
+		{
+			ln = ln->parent;
+			rn = rn->parent;
+		}
+
+		return node_is_before_sibling(ln, rn);
 	}
 
 	PUGI__FN bool node_is_ancestor(xml_node parent, xml_node node)
@@ -6933,11 +6960,10 @@ PUGI__NS_BEGIN
 			}
 
 			if (ln == rn) return false;
+
+			if (!ln || !rn) return ln < rn;
 			
-			unsigned int lh = node_height(ln);
-			unsigned int rh = node_height(rn);
-			
-			return node_is_before(ln, lh, rn, rh);
+			return node_is_before(ln.internal_object(), rn.internal_object());
 		}
 	};