This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[v3] Rewrite __copy_backward/__copy_backward_aux, etc...
- From: Paolo Carlini <pcarlini at suse dot de>
- To: "'gcc-patches at gcc dot gnu dot org'" <gcc-patches at gcc dot gnu dot org>
- Date: Wed, 30 Jun 2004 11:25:29 +0200
- Subject: [v3] Rewrite __copy_backward/__copy_backward_aux, etc...
Hi,
the below is what I have finally committed to mainline. Tested
x86-linux, check/check-performance.
Paolo.
////////////
2004-06-30 Gabriel Dos Reis <gdr@integrable-solutions.net>
Paolo Carlini <pcarlini@suse.de>
* include/bits/cpp_type_traits.h: Add __is_pointer and
__is_trivially_copyable.
* include/bits/stl_algobase.h (fill, fill_n): Slightly
tweak to use the latter.
(__copy_backward_dispatch): Remove.
(__copy_backward_aux): Rewrite to use __is_pointer and
__is_trivially_copyable and __copy_backward::copy_b.
(__copy_backward): Rewrite as a class template and two
specializations.
2004-06-30 Paolo Carlini <pcarlini@suse.de>
* testsuite/25_algorithms/copy.cc: Move to...
* testsuite/25_algorithms/copy/1.cc: ... here, extend.
* testsuite/25_algorithms/copy/2.cc: New.
* testsuite/25_algorithms/copy/3.cc: New.
* testsuite/25_algorithms/copy/4.cc: New.diff -prN libstdc++-v3-orig/include/bits/cpp_type_traits.h libstdc++-v3/include/bits/cpp_type_traits.h
*** libstdc++-v3-orig/include/bits/cpp_type_traits.h Mon Jun 28 20:14:46 2004
--- libstdc++-v3/include/bits/cpp_type_traits.h Mon Jun 28 23:40:55 2004
*************** namespace std
*** 304,309 ****
--- 304,330 ----
};
//
+ // Pointer types
+ //
+ template<typename _Tp>
+ struct __is_pointer
+ {
+ enum
+ {
+ _M_type = 0
+ };
+ };
+
+ template<typename _Tp>
+ struct __is_pointer<_Tp*>
+ {
+ enum
+ {
+ _M_type = 1
+ };
+ };
+
+ //
// An arithmetic type is an integer type or a floating point type
//
template<typename _Tp>
*************** namespace std
*** 328,333 ****
--- 349,366 ----
};
//
+ // A trivially copyable type is an arithmetic type or a pointer type
+ //
+ template<typename _Tp>
+ struct __is_trivially_copyable
+ {
+ enum
+ {
+ _M_type = __is_arithmetic<_Tp>::_M_type || __is_pointer<_Tp>::_M_type
+ };
+ };
+
+ //
// For the immediate use, the following is a good approximation
//
template<typename _Tp>
diff -prN libstdc++-v3-orig/include/bits/stl_algobase.h libstdc++-v3/include/bits/stl_algobase.h
*** libstdc++-v3-orig/include/bits/stl_algobase.h Mon Jun 28 21:03:11 2004
--- libstdc++-v3/include/bits/stl_algobase.h Tue Jun 29 21:00:18 2004
***************
*** 70,75 ****
--- 70,76 ----
#include <iosfwd>
#include <bits/stl_pair.h>
#include <bits/type_traits.h>
+ #include <bits/cpp_type_traits.h>
#include <bits/stl_iterator_base_types.h>
#include <bits/stl_iterator_base_funcs.h>
#include <bits/stl_iterator.h>
*************** namespace std
*** 357,435 ****
typedef typename _Is_normal_iterator<_InputIterator>::_Normal __Normal;
return std::__copy_ni1(__first, __last, __result, __Normal());
}
!
! template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
! inline _BidirectionalIterator2
! __copy_backward(_BidirectionalIterator1 __first,
! _BidirectionalIterator1 __last,
! _BidirectionalIterator2 __result,
! bidirectional_iterator_tag)
! {
! while (__first != __last)
! *--__result = *--__last;
! return __result;
! }
!
! template<typename _RandomAccessIterator, typename _BidirectionalIterator>
! inline _BidirectionalIterator
! __copy_backward(_RandomAccessIterator __first, _RandomAccessIterator __last,
! _BidirectionalIterator __result, random_access_iterator_tag)
! {
! typename iterator_traits<_RandomAccessIterator>::difference_type __n;
! for (__n = __last - __first; __n > 0; --__n)
! *--__result = *--__last;
! return __result;
! }
!
!
! // This dispatch class is a workaround for compilers that do not
! // have partial ordering of function templates. All we're doing is
! // creating a specialization so that we can turn a call to copy_backward
! // into a memmove whenever possible.
! template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
! typename _BoolType>
! struct __copy_backward_dispatch
! {
! static _BidirectionalIterator2
! copy(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
! _BidirectionalIterator2 __result)
! { return std::__copy_backward(__first, __last, __result,
! std::__iterator_category(__first)); }
};
! template<typename _Tp>
! struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
{
! static _Tp*
! copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
! {
! const ptrdiff_t _Num = __last - __first;
! std::memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
! return __result - _Num;
! }
};
! template<typename _Tp>
! struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type>
{
! static _Tp*
! copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
! {
! return std::__copy_backward_dispatch<_Tp*, _Tp*, __true_type>
! ::copy(__first, __last, __result);
! }
};
template<typename _BI1, typename _BI2>
inline _BI2
__copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result)
{
! typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>
! ::has_trivial_assignment_operator _Trivial;
! return
! std::__copy_backward_dispatch<_BI1, _BI2, _Trivial>::copy(__first,
! __last,
! __result);
}
template <typename _BI1, typename _BI2>
--- 358,416 ----
typedef typename _Is_normal_iterator<_InputIterator>::_Normal __Normal;
return std::__copy_ni1(__first, __last, __result, __Normal());
}
!
! template<bool, typename>
! struct __copy_backward
! {
! template<typename _BI1, typename _BI2>
! static _BI2
! copy_b(_BI1 __first, _BI1 __last, _BI2 __result)
! {
! while (__first != __last)
! *--__result = *--__last;
! return __result;
! }
};
! template<bool _BoolType>
! struct __copy_backward<_BoolType, random_access_iterator_tag>
{
! template<typename _BI1, typename _BI2>
! static _BI2
! copy_b(_BI1 __first, _BI1 __last, _BI2 __result)
! {
! typename iterator_traits<_BI1>::difference_type __n;
! for (__n = __last - __first; __n > 0; --__n)
! *--__result = *--__last;
! return __result;
! }
};
! template<>
! struct __copy_backward<true, random_access_iterator_tag>
{
! template<typename _Tp>
! static _Tp*
! copy_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
! {
! const ptrdiff_t _Num = __last - __first;
! std::memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
! return __result - _Num;
! }
};
template<typename _BI1, typename _BI2>
inline _BI2
__copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result)
{
! typedef typename iterator_traits<_BI2>::value_type _ValueType;
! typedef typename iterator_traits<_BI1>::iterator_category _Category;
! const bool __simple = (__is_trivially_copyable<_ValueType>::_M_type
! && __is_pointer<_BI1>::_M_type
! && __is_pointer<_BI2>::_M_type);
!
! return __copy_backward<__simple, _Category>::copy_b(__first, __last,
! __result);
}
template <typename _BI1, typename _BI2>
*************** namespace std
*** 499,505 ****
__result, __Normal());
}
! template<typename>
struct __fill
{
template<typename _ForwardIterator, typename _Tp>
--- 480,486 ----
__result, __Normal());
}
! template<bool>
struct __fill
{
template<typename _ForwardIterator, typename _Tp>
*************** namespace std
*** 513,519 ****
};
template<>
! struct __fill<__true_type>
{
template<typename _ForwardIterator, typename _Tp>
static void
--- 494,500 ----
};
template<>
! struct __fill<true>
{
template<typename _ForwardIterator, typename _Tp>
static void
*************** namespace std
*** 546,554 ****
_ForwardIterator>)
__glibcxx_requires_valid_range(__first, __last);
! typedef typename __type_traits<_Tp>::has_trivial_copy_constructor
! _Trivial;
! std::__fill<_Trivial>::fill(__first, __last, __value);
}
// Specialization: for one-byte types we can use memset.
--- 527,534 ----
_ForwardIterator>)
__glibcxx_requires_valid_range(__first, __last);
! const bool __trivial = __is_trivially_copyable<_Tp>::_M_type;
! std::__fill<__trivial>::fill(__first, __last, __value);
}
// Specialization: for one-byte types we can use memset.
*************** namespace std
*** 576,582 ****
std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
}
! template<typename>
struct __fill_n
{
template<typename _OutputIterator, typename _Size, typename _Tp>
--- 556,562 ----
std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
}
! template<bool>
struct __fill_n
{
template<typename _OutputIterator, typename _Size, typename _Tp>
*************** namespace std
*** 590,596 ****
};
template<>
! struct __fill_n<__true_type>
{
template<typename _OutputIterator, typename _Size, typename _Tp>
static _OutputIterator
--- 570,576 ----
};
template<>
! struct __fill_n<true>
{
template<typename _OutputIterator, typename _Size, typename _Tp>
static _OutputIterator
*************** namespace std
*** 621,629 ****
// concept requirements
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _Tp>)
! typedef typename __type_traits<_Tp>::has_trivial_copy_constructor
! _Trivial;
! return std::__fill_n<_Trivial>::fill_n(__first, __n, __value);
}
template<typename _Size>
--- 601,608 ----
// concept requirements
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _Tp>)
! const bool __trivial = __is_trivially_copyable<_Tp>::_M_type;
! return std::__fill_n<__trivial>::fill_n(__first, __n, __value);
}
template<typename _Size>
diff -prN libstdc++-v3-orig/testsuite/25_algorithms/copy/1.cc libstdc++-v3/testsuite/25_algorithms/copy/1.cc
*** libstdc++-v3-orig/testsuite/25_algorithms/copy/1.cc Thu Jan 1 01:00:00 1970
--- libstdc++-v3/testsuite/25_algorithms/copy/1.cc Wed Jun 30 00:41:37 2004
***************
*** 0 ****
--- 1,56 ----
+ // 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 Pred 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.2.1 [lib.alg.copy] Copy.
+
+ #include <algorithm>
+ #include <vector>
+ #include <testsuite_hooks.h>
+
+ void
+ test01()
+ {
+ using namespace std;
+ 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};
+ const int N = sizeof(A) / sizeof(int);
+
+ int s1[N];
+ copy(A, A + N, s1);
+ VERIFY( equal(s1, s1 + N, A) );
+
+ vector<int> v1(N);
+ copy(A, A + N, v1.begin());
+ VERIFY( equal(v1.begin(), v1.end(), A) );
+
+ int s2[N];
+ copy_backward(A, A + N, s2 + N);
+ VERIFY( equal(s2, s2 + N, A) );
+
+ vector<int> v2(N);
+ copy_backward(A, A + N, v2.end());
+ VERIFY( equal(v2.begin(), v2.end(), A) );
+ }
+
+ int
+ main()
+ {
+ test01();
+ return 0;
+ }
diff -prN libstdc++-v3-orig/testsuite/25_algorithms/copy/2.cc libstdc++-v3/testsuite/25_algorithms/copy/2.cc
*** libstdc++-v3-orig/testsuite/25_algorithms/copy/2.cc Thu Jan 1 01:00:00 1970
--- libstdc++-v3/testsuite/25_algorithms/copy/2.cc Wed Jun 30 00:42:17 2004
***************
*** 0 ****
--- 1,57 ----
+ // Copyright (C) 2004 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 Pred 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.2.1 [lib.alg.copy] Copy.
+
+ #include <algorithm>
+ #include <vector>
+ #include <testsuite_hooks.h>
+
+ void
+ test01()
+ {
+ using namespace std;
+ 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};
+ const int N = sizeof(A) / sizeof(int);
+ const vector<int> a(A, A + N);
+
+ int s1[N];
+ copy(a.begin(), a.end(), s1);
+ VERIFY( equal(s1, s1 + N, a.begin()) );
+
+ vector<int> v1(N);
+ copy(a.begin(), a.end(), v1.begin());
+ VERIFY( equal(v1.begin(), v1.end(), a.begin()) );
+
+ int s2[N];
+ copy_backward(a.begin(), a.end(), s2 + N);
+ VERIFY( equal(s2, s2 + N, a.begin()) );
+
+ vector<int> v2(N);
+ copy_backward(a.begin(), a.end(), v2.end());
+ VERIFY( equal(v2.begin(), v2.end(), a.begin()) );
+ }
+
+ int
+ main()
+ {
+ test01();
+ return 0;
+ }
diff -prN libstdc++-v3-orig/testsuite/25_algorithms/copy/3.cc libstdc++-v3/testsuite/25_algorithms/copy/3.cc
*** libstdc++-v3-orig/testsuite/25_algorithms/copy/3.cc Thu Jan 1 01:00:00 1970
--- libstdc++-v3/testsuite/25_algorithms/copy/3.cc Wed Jun 30 00:42:59 2004
***************
*** 0 ****
--- 1,58 ----
+ // Copyright (C) 2004 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 Pred 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.2.1 [lib.alg.copy] Copy.
+
+ #include <algorithm>
+ #include <vector>
+ #include <deque>
+ #include <testsuite_hooks.h>
+
+ void
+ test01()
+ {
+ using namespace std;
+ 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};
+ const int N = sizeof(A) / sizeof(int);
+ const deque<int> a(A, A + N);
+
+ int s1[N];
+ copy(a.begin(), a.end(), s1);
+ VERIFY( equal(s1, s1 + N, a.begin()) );
+
+ vector<int> v1(N);
+ copy(a.begin(), a.end(), v1.begin());
+ VERIFY( equal(v1.begin(), v1.end(), a.begin()) );
+
+ int s2[N];
+ copy_backward(a.begin(), a.end(), s2 + N);
+ VERIFY( equal(s2, s2 + N, a.begin()) );
+
+ vector<int> v2(N);
+ copy_backward(a.begin(), a.end(), v2.end());
+ VERIFY( equal(v2.begin(), v2.end(), a.begin()) );
+ }
+
+ int
+ main()
+ {
+ test01();
+ return 0;
+ }
diff -prN libstdc++-v3-orig/testsuite/25_algorithms/copy/4.cc libstdc++-v3/testsuite/25_algorithms/copy/4.cc
*** libstdc++-v3-orig/testsuite/25_algorithms/copy/4.cc Thu Jan 1 01:00:00 1970
--- libstdc++-v3/testsuite/25_algorithms/copy/4.cc Wed Jun 30 00:43:42 2004
***************
*** 0 ****
--- 1,58 ----
+ // Copyright (C) 2004 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 Pred 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.2.1 [lib.alg.copy] Copy.
+
+ #include <algorithm>
+ #include <vector>
+ #include <list>
+ #include <testsuite_hooks.h>
+
+ void
+ test01()
+ {
+ using namespace std;
+ 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};
+ const int N = sizeof(A) / sizeof(int);
+ const list<int> a(A, A + N);
+
+ int s1[N];
+ copy(a.begin(), a.end(), s1);
+ VERIFY( equal(s1, s1 + N, a.begin()) );
+
+ vector<int> v1(N);
+ copy(a.begin(), a.end(), v1.begin());
+ VERIFY( equal(v1.begin(), v1.end(), a.begin()) );
+
+ int s2[N];
+ copy_backward(a.begin(), a.end(), s2 + N);
+ VERIFY( equal(s2, s2 + N, a.begin()) );
+
+ vector<int> v2(N);
+ copy_backward(a.begin(), a.end(), v2.end());
+ VERIFY( equal(v2.begin(), v2.end(), a.begin()) );
+ }
+
+ int
+ main()
+ {
+ test01();
+ return 0;
+ }
diff -prN libstdc++-v3-orig/testsuite/25_algorithms/copy.cc libstdc++-v3/testsuite/25_algorithms/copy.cc
*** libstdc++-v3-orig/testsuite/25_algorithms/copy.cc Tue Sep 23 22:02:52 2003
--- libstdc++-v3/testsuite/25_algorithms/copy.cc Thu Jan 1 01:00:00 1970
***************
*** 1,58 ****
- // 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 Pred 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.2.12 [lib.alg.partitions] Partitions.
-
- #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};
- const int N = sizeof(A) / sizeof(int);
-
- // copy
- void
- test01()
- {
- using std::copy;
-
- int s1[N];
- copy(A, A + N, s1);
- VERIFY(std::equal(s1, s1 + N, A));
- }
-
- // copy_backward
- void
- test02()
- {
- using std::copy_backward;
-
- int s1[N];
- copy_backward(A, A + N, s1 + N);
- VERIFY(std::equal(s1, s1 + N, A));
- }
-
- int
- main()
- {
- test01();
- test02();
-
- return 0;
- }
--- 0 ----