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 _IIter, typename _OutputIterator>
00045 _OutputIterator
00046 __copy_tail(std::pair<_IIter, _IIter> __b,
00047 std::pair<_IIter, _IIter> __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 _IIter,
00066 typename _OutputIterator,
00067 typename _Compare>
00068 struct __symmetric_difference_func
00069 {
00070 typedef std::iterator_traits<_IIter> _TraitsType;
00071 typedef typename _TraitsType::difference_type _DifferenceType;
00072 typedef typename std::pair<_IIter, _IIter> _IteratorPair;
00073
00074 __symmetric_difference_func(_Compare __comp) : _M_comp(__comp) {}
00075
00076 _Compare _M_comp;
00077
00078 _OutputIterator
00079 _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
00080 _OutputIterator __r) const
00081 {
00082 while (__a != __b && __c != __d)
00083 {
00084 if (_M_comp(*__a, *__c))
00085 {
00086 *__r = *__a;
00087 ++__a;
00088 ++__r;
00089 }
00090 else if (_M_comp(*__c, *__a))
00091 {
00092 *__r = *__c;
00093 ++__c;
00094 ++__r;
00095 }
00096 else
00097 {
00098 ++__a;
00099 ++__c;
00100 }
00101 }
00102 return std::copy(__c, __d, std::copy(__a, __b, __r));
00103 }
00104
00105 _DifferenceType
00106 __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
00107 {
00108 _DifferenceType __counter = 0;
00109
00110 while (__a != __b && __c != __d)
00111 {
00112 if (_M_comp(*__a, *__c))
00113 {
00114 ++__a;
00115 ++__counter;
00116 }
00117 else if (_M_comp(*__c, *__a))
00118 {
00119 ++__c;
00120 ++__counter;
00121 }
00122 else
00123 {
00124 ++__a;
00125 ++__c;
00126 }
00127 }
00128
00129 return __counter + (__b - __a) + (__d - __c);
00130 }
00131
00132 _OutputIterator
00133 __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const
00134 { return std::copy(__c, __d, __out); }
00135
00136 _OutputIterator
00137 __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
00138 { return std::copy(__a, __b, __out); }
00139 };
00140
00141
00142 template<typename _IIter,
00143 typename _OutputIterator,
00144 typename _Compare>
00145 struct __difference_func
00146 {
00147 typedef std::iterator_traits<_IIter> _TraitsType;
00148 typedef typename _TraitsType::difference_type _DifferenceType;
00149 typedef typename std::pair<_IIter, _IIter> _IteratorPair;
00150
00151 __difference_func(_Compare __comp) : _M_comp(__comp) {}
00152
00153 _Compare _M_comp;
00154
00155 _OutputIterator
00156 _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
00157 _OutputIterator __r) const
00158 {
00159 while (__a != __b && __c != __d)
00160 {
00161 if (_M_comp(*__a, *__c))
00162 {
00163 *__r = *__a;
00164 ++__a;
00165 ++__r;
00166 }
00167 else if (_M_comp(*__c, *__a))
00168 { ++__c; }
00169 else
00170 {
00171 ++__a;
00172 ++__c;
00173 }
00174 }
00175 return std::copy(__a, __b, __r);
00176 }
00177
00178 _DifferenceType
00179 __count(_IIter __a, _IIter __b,
00180 _IIter __c, _IIter __d) const
00181 {
00182 _DifferenceType __counter = 0;
00183
00184 while (__a != __b && __c != __d)
00185 {
00186 if (_M_comp(*__a, *__c))
00187 {
00188 ++__a;
00189 ++__counter;
00190 }
00191 else if (_M_comp(*__c, *__a))
00192 { ++__c; }
00193 else
00194 { ++__a; ++__c; }
00195 }
00196
00197 return __counter + (__b - __a);
00198 }
00199
00200 _OutputIterator
00201 __first_empty(_IIter, _IIter, _OutputIterator __out) const
00202 { return __out; }
00203
00204 _OutputIterator
00205 __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
00206 { return std::copy(__a, __b, __out); }
00207 };
00208
00209
00210 template<typename _IIter,
00211 typename _OutputIterator,
00212 typename _Compare>
00213 struct __intersection_func
00214 {
00215 typedef std::iterator_traits<_IIter> _TraitsType;
00216 typedef typename _TraitsType::difference_type _DifferenceType;
00217 typedef typename std::pair<_IIter, _IIter> _IteratorPair;
00218
00219 __intersection_func(_Compare __comp) : _M_comp(__comp) {}
00220
00221 _Compare _M_comp;
00222
00223 _OutputIterator
00224 _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
00225 _OutputIterator __r) const
00226 {
00227 while (__a != __b && __c != __d)
00228 {
00229 if (_M_comp(*__a, *__c))
00230 { ++__a; }
00231 else if (_M_comp(*__c, *__a))
00232 { ++__c; }
00233 else
00234 {
00235 *__r = *__a;
00236 ++__a;
00237 ++__c;
00238 ++__r;
00239 }
00240 }
00241
00242 return __r;
00243 }
00244
00245 _DifferenceType
00246 __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
00247 {
00248 _DifferenceType __counter = 0;
00249
00250 while (__a != __b && __c != __d)
00251 {
00252 if (_M_comp(*__a, *__c))
00253 { ++__a; }
00254 else if (_M_comp(*__c, *__a))
00255 { ++__c; }
00256 else
00257 {
00258 ++__a;
00259 ++__c;
00260 ++__counter;
00261 }
00262 }
00263
00264 return __counter;
00265 }
00266
00267 _OutputIterator
00268 __first_empty(_IIter, _IIter, _OutputIterator __out) const
00269 { return __out; }
00270
00271 _OutputIterator
00272 __second_empty(_IIter, _IIter, _OutputIterator __out) const
00273 { return __out; }
00274 };
00275
00276 template<class _IIter, class _OutputIterator, class _Compare>
00277 struct __union_func
00278 {
00279 typedef typename std::iterator_traits<_IIter>::difference_type
00280 _DifferenceType;
00281
00282 __union_func(_Compare __comp) : _M_comp(__comp) {}
00283
00284 _Compare _M_comp;
00285
00286 _OutputIterator
00287 _M_invoke(_IIter __a, const _IIter __b, _IIter __c,
00288 const _IIter __d, _OutputIterator __r) const
00289 {
00290 while (__a != __b && __c != __d)
00291 {
00292 if (_M_comp(*__a, *__c))
00293 {
00294 *__r = *__a;
00295 ++__a;
00296 }
00297 else if (_M_comp(*__c, *__a))
00298 {
00299 *__r = *__c;
00300 ++__c;
00301 }
00302 else
00303 {
00304 *__r = *__a;
00305 ++__a;
00306 ++__c;
00307 }
00308 ++__r;
00309 }
00310 return std::copy(__c, __d, std::copy(__a, __b, __r));
00311 }
00312
00313 _DifferenceType
00314 __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
00315 {
00316 _DifferenceType __counter = 0;
00317
00318 while (__a != __b && __c != __d)
00319 {
00320 if (_M_comp(*__a, *__c))
00321 { ++__a; }
00322 else if (_M_comp(*__c, *__a))
00323 { ++__c; }
00324 else
00325 {
00326 ++__a;
00327 ++__c;
00328 }
00329 ++__counter;
00330 }
00331
00332 __counter += (__b - __a);
00333 __counter += (__d - __c);
00334 return __counter;
00335 }
00336
00337 _OutputIterator
00338 __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const
00339 { return std::copy(__c, __d, __out); }
00340
00341 _OutputIterator
00342 __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
00343 { return std::copy(__a, __b, __out); }
00344 };
00345
00346 template<typename _IIter,
00347 typename _OutputIterator,
00348 typename _Operation>
00349 _OutputIterator
00350 __parallel_set_operation(_IIter __begin1, _IIter __end1,
00351 _IIter __begin2, _IIter __end2,
00352 _OutputIterator __result, _Operation __op)
00353 {
00354 _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2))
00355
00356 typedef std::iterator_traits<_IIter> _TraitsType;
00357 typedef typename _TraitsType::difference_type _DifferenceType;
00358 typedef typename std::pair<_IIter, _IIter> _IteratorPair;
00359
00360 if (__begin1 == __end1)
00361 return __op.__first_empty(__begin2, __end2, __result);
00362
00363 if (__begin2 == __end2)
00364 return __op.__second_empty(__begin1, __end1, __result);
00365
00366 const _DifferenceType __size = (__end1 - __begin1) + (__end2 - __begin2);
00367
00368 const _IteratorPair __sequence[2] = { std::make_pair(__begin1, __end1),
00369 std::make_pair(__begin2, __end2) };
00370 _OutputIterator __return_value = __result;
00371 _DifferenceType *__borders;
00372 _IteratorPair *__block_begins;
00373 _DifferenceType* __lengths;
00374
00375 _ThreadIndex __num_threads =
00376 std::min<_DifferenceType>(__get_max_threads(),
00377 std::min(__end1 - __begin1, __end2 - __begin2));
00378
00379 # pragma omp parallel num_threads(__num_threads)
00380 {
00381 # pragma omp single
00382 {
00383 __num_threads = omp_get_num_threads();
00384
00385 __borders = new _DifferenceType[__num_threads + 2];
00386 equally_split(__size, __num_threads + 1, __borders);
00387 __block_begins = new _IteratorPair[__num_threads + 1];
00388
00389 __block_begins[0] = std::make_pair(__begin1, __begin2);
00390 __lengths = new _DifferenceType[__num_threads];
00391 }
00392
00393 _ThreadIndex __iam = omp_get_thread_num();
00394
00395
00396 _IIter __offset[2];
00397 const _DifferenceType __rank = __borders[__iam + 1];
00398
00399 multiseq_partition(__sequence, __sequence + 2,
00400 __rank, __offset, __op._M_comp);
00401
00402
00403
00404
00405 if (__offset[ 0 ] != __begin1 && __offset[1] != __end2
00406 && !__op._M_comp(*(__offset[0] - 1), *__offset[1])
00407 && !__op._M_comp(*__offset[1], *(__offset[0] - 1)))
00408 {
00409
00410
00411 --__offset[0];
00412 }
00413
00414 _IteratorPair __block_end = __block_begins[__iam + 1] =
00415 _IteratorPair(__offset[0], __offset[1]);
00416
00417
00418 # pragma omp barrier
00419
00420 _IteratorPair __block_begin = __block_begins[__iam];
00421
00422
00423
00424 if (__iam == 0)
00425 {
00426
00427 __lengths[ __iam ] =
00428 __op._M_invoke(__block_begin.first, __block_end.first,
00429 __block_begin.second, __block_end.second,
00430 __result) - __result;
00431 }
00432 else
00433 {
00434 __lengths[ __iam ] =
00435 __op.__count(__block_begin.first, __block_end.first,
00436 __block_begin.second, __block_end.second);
00437 }
00438
00439
00440 # pragma omp barrier
00441
00442 _OutputIterator __r = __result;
00443
00444 if (__iam == 0)
00445 {
00446
00447 for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
00448 __r += __lengths[__i];
00449
00450 __block_begin = __block_begins[__num_threads];
00451
00452
00453 __return_value =
00454 __op._M_invoke(__block_begin.first, __end1,
00455 __block_begin.second, __end2, __r);
00456
00457 }
00458 else
00459 {
00460 for (_ThreadIndex __i = 0; __i < __iam; ++__i)
00461 __r += __lengths[ __i ];
00462
00463
00464 __op._M_invoke(__block_begin.first, __block_end.first,
00465 __block_begin.second, __block_end.second, __r);
00466 }
00467 }
00468 return __return_value;
00469 }
00470
00471 template<typename _IIter,
00472 typename _OutputIterator,
00473 typename _Compare>
00474 inline _OutputIterator
00475 __parallel_set_union(_IIter __begin1, _IIter __end1,
00476 _IIter __begin2, _IIter __end2,
00477 _OutputIterator __result, _Compare __comp)
00478 {
00479 return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
00480 __result,
00481 __union_func< _IIter, _OutputIterator,
00482 _Compare>(__comp));
00483 }
00484
00485 template<typename _IIter,
00486 typename _OutputIterator,
00487 typename _Compare>
00488 inline _OutputIterator
00489 __parallel_set_intersection(_IIter __begin1, _IIter __end1,
00490 _IIter __begin2, _IIter __end2,
00491 _OutputIterator __result, _Compare __comp)
00492 {
00493 return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
00494 __result,
00495 __intersection_func<_IIter,
00496 _OutputIterator, _Compare>(__comp));
00497 }
00498
00499 template<typename _IIter,
00500 typename _OutputIterator,
00501 typename _Compare>
00502 inline _OutputIterator
00503 __parallel_set_difference(_IIter __begin1, _IIter __end1,
00504 _IIter __begin2, _IIter __end2,
00505 _OutputIterator __result, _Compare __comp)
00506 {
00507 return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
00508 __result,
00509 __difference_func<_IIter,
00510 _OutputIterator, _Compare>(__comp));
00511 }
00512
00513 template<typename _IIter,
00514 typename _OutputIterator,
00515 typename _Compare>
00516 inline _OutputIterator
00517 __parallel_set_symmetric_difference(_IIter __begin1, _IIter __end1,
00518 _IIter __begin2, _IIter __end2,
00519 _OutputIterator __result,
00520 _Compare __comp)
00521 {
00522 return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
00523 __result,
00524 __symmetric_difference_func<_IIter,
00525 _OutputIterator, _Compare>(__comp));
00526 }
00527 }
00528
00529 #endif