mingw/lib/gcc/mingw32/4.3.3/include/c++/parallel/set_operations.h

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