3 // Copyright (C) 2007, 2008 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 2, 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 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 /** @file parallel/algobase.h
32 * @brief Parallel STL function calls corresponding to the
33 * stl_algobase.h header. The functions defined here mainly do case
34 * switches and call the actual parallelized versions in other files.
35 * Inlining policy: Functions that basically only contain one
36 * function call, are declared inline.
37 * This file is a GNU parallel extension to the Standard C++ Library.
40 // Written by Johannes Singler and Felix Putze.
42 #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H
43 #define _GLIBCXX_PARALLEL_ALGOBASE_H 1
45 #include <bits/stl_algobase.h>
46 #include <parallel/base.h>
47 #include <parallel/tags.h>
48 #include <parallel/settings.h>
49 #include <parallel/find.h>
50 #include <parallel/find_selectors.h>
56 // NB: equal and lexicographical_compare require mismatch.
58 // Sequential fallback
59 template<typename InputIterator1
, typename InputIterator2
>
60 inline pair
<InputIterator1
, InputIterator2
>
61 mismatch(InputIterator1 begin1
, InputIterator1 end1
, InputIterator2 begin2
,
62 __gnu_parallel::sequential_tag
)
63 { return _GLIBCXX_STD_P::mismatch(begin1
, end1
, begin2
); }
65 // Sequential fallback
66 template<typename InputIterator1
, typename InputIterator2
,
68 inline pair
<InputIterator1
, InputIterator2
>
69 mismatch(InputIterator1 begin1
, InputIterator1 end1
, InputIterator2 begin2
,
70 Predicate pred
, __gnu_parallel::sequential_tag
)
71 { return _GLIBCXX_STD_P::mismatch(begin1
, end1
, begin2
, pred
); }
73 // Sequential fallback for input iterator case
74 template<typename InputIterator1
, typename InputIterator2
,
75 typename Predicate
, typename IteratorTag1
, typename IteratorTag2
>
76 inline pair
<InputIterator1
, InputIterator2
>
77 mismatch_switch(InputIterator1 begin1
, InputIterator1 end1
,
78 InputIterator2 begin2
, Predicate pred
, IteratorTag1
,
80 { return _GLIBCXX_STD_P::mismatch(begin1
, end1
, begin2
, pred
); }
82 // Parallel mismatch for random access iterators
83 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
85 pair
<RandomAccessIterator1
, RandomAccessIterator2
>
86 mismatch_switch(RandomAccessIterator1 begin1
, RandomAccessIterator1 end1
,
87 RandomAccessIterator2 begin2
, Predicate pred
,
88 random_access_iterator_tag
, random_access_iterator_tag
)
90 if (_GLIBCXX_PARALLEL_CONDITION(true))
92 RandomAccessIterator1 res
=
93 __gnu_parallel::find_template(begin1
, end1
, begin2
, pred
,
95 mismatch_selector()).first
;
96 return make_pair(res
, begin2
+ (res
- begin1
));
99 return _GLIBCXX_STD_P::mismatch(begin1
, end1
, begin2
, pred
);
103 template<typename InputIterator1
, typename InputIterator2
>
104 inline pair
<InputIterator1
, InputIterator2
>
105 mismatch(InputIterator1 begin1
, InputIterator1 end1
, InputIterator2 begin2
)
107 typedef std::iterator_traits
<InputIterator1
> iterator1_traits
;
108 typedef std::iterator_traits
<InputIterator2
> iterator2_traits
;
109 typedef typename
iterator1_traits::value_type value1_type
;
110 typedef typename
iterator2_traits::value_type value2_type
;
111 typedef typename
iterator1_traits::iterator_category iterator1_category
;
112 typedef typename
iterator2_traits::iterator_category iterator2_category
;
114 typedef __gnu_parallel::equal_to
<value1_type
, value2_type
> equal_to_type
;
116 return mismatch_switch(begin1
, end1
, begin2
, equal_to_type(),
117 iterator1_category(), iterator2_category());
121 template<typename InputIterator1
, typename InputIterator2
,
123 inline pair
<InputIterator1
, InputIterator2
>
124 mismatch(InputIterator1 begin1
, InputIterator1 end1
, InputIterator2 begin2
,
127 typedef std::iterator_traits
<InputIterator1
> iterator1_traits
;
128 typedef std::iterator_traits
<InputIterator2
> iterator2_traits
;
129 typedef typename
iterator1_traits::iterator_category iterator1_category
;
130 typedef typename
iterator2_traits::iterator_category iterator2_category
;
132 return mismatch_switch(begin1
, end1
, begin2
, pred
, iterator1_category(),
133 iterator2_category());
136 // Sequential fallback
137 template<typename InputIterator1
, typename InputIterator2
>
139 equal(InputIterator1 begin1
, InputIterator1 end1
, InputIterator2 begin2
,
140 __gnu_parallel::sequential_tag
)
141 { return _GLIBCXX_STD_P::equal(begin1
, end1
, begin2
); }
143 // Sequential fallback
144 template<typename InputIterator1
, typename InputIterator2
,
147 equal(InputIterator1 begin1
, InputIterator1 end1
, InputIterator2 begin2
,
148 Predicate pred
, __gnu_parallel::sequential_tag
)
149 { return _GLIBCXX_STD_P::equal(begin1
, end1
, begin2
, pred
); }
152 template<typename InputIterator1
, typename InputIterator2
>
154 equal(InputIterator1 begin1
, InputIterator1 end1
, InputIterator2 begin2
)
155 { return mismatch(begin1
, end1
, begin2
).first
== end1
; }
158 template<typename InputIterator1
, typename InputIterator2
,
161 equal(InputIterator1 begin1
, InputIterator1 end1
, InputIterator2 begin2
,
163 { return mismatch(begin1
, end1
, begin2
, pred
).first
== end1
; }
165 // Sequential fallback
166 template<typename InputIterator1
, typename InputIterator2
>
168 lexicographical_compare(InputIterator1 begin1
, InputIterator1 end1
,
169 InputIterator2 begin2
, InputIterator2 end2
,
170 __gnu_parallel::sequential_tag
)
171 { return _GLIBCXX_STD_P::lexicographical_compare(begin1
, end1
,
174 // Sequential fallback
175 template<typename InputIterator1
, typename InputIterator2
,
178 lexicographical_compare(InputIterator1 begin1
, InputIterator1 end1
,
179 InputIterator2 begin2
, InputIterator2 end2
,
180 Predicate pred
, __gnu_parallel::sequential_tag
)
181 { return _GLIBCXX_STD_P::lexicographical_compare(begin1
, end1
,
182 begin2
, end2
, pred
); }
184 // Sequential fallback for input iterator case
185 template<typename InputIterator1
, typename InputIterator2
,
186 typename Predicate
, typename IteratorTag1
, typename IteratorTag2
>
188 lexicographical_compare_switch(InputIterator1 begin1
, InputIterator1 end1
,
189 InputIterator2 begin2
, InputIterator2 end2
,
190 Predicate pred
, IteratorTag1
, IteratorTag2
)
191 { return _GLIBCXX_STD_P::lexicographical_compare(begin1
, end1
,
192 begin2
, end2
, pred
); }
194 // Parallel lexicographical_compare for random access iterators
195 // Limitation: Both valuetypes must be the same
196 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
199 lexicographical_compare_switch(RandomAccessIterator1 begin1
,
200 RandomAccessIterator1 end1
,
201 RandomAccessIterator2 begin2
,
202 RandomAccessIterator2 end2
, Predicate pred
,
203 random_access_iterator_tag
,
204 random_access_iterator_tag
)
206 if (_GLIBCXX_PARALLEL_CONDITION(true))
208 typedef iterator_traits
<RandomAccessIterator1
> traits1_type
;
209 typedef typename
traits1_type::value_type value1_type
;
211 typedef iterator_traits
<RandomAccessIterator2
> traits2_type
;
212 typedef typename
traits2_type::value_type value2_type
;
214 typedef __gnu_parallel::equal_from_less
<Predicate
, value1_type
,
215 value2_type
> equal_type
;
217 // Longer sequence in first place.
218 if ((end1
- begin1
) < (end2
- begin2
))
220 typedef pair
<RandomAccessIterator1
, RandomAccessIterator2
>
222 pair_type mm
= mismatch_switch(begin1
, end1
, begin2
,
224 random_access_iterator_tag(),
225 random_access_iterator_tag());
227 return (mm
.first
== end1
) || bool(pred(*mm
.first
, *mm
.second
));
231 typedef pair
<RandomAccessIterator2
, RandomAccessIterator1
>
233 pair_type mm
= mismatch_switch(begin2
, end2
, begin1
,
235 random_access_iterator_tag(),
236 random_access_iterator_tag());
238 return (mm
.first
!= end2
) && bool(pred(*mm
.second
, *mm
.first
));
242 return _GLIBCXX_STD_P::lexicographical_compare(begin1
, end1
,
247 template<typename InputIterator1
, typename InputIterator2
>
249 lexicographical_compare(InputIterator1 begin1
, InputIterator1 end1
,
250 InputIterator2 begin2
, InputIterator2 end2
)
252 typedef iterator_traits
<InputIterator1
> traits1_type
;
253 typedef typename
traits1_type::value_type value1_type
;
254 typedef typename
traits1_type::iterator_category iterator1_category
;
256 typedef iterator_traits
<InputIterator2
> traits2_type
;
257 typedef typename
traits2_type::value_type value2_type
;
258 typedef typename
traits2_type::iterator_category iterator2_category
;
259 typedef __gnu_parallel::less
<value1_type
, value2_type
> less_type
;
261 return lexicographical_compare_switch(begin1
, end1
, begin2
, end2
,
262 less_type(), iterator1_category(),
263 iterator2_category());
267 template<typename InputIterator1
, typename InputIterator2
,
270 lexicographical_compare(InputIterator1 begin1
, InputIterator1 end1
,
271 InputIterator2 begin2
, InputIterator2 end2
,
274 typedef iterator_traits
<InputIterator1
> traits1_type
;
275 typedef typename
traits1_type::iterator_category iterator1_category
;
277 typedef iterator_traits
<InputIterator2
> traits2_type
;
278 typedef typename
traits2_type::iterator_category iterator2_category
;
280 return lexicographical_compare_switch(begin1
, end1
, begin2
, end2
, pred
,
281 iterator1_category(),
282 iterator2_category());
287 #endif /* _GLIBCXX_ALGOBASE_H */