]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
748086b7 | 3 | // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. |
c2ba9709 JS |
4 | // |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
c2ba9709 JS |
9 | // version. |
10 | ||
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. | |
15 | ||
748086b7 JJ |
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. | |
c2ba9709 | 19 | |
748086b7 JJ |
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/>. | |
c2ba9709 JS |
24 | |
25 | /** | |
26 | * @file parallel/set_operations.h | |
27 | * @brief Parallel implementations of set operations for random-access | |
28 | * iterators. | |
29 | * This file is a GNU parallel extension to the Standard C++ Library. | |
30 | */ | |
31 | ||
32 | // Written by Marius Elvert and Felix Bondarenko. | |
33 | ||
34 | #ifndef _GLIBCXX_PARALLEL_SET_OPERATIONS_H | |
35 | #define _GLIBCXX_PARALLEL_SET_OPERATIONS_H 1 | |
36 | ||
37 | #include <omp.h> | |
38 | ||
39 | #include <parallel/settings.h> | |
40 | #include <parallel/multiseq_selection.h> | |
41 | ||
42 | namespace __gnu_parallel | |
43 | { | |
e683ee2a | 44 | template<typename InputIterator, typename OutputIterator> |
5817ff8e | 45 | OutputIterator |
c2ba9709 | 46 | copy_tail(std::pair<InputIterator, InputIterator> b, |
e683ee2a | 47 | std::pair<InputIterator, InputIterator> e, OutputIterator r) |
c2ba9709 JS |
48 | { |
49 | if (b.first != e.first) | |
50 | { | |
e683ee2a JS |
51 | do |
52 | { | |
53 | *r++ = *b.first++; | |
54 | } | |
55 | while (b.first != e.first); | |
c2ba9709 JS |
56 | } |
57 | else | |
58 | { | |
e683ee2a JS |
59 | while (b.second != e.second) |
60 | *r++ = *b.second++; | |
c2ba9709 JS |
61 | } |
62 | return r; | |
63 | } | |
64 | ||
5817ff8e PC |
65 | template<typename InputIterator, |
66 | typename OutputIterator, | |
67 | typename Comparator> | |
c2ba9709 JS |
68 | struct symmetric_difference_func |
69 | { | |
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; | |
73 | ||
74 | symmetric_difference_func(Comparator c) : comp(c) {} | |
75 | ||
76 | Comparator comp; | |
77 | ||
5817ff8e PC |
78 | OutputIterator |
79 | invoke(InputIterator a, InputIterator b, | |
80 | InputIterator c, InputIterator d, | |
81 | OutputIterator r) const | |
c2ba9709 JS |
82 | { |
83 | while (a != b && c != d) | |
e683ee2a JS |
84 | { |
85 | if (comp(*a, *c)) | |
86 | { | |
87 | *r = *a; | |
88 | ++a; | |
89 | ++r; | |
90 | } | |
91 | else if (comp(*c, *a)) | |
92 | { | |
93 | *r = *c; | |
94 | ++c; | |
95 | ++r; | |
96 | } | |
97 | else | |
98 | { | |
99 | ++a; | |
100 | ++c; | |
101 | } | |
102 | } | |
c2ba9709 JS |
103 | return std::copy(c, d, std::copy(a, b, r)); |
104 | } | |
105 | ||
5817ff8e PC |
106 | difference_type |
107 | count(InputIterator a, InputIterator b, | |
108 | InputIterator c, InputIterator d) const | |
c2ba9709 JS |
109 | { |
110 | difference_type counter = 0; | |
111 | ||
112 | while (a != b && c != d) | |
e683ee2a JS |
113 | { |
114 | if (comp(*a, *c)) | |
115 | { | |
116 | ++a; | |
117 | ++counter; | |
118 | } | |
119 | else if (comp(*c, *a)) | |
120 | { | |
121 | ++c; | |
122 | ++counter; | |
123 | } | |
124 | else | |
125 | { | |
126 | ++a; | |
127 | ++c; | |
128 | } | |
129 | } | |
c2ba9709 JS |
130 | |
131 | return counter + (b - a) + (d - c); | |
132 | } | |
133 | ||
5817ff8e | 134 | OutputIterator |
c2ba9709 JS |
135 | first_empty(InputIterator c, InputIterator d, OutputIterator out) const |
136 | { return std::copy(c, d, out); } | |
137 | ||
5817ff8e | 138 | OutputIterator |
c2ba9709 JS |
139 | second_empty(InputIterator a, InputIterator b, OutputIterator out) const |
140 | { return std::copy(a, b, out); } | |
c2ba9709 JS |
141 | }; |
142 | ||
143 | ||
5817ff8e PC |
144 | template<typename InputIterator, |
145 | typename OutputIterator, | |
146 | typename Comparator> | |
c2ba9709 JS |
147 | struct difference_func |
148 | { | |
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; | |
152 | ||
153 | difference_func(Comparator c) : comp(c) {} | |
154 | ||
155 | Comparator comp; | |
156 | ||
5817ff8e | 157 | OutputIterator |
c2ba9709 | 158 | invoke(InputIterator a, InputIterator b, InputIterator c, InputIterator d, |
e683ee2a | 159 | OutputIterator r) const |
c2ba9709 JS |
160 | { |
161 | while (a != b && c != d) | |
e683ee2a JS |
162 | { |
163 | if (comp(*a, *c)) | |
164 | { | |
165 | *r = *a; | |
166 | ++a; | |
167 | ++r; | |
168 | } | |
169 | else if (comp(*c, *a)) | |
170 | { ++c; } | |
171 | else | |
172 | { | |
173 | ++a; | |
174 | ++c; | |
175 | } | |
176 | } | |
c2ba9709 JS |
177 | return std::copy(a, b, r); |
178 | } | |
179 | ||
5817ff8e PC |
180 | difference_type |
181 | count(InputIterator a, InputIterator b, | |
182 | InputIterator c, InputIterator d) const | |
c2ba9709 JS |
183 | { |
184 | difference_type counter = 0; | |
185 | ||
186 | while (a != b && c != d) | |
e683ee2a JS |
187 | { |
188 | if (comp(*a, *c)) | |
189 | { | |
190 | ++a; | |
191 | ++counter; | |
192 | } | |
193 | else if (comp(*c, *a)) | |
194 | { ++c; } | |
195 | else | |
196 | { ++a; ++c; } | |
197 | } | |
c2ba9709 JS |
198 | |
199 | return counter + (b - a); | |
200 | } | |
201 | ||
202 | inline OutputIterator | |
203 | first_empty(InputIterator c, InputIterator d, OutputIterator out) const | |
204 | { return out; } | |
205 | ||
206 | inline OutputIterator | |
207 | second_empty(InputIterator a, InputIterator b, OutputIterator out) const | |
208 | { return std::copy(a, b, out); } | |
209 | }; | |
210 | ||
211 | ||
5817ff8e PC |
212 | template<typename InputIterator, |
213 | typename OutputIterator, | |
214 | typename Comparator> | |
c2ba9709 JS |
215 | struct intersection_func |
216 | { | |
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; | |
220 | ||
221 | intersection_func(Comparator c) : comp(c) {} | |
222 | ||
223 | Comparator comp; | |
224 | ||
5817ff8e | 225 | OutputIterator |
c2ba9709 | 226 | invoke(InputIterator a, InputIterator b, InputIterator c, InputIterator d, |
e683ee2a | 227 | OutputIterator r) const |
c2ba9709 JS |
228 | { |
229 | while (a != b && c != d) | |
e683ee2a JS |
230 | { |
231 | if (comp(*a, *c)) | |
232 | { ++a; } | |
233 | else if (comp(*c, *a)) | |
234 | { ++c; } | |
235 | else | |
236 | { | |
237 | *r = *a; | |
238 | ++a; | |
239 | ++c; | |
240 | ++r; | |
241 | } | |
242 | } | |
c2ba9709 JS |
243 | |
244 | return r; | |
245 | } | |
246 | ||
5817ff8e PC |
247 | difference_type |
248 | count(InputIterator a, InputIterator b, | |
249 | InputIterator c, InputIterator d) const | |
c2ba9709 JS |
250 | { |
251 | difference_type counter = 0; | |
252 | ||
253 | while (a != b && c != d) | |
e683ee2a JS |
254 | { |
255 | if (comp(*a, *c)) | |
256 | { ++a; } | |
257 | else if (comp(*c, *a)) | |
258 | { ++c; } | |
259 | else | |
260 | { | |
261 | ++a; | |
262 | ++c; | |
263 | ++counter; | |
264 | } | |
265 | } | |
c2ba9709 JS |
266 | |
267 | return counter; | |
268 | } | |
269 | ||
270 | inline OutputIterator | |
271 | first_empty(InputIterator c, InputIterator d, OutputIterator out) const | |
272 | { return out; } | |
273 | ||
274 | inline OutputIterator | |
275 | second_empty(InputIterator a, InputIterator b, OutputIterator out) const | |
276 | { return out; } | |
277 | }; | |
278 | ||
e683ee2a | 279 | template<class InputIterator, class OutputIterator, class Comparator> |
c2ba9709 JS |
280 | struct union_func |
281 | { | |
e683ee2a | 282 | typedef typename std::iterator_traits<InputIterator>::difference_type |
5817ff8e | 283 | difference_type; |
c2ba9709 JS |
284 | |
285 | union_func(Comparator c) : comp(c) {} | |
286 | ||
287 | Comparator comp; | |
288 | ||
5817ff8e | 289 | OutputIterator |
c2ba9709 | 290 | invoke(InputIterator a, const InputIterator b, InputIterator c, |
e683ee2a | 291 | const InputIterator d, OutputIterator r) const |
c2ba9709 JS |
292 | { |
293 | while (a != b && c != d) | |
e683ee2a JS |
294 | { |
295 | if (comp(*a, *c)) | |
296 | { | |
297 | *r = *a; | |
298 | ++a; | |
299 | } | |
300 | else if (comp(*c, *a)) | |
301 | { | |
302 | *r = *c; | |
303 | ++c; | |
304 | } | |
305 | else | |
306 | { | |
307 | *r = *a; | |
308 | ++a; | |
309 | ++c; | |
310 | } | |
311 | ++r; | |
312 | } | |
c2ba9709 JS |
313 | return std::copy(c, d, std::copy(a, b, r)); |
314 | } | |
315 | ||
5817ff8e PC |
316 | difference_type |
317 | count(InputIterator a, InputIterator b, | |
318 | InputIterator c, InputIterator d) const | |
c2ba9709 JS |
319 | { |
320 | difference_type counter = 0; | |
321 | ||
322 | while (a != b && c != d) | |
e683ee2a JS |
323 | { |
324 | if (comp(*a, *c)) | |
325 | { ++a; } | |
326 | else if (comp(*c, *a)) | |
327 | { ++c; } | |
328 | else | |
329 | { | |
330 | ++a; | |
331 | ++c; | |
332 | } | |
333 | ++counter; | |
334 | } | |
c2ba9709 JS |
335 | |
336 | counter += (b - a); | |
337 | counter += (d - c); | |
338 | return counter; | |
339 | } | |
340 | ||
341 | inline OutputIterator | |
342 | first_empty(InputIterator c, InputIterator d, OutputIterator out) const | |
343 | { return std::copy(c, d, out); } | |
344 | ||
345 | inline OutputIterator | |
346 | second_empty(InputIterator a, InputIterator b, OutputIterator out) const | |
347 | { return std::copy(a, b, out); } | |
348 | }; | |
349 | ||
5817ff8e PC |
350 | template<typename InputIterator, |
351 | typename OutputIterator, | |
352 | typename Operation> | |
c2ba9709 JS |
353 | OutputIterator |
354 | parallel_set_operation(InputIterator begin1, InputIterator end1, | |
e683ee2a JS |
355 | InputIterator begin2, InputIterator end2, |
356 | OutputIterator result, Operation op) | |
c2ba9709 JS |
357 | { |
358 | _GLIBCXX_CALL((end1 - begin1) + (end2 - begin2)) | |
359 | ||
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; | |
363 | ||
c2ba9709 JS |
364 | if (begin1 == end1) |
365 | return op.first_empty(begin2, end2, result); | |
366 | ||
367 | if (begin2 == end2) | |
368 | return op.second_empty(begin1, end1, result); | |
369 | ||
370 | const difference_type size = (end1 - begin1) + (end2 - begin2); | |
371 | ||
e683ee2a JS |
372 | const iterator_pair sequence[ 2 ] = |
373 | { std::make_pair(begin1, end1), std::make_pair(begin2, end2) } ; | |
c2ba9709 | 374 | OutputIterator return_value = result; |
e683ee2a JS |
375 | difference_type *borders; |
376 | iterator_pair *block_begins; | |
377 | difference_type* lengths; | |
c2ba9709 | 378 | |
e683ee2a JS |
379 | thread_index_t num_threads = |
380 | std::min<difference_type>(get_max_threads(), | |
381 | std::min(end1 - begin1, end2 - begin2)); | |
382 | ||
383 | # pragma omp parallel num_threads(num_threads) | |
384 | { | |
385 | # pragma omp single | |
386 | { | |
387 | num_threads = omp_get_num_threads(); | |
388 | ||
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]; | |
392 | // Very start. | |
393 | block_begins[0] = std::make_pair(begin1, begin2); | |
394 | lengths = new difference_type[num_threads]; | |
395 | } //single | |
396 | ||
397 | thread_index_t iam = omp_get_thread_num(); | |
398 | ||
399 | // Result from multiseq_partition. | |
400 | InputIterator offset[2]; | |
401 | const difference_type rank = borders[iam + 1]; | |
402 | ||
403 | multiseq_partition(sequence, sequence + 2, rank, offset, op.comp); | |
404 | ||
405 | // allowed to read? | |
406 | // together | |
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))) | |
411 | { | |
412 | // Avoid split between globally equal elements: move one to | |
413 | // front in first sequence. | |
414 | --offset[ 0 ]; | |
415 | } | |
416 | ||
417 | iterator_pair block_end = block_begins[ iam + 1 ] = | |
418 | iterator_pair(offset[ 0 ], offset[ 1 ]); | |
419 | ||
420 | // Make sure all threads have their block_begin result written out. | |
421 | # pragma omp barrier | |
422 | ||
423 | iterator_pair block_begin = block_begins[ iam ]; | |
424 | ||
425 | // Begin working for the first block, while the others except | |
426 | // the last start to count. | |
427 | if (iam == 0) | |
428 | { | |
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, | |
432 | result) | |
433 | - result; | |
434 | } | |
435 | else | |
436 | { | |
437 | lengths[ iam ] = op.count(block_begin.first, block_end.first, | |
438 | block_begin.second, block_end.second); | |
439 | } | |
440 | ||
441 | // Make sure everyone wrote their lengths. | |
442 | # pragma omp barrier | |
443 | ||
444 | OutputIterator r = result; | |
445 | ||
446 | if (iam == 0) | |
447 | { | |
448 | // Do the last block. | |
449 | for (int i = 0; i < num_threads; ++i) | |
450 | r += lengths[i]; | |
451 | ||
452 | block_begin = block_begins[num_threads]; | |
453 | ||
454 | // Return the result iterator of the last block. | |
455 | return_value = op.invoke( | |
456 | block_begin.first, end1, block_begin.second, end2, r); | |
457 | ||
458 | } | |
459 | else | |
460 | { | |
461 | for (int i = 0; i < iam; ++i) | |
462 | r += lengths[ i ]; | |
463 | ||
464 | // Reset begins for copy pass. | |
465 | op.invoke(block_begin.first, block_end.first, | |
466 | block_begin.second, block_end.second, r); | |
467 | } | |
468 | } | |
c2ba9709 JS |
469 | return return_value; |
470 | } | |
471 | ||
472 | ||
5817ff8e PC |
473 | template<typename InputIterator, |
474 | typename OutputIterator, | |
475 | typename Comparator> | |
476 | inline OutputIterator | |
c2ba9709 | 477 | parallel_set_union(InputIterator begin1, InputIterator end1, |
e683ee2a JS |
478 | InputIterator begin2, InputIterator end2, |
479 | OutputIterator result, Comparator comp) | |
c2ba9709 JS |
480 | { |
481 | return parallel_set_operation(begin1, end1, begin2, end2, result, | |
e683ee2a | 482 | union_func< InputIterator, OutputIterator, Comparator>(comp)); |
c2ba9709 JS |
483 | } |
484 | ||
5817ff8e PC |
485 | template<typename InputIterator, |
486 | typename OutputIterator, | |
487 | typename Comparator> | |
488 | inline OutputIterator | |
c2ba9709 | 489 | parallel_set_intersection(InputIterator begin1, InputIterator end1, |
e683ee2a JS |
490 | InputIterator begin2, InputIterator end2, |
491 | OutputIterator result, Comparator comp) | |
c2ba9709 JS |
492 | { |
493 | return parallel_set_operation(begin1, end1, begin2, end2, result, | |
e683ee2a | 494 | intersection_func<InputIterator, OutputIterator, Comparator>(comp)); |
c2ba9709 JS |
495 | } |
496 | ||
5817ff8e PC |
497 | template<typename InputIterator, |
498 | typename OutputIterator, | |
499 | typename Comparator> | |
500 | inline OutputIterator | |
c2ba9709 | 501 | parallel_set_difference(InputIterator begin1, InputIterator end1, |
e683ee2a JS |
502 | InputIterator begin2, InputIterator end2, |
503 | OutputIterator result, Comparator comp) | |
c2ba9709 JS |
504 | { |
505 | return parallel_set_operation(begin1, end1, begin2, end2, result, | |
e683ee2a | 506 | difference_func<InputIterator, OutputIterator, Comparator>(comp)); |
c2ba9709 JS |
507 | } |
508 | ||
5817ff8e PC |
509 | template<typename InputIterator, |
510 | typename OutputIterator, | |
511 | typename Comparator> | |
512 | inline OutputIterator | |
e683ee2a JS |
513 | parallel_set_symmetric_difference(InputIterator begin1, InputIterator end1, |
514 | InputIterator begin2, InputIterator end2, | |
515 | OutputIterator result, Comparator comp) | |
c2ba9709 JS |
516 | { |
517 | return parallel_set_operation(begin1, end1, begin2, end2, result, | |
e683ee2a JS |
518 | symmetric_difference_func<InputIterator, OutputIterator, Comparator> |
519 | (comp)); | |
c2ba9709 JS |
520 | } |
521 | ||
522 | } | |
523 | ||
cbcd1e45 | 524 | #endif /* _GLIBCXX_PARALLEL_SET_OPERATIONS_H */ |