l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.4/include/parallel/set_operations.h

   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 */