libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** 00026 * @file parallel/set_operations.h 00027 * @brief Parallel implementations of set operations for random-access 00028 * iterators. 00029 * This file is a GNU parallel extension to the Standard C++ Library. 00030 */ 00031 00032 // Written by Marius Elvert and Felix Bondarenko. 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 // Very __start. 00389 __block_begins[0] = std::make_pair(__begin1, __begin2); 00390 __lengths = new _DifferenceType[__num_threads]; 00391 } //single 00392 00393 _ThreadIndex __iam = omp_get_thread_num(); 00394 00395 // _Result from multiseq_partition. 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 // allowed to read? 00403 // together 00404 // *(__offset[ 0 ] - 1) == *__offset[ 1 ] 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 // Avoid split between globally equal elements: move one to 00410 // front in first sequence. 00411 --__offset[0]; 00412 } 00413 00414 _IteratorPair __block_end = __block_begins[__iam + 1] = 00415 _IteratorPair(__offset[0], __offset[1]); 00416 00417 // Make sure all threads have their block_begin result written out. 00418 # pragma omp barrier 00419 00420 _IteratorPair __block_begin = __block_begins[__iam]; 00421 00422 // Begin working for the first block, while the others except 00423 // the last start to count. 00424 if (__iam == 0) 00425 { 00426 // The first thread can copy already. 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 // Make sure everyone wrote their lengths. 00440 # pragma omp barrier 00441 00442 _OutputIterator __r = __result; 00443 00444 if (__iam == 0) 00445 { 00446 // Do the last block. 00447 for (_ThreadIndex __i = 0; __i < __num_threads; ++__i) 00448 __r += __lengths[__i]; 00449 00450 __block_begin = __block_begins[__num_threads]; 00451 00452 // Return the result iterator of the last block. 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 // Reset begins for copy pass. 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 /* _GLIBCXX_PARALLEL_SET_OPERATIONS_H */