libstdc++-v3/include/parallel/set_operations.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007-2018 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 */