1 // -*- C++ -*- 2 3 // Copyright (C) 2007-2013 Free Software Foundation, Inc. 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 8 // Foundation; either version 3, or (at your option) any later 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 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. 19 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/>. 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 { 44 template<typename _IIter, typename _OutputIterator> 45 _OutputIterator 46 __copy_tail(std::pair<_IIter, _IIter> __b, 47 std::pair<_IIter, _IIter> __e, _OutputIterator __r) 48 { 49 if (__b.first != __e.first) 50 { 51 do 52 { 53 *__r++ = *__b.first++; 54 } 55 while (__b.first != __e.first); 56 } 57 else 58 { 59 while (__b.second != __e.second) 60 *__r++ = *__b.second++; 61 } 62 return __r; 63 } 64 65 template<typename _IIter, 66 typename _OutputIterator, 67 typename _Compare> 68 struct __symmetric_difference_func 69 { 70 typedef std::iterator_traits<_IIter> _TraitsType; 71 typedef typename _TraitsType::difference_type _DifferenceType; 72 typedef typename std::pair<_IIter, _IIter> _IteratorPair; 73 74 __symmetric_difference_func(_Compare __comp) : _M_comp(__comp) {} 75 76 _Compare _M_comp; 77 78 _OutputIterator 79 _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d, 80 _OutputIterator __r) const 81 { 82 while (__a != __b && __c != __d) 83 { 84 if (_M_comp(*__a, *__c)) 85 { 86 *__r = *__a; 87 ++__a; 88 ++__r; 89 } 90 else if (_M_comp(*__c, *__a)) 91 { 92 *__r = *__c; 93 ++__c; 94 ++__r; 95 } 96 else 97 { 98 ++__a; 99 ++__c; 100 } 101 } 102 return std::copy(__c, __d, std::copy(__a, __b, __r)); 103 } 104 105 _DifferenceType 106 __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const 107 { 108 _DifferenceType __counter = 0; 109 110 while (__a != __b && __c != __d) 111 { 112 if (_M_comp(*__a, *__c)) 113 { 114 ++__a; 115 ++__counter; 116 } 117 else if (_M_comp(*__c, *__a)) 118 { 119 ++__c; 120 ++__counter; 121 } 122 else 123 { 124 ++__a; 125 ++__c; 126 } 127 } 128 129 return __counter + (__b - __a) + (__d - __c); 130 } 131 132 _OutputIterator 133 __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const 134 { return std::copy(__c, __d, __out); } 135 136 _OutputIterator 137 __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const 138 { return std::copy(__a, __b, __out); } 139 }; 140 141 142 template<typename _IIter, 143 typename _OutputIterator, 144 typename _Compare> 145 struct __difference_func 146 { 147 typedef std::iterator_traits<_IIter> _TraitsType; 148 typedef typename _TraitsType::difference_type _DifferenceType; 149 typedef typename std::pair<_IIter, _IIter> _IteratorPair; 150 151 __difference_func(_Compare __comp) : _M_comp(__comp) {} 152 153 _Compare _M_comp; 154 155 _OutputIterator 156 _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d, 157 _OutputIterator __r) const 158 { 159 while (__a != __b && __c != __d) 160 { 161 if (_M_comp(*__a, *__c)) 162 { 163 *__r = *__a; 164 ++__a; 165 ++__r; 166 } 167 else if (_M_comp(*__c, *__a)) 168 { ++__c; } 169 else 170 { 171 ++__a; 172 ++__c; 173 } 174 } 175 return std::copy(__a, __b, __r); 176 } 177 178 _DifferenceType 179 __count(_IIter __a, _IIter __b, 180 _IIter __c, _IIter __d) const 181 { 182 _DifferenceType __counter = 0; 183 184 while (__a != __b && __c != __d) 185 { 186 if (_M_comp(*__a, *__c)) 187 { 188 ++__a; 189 ++__counter; 190 } 191 else if (_M_comp(*__c, *__a)) 192 { ++__c; } 193 else 194 { ++__a; ++__c; } 195 } 196 197 return __counter + (__b - __a); 198 } 199 200 _OutputIterator 201 __first_empty(_IIter, _IIter, _OutputIterator __out) const 202 { return __out; } 203 204 _OutputIterator 205 __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const 206 { return std::copy(__a, __b, __out); } 207 }; 208 209 210 template<typename _IIter, 211 typename _OutputIterator, 212 typename _Compare> 213 struct __intersection_func 214 { 215 typedef std::iterator_traits<_IIter> _TraitsType; 216 typedef typename _TraitsType::difference_type _DifferenceType; 217 typedef typename std::pair<_IIter, _IIter> _IteratorPair; 218 219 __intersection_func(_Compare __comp) : _M_comp(__comp) {} 220 221 _Compare _M_comp; 222 223 _OutputIterator 224 _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d, 225 _OutputIterator __r) const 226 { 227 while (__a != __b && __c != __d) 228 { 229 if (_M_comp(*__a, *__c)) 230 { ++__a; } 231 else if (_M_comp(*__c, *__a)) 232 { ++__c; } 233 else 234 { 235 *__r = *__a; 236 ++__a; 237 ++__c; 238 ++__r; 239 } 240 } 241 242 return __r; 243 } 244 245 _DifferenceType 246 __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const 247 { 248 _DifferenceType __counter = 0; 249 250 while (__a != __b && __c != __d) 251 { 252 if (_M_comp(*__a, *__c)) 253 { ++__a; } 254 else if (_M_comp(*__c, *__a)) 255 { ++__c; } 256 else 257 { 258 ++__a; 259 ++__c; 260 ++__counter; 261 } 262 } 263 264 return __counter; 265 } 266 267 _OutputIterator 268 __first_empty(_IIter, _IIter, _OutputIterator __out) const 269 { return __out; } 270 271 _OutputIterator 272 __second_empty(_IIter, _IIter, _OutputIterator __out) const 273 { return __out; } 274 }; 275 276 template<class _IIter, class _OutputIterator, class _Compare> 277 struct __union_func 278 { 279 typedef typename std::iterator_traits<_IIter>::difference_type 280 _DifferenceType; 281 282 __union_func(_Compare __comp) : _M_comp(__comp) {} 283 284 _Compare _M_comp; 285 286 _OutputIterator 287 _M_invoke(_IIter __a, const _IIter __b, _IIter __c, 288 const _IIter __d, _OutputIterator __r) const 289 { 290 while (__a != __b && __c != __d) 291 { 292 if (_M_comp(*__a, *__c)) 293 { 294 *__r = *__a; 295 ++__a; 296 } 297 else if (_M_comp(*__c, *__a)) 298 { 299 *__r = *__c; 300 ++__c; 301 } 302 else 303 { 304 *__r = *__a; 305 ++__a; 306 ++__c; 307 } 308 ++__r; 309 } 310 return std::copy(__c, __d, std::copy(__a, __b, __r)); 311 } 312 313 _DifferenceType 314 __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const 315 { 316 _DifferenceType __counter = 0; 317 318 while (__a != __b && __c != __d) 319 { 320 if (_M_comp(*__a, *__c)) 321 { ++__a; } 322 else if (_M_comp(*__c, *__a)) 323 { ++__c; } 324 else 325 { 326 ++__a; 327 ++__c; 328 } 329 ++__counter; 330 } 331 332 __counter += (__b - __a); 333 __counter += (__d - __c); 334 return __counter; 335 } 336 337 _OutputIterator 338 __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const 339 { return std::copy(__c, __d, __out); } 340 341 _OutputIterator 342 __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const 343 { return std::copy(__a, __b, __out); } 344 }; 345 346 template<typename _IIter, 347 typename _OutputIterator, 348 typename _Operation> 349 _OutputIterator 350 __parallel_set_operation(_IIter __begin1, _IIter __end1, 351 _IIter __begin2, _IIter __end2, 352 _OutputIterator __result, _Operation __op) 353 { 354 _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2)) 355 356 typedef std::iterator_traits<_IIter> _TraitsType; 357 typedef typename _TraitsType::difference_type _DifferenceType; 358 typedef typename std::pair<_IIter, _IIter> _IteratorPair; 359 360 if (__begin1 == __end1) 361 return __op.__first_empty(__begin2, __end2, __result); 362 363 if (__begin2 == __end2) 364 return __op.__second_empty(__begin1, __end1, __result); 365 366 const _DifferenceType __size = (__end1 - __begin1) + (__end2 - __begin2); 367 368 const _IteratorPair __sequence[2] = { std::make_pair(__begin1, __end1), 369 std::make_pair(__begin2, __end2) }; 370 _OutputIterator __return_value = __result; 371 _DifferenceType *__borders; 372 _IteratorPair *__block_begins; 373 _DifferenceType* __lengths; 374 375 _ThreadIndex __num_threads = 376 std::min<_DifferenceType>(__get_max_threads(), 377 std::min(__end1 - __begin1, __end2 - __begin2)); 378 379 # pragma omp parallel num_threads(__num_threads) 380 { 381 # pragma omp single 382 { 383 __num_threads = omp_get_num_threads(); 384 385 __borders = new _DifferenceType[__num_threads + 2]; 386 __equally_split(__size, __num_threads + 1, __borders); 387 __block_begins = new _IteratorPair[__num_threads + 1]; 388 // Very __start. 389 __block_begins[0] = std::make_pair(__begin1, __begin2); 390 __lengths = new _DifferenceType[__num_threads]; 391 } //single 392 393 _ThreadIndex __iam = omp_get_thread_num(); 394 395 // _Result from multiseq_partition. 396 _IIter __offset[2]; 397 const _DifferenceType __rank = __borders[__iam + 1]; 398 399 multiseq_partition(__sequence, __sequence + 2, 400 __rank, __offset, __op._M_comp); 401 402 // allowed to read? 403 // together 404 // *(__offset[ 0 ] - 1) == *__offset[ 1 ] 405 if (__offset[ 0 ] != __begin1 && __offset[1] != __end2 406 && !__op._M_comp(*(__offset[0] - 1), *__offset[1]) 407 && !__op._M_comp(*__offset[1], *(__offset[0] - 1))) 408 { 409 // Avoid split between globally equal elements: move one to 410 // front in first sequence. 411 --__offset[0]; 412 } 413 414 _IteratorPair __block_end = __block_begins[__iam + 1] = 415 _IteratorPair(__offset[0], __offset[1]); 416 417 // Make sure all threads have their block_begin result written out. 418 # pragma omp barrier 419 420 _IteratorPair __block_begin = __block_begins[__iam]; 421 422 // Begin working for the first block, while the others except 423 // the last start to count. 424 if (__iam == 0) 425 { 426 // The first thread can copy already. 427 __lengths[ __iam ] = 428 __op._M_invoke(__block_begin.first, __block_end.first, 429 __block_begin.second, __block_end.second, 430 __result) - __result; 431 } 432 else 433 { 434 __lengths[ __iam ] = 435 __op.__count(__block_begin.first, __block_end.first, 436 __block_begin.second, __block_end.second); 437 } 438 439 // Make sure everyone wrote their lengths. 440 # pragma omp barrier 441 442 _OutputIterator __r = __result; 443 444 if (__iam == 0) 445 { 446 // Do the last block. 447 for (_ThreadIndex __i = 0; __i < __num_threads; ++__i) 448 __r += __lengths[__i]; 449 450 __block_begin = __block_begins[__num_threads]; 451 452 // Return the result iterator of the last block. 453 __return_value = 454 __op._M_invoke(__block_begin.first, __end1, 455 __block_begin.second, __end2, __r); 456 457 } 458 else 459 { 460 for (_ThreadIndex __i = 0; __i < __iam; ++__i) 461 __r += __lengths[ __i ]; 462 463 // Reset begins for copy pass. 464 __op._M_invoke(__block_begin.first, __block_end.first, 465 __block_begin.second, __block_end.second, __r); 466 } 467 } 468 return __return_value; 469 } 470 471 template<typename _IIter, 472 typename _OutputIterator, 473 typename _Compare> 474 inline _OutputIterator 475 __parallel_set_union(_IIter __begin1, _IIter __end1, 476 _IIter __begin2, _IIter __end2, 477 _OutputIterator __result, _Compare __comp) 478 { 479 return __parallel_set_operation(__begin1, __end1, __begin2, __end2, 480 __result, 481 __union_func< _IIter, _OutputIterator, 482 _Compare>(__comp)); 483 } 484 485 template<typename _IIter, 486 typename _OutputIterator, 487 typename _Compare> 488 inline _OutputIterator 489 __parallel_set_intersection(_IIter __begin1, _IIter __end1, 490 _IIter __begin2, _IIter __end2, 491 _OutputIterator __result, _Compare __comp) 492 { 493 return __parallel_set_operation(__begin1, __end1, __begin2, __end2, 494 __result, 495 __intersection_func<_IIter, 496 _OutputIterator, _Compare>(__comp)); 497 } 498 499 template<typename _IIter, 500 typename _OutputIterator, 501 typename _Compare> 502 inline _OutputIterator 503 __parallel_set_difference(_IIter __begin1, _IIter __end1, 504 _IIter __begin2, _IIter __end2, 505 _OutputIterator __result, _Compare __comp) 506 { 507 return __parallel_set_operation(__begin1, __end1, __begin2, __end2, 508 __result, 509 __difference_func<_IIter, 510 _OutputIterator, _Compare>(__comp)); 511 } 512 513 template<typename _IIter, 514 typename _OutputIterator, 515 typename _Compare> 516 inline _OutputIterator 517 __parallel_set_symmetric_difference(_IIter __begin1, _IIter __end1, 518 _IIter __begin2, _IIter __end2, 519 _OutputIterator __result, 520 _Compare __comp) 521 { 522 return __parallel_set_operation(__begin1, __end1, __begin2, __end2, 523 __result, 524 __symmetric_difference_func<_IIter, 525 _OutputIterator, _Compare>(__comp)); 526 } 527 } 528 529 #endif /* _GLIBCXX_PARALLEL_SET_OPERATIONS_H */ 530
