00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 #ifndef _GLIBCXX_PARALLEL_SET_OPERATIONS_H
00035 #define _GLIBCXX_PARALLEL_SET_OPERATIONS_H 1
00036
00037 #include <omp.h>
00038
00039 #include <parallel/settings.h>
00040 #include <parallel/multiseq_selection.h>
00041
00042 namespace __gnu_parallel
00043 {
00044 template<typename InputIterator, typename OutputIterator>
00045 OutputIterator
00046 copy_tail(std::pair<InputIterator, InputIterator> b,
00047 std::pair<InputIterator, InputIterator> e, OutputIterator r)
00048 {
00049 if (b.first != e.first)
00050 {
00051 do
00052 {
00053 *r++ = *b.first++;
00054 }
00055 while (b.first != e.first);
00056 }
00057 else
00058 {
00059 while (b.second != e.second)
00060 *r++ = *b.second++;
00061 }
00062 return r;
00063 }
00064
00065 template<typename InputIterator,
00066 typename OutputIterator,
00067 typename Comparator>
00068 struct symmetric_difference_func
00069 {
00070 typedef std::iterator_traits<InputIterator> traits_type;
00071 typedef typename traits_type::difference_type difference_type;
00072 typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
00073
00074 symmetric_difference_func(Comparator c) : comp(c) {}
00075
00076 Comparator comp;
00077
00078 OutputIterator
00079 invoke(InputIterator a, InputIterator b,
00080 InputIterator c, InputIterator d,
00081 OutputIterator r) const
00082 {
00083 while (a != b && c != d)
00084 {
00085 if (comp(*a, *c))
00086 {
00087 *r = *a;
00088 ++a;
00089 ++r;
00090 }
00091 else if (comp(*c, *a))
00092 {
00093 *r = *c;
00094 ++c;
00095 ++r;
00096 }
00097 else
00098 {
00099 ++a;
00100 ++c;
00101 }
00102 }
00103 return std::copy(c, d, std::copy(a, b, r));
00104 }
00105
00106 difference_type
00107 count(InputIterator a, InputIterator b,
00108 InputIterator c, InputIterator d) const
00109 {
00110 difference_type counter = 0;
00111
00112 while (a != b && c != d)
00113 {
00114 if (comp(*a, *c))
00115 {
00116 ++a;
00117 ++counter;
00118 }
00119 else if (comp(*c, *a))
00120 {
00121 ++c;
00122 ++counter;
00123 }
00124 else
00125 {
00126 ++a;
00127 ++c;
00128 }
00129 }
00130
00131 return counter + (b - a) + (d - c);
00132 }
00133
00134 OutputIterator
00135 first_empty(InputIterator c, InputIterator d, OutputIterator out) const
00136 { return std::copy(c, d, out); }
00137
00138 OutputIterator
00139 second_empty(InputIterator a, InputIterator b, OutputIterator out) const
00140 { return std::copy(a, b, out); }
00141 };
00142
00143
00144 template<typename InputIterator,
00145 typename OutputIterator,
00146 typename Comparator>
00147 struct difference_func
00148 {
00149 typedef std::iterator_traits<InputIterator> traits_type;
00150 typedef typename traits_type::difference_type difference_type;
00151 typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
00152
00153 difference_func(Comparator c) : comp(c) {}
00154
00155 Comparator comp;
00156
00157 OutputIterator
00158 invoke(InputIterator a, InputIterator b, InputIterator c, InputIterator d,
00159 OutputIterator r) const
00160 {
00161 while (a != b && c != d)
00162 {
00163 if (comp(*a, *c))
00164 {
00165 *r = *a;
00166 ++a;
00167 ++r;
00168 }
00169 else if (comp(*c, *a))
00170 { ++c; }
00171 else
00172 {
00173 ++a;
00174 ++c;
00175 }
00176 }
00177 return std::copy(a, b, r);
00178 }
00179
00180 difference_type
00181 count(InputIterator a, InputIterator b,
00182 InputIterator c, InputIterator d) const
00183 {
00184 difference_type counter = 0;
00185
00186 while (a != b && c != d)
00187 {
00188 if (comp(*a, *c))
00189 {
00190 ++a;
00191 ++counter;
00192 }
00193 else if (comp(*c, *a))
00194 { ++c; }
00195 else
00196 { ++a; ++c; }
00197 }
00198
00199 return counter + (b - a);
00200 }
00201
00202 inline OutputIterator
00203 first_empty(InputIterator c, InputIterator d, OutputIterator out) const
00204 { return out; }
00205
00206 inline OutputIterator
00207 second_empty(InputIterator a, InputIterator b, OutputIterator out) const
00208 { return std::copy(a, b, out); }
00209 };
00210
00211
00212 template<typename InputIterator,
00213 typename OutputIterator,
00214 typename Comparator>
00215 struct intersection_func
00216 {
00217 typedef std::iterator_traits<InputIterator> traits_type;
00218 typedef typename traits_type::difference_type difference_type;
00219 typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
00220
00221 intersection_func(Comparator c) : comp(c) {}
00222
00223 Comparator comp;
00224
00225 OutputIterator
00226 invoke(InputIterator a, InputIterator b, InputIterator c, InputIterator d,
00227 OutputIterator r) const
00228 {
00229 while (a != b && c != d)
00230 {
00231 if (comp(*a, *c))
00232 { ++a; }
00233 else if (comp(*c, *a))
00234 { ++c; }
00235 else
00236 {
00237 *r = *a;
00238 ++a;
00239 ++c;
00240 ++r;
00241 }
00242 }
00243
00244 return r;
00245 }
00246
00247 difference_type
00248 count(InputIterator a, InputIterator b,
00249 InputIterator c, InputIterator d) const
00250 {
00251 difference_type counter = 0;
00252
00253 while (a != b && c != d)
00254 {
00255 if (comp(*a, *c))
00256 { ++a; }
00257 else if (comp(*c, *a))
00258 { ++c; }
00259 else
00260 {
00261 ++a;
00262 ++c;
00263 ++counter;
00264 }
00265 }
00266
00267 return counter;
00268 }
00269
00270 inline OutputIterator
00271 first_empty(InputIterator c, InputIterator d, OutputIterator out) const
00272 { return out; }
00273
00274 inline OutputIterator
00275 second_empty(InputIterator a, InputIterator b, OutputIterator out) const
00276 { return out; }
00277 };
00278
00279 template<class InputIterator, class OutputIterator, class Comparator>
00280 struct union_func
00281 {
00282 typedef typename std::iterator_traits<InputIterator>::difference_type
00283 difference_type;
00284
00285 union_func(Comparator c) : comp(c) {}
00286
00287 Comparator comp;
00288
00289 OutputIterator
00290 invoke(InputIterator a, const InputIterator b, InputIterator c,
00291 const InputIterator d, OutputIterator r) const
00292 {
00293 while (a != b && c != d)
00294 {
00295 if (comp(*a, *c))
00296 {
00297 *r = *a;
00298 ++a;
00299 }
00300 else if (comp(*c, *a))
00301 {
00302 *r = *c;
00303 ++c;
00304 }
00305 else
00306 {
00307 *r = *a;
00308 ++a;
00309 ++c;
00310 }
00311 ++r;
00312 }
00313 return std::copy(c, d, std::copy(a, b, r));
00314 }
00315
00316 difference_type
00317 count(InputIterator a, InputIterator b,
00318 InputIterator c, InputIterator d) const
00319 {
00320 difference_type counter = 0;
00321
00322 while (a != b && c != d)
00323 {
00324 if (comp(*a, *c))
00325 { ++a; }
00326 else if (comp(*c, *a))
00327 { ++c; }
00328 else
00329 {
00330 ++a;
00331 ++c;
00332 }
00333 ++counter;
00334 }
00335
00336 counter += (b - a);
00337 counter += (d - c);
00338 return counter;
00339 }
00340
00341 inline OutputIterator
00342 first_empty(InputIterator c, InputIterator d, OutputIterator out) const
00343 { return std::copy(c, d, out); }
00344
00345 inline OutputIterator
00346 second_empty(InputIterator a, InputIterator b, OutputIterator out) const
00347 { return std::copy(a, b, out); }
00348 };
00349
00350 template<typename InputIterator,
00351 typename OutputIterator,
00352 typename Operation>
00353 OutputIterator
00354 parallel_set_operation(InputIterator begin1, InputIterator end1,
00355 InputIterator begin2, InputIterator end2,
00356 OutputIterator result, Operation op)
00357 {
00358 _GLIBCXX_CALL((end1 - begin1) + (end2 - begin2))
00359
00360 typedef std::iterator_traits<InputIterator> traits_type;
00361 typedef typename traits_type::difference_type difference_type;
00362 typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
00363
00364 if (begin1 == end1)
00365 return op.first_empty(begin2, end2, result);
00366
00367 if (begin2 == end2)
00368 return op.second_empty(begin1, end1, result);
00369
00370 const difference_type size = (end1 - begin1) + (end2 - begin2);
00371
00372 const iterator_pair sequence[ 2 ] =
00373 { std::make_pair(begin1, end1), std::make_pair(begin2, end2) } ;
00374 OutputIterator return_value = result;
00375 difference_type *borders;
00376 iterator_pair *block_begins;
00377 difference_type* lengths;
00378
00379 thread_index_t num_threads =
00380 std::min<difference_type>(get_max_threads(),
00381 std::min(end1 - begin1, end2 - begin2));
00382
00383 # pragma omp parallel num_threads(num_threads)
00384 {
00385 # pragma omp single
00386 {
00387 num_threads = omp_get_num_threads();
00388
00389 borders = new difference_type[num_threads + 2];
00390 equally_split(size, num_threads + 1, borders);
00391 block_begins = new iterator_pair[num_threads + 1];
00392
00393 block_begins[0] = std::make_pair(begin1, begin2);
00394 lengths = new difference_type[num_threads];
00395 }
00396
00397 thread_index_t iam = omp_get_thread_num();
00398
00399
00400 InputIterator offset[2];
00401 const difference_type rank = borders[iam + 1];
00402
00403 multiseq_partition(sequence, sequence + 2, rank, offset, op.comp);
00404
00405
00406
00407
00408 if (offset[ 0 ] != begin1 && offset[ 1 ] != end2
00409 && !op.comp(*(offset[ 0 ] - 1), *offset[ 1 ])
00410 && !op.comp(*offset[ 1 ], *(offset[ 0 ] - 1)))
00411 {
00412
00413
00414 --offset[ 0 ];
00415 }
00416
00417 iterator_pair block_end = block_begins[ iam + 1 ] =
00418 iterator_pair(offset[ 0 ], offset[ 1 ]);
00419
00420
00421 # pragma omp barrier
00422
00423 iterator_pair block_begin = block_begins[ iam ];
00424
00425
00426
00427 if (iam == 0)
00428 {
00429
00430 lengths[ iam ] = op.invoke(block_begin.first, block_end.first,
00431 block_begin.second, block_end.second,
00432 result)
00433 - result;
00434 }
00435 else
00436 {
00437 lengths[ iam ] = op.count(block_begin.first, block_end.first,
00438 block_begin.second, block_end.second);
00439 }
00440
00441
00442 # pragma omp barrier
00443
00444 OutputIterator r = result;
00445
00446 if (iam == 0)
00447 {
00448
00449 for (int i = 0; i < num_threads; ++i)
00450 r += lengths[i];
00451
00452 block_begin = block_begins[num_threads];
00453
00454
00455 return_value = op.invoke(
00456 block_begin.first, end1, block_begin.second, end2, r);
00457
00458 }
00459 else
00460 {
00461 for (int i = 0; i < iam; ++i)
00462 r += lengths[ i ];
00463
00464
00465 op.invoke(block_begin.first, block_end.first,
00466 block_begin.second, block_end.second, r);
00467 }
00468 }
00469 return return_value;
00470 }
00471
00472
00473 template<typename InputIterator,
00474 typename OutputIterator,
00475 typename Comparator>
00476 inline OutputIterator
00477 parallel_set_union(InputIterator begin1, InputIterator end1,
00478 InputIterator begin2, InputIterator end2,
00479 OutputIterator result, Comparator comp)
00480 {
00481 return parallel_set_operation(begin1, end1, begin2, end2, result,
00482 union_func< InputIterator, OutputIterator, Comparator>(comp));
00483 }
00484
00485 template<typename InputIterator,
00486 typename OutputIterator,
00487 typename Comparator>
00488 inline OutputIterator
00489 parallel_set_intersection(InputIterator begin1, InputIterator end1,
00490 InputIterator begin2, InputIterator end2,
00491 OutputIterator result, Comparator comp)
00492 {
00493 return parallel_set_operation(begin1, end1, begin2, end2, result,
00494 intersection_func<InputIterator, OutputIterator, Comparator>(comp));
00495 }
00496
00497 template<typename InputIterator,
00498 typename OutputIterator,
00499 typename Comparator>
00500 inline OutputIterator
00501 parallel_set_difference(InputIterator begin1, InputIterator end1,
00502 InputIterator begin2, InputIterator end2,
00503 OutputIterator result, Comparator comp)
00504 {
00505 return parallel_set_operation(begin1, end1, begin2, end2, result,
00506 difference_func<InputIterator, OutputIterator, Comparator>(comp));
00507 }
00508
00509 template<typename InputIterator,
00510 typename OutputIterator,
00511 typename Comparator>
00512 inline OutputIterator
00513 parallel_set_symmetric_difference(InputIterator begin1, InputIterator end1,
00514 InputIterator begin2, InputIterator end2,
00515 OutputIterator result, Comparator comp)
00516 {
00517 return parallel_set_operation(begin1, end1, begin2, end2, result,
00518 symmetric_difference_func<InputIterator, OutputIterator, Comparator>
00519 (comp));
00520 }
00521
00522 }
00523
00524 #endif