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/>.
26 * @file parallel/set_operations.h
27 * @brief Parallel implementations of set operations for random-access
29 * This file is a GNU parallel extension to the Standard C++ Library.
32 // Written by Marius Elvert and Felix Bondarenko.
34 #ifndef _GLIBCXX_PARALLEL_SET_OPERATIONS_H
35 #define _GLIBCXX_PARALLEL_SET_OPERATIONS_H 1
39 #include <parallel/settings.h>
40 #include <parallel/multiseq_selection.h>
42 namespace __gnu_parallel
44 template<typename InputIterator
, typename OutputIterator
>
46 copy_tail(std::pair
<InputIterator
, InputIterator
> b
,
47 std::pair
<InputIterator
, InputIterator
> e
, OutputIterator r
)
49 if (b
.first
!= e
.first
)
55 while (b
.first
!= e
.first
);
59 while (b
.second
!= e
.second
)
65 template<typename InputIterator
,
66 typename OutputIterator
,
68 struct symmetric_difference_func
70 typedef std::iterator_traits
<InputIterator
> traits_type
;
71 typedef typename
traits_type::difference_type difference_type
;
72 typedef typename
std::pair
<InputIterator
, InputIterator
> iterator_pair
;
74 symmetric_difference_func(Comparator c
) : comp(c
) {}
79 invoke(InputIterator a
, InputIterator b
,
80 InputIterator c
, InputIterator d
,
81 OutputIterator r
) const
83 while (a
!= b
&& c
!= d
)
91 else if (comp(*c
, *a
))
103 return std::copy(c
, d
, std::copy(a
, b
, r
));
107 count(InputIterator a
, InputIterator b
,
108 InputIterator c
, InputIterator d
) const
110 difference_type counter
= 0;
112 while (a
!= b
&& c
!= d
)
119 else if (comp(*c
, *a
))
131 return counter
+ (b
- a
) + (d
- c
);
135 first_empty(InputIterator c
, InputIterator d
, OutputIterator out
) const
136 { return std::copy(c
, d
, out
); }
139 second_empty(InputIterator a
, InputIterator b
, OutputIterator out
) const
140 { return std::copy(a
, b
, out
); }
144 template<typename InputIterator
,
145 typename OutputIterator
,
147 struct difference_func
149 typedef std::iterator_traits
<InputIterator
> traits_type
;
150 typedef typename
traits_type::difference_type difference_type
;
151 typedef typename
std::pair
<InputIterator
, InputIterator
> iterator_pair
;
153 difference_func(Comparator c
) : comp(c
) {}
158 invoke(InputIterator a
, InputIterator b
, InputIterator c
, InputIterator d
,
159 OutputIterator r
) const
161 while (a
!= b
&& c
!= d
)
169 else if (comp(*c
, *a
))
177 return std::copy(a
, b
, r
);
181 count(InputIterator a
, InputIterator b
,
182 InputIterator c
, InputIterator d
) const
184 difference_type counter
= 0;
186 while (a
!= b
&& c
!= d
)
193 else if (comp(*c
, *a
))
199 return counter
+ (b
- a
);
202 inline OutputIterator
203 first_empty(InputIterator c
, InputIterator d
, OutputIterator out
) const
206 inline OutputIterator
207 second_empty(InputIterator a
, InputIterator b
, OutputIterator out
) const
208 { return std::copy(a
, b
, out
); }
212 template<typename InputIterator
,
213 typename OutputIterator
,
215 struct intersection_func
217 typedef std::iterator_traits
<InputIterator
> traits_type
;
218 typedef typename
traits_type::difference_type difference_type
;
219 typedef typename
std::pair
<InputIterator
, InputIterator
> iterator_pair
;
221 intersection_func(Comparator c
) : comp(c
) {}
226 invoke(InputIterator a
, InputIterator b
, InputIterator c
, InputIterator d
,
227 OutputIterator r
) const
229 while (a
!= b
&& c
!= d
)
233 else if (comp(*c
, *a
))
248 count(InputIterator a
, InputIterator b
,
249 InputIterator c
, InputIterator d
) const
251 difference_type counter
= 0;
253 while (a
!= b
&& c
!= d
)
257 else if (comp(*c
, *a
))
270 inline OutputIterator
271 first_empty(InputIterator c
, InputIterator d
, OutputIterator out
) const
274 inline OutputIterator
275 second_empty(InputIterator a
, InputIterator b
, OutputIterator out
) const
279 template<class InputIterator
, class OutputIterator
, class Comparator
>
282 typedef typename
std::iterator_traits
<InputIterator
>::difference_type
285 union_func(Comparator c
) : comp(c
) {}
290 invoke(InputIterator a
, const InputIterator b
, InputIterator c
,
291 const InputIterator d
, OutputIterator r
) const
293 while (a
!= b
&& c
!= d
)
300 else if (comp(*c
, *a
))
313 return std::copy(c
, d
, std::copy(a
, b
, r
));
317 count(InputIterator a
, InputIterator b
,
318 InputIterator c
, InputIterator d
) const
320 difference_type counter
= 0;
322 while (a
!= b
&& c
!= d
)
326 else if (comp(*c
, *a
))
341 inline OutputIterator
342 first_empty(InputIterator c
, InputIterator d
, OutputIterator out
) const
343 { return std::copy(c
, d
, out
); }
345 inline OutputIterator
346 second_empty(InputIterator a
, InputIterator b
, OutputIterator out
) const
347 { return std::copy(a
, b
, out
); }
350 template<typename InputIterator
,
351 typename OutputIterator
,
354 parallel_set_operation(InputIterator begin1
, InputIterator end1
,
355 InputIterator begin2
, InputIterator end2
,
356 OutputIterator result
, Operation op
)
358 _GLIBCXX_CALL((end1
- begin1
) + (end2
- begin2
))
360 typedef std::iterator_traits
<InputIterator
> traits_type
;
361 typedef typename
traits_type::difference_type difference_type
;
362 typedef typename
std::pair
<InputIterator
, InputIterator
> iterator_pair
;
365 return op
.first_empty(begin2
, end2
, result
);
368 return op
.second_empty(begin1
, end1
, result
);
370 const difference_type size
= (end1
- begin1
) + (end2
- begin2
);
372 const iterator_pair sequence
[ 2 ] =
373 { std::make_pair(begin1
, end1
), std::make_pair(begin2
, end2
) } ;
374 OutputIterator return_value
= result
;
375 difference_type
*borders
;
376 iterator_pair
*block_begins
;
377 difference_type
* lengths
;
379 thread_index_t num_threads
=
380 std::min
<difference_type
>(get_max_threads(),
381 std::min(end1
- begin1
, end2
- begin2
));
383 # pragma omp parallel num_threads(num_threads)
387 num_threads
= omp_get_num_threads();
389 borders
= new difference_type
[num_threads
+ 2];
390 equally_split(size
, num_threads
+ 1, borders
);
391 block_begins
= new iterator_pair
[num_threads
+ 1];
393 block_begins
[0] = std::make_pair(begin1
, begin2
);
394 lengths
= new difference_type
[num_threads
];
397 thread_index_t iam
= omp_get_thread_num();
399 // Result from multiseq_partition.
400 InputIterator offset
[2];
401 const difference_type rank
= borders
[iam
+ 1];
403 multiseq_partition(sequence
, sequence
+ 2, rank
, offset
, op
.comp
);
407 // *(offset[ 0 ] - 1) == *offset[ 1 ]
408 if (offset
[ 0 ] != begin1
&& offset
[ 1 ] != end2
409 && !op
.comp(*(offset
[ 0 ] - 1), *offset
[ 1 ])
410 && !op
.comp(*offset
[ 1 ], *(offset
[ 0 ] - 1)))
412 // Avoid split between globally equal elements: move one to
413 // front in first sequence.
417 iterator_pair block_end
= block_begins
[ iam
+ 1 ] =
418 iterator_pair(offset
[ 0 ], offset
[ 1 ]);
420 // Make sure all threads have their block_begin result written out.
423 iterator_pair block_begin
= block_begins
[ iam
];
425 // Begin working for the first block, while the others except
426 // the last start to count.
429 // The first thread can copy already.
430 lengths
[ iam
] = op
.invoke(block_begin
.first
, block_end
.first
,
431 block_begin
.second
, block_end
.second
,
437 lengths
[ iam
] = op
.count(block_begin
.first
, block_end
.first
,
438 block_begin
.second
, block_end
.second
);
441 // Make sure everyone wrote their lengths.
444 OutputIterator r
= result
;
448 // Do the last block.
449 for (int i
= 0; i
< num_threads
; ++i
)
452 block_begin
= block_begins
[num_threads
];
454 // Return the result iterator of the last block.
455 return_value
= op
.invoke(
456 block_begin
.first
, end1
, block_begin
.second
, end2
, r
);
461 for (int i
= 0; i
< iam
; ++i
)
464 // Reset begins for copy pass.
465 op
.invoke(block_begin
.first
, block_end
.first
,
466 block_begin
.second
, block_end
.second
, r
);
473 template<typename InputIterator
,
474 typename OutputIterator
,
476 inline OutputIterator
477 parallel_set_union(InputIterator begin1
, InputIterator end1
,
478 InputIterator begin2
, InputIterator end2
,
479 OutputIterator result
, Comparator comp
)
481 return parallel_set_operation(begin1
, end1
, begin2
, end2
, result
,
482 union_func
< InputIterator
, OutputIterator
, Comparator
>(comp
));
485 template<typename InputIterator
,
486 typename OutputIterator
,
488 inline OutputIterator
489 parallel_set_intersection(InputIterator begin1
, InputIterator end1
,
490 InputIterator begin2
, InputIterator end2
,
491 OutputIterator result
, Comparator comp
)
493 return parallel_set_operation(begin1
, end1
, begin2
, end2
, result
,
494 intersection_func
<InputIterator
, OutputIterator
, Comparator
>(comp
));
497 template<typename InputIterator
,
498 typename OutputIterator
,
500 inline OutputIterator
501 parallel_set_difference(InputIterator begin1
, InputIterator end1
,
502 InputIterator begin2
, InputIterator end2
,
503 OutputIterator result
, Comparator comp
)
505 return parallel_set_operation(begin1
, end1
, begin2
, end2
, result
,
506 difference_func
<InputIterator
, OutputIterator
, Comparator
>(comp
));
509 template<typename InputIterator
,
510 typename OutputIterator
,
512 inline OutputIterator
513 parallel_set_symmetric_difference(InputIterator begin1
, InputIterator end1
,
514 InputIterator begin2
, InputIterator end2
,
515 OutputIterator result
, Comparator comp
)
517 return parallel_set_operation(begin1
, end1
, begin2
, end2
, result
,
518 symmetric_difference_func
<InputIterator
, OutputIterator
, Comparator
>
524 #endif /* _GLIBCXX_PARALLEL_SET_OPERATIONS_H */