libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009 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 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 // Very start. 00393 block_begins[0] = std::make_pair(begin1, begin2); 00394 lengths = new difference_type[num_threads]; 00395 } //single 00396 00397 thread_index_t iam = omp_get_thread_num(); 00398 00399 // Result from multiseq_partition. 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 // allowed to read? 00406 // together 00407 // *(offset[ 0 ] - 1) == *offset[ 1 ] 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 // Avoid split between globally equal elements: move one to 00413 // front in first sequence. 00414 --offset[ 0 ]; 00415 } 00416 00417 iterator_pair block_end = block_begins[ iam + 1 ] = 00418 iterator_pair(offset[ 0 ], offset[ 1 ]); 00419 00420 // Make sure all threads have their block_begin result written out. 00421 # pragma omp barrier 00422 00423 iterator_pair block_begin = block_begins[ iam ]; 00424 00425 // Begin working for the first block, while the others except 00426 // the last start to count. 00427 if (iam == 0) 00428 { 00429 // The first thread can copy already. 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 // Make sure everyone wrote their lengths. 00442 # pragma omp barrier 00443 00444 OutputIterator r = result; 00445 00446 if (iam == 0) 00447 { 00448 // Do the last block. 00449 for (int i = 0; i < num_threads; ++i) 00450 r += lengths[i]; 00451 00452 block_begin = block_begins[num_threads]; 00453 00454 // Return the result iterator of the last block. 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 // Reset begins for copy pass. 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 /* _GLIBCXX_PARALLEL_SET_OPERATIONS_H */