libstdc++-v3/include/parallel/merge.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 /** @file parallel/merge.h
  26  *  @brief Parallel implementation of std::merge().
  27  *  This file is a GNU parallel extension to the Standard C++ Library.
  28  */
  29
  30 // Written by Johannes Singler.
  31
  32 #ifndef _GLIBCXX_PARALLEL_MERGE_H
  33 #define _GLIBCXX_PARALLEL_MERGE_H 1
  34
  35 #include <parallel/basic_iterator.h>
  36 #include <bits/stl_algo.h>
  37
  38 namespace __gnu_parallel
  39 {
  40   /** @brief Merge routine being able to merge only the @__c __max_length
  41    * smallest elements.
  42    *
  43    * The @__c __begin iterators are advanced accordingly, they might not
  44    * reach @__c __end, in contrast to the usual variant.
  45    * @param __begin1 Begin iterator of first sequence.
  46    * @param __end1 End iterator of first sequence.
  47    * @param __begin2 Begin iterator of second sequence.
  48    * @param __end2 End iterator of second sequence.
  49    * @param __target Target begin iterator.
  50    * @param __max_length Maximum number of elements to merge.
  51    * @param __comp Comparator.
  52    * @return Output end iterator. */
  53   template<typename _RAIter1, typename _RAIter2,
  54            typename _OutputIterator, typename _DifferenceTp,
  55            typename _Compare>
  56     _OutputIterator
  57     __merge_advance_usual(_RAIter1& __begin1,
  58                         _RAIter1 __end1,
  59                         _RAIter2& __begin2,
  60                         _RAIter2 __end2, _OutputIterator __target,
  61                         _DifferenceTp __max_length, _Compare __comp)
  62     {
  63       typedef _DifferenceTp _DifferenceType;
  64       while (__begin1 != __end1 && __begin2 != __end2 && __max_length > 0)
  65         {
  66           // array1[__i1] < array0[i0]
  67           if (__comp(*__begin2, *__begin1))
  68             *__target++ = *__begin2++;
  69           else
  70             *__target++ = *__begin1++;
  71           --__max_length;
  72         }
  73
  74       if (__begin1 != __end1)
  75         {
  76           __target = std::copy(__begin1, __begin1 + __max_length, __target);
  77           __begin1 += __max_length;
  78         }
  79       else
  80         {
  81           __target = std::copy(__begin2, __begin2 + __max_length, __target);
  82           __begin2 += __max_length;
  83         }
  84       return __target;
  85     }
  86
  87   /** @brief Merge routine being able to merge only the @__c __max_length
  88    * smallest elements.
  89    *
  90    * The @__c __begin iterators are advanced accordingly, they might not
  91    * reach @__c __end, in contrast to the usual variant.
  92    * Specially designed code should allow the compiler to generate
  93    * conditional moves instead of branches.
  94    * @param __begin1 Begin iterator of first sequence.
  95    * @param __end1 End iterator of first sequence.
  96    * @param __begin2 Begin iterator of second sequence.
  97    * @param __end2 End iterator of second sequence.
  98    * @param __target Target begin iterator.
  99    * @param __max_length Maximum number of elements to merge.
 100    * @param __comp Comparator.
 101    * @return Output end iterator. */
 102   template<typename _RAIter1, typename _RAIter2,
 103            typename _OutputIterator, typename _DifferenceTp,
 104            typename _Compare>
 105     _OutputIterator
 106     __merge_advance_movc(_RAIter1& __begin1,
 107                        _RAIter1 __end1,
 108                        _RAIter2& __begin2,
 109                        _RAIter2 __end2,
 110                        _OutputIterator __target,
 111                        _DifferenceTp __max_length, _Compare __comp)
 112     {
 113       typedef _DifferenceTp _DifferenceType;
 114       typedef typename std::iterator_traits<_RAIter1>::value_type
 115         value_type1;
 116       typedef typename std::iterator_traits<_RAIter2>::value_type
 117         value_type2;
 118
 119 #if _GLIBCXX_ASSERTIONS
 120       _GLIBCXX_PARALLEL_ASSERT(__max_length >= 0);
 121 #endif
 122
 123       while (__begin1 != __end1 && __begin2 != __end2 && __max_length > 0)
 124         {
 125           _RAIter1 __next1 = __begin1 + 1;
 126           _RAIter2 __next2 = __begin2 + 1;
 127           value_type1 __element1 = *__begin1;
 128           value_type2 __element2 = *__begin2;
 129
 130           if (__comp(__element2, __element1))
 131             {
 132               __element1 = __element2;
 133               __begin2 = __next2;
 134             }
 135           else
 136             __begin1 = __next1;
 137
 138           *__target = __element1;
 139
 140           ++__target;
 141           --__max_length;
 142         }
 143       if (__begin1 != __end1)
 144         {
 145           __target = std::copy(__begin1, __begin1 + __max_length, __target);
 146           __begin1 += __max_length;
 147         }
 148       else
 149         {
 150           __target = std::copy(__begin2, __begin2 + __max_length, __target);
 151           __begin2 += __max_length;
 152         }
 153       return __target;
 154     }
 155
 156   /** @brief Merge routine being able to merge only the @__c __max_length
 157    * smallest elements.
 158    *
 159    *  The @__c __begin iterators are advanced accordingly, they might not
 160    *  reach @__c __end, in contrast to the usual variant.
 161    *  Static switch on whether to use the conditional-move variant.
 162    *  @param __begin1 Begin iterator of first sequence.
 163    *  @param __end1 End iterator of first sequence.
 164    *  @param __begin2 Begin iterator of second sequence.
 165    *  @param __end2 End iterator of second sequence.
 166    *  @param __target Target begin iterator.
 167    *  @param __max_length Maximum number of elements to merge.
 168    *  @param __comp Comparator.
 169    *  @return Output end iterator. */
 170   template<typename _RAIter1, typename _RAIter2,
 171            typename _OutputIterator, typename _DifferenceTp,
 172            typename _Compare>
 173     inline _OutputIterator
 174     __merge_advance(_RAIter1& __begin1, _RAIter1 __end1,
 175                   _RAIter2& __begin2, _RAIter2 __end2,
 176                   _OutputIterator __target, _DifferenceTp __max_length,
 177                   _Compare __comp)
 178     {
 179       _GLIBCXX_CALL(__max_length)
 180
 181       return __merge_advance_movc(__begin1, __end1, __begin2, __end2, __target,
 182                                 __max_length, __comp);
 183     }
 184
 185   /** @brief Merge routine fallback to sequential in case the
 186       iterators of the two input sequences are of different type.
 187       *  @param __begin1 Begin iterator of first sequence.
 188       *  @param __end1 End iterator of first sequence.
 189       *  @param __begin2 Begin iterator of second sequence.
 190       *  @param __end2 End iterator of second sequence.
 191       *  @param __target Target begin iterator.
 192       *  @param __max_length Maximum number of elements to merge.
 193       *  @param __comp Comparator.
 194       *  @return Output end iterator. */
 195   template<typename _RAIter1, typename _RAIter2,
 196            typename _RAIter3, typename _Compare>
 197     inline _RAIter3
 198     __parallel_merge_advance(_RAIter1& __begin1,
 199                            _RAIter1 __end1,
 200                            _RAIter2& __begin2,
 201                            // different iterators, parallel implementation
 202                            // not available
 203                            _RAIter2 __end2,
 204                            _RAIter3 __target, typename
 205                            std::iterator_traits<_RAIter1>::
 206                            difference_type __max_length, _Compare __comp)
 207     { return __merge_advance(__begin1, __end1, __begin2, __end2, __target,
 208                            __max_length, __comp); }
 209
 210   /** @brief Parallel merge routine being able to merge only the @__c
 211    * __max_length smallest elements.
 212    *
 213    *  The @__c __begin iterators are advanced accordingly, they might not
 214    *  reach @__c __end, in contrast to the usual variant.
 215    *  The functionality is projected onto parallel_multiway_merge.
 216    *  @param __begin1 Begin iterator of first sequence.
 217    *  @param __end1 End iterator of first sequence.
 218    *  @param __begin2 Begin iterator of second sequence.
 219    *  @param __end2 End iterator of second sequence.
 220    *  @param __target Target begin iterator.
 221    *  @param __max_length Maximum number of elements to merge.
 222    *  @param __comp Comparator.
 223    *  @return Output end iterator.
 224    */
 225   template<typename _RAIter1, typename _RAIter3,
 226            typename _Compare>
 227     inline _RAIter3
 228     __parallel_merge_advance(_RAIter1& __begin1,
 229                            _RAIter1 __end1,
 230                            _RAIter1& __begin2,
 231                            _RAIter1 __end2,
 232                            _RAIter3 __target, typename
 233                            std::iterator_traits<_RAIter1>::
 234                            difference_type __max_length, _Compare __comp)
 235     {
 236       typedef typename
 237           std::iterator_traits<_RAIter1>::value_type _ValueType;
 238       typedef typename std::iterator_traits<_RAIter1>::
 239         difference_type _DifferenceType1 /* == difference_type2 */;
 240       typedef typename std::iterator_traits<_RAIter3>::
 241         difference_type _DifferenceType3;
 242       typedef typename std::pair<_RAIter1, _RAIter1>
 243         _IteratorPair;
 244
 245       _IteratorPair
 246         seqs[2] = { std::make_pair(__begin1, __end1),
 247                     std::make_pair(__begin2, __end2) };
 248       _RAIter3
 249         __target_end = parallel_multiway_merge
 250           < /* __stable = */ true, /* __sentinels = */ false>(
 251             seqs, seqs + 2, __target,
 252             multiway_merge_exact_splitting
 253               < /* __stable = */ true, _IteratorPair*,
 254                 _Compare, _DifferenceType1>,
 255             __max_length, __comp, omp_get_max_threads());
 256
 257       return __target_end;
 258     }
 259 }       //namespace __gnu_parallel
 260
 261 #endif /* _GLIBCXX_PARALLEL_MERGE_H */