libstdc++-v3/include/parallel/merge.h

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