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());
 		}
 	};