summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/pugixml.cpp38
1 files changed, 12 insertions, 26 deletions
diff --git a/src/pugixml.cpp b/src/pugixml.cpp
index 110ece6..90b24aa 100644
--- a/src/pugixml.cpp
+++ b/src/pugixml.cpp
@@ -7216,39 +7216,25 @@ PUGI__NS_BEGIN
return write + 1;
}
- template <typename I> void copy_backwards(I begin, I end, I target)
+ template <typename T, typename Pred> void insertion_sort(T* begin, T* end, const Pred& pred)
{
- while (begin != end) *--target = *--end;
- }
-
- template <typename I, typename Pred, typename T> void insertion_sort(I begin, I end, const Pred& pred, T*)
- {
- assert(begin != end);
+ if (begin == end)
+ return;
- for (I it = begin + 1; it != end; ++it)
+ for (T* it = begin + 1; it != end; ++it)
{
T val = *it;
+ T* hole = it;
- if (pred(val, *begin))
+ // move hole backwards
+ while (hole > begin && pred(val, *(hole - 1)))
{
- // move to front
- copy_backwards(begin, it, it + 1);
- *begin = val;
+ *hole = *(hole - 1);
+ hole--;
}
- else
- {
- I hole = it;
- // move hole backwards
- while (pred(val, *(hole - 1)))
- {
- *hole = *(hole - 1);
- hole--;
- }
-
- // fill hole with element
- *hole = val;
- }
+ // fill hole with element
+ *hole = val;
}
}
@@ -7359,7 +7345,7 @@ PUGI__NS_BEGIN
}
// insertion sort small chunk
- if (begin != end) insertion_sort(begin, end, pred, &*begin);
+ insertion_sort(begin, end, pred);
}
PUGI__NS_END