3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file parallel/algobase.h
26 * @brief Parallel STL function calls corresponding to the
27 * stl_algobase.h header. The functions defined here mainly do case
28 * switches and call the actual parallelized versions in other files.
29 * Inlining policy: Functions that basically only contain one
30 * function call, are declared inline.
31 * This file is a GNU parallel extension to the Standard C++ Library.
34 // Written by Johannes Singler and Felix Putze.
36 #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H
37 #define _GLIBCXX_PARALLEL_ALGOBASE_H 1
39 #include <bits/stl_algobase.h>
40 #include <parallel/base.h>
41 #include <parallel/tags.h>
42 #include <parallel/settings.h>
43 #include <parallel/find.h>
44 #include <parallel/find_selectors.h>
50 // NB: equal and lexicographical_compare require mismatch.
52 // Sequential fallback
53 template<typename _IIter1, typename _IIter2>
54 inline pair<_IIter1, _IIter2>
55 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
56 __gnu_parallel::sequential_tag)
57 { return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2); }
59 // Sequential fallback
60 template<typename _IIter1, typename _IIter2, typename _Predicate>
61 inline pair<_IIter1, _IIter2>
62 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
63 _Predicate __pred, __gnu_parallel::sequential_tag)
64 { return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2, __pred); }
66 // Sequential fallback for input iterator case
67 template<typename _IIter1, typename _IIter2,
68 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
69 inline pair<_IIter1, _IIter2>
70 __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
71 _Predicate __pred, _IteratorTag1, _IteratorTag2)
72 { return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2, __pred); }
74 // Parallel mismatch for random access iterators
75 template<typename _RAIter1, typename _RAIter2, typename _Predicate>
76 pair<_RAIter1, _RAIter2>
77 __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1,
78 _RAIter2 __begin2, _Predicate __pred,
79 random_access_iterator_tag, random_access_iterator_tag)
81 if (_GLIBCXX_PARALLEL_CONDITION(true))
84 __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
86 __mismatch_selector()).first;
87 return make_pair(__res , __begin2 + (__res - __begin1));
90 return _GLIBCXX_STD_P::mismatch(__begin1, __end1, __begin2, __pred);
94 template<typename _IIter1, typename _IIter2>
95 inline pair<_IIter1, _IIter2>
96 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
98 typedef std::iterator_traits<_IIter1> _Iterator1Traits;
99 typedef std::iterator_traits<_IIter2> _Iterator2Traits;
100 typedef typename _Iterator1Traits::value_type _ValueType1;
101 typedef typename _Iterator2Traits::value_type _ValueType2;
102 typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
103 typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
105 typedef __gnu_parallel::_EqualTo<_ValueType1, _ValueType2> _EqualTo;
107 return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(),
108 _IteratorCategory1(), _IteratorCategory2());
112 template<typename _IIter1, typename _IIter2, typename _Predicate>
113 inline pair<_IIter1, _IIter2>
114 mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
117 typedef std::iterator_traits<_IIter1> _Iterator1Traits;
118 typedef std::iterator_traits<_IIter2> _Iterator2Traits;
119 typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
120 typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
122 return __mismatch_switch(__begin1, __end1, __begin2, __pred,
123 _IteratorCategory1(), _IteratorCategory2());
126 // Sequential fallback
127 template<typename _IIter1, typename _IIter2>
129 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
130 __gnu_parallel::sequential_tag)
131 { return _GLIBCXX_STD_P::equal(__begin1, __end1, __begin2); }
133 // Sequential fallback
134 template<typename _IIter1, typename _IIter2, typename _Predicate>
136 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
137 _Predicate __pred, __gnu_parallel::sequential_tag)
138 { return _GLIBCXX_STD_P::equal(__begin1, __end1, __begin2, __pred); }
141 template<typename _IIter1, typename _IIter2>
143 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
144 { return mismatch(__begin1, __end1, __begin2).first == __end1; }
147 template<typename _IIter1, typename _IIter2, typename _Predicate>
149 equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
151 { return mismatch(__begin1, __end1, __begin2, __pred).first == __end1; }
153 // Sequential fallback
154 template<typename _IIter1, typename _IIter2>
156 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
157 _IIter2 __begin2, _IIter2 __end2,
158 __gnu_parallel::sequential_tag)
159 { return _GLIBCXX_STD_P::lexicographical_compare(__begin1, __end1,
162 // Sequential fallback
163 template<typename _IIter1, typename _IIter2, typename _Predicate>
165 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
166 _IIter2 __begin2, _IIter2 __end2,
167 _Predicate __pred, __gnu_parallel::sequential_tag)
168 { return _GLIBCXX_STD_P::lexicographical_compare(
169 __begin1, __end1, __begin2, __end2, __pred); }
171 // Sequential fallback for input iterator case
172 template<typename _IIter1, typename _IIter2,
173 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
175 __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
176 _IIter2 __begin2, _IIter2 __end2,
178 _IteratorTag1, _IteratorTag2)
179 { return _GLIBCXX_STD_P::lexicographical_compare(
180 __begin1, __end1, __begin2, __end2, __pred); }
182 // Parallel lexicographical_compare for random access iterators
183 // Limitation: Both valuetypes must be the same
184 template<typename _RAIter1, typename _RAIter2, typename _Predicate>
186 __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1,
187 _RAIter2 __begin2, _RAIter2 __end2,
189 random_access_iterator_tag,
190 random_access_iterator_tag)
192 if (_GLIBCXX_PARALLEL_CONDITION(true))
194 typedef iterator_traits<_RAIter1> _TraitsType1;
195 typedef typename _TraitsType1::value_type _ValueType1;
197 typedef iterator_traits<_RAIter2> _TraitsType2;
198 typedef typename _TraitsType2::value_type _ValueType2;
200 typedef __gnu_parallel::
201 _EqualFromLess<_ValueType1, _ValueType2, _Predicate>
202 _EqualFromLessCompare;
204 // Longer sequence in first place.
205 if ((__end1 - __begin1) < (__end2 - __begin2))
207 typedef pair<_RAIter1, _RAIter2> _SpotType;
208 _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2,
209 _EqualFromLessCompare(__pred),
210 random_access_iterator_tag(),
211 random_access_iterator_tag());
213 return (__mm.first == __end1)
214 || bool(__pred(*__mm.first, *__mm.second));
218 typedef pair<_RAIter2, _RAIter1> _SpotType;
219 _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1,
220 _EqualFromLessCompare(__pred),
221 random_access_iterator_tag(),
222 random_access_iterator_tag());
224 return (__mm.first != __end2)
225 && bool(__pred(*__mm.second, *__mm.first));
229 return _GLIBCXX_STD_P::lexicographical_compare(
230 __begin1, __end1, __begin2, __end2, __pred);
234 template<typename _IIter1, typename _IIter2>
236 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
237 _IIter2 __begin2, _IIter2 __end2)
239 typedef iterator_traits<_IIter1> _TraitsType1;
240 typedef typename _TraitsType1::value_type _ValueType1;
241 typedef typename _TraitsType1::iterator_category _IteratorCategory1;
243 typedef iterator_traits<_IIter2> _TraitsType2;
244 typedef typename _TraitsType2::value_type _ValueType2;
245 typedef typename _TraitsType2::iterator_category _IteratorCategory2;
246 typedef __gnu_parallel::_Less<_ValueType1, _ValueType2> _LessType;
248 return __lexicographical_compare_switch(
249 __begin1, __end1, __begin2, __end2, _LessType(),
250 _IteratorCategory1(), _IteratorCategory2());
254 template<typename _IIter1, typename _IIter2, typename _Predicate>
256 lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
257 _IIter2 __begin2, _IIter2 __end2,
260 typedef iterator_traits<_IIter1> _TraitsType1;
261 typedef typename _TraitsType1::iterator_category _IteratorCategory1;
263 typedef iterator_traits<_IIter2> _TraitsType2;
264 typedef typename _TraitsType2::iterator_category _IteratorCategory2;
266 return __lexicographical_compare_switch(
267 __begin1, __end1, __begin2, __end2, __pred,
268 _IteratorCategory1(), _IteratorCategory2());
273 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */