XPath: Introduce _first/_any set evaluation modes

Sometimes when evaluating the node set we don't need the entire set and
only need the first element in docorder or any element. In the absence of
iterator support we can still use this information to short-circuit
traversals.

This does not have any effect on straightforward node collection queries,
but frequently improves performance of complex queries with predicates
etc. XMark benchmark gets 15x faster with some queries enjoying 100x
speedup on 10 Mb dataset due to a significant complexity improvement.

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

1 files changed, 22 insertions, 0 deletions

diff --git a/tests/test_xpath.cpp b/tests/test_xpath.cpp
index f7da258..2143376 100644
--- a/tests/test_xpath.cpp
+++ b/tests/test_xpath.cpp
@@ -122,6 +122,28 @@ TEST_XML(xpath_sort_attributes, "<node/>")
 	xpath_node_set_tester(reverse_sorted, "reverse sorted order failed") % 5 % 4 % 3;
 }
 
+TEST(xpath_sort_random_medium)
+{
+	xml_document doc;
+	load_document_copy(doc, STR("<node>")
+		STR("<child1 attr1='value1' attr2='value2'/><child2 attr1='value1'>test</child2><child1 attr1='value1' attr2='value2'/><child2 attr1='value1'>test</child2>")
+		STR("<child1 attr1='value1' attr2='value2'/><child2 attr1='value1'>test</child2><child1 attr1='value1' attr2='value2'/><child2 attr1='value1'>test</child2>")
+		STR("<child1 attr1='value1' attr2='value2'/><child2 attr1='value1'>test</child2><child1 attr1='value1' attr2='value2'/><child2 attr1='value1'>test</child2>")
+		STR("</node>"));
+
+	xpath_node_set ns = doc.select_nodes(STR("//node() | //@*"));
+
+	std::vector<xpath_node> nsv(ns.begin(), ns.end());
+	std::random_shuffle(nsv.begin(), nsv.end());
+
+	xpath_node_set copy(&nsv[0], &nsv[0] + nsv.size());
+	copy.sort();
+
+	xpath_node_set_tester tester(copy, "sorted order failed");
+
+	for (unsigned int i = 2; i < 39; ++i) tester % i;
+}
+
 TEST(xpath_sort_random_large)
 {
 	xml_document doc;