libstdc++
set_operations.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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 _IIter, typename _OutputIterator>
00045     _OutputIterator
00046     __copy_tail(std::pair<_IIter, _IIter> __b,
00047         std::pair<_IIter, _IIter> __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 _IIter,
00066            typename _OutputIterator,
00067            typename _Compare>
00068     struct __symmetric_difference_func
00069     {
00070       typedef std::iterator_traits<_IIter> _TraitsType;
00071       typedef typename _TraitsType::difference_type _DifferenceType;
00072       typedef typename std::pair<_IIter, _IIter> _IteratorPair;
00073 
00074       __symmetric_difference_func(_Compare __comp) : _M_comp(__comp) {}
00075 
00076       _Compare _M_comp;
00077 
00078       _OutputIterator
00079       _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
00080         _OutputIterator __r) const
00081       {
00082     while (__a != __b && __c != __d)
00083           {
00084             if (_M_comp(*__a, *__c))
00085               {
00086             *__r = *__a;
00087             ++__a;
00088             ++__r;
00089               }
00090             else if (_M_comp(*__c, *__a))
00091               {
00092             *__r = *__c;
00093             ++__c;
00094             ++__r;
00095               }
00096             else
00097               {
00098             ++__a;
00099             ++__c;
00100               }
00101           }
00102     return std::copy(__c, __d, std::copy(__a, __b, __r));
00103       }
00104 
00105       _DifferenceType
00106       __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
00107       {
00108     _DifferenceType __counter = 0;
00109 
00110     while (__a != __b && __c != __d)
00111           {
00112             if (_M_comp(*__a, *__c))
00113               {
00114             ++__a;
00115             ++__counter;
00116               }
00117             else if (_M_comp(*__c, *__a))
00118               {
00119             ++__c;
00120             ++__counter;
00121               }
00122             else
00123               {
00124             ++__a;
00125             ++__c;
00126               }
00127           }
00128 
00129     return __counter + (__b - __a) + (__d - __c);
00130       }
00131 
00132       _OutputIterator
00133       __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const
00134       { return std::copy(__c, __d, __out); }
00135 
00136       _OutputIterator
00137       __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
00138       { return std::copy(__a, __b, __out); }
00139     };
00140 
00141 
00142   template<typename _IIter,
00143            typename _OutputIterator,
00144            typename _Compare>
00145     struct __difference_func
00146     {
00147       typedef std::iterator_traits<_IIter> _TraitsType;
00148       typedef typename _TraitsType::difference_type _DifferenceType;
00149       typedef typename std::pair<_IIter, _IIter> _IteratorPair;
00150 
00151       __difference_func(_Compare __comp) : _M_comp(__comp) {}
00152 
00153       _Compare _M_comp;
00154 
00155       _OutputIterator
00156       _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
00157         _OutputIterator __r) const
00158       {
00159     while (__a != __b && __c != __d)
00160           {
00161             if (_M_comp(*__a, *__c))
00162               {
00163             *__r = *__a;
00164             ++__a;
00165             ++__r;
00166               }
00167             else if (_M_comp(*__c, *__a))
00168               { ++__c; }
00169             else
00170               {
00171             ++__a;
00172             ++__c;
00173               }
00174           }
00175     return std::copy(__a, __b, __r);
00176       }
00177 
00178       _DifferenceType
00179       __count(_IIter __a, _IIter __b,
00180           _IIter __c, _IIter __d) const
00181       {
00182     _DifferenceType __counter = 0;
00183 
00184     while (__a != __b && __c != __d)
00185           {
00186             if (_M_comp(*__a, *__c))
00187               {
00188             ++__a;
00189             ++__counter;
00190               }
00191             else if (_M_comp(*__c, *__a))
00192               { ++__c; }
00193             else
00194               { ++__a; ++__c; }
00195           }
00196 
00197     return __counter + (__b - __a);
00198       }
00199 
00200       _OutputIterator
00201       __first_empty(_IIter, _IIter, _OutputIterator __out) const
00202       { return __out; }
00203 
00204       _OutputIterator
00205       __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
00206       { return std::copy(__a, __b, __out); }
00207     };
00208 
00209 
00210   template<typename _IIter,
00211            typename _OutputIterator,
00212            typename _Compare>
00213     struct __intersection_func
00214     {
00215       typedef std::iterator_traits<_IIter> _TraitsType;
00216       typedef typename _TraitsType::difference_type _DifferenceType;
00217       typedef typename std::pair<_IIter, _IIter> _IteratorPair;
00218 
00219       __intersection_func(_Compare __comp) : _M_comp(__comp) {}
00220 
00221       _Compare _M_comp;
00222 
00223       _OutputIterator
00224       _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,
00225         _OutputIterator __r) const
00226       {
00227     while (__a != __b && __c != __d)
00228           {
00229             if (_M_comp(*__a, *__c))
00230               { ++__a; }
00231             else if (_M_comp(*__c, *__a))
00232               { ++__c; }
00233             else
00234               {
00235             *__r = *__a;
00236             ++__a;
00237             ++__c;
00238             ++__r;
00239               }
00240           }
00241 
00242     return __r;
00243       }
00244 
00245       _DifferenceType
00246       __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
00247       {
00248     _DifferenceType __counter = 0;
00249 
00250     while (__a != __b && __c != __d)
00251           {
00252             if (_M_comp(*__a, *__c))
00253               { ++__a; }
00254             else if (_M_comp(*__c, *__a))
00255               { ++__c; }
00256             else
00257               {
00258             ++__a;
00259             ++__c;
00260             ++__counter;
00261               }
00262           }
00263 
00264     return __counter;
00265       }
00266 
00267       _OutputIterator
00268       __first_empty(_IIter, _IIter, _OutputIterator __out) const
00269       { return __out; }
00270 
00271       _OutputIterator
00272       __second_empty(_IIter, _IIter, _OutputIterator __out) const
00273       { return __out; }
00274     };
00275 
00276   template<class _IIter, class _OutputIterator, class _Compare>
00277     struct __union_func
00278     {
00279       typedef typename std::iterator_traits<_IIter>::difference_type
00280       _DifferenceType;
00281 
00282       __union_func(_Compare __comp) : _M_comp(__comp) {}
00283 
00284       _Compare _M_comp;
00285 
00286       _OutputIterator
00287       _M_invoke(_IIter __a, const _IIter __b, _IIter __c,
00288         const _IIter __d, _OutputIterator __r) const
00289       {
00290     while (__a != __b && __c != __d)
00291           {
00292             if (_M_comp(*__a, *__c))
00293               {
00294             *__r = *__a;
00295             ++__a;
00296               }
00297             else if (_M_comp(*__c, *__a))
00298               {
00299             *__r = *__c;
00300             ++__c;
00301               }
00302             else
00303               {
00304             *__r = *__a;
00305             ++__a;
00306             ++__c;
00307               }
00308             ++__r;
00309           }
00310     return std::copy(__c, __d, std::copy(__a, __b, __r));
00311       }
00312 
00313       _DifferenceType
00314       __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const
00315       {
00316     _DifferenceType __counter = 0;
00317 
00318     while (__a != __b && __c != __d)
00319           {
00320             if (_M_comp(*__a, *__c))
00321               { ++__a; }
00322             else if (_M_comp(*__c, *__a))
00323               { ++__c; }
00324             else
00325               {
00326             ++__a;
00327             ++__c;
00328               }
00329             ++__counter;
00330           }
00331 
00332     __counter += (__b - __a);
00333     __counter += (__d - __c);
00334     return __counter;
00335       }
00336 
00337       _OutputIterator
00338       __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const
00339       { return std::copy(__c, __d, __out); }
00340 
00341       _OutputIterator
00342       __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
00343       { return std::copy(__a, __b, __out); }
00344     };
00345 
00346   template<typename _IIter,
00347            typename _OutputIterator,
00348            typename _Operation>
00349     _OutputIterator
00350     __parallel_set_operation(_IIter __begin1, _IIter __end1,
00351                  _IIter __begin2, _IIter __end2,
00352                  _OutputIterator __result, _Operation __op)
00353     {
00354       _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2))
00355 
00356       typedef std::iterator_traits<_IIter> _TraitsType;
00357       typedef typename _TraitsType::difference_type _DifferenceType;
00358       typedef typename std::pair<_IIter, _IIter> _IteratorPair;
00359 
00360       if (__begin1 == __end1)
00361     return __op.__first_empty(__begin2, __end2, __result);
00362 
00363       if (__begin2 == __end2)
00364     return __op.__second_empty(__begin1, __end1, __result);
00365 
00366       const _DifferenceType __size = (__end1 - __begin1) + (__end2 - __begin2);
00367 
00368       const _IteratorPair __sequence[2] = { std::make_pair(__begin1, __end1),
00369                         std::make_pair(__begin2, __end2) };
00370       _OutputIterator __return_value = __result;
00371       _DifferenceType *__borders;
00372       _IteratorPair *__block_begins;
00373       _DifferenceType* __lengths;
00374 
00375       _ThreadIndex __num_threads =
00376           std::min<_DifferenceType>(__get_max_threads(),
00377               std::min(__end1 - __begin1, __end2 - __begin2));
00378 
00379 #     pragma omp parallel num_threads(__num_threads)
00380       {
00381 #       pragma omp single
00382     {
00383       __num_threads = omp_get_num_threads();
00384 
00385       __borders = new _DifferenceType[__num_threads + 2];
00386       __equally_split(__size, __num_threads + 1, __borders);
00387       __block_begins = new _IteratorPair[__num_threads + 1];
00388       // Very __start.
00389       __block_begins[0] = std::make_pair(__begin1, __begin2);
00390       __lengths = new _DifferenceType[__num_threads];
00391     } //single
00392 
00393     _ThreadIndex __iam = omp_get_thread_num();
00394 
00395     // _Result from multiseq_partition.
00396     _IIter __offset[2];
00397     const _DifferenceType __rank = __borders[__iam + 1];
00398 
00399     multiseq_partition(__sequence, __sequence + 2,
00400                __rank, __offset, __op._M_comp);
00401 
00402     // allowed to read?
00403     // together
00404     // *(__offset[ 0 ] - 1) == *__offset[ 1 ]
00405     if (__offset[ 0 ] != __begin1 && __offset[1] != __end2
00406         && !__op._M_comp(*(__offset[0] - 1), *__offset[1])
00407         && !__op._M_comp(*__offset[1], *(__offset[0] - 1)))
00408       {
00409         // Avoid split between globally equal elements: move one to
00410         // front in first sequence.
00411               --__offset[0];
00412       }
00413 
00414     _IteratorPair __block_end = __block_begins[__iam + 1] =
00415       _IteratorPair(__offset[0], __offset[1]);
00416 
00417     // Make sure all threads have their block_begin result written out.
00418 #       pragma omp barrier
00419 
00420     _IteratorPair __block_begin = __block_begins[__iam];
00421 
00422     // Begin working for the first block, while the others except
00423     // the last start to count.
00424     if (__iam == 0)
00425       {
00426         // The first thread can copy already.
00427         __lengths[ __iam ] =
00428           __op._M_invoke(__block_begin.first, __block_end.first,
00429                  __block_begin.second, __block_end.second,
00430                  __result) - __result;
00431       }
00432     else
00433       {
00434         __lengths[ __iam ] =
00435           __op.__count(__block_begin.first, __block_end.first,
00436                __block_begin.second, __block_end.second);
00437       }
00438 
00439     // Make sure everyone wrote their lengths.
00440 #       pragma omp barrier
00441 
00442     _OutputIterator __r = __result;
00443 
00444     if (__iam == 0)
00445       {
00446         // Do the last block.
00447         for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
00448           __r += __lengths[__i];
00449 
00450         __block_begin = __block_begins[__num_threads];
00451 
00452         // Return the result iterator of the last block.
00453         __return_value =
00454           __op._M_invoke(__block_begin.first, __end1,
00455                  __block_begin.second, __end2, __r);
00456 
00457       }
00458           else
00459             {
00460               for (_ThreadIndex __i = 0; __i < __iam; ++__i)
00461             __r += __lengths[ __i ];
00462 
00463               // Reset begins for copy pass.
00464               __op._M_invoke(__block_begin.first, __block_end.first,
00465                  __block_begin.second, __block_end.second, __r);
00466             }
00467     }
00468       return __return_value;
00469     }
00470 
00471   template<typename _IIter,
00472            typename _OutputIterator,
00473            typename _Compare>
00474     inline _OutputIterator
00475     __parallel_set_union(_IIter __begin1, _IIter __end1,
00476              _IIter __begin2, _IIter __end2,
00477              _OutputIterator __result, _Compare __comp)
00478     {
00479       return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
00480                       __result,
00481                       __union_func< _IIter, _OutputIterator,
00482                       _Compare>(__comp));
00483     }
00484 
00485   template<typename _IIter,
00486            typename _OutputIterator,
00487            typename _Compare>
00488     inline _OutputIterator
00489     __parallel_set_intersection(_IIter __begin1, _IIter __end1,
00490                             _IIter __begin2, _IIter __end2,
00491                             _OutputIterator __result, _Compare __comp)
00492     {
00493       return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
00494                       __result,
00495                       __intersection_func<_IIter,
00496                       _OutputIterator, _Compare>(__comp));
00497     }
00498 
00499   template<typename _IIter,
00500            typename _OutputIterator,
00501            typename _Compare>
00502     inline _OutputIterator
00503     __parallel_set_difference(_IIter __begin1, _IIter __end1,
00504                               _IIter __begin2, _IIter __end2,
00505                               _OutputIterator __result, _Compare __comp)
00506     {
00507       return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
00508                       __result,
00509                       __difference_func<_IIter,
00510                       _OutputIterator, _Compare>(__comp));
00511     }
00512 
00513   template<typename _IIter,
00514            typename _OutputIterator,
00515            typename _Compare>
00516     inline _OutputIterator
00517     __parallel_set_symmetric_difference(_IIter __begin1, _IIter __end1,
00518                                     _IIter __begin2, _IIter __end2,
00519                                     _OutputIterator __result,
00520                                     _Compare __comp)
00521     {
00522       return __parallel_set_operation(__begin1, __end1, __begin2, __end2,
00523                       __result,
00524                       __symmetric_difference_func<_IIter,
00525                       _OutputIterator, _Compare>(__comp));
00526     }
00527 }
00528 
00529 #endif /* _GLIBCXX_PARALLEL_SET_OPERATIONS_H */