set_operations.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /**
00026  * @file parallel/set_operations.h
00027  * @brief Parallel implementations of set operations for random-access
00028  * iterators.
00029  *  This file is a GNU parallel extension to the Standard C++ Library.
00030  */
00031 
00032 // Written by Marius Elvert and Felix Bondarenko.
00033 
00034 #ifndef _GLIBCXX_PARALLEL_SET_OPERATIONS_H
00035 #define _GLIBCXX_PARALLEL_SET_OPERATIONS_H 1
00036 
00037 #include <omp.h>
00038 
00039 #include <parallel/settings.h>
00040 #include <parallel/multiseq_selection.h>
00041 
00042 namespace __gnu_parallel
00043 {
00044 template<typename InputIterator, typename OutputIterator>
00045   OutputIterator
00046   copy_tail(std::pair<InputIterator, InputIterator> b,
00047             std::pair<InputIterator, InputIterator> e, OutputIterator r)
00048   {
00049     if (b.first != e.first)
00050       {
00051         do
00052           {
00053             *r++ = *b.first++;
00054           }
00055         while (b.first != e.first);
00056       }
00057     else
00058       {
00059         while (b.second != e.second)
00060           *r++ = *b.second++;
00061       }
00062     return r;
00063   }
00064 
00065 template<typename InputIterator,
00066      typename OutputIterator,
00067      typename Comparator>
00068   struct symmetric_difference_func
00069   {
00070     typedef std::iterator_traits<InputIterator> traits_type;
00071     typedef typename traits_type::difference_type difference_type;
00072     typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
00073 
00074     symmetric_difference_func(Comparator c) : comp(c) {}
00075 
00076     Comparator comp;
00077 
00078     OutputIterator
00079     invoke(InputIterator a, InputIterator b,
00080        InputIterator c, InputIterator d,
00081        OutputIterator r) const
00082     {
00083       while (a != b && c != d)
00084         {
00085           if (comp(*a, *c))
00086             {
00087               *r = *a;
00088               ++a;
00089               ++r;
00090             }
00091           else if (comp(*c, *a))
00092             {
00093               *r = *c;
00094               ++c;
00095               ++r;
00096             }
00097           else
00098             {
00099               ++a;
00100               ++c;
00101             }
00102         }
00103       return std::copy(c, d, std::copy(a, b, r));
00104     }
00105 
00106     difference_type
00107     count(InputIterator a, InputIterator b,
00108       InputIterator c, InputIterator d) const
00109     {
00110       difference_type counter = 0;
00111 
00112       while (a != b && c != d)
00113         {
00114           if (comp(*a, *c))
00115             {
00116               ++a;
00117               ++counter;
00118             }
00119           else if (comp(*c, *a))
00120             {
00121               ++c;
00122               ++counter;
00123             }
00124           else
00125             {
00126               ++a;
00127               ++c;
00128             }
00129         }
00130 
00131       return counter + (b - a) + (d - c);
00132     }
00133 
00134     OutputIterator
00135     first_empty(InputIterator c, InputIterator d, OutputIterator out) const
00136     { return std::copy(c, d, out); }
00137 
00138     OutputIterator
00139     second_empty(InputIterator a, InputIterator b, OutputIterator out) const
00140     { return std::copy(a, b, out); }
00141   };
00142 
00143 
00144 template<typename InputIterator,
00145      typename OutputIterator,
00146      typename Comparator>
00147   struct difference_func
00148   {
00149     typedef std::iterator_traits<InputIterator> traits_type;
00150     typedef typename traits_type::difference_type difference_type;
00151     typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
00152 
00153     difference_func(Comparator c) : comp(c) {}
00154 
00155     Comparator comp;
00156 
00157     OutputIterator
00158     invoke(InputIterator a, InputIterator b, InputIterator c, InputIterator d,
00159           OutputIterator r) const
00160     {
00161       while (a != b && c != d)
00162         {
00163           if (comp(*a, *c))
00164             {
00165               *r = *a;
00166               ++a;
00167               ++r;
00168             }
00169           else if (comp(*c, *a))
00170             { ++c; }
00171           else
00172             {
00173               ++a;
00174               ++c;
00175             }
00176         }
00177       return std::copy(a, b, r);
00178     }
00179 
00180     difference_type
00181     count(InputIterator a, InputIterator b,
00182       InputIterator c, InputIterator d) const
00183     {
00184       difference_type counter = 0;
00185 
00186       while (a != b && c != d)
00187         {
00188           if (comp(*a, *c))
00189             {
00190               ++a;
00191               ++counter;
00192             }
00193           else if (comp(*c, *a))
00194             { ++c; }
00195           else
00196             { ++a; ++c; }
00197         }
00198 
00199       return counter + (b - a);
00200     }
00201 
00202     inline OutputIterator
00203     first_empty(InputIterator c, InputIterator d, OutputIterator out) const
00204     { return out; }
00205 
00206     inline OutputIterator
00207     second_empty(InputIterator a, InputIterator b, OutputIterator out) const
00208     { return std::copy(a, b, out); }
00209   };
00210 
00211 
00212 template<typename InputIterator,
00213      typename OutputIterator,
00214      typename Comparator>
00215   struct intersection_func
00216   {
00217     typedef std::iterator_traits<InputIterator> traits_type;
00218     typedef typename traits_type::difference_type difference_type;
00219     typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
00220 
00221     intersection_func(Comparator c) : comp(c) {}
00222 
00223     Comparator comp;
00224 
00225     OutputIterator
00226     invoke(InputIterator a, InputIterator b, InputIterator c, InputIterator d,
00227           OutputIterator r) const
00228     {
00229       while (a != b && c != d)
00230         {
00231           if (comp(*a, *c))
00232             { ++a; }
00233           else if (comp(*c, *a))
00234             { ++c; }
00235           else
00236             {
00237               *r = *a;
00238               ++a;
00239               ++c;
00240               ++r;
00241             }
00242         }
00243 
00244       return r;
00245     }
00246 
00247     difference_type
00248     count(InputIterator a, InputIterator b,
00249       InputIterator c, InputIterator d) const
00250     {
00251       difference_type counter = 0;
00252 
00253       while (a != b && c != d)
00254         {
00255           if (comp(*a, *c))
00256             { ++a; }
00257           else if (comp(*c, *a))
00258             { ++c; }
00259           else
00260             {
00261               ++a;
00262               ++c;
00263               ++counter;
00264             }
00265         }
00266 
00267       return counter;
00268     }
00269 
00270     inline OutputIterator
00271     first_empty(InputIterator c, InputIterator d, OutputIterator out) const
00272     { return out; }
00273 
00274     inline OutputIterator
00275     second_empty(InputIterator a, InputIterator b, OutputIterator out) const
00276     { return out; }
00277   };
00278 
00279 template<class InputIterator, class OutputIterator, class Comparator>
00280   struct union_func
00281   {
00282     typedef typename std::iterator_traits<InputIterator>::difference_type
00283     difference_type;
00284 
00285     union_func(Comparator c) : comp(c) {}
00286 
00287     Comparator comp;
00288 
00289     OutputIterator
00290     invoke(InputIterator a, const InputIterator b, InputIterator c,
00291           const InputIterator d, OutputIterator r) const
00292     {
00293       while (a != b && c != d)
00294         {
00295           if (comp(*a, *c))
00296             {
00297               *r = *a;
00298               ++a;
00299             }
00300           else if (comp(*c, *a))
00301             {
00302               *r = *c;
00303               ++c;
00304             }
00305           else
00306             {
00307               *r = *a;
00308               ++a;
00309               ++c;
00310             }
00311           ++r;
00312         }
00313       return std::copy(c, d, std::copy(a, b, r));
00314     }
00315 
00316     difference_type
00317     count(InputIterator a, InputIterator b,
00318       InputIterator c, InputIterator d) const
00319     {
00320       difference_type counter = 0;
00321 
00322       while (a != b && c != d)
00323         {
00324           if (comp(*a, *c))
00325             { ++a; }
00326           else if (comp(*c, *a))
00327             { ++c; }
00328           else
00329             {
00330               ++a;
00331               ++c;
00332             }
00333           ++counter;
00334         }
00335 
00336       counter += (b - a);
00337       counter += (d - c);
00338       return counter;
00339     }
00340 
00341     inline OutputIterator
00342     first_empty(InputIterator c, InputIterator d, OutputIterator out) const
00343     { return std::copy(c, d, out); }
00344 
00345     inline OutputIterator
00346     second_empty(InputIterator a, InputIterator b, OutputIterator out) const
00347     { return std::copy(a, b, out); }
00348   };
00349 
00350 template<typename InputIterator,
00351      typename OutputIterator,
00352      typename Operation>
00353   OutputIterator
00354   parallel_set_operation(InputIterator begin1, InputIterator end1,
00355                          InputIterator begin2, InputIterator end2,
00356                          OutputIterator result, Operation op)
00357   {
00358     _GLIBCXX_CALL((end1 - begin1) + (end2 - begin2))
00359 
00360     typedef std::iterator_traits<InputIterator> traits_type;
00361     typedef typename traits_type::difference_type difference_type;
00362     typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
00363 
00364     if (begin1 == end1)
00365       return op.first_empty(begin2, end2, result);
00366 
00367     if (begin2 == end2)
00368       return op.second_empty(begin1, end1, result);
00369 
00370     const difference_type size = (end1 - begin1) + (end2 - begin2);
00371 
00372     const iterator_pair sequence[ 2 ] =
00373         { std::make_pair(begin1, end1), std::make_pair(begin2, end2) } ;
00374     OutputIterator return_value = result;
00375     difference_type *borders;
00376     iterator_pair *block_begins;
00377     difference_type* lengths;
00378 
00379     thread_index_t num_threads =
00380         std::min<difference_type>(get_max_threads(),
00381             std::min(end1 - begin1, end2 - begin2));
00382 
00383 #   pragma omp parallel num_threads(num_threads)
00384       {
00385 #       pragma omp single
00386           {
00387             num_threads = omp_get_num_threads();
00388 
00389             borders = new difference_type[num_threads + 2];
00390             equally_split(size, num_threads + 1, borders);
00391             block_begins = new iterator_pair[num_threads + 1];
00392             // Very start.
00393             block_begins[0] = std::make_pair(begin1, begin2);
00394             lengths = new difference_type[num_threads];
00395           } //single
00396 
00397         thread_index_t iam = omp_get_thread_num();
00398 
00399         // Result from multiseq_partition.
00400         InputIterator offset[2];
00401         const difference_type rank = borders[iam + 1];
00402 
00403         multiseq_partition(sequence, sequence + 2, rank, offset, op.comp);
00404 
00405         // allowed to read?
00406         // together
00407         // *(offset[ 0 ] - 1) == *offset[ 1 ]
00408         if (offset[ 0 ] != begin1 && offset[ 1 ] != end2
00409             && !op.comp(*(offset[ 0 ] - 1), *offset[ 1 ])
00410             && !op.comp(*offset[ 1 ], *(offset[ 0 ] - 1)))
00411           {
00412             // Avoid split between globally equal elements: move one to
00413             // front in first sequence.
00414             --offset[ 0 ];
00415           }
00416 
00417         iterator_pair block_end = block_begins[ iam + 1 ] =
00418             iterator_pair(offset[ 0 ], offset[ 1 ]);
00419 
00420         // Make sure all threads have their block_begin result written out.
00421 #       pragma omp barrier
00422 
00423         iterator_pair block_begin = block_begins[ iam ];
00424 
00425         // Begin working for the first block, while the others except
00426         // the last start to count.
00427         if (iam == 0)
00428           {
00429             // The first thread can copy already.
00430             lengths[ iam ] = op.invoke(block_begin.first, block_end.first,
00431                                        block_begin.second, block_end.second,
00432                                        result)
00433                               - result;
00434           }
00435         else
00436           {
00437             lengths[ iam ] = op.count(block_begin.first, block_end.first,
00438                         block_begin.second, block_end.second);
00439           }
00440 
00441         // Make sure everyone wrote their lengths.
00442 #       pragma omp barrier
00443 
00444         OutputIterator r = result;
00445 
00446         if (iam == 0)
00447           {
00448             // Do the last block.
00449             for (int i = 0; i < num_threads; ++i)
00450               r += lengths[i];
00451 
00452             block_begin = block_begins[num_threads];
00453 
00454             // Return the result iterator of the last block.
00455             return_value = op.invoke(
00456                 block_begin.first, end1, block_begin.second, end2, r);
00457 
00458           }
00459         else
00460           {
00461             for (int i = 0; i < iam; ++i)
00462               r += lengths[ i ];
00463 
00464             // Reset begins for copy pass.
00465             op.invoke(block_begin.first, block_end.first,
00466                   block_begin.second, block_end.second, r);
00467           }
00468       }
00469     return return_value;
00470   }
00471 
00472 
00473 template<typename InputIterator,
00474      typename OutputIterator,
00475      typename Comparator>
00476   inline OutputIterator
00477   parallel_set_union(InputIterator begin1, InputIterator end1,
00478                      InputIterator begin2, InputIterator end2,
00479                      OutputIterator result, Comparator comp)
00480   {
00481     return parallel_set_operation(begin1, end1, begin2, end2, result,
00482         union_func< InputIterator, OutputIterator, Comparator>(comp));
00483   }
00484 
00485 template<typename InputIterator,
00486      typename OutputIterator,
00487      typename Comparator>
00488   inline OutputIterator
00489   parallel_set_intersection(InputIterator begin1, InputIterator end1,
00490                             InputIterator begin2, InputIterator end2,
00491                             OutputIterator result, Comparator comp)
00492   {
00493     return parallel_set_operation(begin1, end1, begin2, end2, result,
00494         intersection_func<InputIterator, OutputIterator, Comparator>(comp));
00495   }
00496 
00497 template<typename InputIterator,
00498      typename OutputIterator,
00499      typename Comparator>
00500   inline OutputIterator
00501   parallel_set_difference(InputIterator begin1, InputIterator end1,
00502                           InputIterator begin2, InputIterator end2,
00503                           OutputIterator result, Comparator comp)
00504   {
00505     return parallel_set_operation(begin1, end1, begin2, end2, result,
00506         difference_func<InputIterator, OutputIterator, Comparator>(comp));
00507   }
00508 
00509 template<typename InputIterator,
00510      typename OutputIterator,
00511      typename Comparator>
00512   inline OutputIterator
00513   parallel_set_symmetric_difference(InputIterator begin1, InputIterator end1,
00514                                     InputIterator begin2, InputIterator end2,
00515                                     OutputIterator result, Comparator comp)
00516   {
00517     return parallel_set_operation(begin1, end1, begin2, end2, result,
00518         symmetric_difference_func<InputIterator, OutputIterator, Comparator>
00519             (comp));
00520   }
00521 
00522 }
00523 
00524 #endif /* _GLIBCXX_PARALLEL_SET_OPERATIONS_H */

Generated on 19 Jun 2018 for libstdc++ by  doxygen 1.6.1