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