This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
| Other format: | [Raw text] | |
Attachment:
ChangeLog-sort
Description: application/text
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/include/bits/stl_algo.h libstdc++-v3/include/bits/stl_algo.h
--- libstdc++-v3.so_7.clean/include/bits/stl_algo.h 2005-05-25 13:38:47.000000000 +0100
+++ libstdc++-v3/include/bits/stl_algo.h 2005-06-03 21:59:13.000000000 +0100
@@ -1929,20 +1929,109 @@
* This is a helper function for the sort routine.
* @endif
*/
- template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
- void
- __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
- _Compare __comp)
+ template<typename _RandomAccessIterator, typename _Compare>
+ inline void
+ __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
{
+ typename iterator_traits<_RandomAccessIterator>::value_type
+ __val(__gnu_cxx::__move(*__last));
_RandomAccessIterator __next = __last;
--__next;
while (__comp(__val, *__next))
{
- *__last = *__next;
+ *__last = __gnu_cxx::__move(*__next);
__last = __next;
--__next;
}
- *__last = __val;
+ *__last = __gnu_cxx::__move(__val);
+ }
+
+ /**
+ * @if maint
+ * This is a helper function. It assumes __pivot is not in the range
+ * [__first, __last).
+ * @endif
+ */
+ template<typename _RandomAccessIterator, typename _Compare>
+ inline _RandomAccessIterator
+ __unguarded_nocopy_partition(_RandomAccessIterator __first,
+ _RandomAccessIterator __last,
+ _RandomAccessIterator __pivot, _Compare __comp)
+ {
+ while (true)
+ {
+ while (__comp(*__first, *__pivot))
+ ++__first;
+ --__last;
+ while (__comp(*__pivot, *__last))
+ --__last;
+ if (!(__first < __last))
+ return __first;
+ std::iter_swap(__first, __last);
+ ++__first;
+ }
+ }
+
+ /**
+ * @if maint
+ * This is a helper function for the sort routine
+ * @endif
+ */
+ template<typename _RandomAccessIterator, typename _Compare>
+ _RandomAccessIterator
+ __unguarded_mid_partition(_RandomAccessIterator __first,
+ _RandomAccessIterator __last,
+ _RandomAccessIterator __pivot, _Compare __comp)
+ {
+ while (true)
+ {
+ while (__comp(*__first, *__pivot))
+ ++__first;
+ --__last;
+ while (__comp(*__pivot, *__last))
+ --__last;
+ if (__first == __pivot)
+ {
+ if(__last == __pivot)
+ return __first;
+ ++__first;
+ while(__comp(*__first, *__pivot))
+ ++__first;
+ if(!(__first < __last))
+ return __first;
+ std::iter_swap(__first, __last);
+ ++__first;
+ break;
+ }
+
+ if (__last == __pivot)
+ {
+ --__last;
+ while(__comp(*__pivot, *__last))
+ --__last;
+ if(!(__first < __last))
+ return __first;
+ std::iter_swap(__first, __last);
+ ++__first;
+ break;
+ }
+ std::iter_swap(__first, __last);
+ ++__first;
+ }
+
+ while (true)
+ {
+ while (__comp(*__first, *__pivot))
+ ++__first;
+ --__last;
+ while (__comp(*__pivot, *__last))
+ --__last;
+
+ if (!(__first < __last))
+ return __first;
+ std::iter_swap(__first, __last);
+ ++__first;
+ }
}
/**
@@ -1959,15 +2048,15 @@
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
{
- typename iterator_traits<_RandomAccessIterator>::value_type
- __val = *__i;
- if (__comp(__val, *__first))
+ if (__comp(*__i, *__first))
{
- std::copy_backward(__first, __i, __i + 1);
- *__first = __val;
+ typename iterator_traits<_RandomAccessIterator>::value_type
+ __val(__gnu_cxx::__move(*__i));
+ std::__move_backward(__first, __i, __i + 1);
+ *__first = __gnu_cxx::__move(__val);
}
else
- std::__unguarded_linear_insert(__i, __val, __comp);
+ std::__unguarded_linear_insert(__i, __comp);
}
}
@@ -1985,7 +2074,7 @@
_ValueType;
for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
- std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
+ std::__unguarded_linear_insert(__i, __comp);
}
/**
@@ -2200,6 +2289,65 @@
__gnu_cxx::__ops::less());
}
+
+
+ template<typename _RandomAccessIterator, typename _Compare>
+ inline typename __enable_if<_RandomAccessIterator,
+ !(__gnu_cxx::__is_moveable<typename iterator_traits<_RandomAccessIterator>
+ ::value_type>::value)>::__type
+ __introsort_partition(_RandomAccessIterator __first,
+ _RandomAccessIterator __last, _Compare __comp)
+ {
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
+
+ return
+ std::__unguarded_partition(__first, __last,
+ _ValueType(std::__median(*__first,
+ *(__first
+ + (__last
+ - __first)
+ / 2),
+ *(__last - 1),
+ __comp)),
+ __comp);
+ }
+
+template<typename _RandomAccessIterator, typename _Compare>
+ inline typename __enable_if<_RandomAccessIterator,
+ __gnu_cxx::__is_moveable<typename iterator_traits<_RandomAccessIterator>
+ ::value_type>::value>::__type
+ __introsort_partition(_RandomAccessIterator __first,
+ _RandomAccessIterator __last, _Compare __comp)
+ {
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
+ _RandomAccessIterator __cut, __pivot(__first + (__last - __first)/2);
+ const _ValueType &__a = *__first;
+ const _ValueType &__b = *__pivot;
+ const _ValueType &__c = *(__last - 1);
+
+ if (__comp(__a, __b))
+ if (__comp(__b, __c))
+ __cut = __unguarded_mid_partition(__first, __last, __pivot,
+ __comp);
+ else if (__comp(__a, __c))
+ __cut = __unguarded_nocopy_partition(__first, __last - 1,
+ __last - 1, __comp);
+ else
+ __cut = __unguarded_nocopy_partition(__first + 1, __last,
+ __first, __comp);
+ else if (__comp(__a, __c))
+ __cut = __unguarded_nocopy_partition(__first + 1, __last, __first,
+ __comp);
+ else if (__comp(__b, __c))
+ __cut = __unguarded_nocopy_partition(__first, __last - 1,
+ __last - 1, __comp);
+ else
+ __cut = __unguarded_mid_partition(__first, __last, __pivot, __comp);
+ return __cut;
+ }
+
/**
* @if maint
* This is a helper function for the sort routine.
@@ -2223,15 +2371,7 @@
}
--__depth_limit;
_RandomAccessIterator __cut =
- std::__unguarded_partition(__first, __last,
- _ValueType(std::__median(*__first,
- *(__first
- + (__last
- - __first)
- / 2),
- *(__last - 1),
- __comp)),
- __comp);
+ std::__introsort_partition(__first, __last, __comp);
std::__introsort_loop(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
@@ -3051,14 +3191,7 @@
while (__last - __first > 3)
{
_RandomAccessIterator __cut =
- std::__unguarded_partition(__first, __last,
- _ValueType(std::__median(*__first,
- *(__first
- + (__last
- - __first)
- / 2),
- *(__last - 1),
- __comp)), __comp);
+ __introsort_partition(__first, __last, __comp);
if (__cut <= __nth)
__first = __cut;
else
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/include/bits/stl_algobase.h libstdc++-v3/include/bits/stl_algobase.h
--- libstdc++-v3.so_7.clean/include/bits/stl_algobase.h 2005-05-25 13:38:47.000000000 +0100
+++ libstdc++-v3/include/bits/stl_algobase.h 2005-05-31 21:42:21.000000000 +0100
@@ -381,6 +381,33 @@
return std::__copy_normal<__in, __out>::copy_n(__first, __last,
__result);
}
+
+ template<typename _InputIterator, typename _OutputIterator>
+ inline typename __enable_if<_OutputIterator,
+ __gnu_cxx::__is_moveable<
+ typename std::iterator_traits<_OutputIterator>::value_type>::value &&
+ __are_same<typename std::iterator_traits<_InputIterator>::value_type,
+ typename std::iterator_traits<_OutputIterator>::value_type>
+ ::__value>::__type
+ __move(_InputIterator __first, _InputIterator __last,
+ _OutputIterator __result)
+ {
+ for(; __first != __last; ++__result, ++__first)
+ *__result = __gnu_cxx::__move(*__first);
+ return __result;
+ }
+
+ template<typename _InputIterator, typename _OutputIterator>
+ inline typename __enable_if<_OutputIterator,
+ !(__gnu_cxx::__is_moveable<
+ typename std::iterator_traits<_OutputIterator>::value_type>::value &&
+ __are_same<typename std::iterator_traits<_InputIterator>::value_type,
+ typename std::iterator_traits<_OutputIterator>::value_type>
+ ::__value)>::__type
+ __move(_InputIterator __first, _InputIterator __last,
+ _OutputIterator __result)
+ { return std::copy(__first, __last, __result); }
+
template<bool, typename>
struct __copy_backward
@@ -512,6 +539,34 @@
__result);
}
+ template<typename _InputIterator, typename _OutputIterator>
+ inline
+ typename __enable_if<_OutputIterator,
+ __gnu_cxx::__is_moveable<
+ typename iterator_traits<_OutputIterator>::value_type>::value &&
+ __are_same<typename iterator_traits<_InputIterator>::value_type,
+ typename iterator_traits<_OutputIterator>::value_type>
+ ::__value>::__type
+ __move_backward(_InputIterator __first, _InputIterator __last,
+ _OutputIterator __result)
+ {
+ while (__first != __last)
+ *--__result = __gnu_cxx::__move(*--__last);
+ return __result;
+ }
+
+ template<typename _InputIterator, typename _OutputIterator>
+ inline
+ typename __enable_if<_OutputIterator,
+ !(__gnu_cxx::__is_moveable<
+ typename iterator_traits<_OutputIterator>::value_type>::value &&
+ __are_same<typename iterator_traits<_InputIterator>::value_type,
+ typename iterator_traits<_OutputIterator>::value_type>
+ ::__value)>::__type
+ __move_backward(_InputIterator __first, _InputIterator __last,
+ _OutputIterator __result)
+ { return std::copy_backward(__first, __last, __result); }
+
template<bool>
struct __fill
{
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/nth_element/moveable.cc libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/nth_element/moveable.cc 1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/nth_element/moveable.cc 2005-05-24 22:51:23.000000000 +0100
@@ -0,0 +1,73 @@
+// Copyright (C) 2005 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.2 [lib.alg.nth.element]
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+using std::nth_element;
+using __gnu_test::rvalstruct;
+
+typedef test_container<rvalstruct, random_access_iterator_wrapper> Container;
+
+void
+test1()
+{
+ int intarray[] = {6, 5, 4, 3, 2, 1, 0};
+ rvalstruct array[7];
+ std::copy(intarray, intarray + 7, array);
+ Container con(array, array + 7);
+ nth_element(con.begin(), con.it(3), con.end());
+ for(int i = 0; i < 3; ++i)
+ VERIFY(array[i].val < 3);
+ for(int i = 4; i < 7; ++i)
+ VERIFY(array[i].val > 3);
+ for(int i = 0; i < 7; ++i)
+ VERIFY(array[i].valid);
+}
+
+void
+test2()
+{
+ int intarray[] = {0, 6, 1, 5, 2, 4, 3};
+ rvalstruct array[7];
+ std::copy(intarray, intarray + 7, array);
+ Container con(array,array + 7);
+ nth_element(con.begin(), con.it(3), con.end());
+ for(int i = 0; i < 3; ++i)
+ VERIFY(array[i].val < 3);
+ for(int i = 4; i < 7; ++i)
+ VERIFY(array[i].val > 3);
+ for(int i = 0; i < 7; ++i)
+ VERIFY(array[i].valid);
+}
+
+int
+main()
+{
+ test1();
+ test2();
+ return 0;
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/partial_sort/moveable.cc libstdc++-v3/testsuite/25_algorithms/partial_sort/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/partial_sort/moveable.cc 1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/partial_sort/moveable.cc 2005-05-22 12:00:46.000000000 +0100
@@ -0,0 +1,67 @@
+// Copyright (C) 2005 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1.3 [lib.partial.sort]
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+#define _GLIBCXX_TESTSUITE_ALLOW_RVALREF_ALIASING
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+using __gnu_test::rvalstruct;
+using std::partial_sort;
+
+typedef test_container<rvalstruct, random_access_iterator_wrapper> Container;
+
+void
+test1()
+{
+ int intarray[] = {6, 5, 4, 3, 2, 1, 0};
+ rvalstruct array[7];
+ std::copy(intarray, intarray + 7, array);
+ Container con(array, array + 7);
+ partial_sort(con.begin(), con.it(3), con.end());
+ VERIFY(array[0].val == 0 && array[1].val == 1 && array[2].val == 2);
+ for(int i = 0; i < 7; ++i)
+ VERIFY(array[i].valid);
+}
+
+void
+test2()
+{
+ int intarray[] = {0, 6, 1, 5, 2, 4, 3};
+ rvalstruct array[7];
+ std::copy(intarray, intarray + 7, array);
+ Container con(array,array + 7);
+ partial_sort(con.begin(), con.it(3), con.end());
+ VERIFY(array[0].val == 0 && array[1].val == 1 && array[2].val == 2);
+ for(int i = 0; i < 7; ++i)
+ VERIFY(array[i].valid);
+}
+
+int
+main()
+{
+ test1();
+ test2();
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort/moveable.cc libstdc++-v3/testsuite/25_algorithms/sort/moveable.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort/moveable.cc 1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/sort/moveable.cc 2005-05-22 12:41:24.000000000 +0100
@@ -0,0 +1,61 @@
+// Copyright (C) 2001 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1 algorithms, sort()
+
+#undef _GLIBCXX_CONCEPT_CHECKS
+#define _GLIBCXX_TESTSUITE_ALLOW_RVALREF_ALIASING
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+#include <testsuite_rvalref.h>
+
+bool test __attribute__((unused)) = true;
+
+using __gnu_test::test_container;
+using __gnu_test::random_access_iterator_wrapper;
+using __gnu_test::rvalstruct;
+using std::partial_sort;
+
+typedef test_container<rvalstruct, random_access_iterator_wrapper> Container;
+
+
+const int A[] = {10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7,
+ 17, 8, 18, 9, 19};
+const int N = sizeof(A) / sizeof(int);
+
+// 25.3.1.1 sort()
+void
+test01()
+{
+ rvalstruct s1[N];
+ std::copy(A, A + N, s1);
+ Container con(s1, s1 + N);
+ std::sort(con.begin(), con.end());
+ VERIFY(s1[0].valid);
+ for(int i = 1; i < N; ++i)
+ VERIFY(s1[i].val>s1[i-1].val && s1[i].valid);
+}
+
+int
+main()
+{
+ test01();
+ return 0;
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort/sort.cc libstdc++-v3/testsuite/25_algorithms/sort/sort.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort/sort.cc 1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/sort/sort.cc 2005-06-04 19:49:08.000000000 +0100
@@ -0,0 +1,171 @@
+// Copyright (C) 2001 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// 25.3.1 algorithms, sort()
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
+const int B[] = {10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19};
+const int C[] = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
+const int N = sizeof(A) / sizeof(int);
+const int logN = 3; // ln(N) rounded up
+const int P = 7;
+
+// comparison predicate for stable_sort: order by rightmost digit
+struct CompLast
+{
+ bool
+ operator()(const int x, const int y)
+ { return x % 10 < y % 10; }
+};
+
+// This functor has the equivalent functionality of std::geater<>,
+// but there is no dependency on <functional> and it also tracks the
+// number of invocations since creation.
+class Gt
+{
+public:
+ static int count() { return itsCount; }
+ static void reset() { itsCount = 0; }
+
+ bool
+ operator()(const int& x, const int& y)
+ {
+ ++itsCount;
+ return x > y;
+ }
+
+private:
+ static int itsCount;
+};
+
+int Gt::itsCount = 0;
+
+
+// 25.3.1.1 sort()
+void
+test01()
+{
+ int s1[N];
+ std::copy(B, B + N, s1);
+ VERIFY(std::equal(s1, s1 + N, B));
+
+ std::sort(s1, s1 + N);
+ VERIFY(std::equal(s1, s1 + N, A));
+
+ Gt gt;
+ gt.reset();
+ std::sort(s1, s1 + N, gt);
+ VERIFY(std::equal(s1, s1 + N, C));
+}
+
+// 25.3.1.2 stable_sort()
+void
+test02()
+{
+ int s1[N];
+ std::copy(A, A + N, s1);
+ VERIFY(std::equal(s1, s1 + N, A));
+
+ std::stable_sort(s1, s1 + N, CompLast());
+ VERIFY(std::equal(s1, s1 + N, B));
+
+ std::stable_sort(s1, s1 + N);
+ VERIFY(std::equal(s1, s1 + N, A));
+
+ Gt gt;
+ gt.reset();
+ std::stable_sort(s1, s1 + N, gt);
+ VERIFY(std::equal(s1, s1 + N, C));
+ VERIFY(gt.count() <= N * logN * logN);
+}
+
+// 25.3.1.3 partial_sort()
+void
+test03()
+{
+ int s1[N];
+ std::copy(B, B + N, s1);
+ VERIFY(std::equal(s1, s1 + N, B));
+
+ std::partial_sort(s1, s1 + P, s1 + N);
+ VERIFY(std::equal(s1, s1 + P, A));
+
+ Gt gt;
+ gt.reset();
+ std::partial_sort(s1, s1 + P, s1 + N, gt);
+ VERIFY(std::equal(s1, s1 + P, C));
+}
+
+// 25.3.1.4 partial_sort_copy()
+void
+test04()
+{
+ using std::partial_sort_copy;
+
+ int s1[N];
+ std::copy(B, B + N, s1);
+ VERIFY(std::equal(s1, s1 + N, B));
+
+ int s2[2*N];
+
+ partial_sort_copy(s1, s1 + N, s2, s2 + P);
+ VERIFY(std::equal(s2, s2 + P, A));
+
+ Gt gt;
+ gt.reset();
+ partial_sort_copy(s1, s1 + N, s2, s2 + P, gt);
+ VERIFY(std::equal(s2, s2 + P, C));
+
+ VERIFY(std::equal(s2, partial_sort_copy(s1, s1 + N, s2, s2 + 2*N), A));
+}
+
+// 25.3.2 nth_element()
+void
+test05()
+{
+ using std::nth_element;
+
+ int s1[N];
+ std::copy(B, B + N, s1);
+ VERIFY(std::equal(s1, s1 + N, B));
+
+ int* pn = s1 + (N / 2) - 1;
+ nth_element(s1, pn, s1 + N);
+ for (const int* i = pn; i < s1 + N; ++i) VERIFY(!(*i < *pn));
+
+ CompLast pred;
+ nth_element(s1, pn, s1 + N, pred);
+ for (const int* i = pn; i < s1 + N; ++i) VERIFY(!pred(*i, *pn));
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+ test04();
+ test05();
+
+ return 0;
+}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort.cc libstdc++-v3/testsuite/25_algorithms/sort.cc
--- libstdc++-v3.so_7.clean/testsuite/25_algorithms/sort.cc 2003-09-23 21:02:52.000000000 +0100
+++ libstdc++-v3/testsuite/25_algorithms/sort.cc 1970-01-01 01:00:00.000000000 +0100
@@ -1,171 +0,0 @@
-// Copyright (C) 2001 Free Software Foundation, Inc.
-//
-// This file is part of the GNU ISO C++ Library. This library is free
-// software; you can redistribute it and/or modify it under the
-// terms of the GNU General Public License as published by the
-// Free Software Foundation; either version 2, or (at your option)
-// any later version.
-
-// This library is distributed in the hope that it will be useful,
-// but WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-// GNU General Public License for more details.
-
-// You should have received a copy of the GNU General Public License along
-// with this library; see the file COPYING. If not, write to the Free
-// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
-// USA.
-
-// 25.3.1 algorithms, sort()
-
-#include <algorithm>
-#include <testsuite_hooks.h>
-
-bool test __attribute__((unused)) = true;
-
-const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
-const int B[] = {10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19};
-const int C[] = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
-const int N = sizeof(A) / sizeof(int);
-const int logN = 3; // ln(N) rounded up
-const int P = 7;
-
-// comparison predicate for stable_sort: order by rightmost digit
-struct CompLast
-{
- bool
- operator()(const int x, const int y)
- { return x % 10 < y % 10; }
-};
-
-// This functor has the equivalent functionality of std::geater<>,
-// but there is no dependency on <functional> and it also tracks the
-// number of invocations since creation.
-class Gt
-{
-public:
- static int count() { return itsCount; }
- static void reset() { itsCount = 0; }
-
- bool
- operator()(const int& x, const int& y)
- {
- ++itsCount;
- return x > y;
- }
-
-private:
- static int itsCount;
-};
-
-int Gt::itsCount = 0;
-
-
-// 25.3.1.1 sort()
-void
-test01()
-{
- int s1[N];
- std::copy(B, B + N, s1);
- VERIFY(std::equal(s1, s1 + N, B));
-
- std::sort(s1, s1 + N);
- VERIFY(std::equal(s1, s1 + N, A));
-
- Gt gt;
- gt.reset();
- std::sort(s1, s1 + N, gt);
- VERIFY(std::equal(s1, s1 + N, C));
-}
-
-// 25.3.1.2 stable_sort()
-void
-test02()
-{
- int s1[N];
- std::copy(A, A + N, s1);
- VERIFY(std::equal(s1, s1 + N, A));
-
- std::stable_sort(s1, s1 + N, CompLast());
- VERIFY(std::equal(s1, s1 + N, B));
-
- std::stable_sort(s1, s1 + N);
- VERIFY(std::equal(s1, s1 + N, A));
-
- Gt gt;
- gt.reset();
- std::stable_sort(s1, s1 + N, gt);
- VERIFY(std::equal(s1, s1 + N, C));
- VERIFY(gt.count() <= N * logN * logN);
-}
-
-// 25.3.1.3 partial_sort()
-void
-test03()
-{
- int s1[N];
- std::copy(B, B + N, s1);
- VERIFY(std::equal(s1, s1 + N, B));
-
- std::partial_sort(s1, s1 + P, s1 + N);
- VERIFY(std::equal(s1, s1 + P, A));
-
- Gt gt;
- gt.reset();
- std::partial_sort(s1, s1 + P, s1 + N, gt);
- VERIFY(std::equal(s1, s1 + P, C));
-}
-
-// 25.3.1.4 partial_sort_copy()
-void
-test04()
-{
- using std::partial_sort_copy;
-
- int s1[N];
- std::copy(B, B + N, s1);
- VERIFY(std::equal(s1, s1 + N, B));
-
- int s2[2*N];
-
- partial_sort_copy(s1, s1 + N, s2, s2 + P);
- VERIFY(std::equal(s2, s2 + P, A));
-
- Gt gt;
- gt.reset();
- partial_sort_copy(s1, s1 + N, s2, s2 + P, gt);
- VERIFY(std::equal(s2, s2 + P, C));
-
- VERIFY(std::equal(s2, partial_sort_copy(s1, s1 + N, s2, s2 + 2*N), A));
-}
-
-// 25.3.2 nth_element()
-void
-test05()
-{
- using std::nth_element;
-
- int s1[N];
- std::copy(B, B + N, s1);
- VERIFY(std::equal(s1, s1 + N, B));
-
- int* pn = s1 + (N / 2) - 1;
- nth_element(s1, pn, s1 + N);
- for (const int* i = pn; i < s1 + N; ++i) VERIFY(!(*i < *pn));
-
- CompLast pred;
- nth_element(s1, pn, s1 + N, pred);
- for (const int* i = pn; i < s1 + N; ++i) VERIFY(!pred(*i, *pn));
-}
-
-int
-main()
-{
- test01();
- test02();
- test03();
- test04();
- test05();
-
- return 0;
-}
diff -urN -x'*CVS*' libstdc++-v3.so_7.clean/testsuite/performance/25_algorithms/sort.cc libstdc++-v3/testsuite/performance/25_algorithms/sort.cc
--- libstdc++-v3.so_7.clean/testsuite/performance/25_algorithms/sort.cc 1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/performance/25_algorithms/sort.cc 2005-05-28 11:28:50.000000000 +0100
@@ -0,0 +1,227 @@
+// Copyright (C) 2005 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction. Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License. This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+
+#define DISABLE_ITERATOR_DEBUG
+
+#include<vector>
+#include<algorithm>
+#include<stdio.h>
+#include<string>
+#include<sstream>
+
+#include<testsuite_performance.h>
+#include<testsuite_iterators.h>
+
+using namespace std;
+using namespace __gnu_test;
+
+// Used to stop move symantics
+struct vec_wrap
+{
+ vector<int> v;
+
+ explicit vec_wrap(vector<int> in_vec) : v(in_vec)
+ { }
+
+ vec_wrap()
+ { }
+};
+
+bool inline
+operator<(const vec_wrap& lhs, const vec_wrap& rhs)
+{ return lhs.v == rhs.v; }
+
+
+// Used to perform the move symantics algorithm on an int
+struct int_wrap
+{
+ int i;
+
+ explicit int_wrap(int in_val) : i(in_val)
+ { }
+
+ int_wrap(__gnu_cxx::__rvalref<int_wrap> in) : i(in.__ref.i)
+ { }
+
+ void
+ operator=(int in)
+ { i = in; }
+
+ void
+ operator=(__gnu_cxx::__rvalref<int_wrap> in)
+ { i = in.__ref.i; }
+
+ int_wrap()
+ { }
+};
+
+struct ptr_wrap
+{
+ vector<int>* ptr;
+ ptr_wrap(vector<int>* in_ptr) : ptr(in_ptr)
+ { }
+};
+
+bool inline
+operator<(ptr_wrap lhs, ptr_wrap rhs)
+{ return *(lhs.ptr) < *(rhs.ptr); }
+
+bool inline
+operator<(const int_wrap& lhs, const int_wrap& rhs)
+{ return lhs.i < rhs.i; }
+
+namespace __gnu_cxx
+{
+ template<>
+ struct __is_moveable<int_wrap>
+ { static const bool value = true; };
+}
+
+struct
+dereference_compare
+{
+ template<typename T>
+ bool operator()(T lhs, T rhs)
+ { return *lhs < *rhs; }
+};
+
+template<typename T>
+void sort_and_output(T& vec, std::string description)
+{
+ time_counter time;
+ resource_counter resource;
+ start_counters(time, resource);
+ std::sort(vec.begin(), vec.end());
+ stop_counters(time, resource);
+ report_performance(__FILE__, description.c_str(), time, resource);
+ clear_counters(time, resource);
+
+}
+
+void
+test1(int vec_length, vector<int> sort_vec, string vec_description)
+{
+ vector<vector<int> > moveable_vecs;
+ for(int i = 0; i < sort_vec.size(); i++)
+ {
+ vector<int> vec(vec_length, sort_vec[i]);
+ moveable_vecs.push_back(vec);
+ }
+ ostringstream outputline;
+ outputline << "moveable vector - length " << sort_vec.size() << ":" <<
+ vec_description;
+ sort_and_output(moveable_vecs, outputline.str());
+}
+
+
+void
+test2(int vec_length, vector<int> sort_vec, string vec_description )
+{
+ vector<vec_wrap> unmoveable_vecs;
+ for(int i = 0; i < sort_vec.size(); i++)
+ {
+ vector<int> vec(vec_length, sort_vec[i]);
+ vec_wrap wrap(vec);
+ unmoveable_vecs.push_back(wrap);
+ }
+ ostringstream outputline;
+ outputline << "unmoveable vector - length " << sort_vec.size() << ":" <<
+ vec_description;
+ sort_and_output(unmoveable_vecs, outputline.str());
+}
+
+
+void
+test3(int vec_length, vector<int> sort_vec, string vec_description)
+{
+ vector<vector<int> > primary_vec;
+ vector<ptr_wrap> ptr_vec;
+ for(int i = 0; i < sort_vec.size(); i++)
+ {
+ vector<int> vec(vec_length, sort_vec[i]);
+ primary_vec.push_back(vec);
+ }
+ for(int i = 0; i < sort_vec.size(); i++)
+ ptr_vec.push_back(&primary_vec[i]);
+ ostringstream outputline;
+ outputline << "pointers to vector - length " << sort_vec.size() << ":" <<
+ vec_description;
+ sort_and_output(ptr_vec, outputline.str());
+}
+
+
+void
+test4(vector<int> sort_vec, string vec_description)
+{
+ ostringstream outputline;
+ outputline << "ints - length " << sort_vec.size() << ":" << vec_description;
+ sort_and_output(sort_vec, outputline.str());
+}
+
+void
+test5(vector<int> sort_vec, string vec_description)
+{
+ vector<int_wrap> moveable_int_vec(sort_vec.size());
+ copy(sort_vec.begin(), sort_vec.end(), moveable_int_vec.begin());
+ ostringstream outputline;
+ outputline << "moveable ints - length " << sort_vec.size() << ":" <<
+ vec_description;
+ sort_and_output(moveable_int_vec, outputline.str());
+}
+
+int
+main(void)
+{
+ for(int length = 100000; length < 1000001; length*=10)
+ {
+ vector<int> sort_vec;
+ int val = 1000;
+ for(int i = 0; i < length; ++i)
+ {
+ val = (val * 88888) % 1000003;
+ sort_vec.push_back(val);
+ }
+ test1(1000000/length, sort_vec, "random vector");
+ test2(1000000/length, sort_vec, "random vector");
+ test3(1000000/length, sort_vec, "random vector");
+
+ }
+
+ for(int length = 1000000; length < 10000001; length*=10)
+ {
+ vector<int> sort_vec;
+ int val = 1000;
+ for(int i = 0; i < length; ++i)
+ {
+ val = (val * 88888) % 1000003;
+ sort_vec.push_back(val);
+ }
+ test4(sort_vec, "random vector");
+ test5(sort_vec, "random vector");
+ }
+}
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |