summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorArseny Kapoulkine <arseny.kapoulkine@gmail.com>2014-10-05 04:20:38 +0000
committerArseny Kapoulkine <arseny.kapoulkine@gmail.com>2014-10-05 04:20:38 +0000
commite66356715c8ab207350bc30904b30c4de4515506 (patch)
treee4f758d06167adbf8b9d24f54d7efc705a627471
parent42219590f3ea1e88e41f8250da5a123f3a9236b2 (diff)
Optimize XPath sorting for sorted sequences
XPath evaluation frequently produces sequences that are sorted but are not tagged as such (area for improvement...). Doing a linear scan before sorting is cheap and results in tremendous speedup for already sorted sequences (especially if document_buffer_order optimization does not apply). git-svn-id: https://pugixml.googlecode.com/svn/trunk@1049 99668b35-9821-0410-8761-19e4c4f06640
-rw-r--r--src/pugixml.cpp29
1 files changed, 26 insertions, 3 deletions
diff --git a/src/pugixml.cpp b/src/pugixml.cpp
index 55dd8ec..94073f3 100644
--- a/src/pugixml.cpp
+++ b/src/pugixml.cpp
@@ -6844,7 +6844,7 @@ PUGI__NS_BEGIN
for (; ln; ln = ln.next_sibling())
if (ln == rn)
return true;
-
+
return false;
}
@@ -7498,15 +7498,38 @@ PUGI__NS_END
// Internal node set class
PUGI__NS_BEGIN
+ PUGI__FN xpath_node_set::type_t xpath_get_order(const xpath_node* begin, const xpath_node* end)
+ {
+ if (end - begin < 2)
+ return xpath_node_set::type_sorted;
+
+ document_order_comparator cmp;
+
+ bool first = cmp(begin[0], begin[1]);
+
+ for (const xpath_node* it = begin + 1; it + 1 < end; ++it)
+ if (cmp(it[0], it[1]) != first)
+ return xpath_node_set::type_unsorted;
+
+ return first ? xpath_node_set::type_sorted : xpath_node_set::type_sorted_reverse;
+ }
+
PUGI__FN xpath_node_set::type_t xpath_sort(xpath_node* begin, xpath_node* end, xpath_node_set::type_t type, bool rev)
{
xpath_node_set::type_t order = rev ? xpath_node_set::type_sorted_reverse : xpath_node_set::type_sorted;
if (type == xpath_node_set::type_unsorted)
{
- sort(begin, end, document_order_comparator());
+ xpath_node_set::type_t sorted = xpath_get_order(begin, end);
+
+ if (sorted == xpath_node_set::type_unsorted)
+ {
+ sort(begin, end, document_order_comparator());
- type = xpath_node_set::type_sorted;
+ type = xpath_node_set::type_sorted;
+ }
+ else
+ type = sorted;
}
if (type != order) reverse(begin, end);