set_operations.h

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

Generated on Wed Dec 31 12:48:59 2008 for libstdc++ by  doxygen 1.5.6