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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 /**
  32  * @file parallel/set_operations.h
  33  * @brief Parallel implementations of set operations for random-access
  34  * iterators.
  35  *  This file is a GNU parallel extension to the Standard C++ Library.
  36  */
  37
  38 // Written by Marius Elvert and Felix Bondarenko.
  39
  40 #ifndef _GLIBCXX_PARALLEL_SET_OPERATIONS_H
  41 #define _GLIBCXX_PARALLEL_SET_OPERATIONS_H 1
  42
  43 #include <omp.h>
  44
  45 #include <parallel/settings.h>
  46 #include <parallel/multiseq_selection.h>
  47
  48 namespace __gnu_parallel
  49 {
  50   template<typename InputIterator, typename OutputIterator>
  51   inline OutputIterator
  52   copy_tail(std::pair<InputIterator, InputIterator> b,
  53             std::pair<InputIterator, InputIterator> e, OutputIterator r)
  54   {
  55     if (b.first != e.first)
  56       {
  57         do
  58           {
  59             *r++ = *b.first++;
  60           }
  61         while (b.first != e.first);
  62       }
  63     else
  64       {
  65         while (b.second != e.second)
  66           *r++ = *b.second++;
  67       }
  68     return r;
  69   }
  70
  71   template<typename InputIterator, typename OutputIterator, typename Comparator>
  72   struct symmetric_difference_func
  73   {
  74     typedef std::iterator_traits<InputIterator> traits_type;
  75     typedef typename traits_type::difference_type difference_type;
  76     typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
  77
  78     symmetric_difference_func(Comparator c) : comp(c) {}
  79
  80     Comparator comp;
  81
  82     inline OutputIterator invoke(InputIterator a, InputIterator b,
  83                                  InputIterator c, InputIterator d,
  84                                  OutputIterator r) const
  85     {
  86       while (a != b && c != d)
  87         {
  88           if (comp(*a, *c))
  89             {
  90               *r = *a;
  91               ++a;
  92               ++r;
  93             }
  94           else if (comp(*c, *a))
  95             {
  96               *r = *c;
  97               ++c;
  98               ++r;
  99             }
 100           else
 101             {
 102               ++a;
 103               ++c;
 104             }
 105         }
 106       return std::copy(c, d, std::copy(a, b, r));
 107     }
 108
 109     inline difference_type
 110     count(InputIterator a, InputIterator b, InputIterator c, InputIterator d) const
 111     {
 112       difference_type counter = 0;
 113
 114       while (a != b && c != d)
 115         {
 116           if (comp(*a, *c))
 117             {
 118               ++a;
 119               ++counter;
 120             }
 121           else if (comp(*c, *a))
 122             {
 123               ++c;
 124               ++counter;
 125             }
 126           else
 127             {
 128               ++a;
 129               ++c;
 130             }
 131         }
 132
 133       return counter + (b - a) + (d - c);
 134     }
 135
 136     inline OutputIterator
 137     first_empty(InputIterator c, InputIterator d, OutputIterator out) const
 138     { return std::copy(c, d, out); }
 139
 140     inline OutputIterator
 141     second_empty(InputIterator a, InputIterator b, OutputIterator out) const
 142     { return std::copy(a, b, out); }
 143
 144   };
 145
 146
 147   template<typename InputIterator, typename OutputIterator, typename Comparator>
 148   struct difference_func
 149   {
 150     typedef std::iterator_traits<InputIterator> traits_type;
 151     typedef typename traits_type::difference_type difference_type;
 152     typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
 153
 154     difference_func(Comparator c) : comp(c) {}
 155
 156     Comparator comp;
 157
 158     inline OutputIterator
 159     invoke(InputIterator a, InputIterator b, InputIterator c, InputIterator d,
 160            OutputIterator r) const
 161     {
 162       while (a != b && c != d)
 163         {
 164           if (comp(*a, *c))
 165             {
 166               *r = *a;
 167               ++a;
 168               ++r;
 169             }
 170           else if (comp(*c, *a))
 171             { ++c; }
 172           else
 173             {
 174               ++a;
 175               ++c;
 176             }
 177         }
 178       return std::copy(a, b, r);
 179     }
 180
 181     inline difference_type
 182     count(InputIterator a, InputIterator b, 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, typename OutputIterator, typename Comparator>
 213   struct intersection_func
 214   {
 215     typedef std::iterator_traits<InputIterator> traits_type;
 216     typedef typename traits_type::difference_type difference_type;
 217     typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
 218
 219     intersection_func(Comparator c) : comp(c) {}
 220
 221     Comparator comp;
 222
 223     inline OutputIterator
 224     invoke(InputIterator a, InputIterator b, InputIterator c, InputIterator d,
 225            OutputIterator r) const
 226     {
 227       while (a != b && c != d)
 228         {
 229           if (comp(*a, *c))
 230             { ++a; }
 231           else if (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     inline difference_type
 246     count(InputIterator a, InputIterator b, InputIterator c, InputIterator d) const
 247     {
 248       difference_type counter = 0;
 249
 250       while (a != b && c != d)
 251         {
 252           if (comp(*a, *c))
 253             { ++a; }
 254           else if (comp(*c, *a))
 255             { ++c; }
 256           else
 257             {
 258               ++a;
 259               ++c;
 260               ++counter;
 261             }
 262         }
 263
 264       return counter;
 265     }
 266
 267     inline OutputIterator
 268     first_empty(InputIterator c, InputIterator d, OutputIterator out) const
 269     { return out; }
 270
 271     inline OutputIterator
 272     second_empty(InputIterator a, InputIterator b, OutputIterator out) const
 273     { return out; }
 274   };
 275
 276   template<class InputIterator, class OutputIterator, class Comparator>
 277   struct union_func
 278   {
 279     typedef typename std::iterator_traits<InputIterator>::difference_type difference_type;
 280
 281     union_func(Comparator c) : comp(c) {}
 282
 283     Comparator comp;
 284
 285     inline OutputIterator
 286     invoke(InputIterator a, const InputIterator b, InputIterator c,
 287            const InputIterator d, OutputIterator r) const
 288     {
 289       while (a != b && c != d)
 290         {
 291           if (comp(*a, *c))
 292             {
 293               *r = *a;
 294               ++a;
 295             }
 296           else if (comp(*c, *a))
 297             {
 298               *r = *c;
 299               ++c;
 300             }
 301           else
 302             {
 303               *r = *a;
 304               ++a;
 305               ++c;
 306             }
 307           ++r;
 308         }
 309       return std::copy(c, d, std::copy(a, b, r));
 310     }
 311
 312     inline difference_type
 313     count(InputIterator a, const InputIterator b, InputIterator c,
 314           const InputIterator d) const
 315     {
 316       difference_type counter = 0;
 317
 318       while (a != b && c != d)
 319         {
 320           if (comp(*a, *c))
 321             { ++a; }
 322           else if (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     inline OutputIterator
 338     first_empty(InputIterator c, InputIterator d, OutputIterator out) const
 339     { return std::copy(c, d, out); }
 340
 341     inline OutputIterator
 342     second_empty(InputIterator a, InputIterator b, OutputIterator out) const
 343     { return std::copy(a, b, out); }
 344   };
 345
 346   template<typename InputIterator, typename OutputIterator, typename Operation>
 347   OutputIterator
 348   parallel_set_operation(InputIterator begin1, InputIterator end1,
 349                          InputIterator begin2, InputIterator end2,
 350                          OutputIterator result, Operation op)
 351   {
 352     _GLIBCXX_CALL((end1 - begin1) + (end2 - begin2))
 353
 354     typedef std::iterator_traits<InputIterator> traits_type;
 355     typedef typename traits_type::difference_type difference_type;
 356     typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
 357
 358
 359     if (begin1 == end1)
 360       return op.first_empty(begin2, end2, result);
 361
 362     if (begin2 == end2)
 363       return op.second_empty(begin1, end1, result);
 364
 365     const difference_type size = (end1 - begin1) + (end2 - begin2);
 366
 367     thread_index_t num_threads = std::min<difference_type>(std::min(end1 - begin1, end2 - begin2), get_max_threads());
 368
 369     difference_type borders[num_threads + 2];
 370     equally_split(size, num_threads + 1, borders);
 371
 372     const iterator_pair sequence[ 2 ] = { std::make_pair(begin1, end1), std::make_pair(begin2, end2) } ;
 373
 374     iterator_pair block_begins[num_threads + 1];
 375
 376     // Very start.
 377     block_begins[0] = std::make_pair(begin1, begin2);
 378     difference_type length[num_threads];
 379
 380     OutputIterator return_value = result;
 381
 382 #pragma omp parallel num_threads(num_threads)
 383     {
 384       Timing<sequential_tag> t;
 385
 386       t.tic();
 387
 388       // Result from multiseq_partition.
 389       InputIterator offset[2];
 390       const int iam = omp_get_thread_num();
 391
 392       const difference_type rank = borders[iam + 1];
 393
 394       multiseq_partition(sequence, sequence + 2, rank, offset, op.comp);
 395
 396       // allowed to read?
 397       // together
 398       // *(offset[ 0 ] - 1) == *offset[ 1 ]
 399       if (offset[ 0 ] != begin1 && offset[ 1 ] != end2
 400            && !op.comp(*(offset[ 0 ] - 1), *offset[ 1 ])
 401            && !op.comp(*offset[ 1 ], *(offset[ 0 ] - 1)))
 402         {
 403           // Avoid split between globally equal elements: move one to
 404           // front in first sequence.
 405           --offset[ 0 ];
 406         }
 407
 408       iterator_pair block_end = block_begins[ iam + 1 ] = iterator_pair(offset[ 0 ], offset[ 1 ]);
 409
 410       t.tic();
 411
 412       // Make sure all threads have their block_begin result written out.
 413 #pragma omp barrier
 414
 415       t.tic();
 416
 417       iterator_pair block_begin = block_begins[ iam ];
 418
 419       // Begin working for the first block, while the others except
 420       // the last start to count.
 421       if (iam == 0)
 422         {
 423           // The first thread can copy already.
 424           length[ iam ] = op.invoke(block_begin.first, block_end.first, block_begin.second, block_end.second, result) - result;
 425         }
 426       else
 427         {
 428           length[ iam ] = op.count(block_begin.first, block_end.first,
 429                                    block_begin.second, block_end.second);
 430         }
 431
 432       t.tic();
 433
 434       // Make sure everyone wrote their lengths.
 435 #pragma omp barrier
 436
 437       t.tic();
 438       OutputIterator r = result;
 439
 440       if (iam == 0)
 441         {
 442           // Do the last block.
 443           for (int i = 0; i < num_threads; ++i)
 444             r += length[i];
 445
 446           block_begin = block_begins[num_threads];
 447
 448           // Return the result iterator of the last block.
 449           return_value = op.invoke(block_begin.first, end1, block_begin.second, end2, r);
 450
 451         }
 452       else
 453         {
 454           for (int i = 0; i < iam; ++i)
 455             r += length[ i ];
 456
 457           // Reset begins for copy pass.
 458           op.invoke(block_begin.first, block_end.first,
 459                     block_begin.second, block_end.second, r);
 460         }
 461
 462       t.tic();
 463       t.print();
 464     }
 465     return return_value;
 466   }
 467
 468
 469   template<typename InputIterator, typename OutputIterator, typename Comparator>
 470   OutputIterator
 471   parallel_set_union(InputIterator begin1, InputIterator end1,
 472                      InputIterator begin2, InputIterator end2,
 473                      OutputIterator result, Comparator comp)
 474   {
 475     return parallel_set_operation(begin1, end1, begin2, end2, result,
 476                                   union_func< InputIterator, OutputIterator, Comparator>(comp));
 477   }
 478
 479   template<typename InputIterator, typename OutputIterator, typename Comparator>
 480   OutputIterator
 481   parallel_set_intersection(InputIterator begin1, InputIterator end1,
 482                             InputIterator begin2, InputIterator end2,
 483                             OutputIterator result, Comparator comp)
 484   {
 485     return parallel_set_operation(begin1, end1, begin2, end2, result,
 486                                   intersection_func<InputIterator, OutputIterator, Comparator>(comp));
 487   }
 488
 489
 490   template<typename InputIterator, typename OutputIterator>
 491   OutputIterator
 492   set_intersection(InputIterator begin1, InputIterator end1, InputIterator begin2, InputIterator end2, OutputIterator result)
 493   {
 494     typedef std::iterator_traits<InputIterator> traits_type;
 495     typedef typename traits_type::value_type value_type;
 496
 497     return set_intersection(begin1, end1, begin2, end2, result,
 498                             std::less<value_type>());
 499   }
 500
 501   template<typename InputIterator, typename OutputIterator, typename Comparator>
 502   OutputIterator
 503   parallel_set_difference(InputIterator begin1, InputIterator end1,
 504                           InputIterator begin2, InputIterator end2,
 505                           OutputIterator result, Comparator comp)
 506   {
 507     return parallel_set_operation(begin1, end1, begin2, end2, result,
 508                                   difference_func<InputIterator, OutputIterator, Comparator>(comp));
 509   }
 510
 511   template<typename InputIterator, typename OutputIterator, typename Comparator>
 512   OutputIterator
 513   parallel_set_symmetric_difference(InputIterator begin1, InputIterator end1, InputIterator begin2, InputIterator end2, OutputIterator result, Comparator comp)
 514   {
 515     return parallel_set_operation(begin1, end1, begin2, end2, result,
 516                                   symmetric_difference_func<InputIterator, OutputIterator, Comparator>(comp));
 517   }
 518
 519 }
 520
 521 #endif // _GLIBCXX_SET_ALGORITHM_
 522
 523
 524
 525
 526
 527
 528
 529