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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 /** @file parallel/merge.h
  32  *  @brief Parallel implementation of std::merge().
  33  *  This file is a GNU parallel extension to the Standard C++ Library.
  34  */
  35
  36 // Written by Johannes Singler.
  37
  38 #ifndef _GLIBCXX_PARALLEL_MERGE_H
  39 #define _GLIBCXX_PARALLEL_MERGE_H 1
  40
  41 #include <parallel/basic_iterator.h>
  42 #include <bits/stl_algo.h>
  43
  44 namespace __gnu_parallel
  45 {
  46   /** @brief Merge routine being able to merge only the @c max_length
  47    * smallest elements.
  48    *
  49    * The @c begin iterators are advanced accordingly, they might not
  50    * reach @c end, in contrast to the usual variant.
  51    * @param begin1 Begin iterator of first sequence.
  52    * @param end1 End iterator of first sequence.
  53    * @param begin2 Begin iterator of second sequence.
  54    * @param end2 End iterator of second sequence.
  55    * @param target Target begin iterator.
  56    * @param max_length Maximum number of elements to merge.
  57    * @param comp Comparator.
  58    * @return Output end iterator. */
  59   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
  60            typename OutputIterator, typename _DifferenceTp,
  61            typename Comparator>
  62     OutputIterator
  63     merge_advance_usual(RandomAccessIterator1& begin1,
  64                         RandomAccessIterator1 end1,
  65                         RandomAccessIterator2& begin2,
  66                         RandomAccessIterator2 end2, OutputIterator target,
  67                         _DifferenceTp max_length, Comparator comp)
  68     {
  69       typedef _DifferenceTp difference_type;
  70       while (begin1 != end1 && begin2 != end2 && max_length > 0)
  71         {
  72           // array1[i1] < array0[i0]
  73           if (comp(*begin2, *begin1))
  74             *target++ = *begin2++;
  75           else
  76             *target++ = *begin1++;
  77           --max_length;
  78         }
  79
  80       if (begin1 != end1)
  81         {
  82           target = std::copy(begin1, begin1 + max_length, target);
  83           begin1 += max_length;
  84         }
  85       else
  86         {
  87           target = std::copy(begin2, begin2 + max_length, target);
  88           begin2 += max_length;
  89         }
  90       return target;
  91     }
  92
  93   /** @brief Merge routine being able to merge only the @c max_length
  94    * smallest elements.
  95    *
  96    * The @c begin iterators are advanced accordingly, they might not
  97    * reach @c end, in contrast to the usual variant.
  98    * Specially designed code should allow the compiler to generate
  99    * conditional moves instead of branches.
 100    * @param begin1 Begin iterator of first sequence.
 101    * @param end1 End iterator of first sequence.
 102    * @param begin2 Begin iterator of second sequence.
 103    * @param end2 End iterator of second sequence.
 104    * @param target Target begin iterator.
 105    * @param max_length Maximum number of elements to merge.
 106    * @param comp Comparator.
 107    * @return Output end iterator. */
 108   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
 109            typename OutputIterator, typename _DifferenceTp,
 110            typename Comparator>
 111     OutputIterator
 112     merge_advance_movc(RandomAccessIterator1& begin1,
 113                        RandomAccessIterator1 end1,
 114                        RandomAccessIterator2& begin2,
 115                        RandomAccessIterator2 end2,
 116                        OutputIterator target,
 117                        _DifferenceTp max_length, Comparator comp)
 118     {
 119       typedef _DifferenceTp difference_type;
 120       typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
 121         value_type1;
 122       typedef typename std::iterator_traits<RandomAccessIterator2>::value_type
 123         value_type2;
 124
 125 #if _GLIBCXX_ASSERTIONS
 126       _GLIBCXX_PARALLEL_ASSERT(max_length >= 0);
 127 #endif
 128
 129       while (begin1 != end1 && begin2 != end2 && max_length > 0)
 130         {
 131           RandomAccessIterator1 next1 = begin1 + 1;
 132           RandomAccessIterator2 next2 = begin2 + 1;
 133           value_type1 element1 = *begin1;
 134           value_type2 element2 = *begin2;
 135
 136           if (comp(element2, element1))
 137             {
 138               element1 = element2;
 139               begin2 = next2;
 140             }
 141           else
 142             begin1 = next1;
 143
 144           *target = element1;
 145
 146           ++target;
 147           --max_length;
 148         }
 149       if (begin1 != end1)
 150         {
 151           target = std::copy(begin1, begin1 + max_length, target);
 152           begin1 += max_length;
 153         }
 154       else
 155         {
 156           target = std::copy(begin2, begin2 + max_length, target);
 157           begin2 += max_length;
 158         }
 159       return target;
 160     }
 161
 162   /** @brief Merge routine being able to merge only the @c max_length
 163    * smallest elements.
 164    *
 165    *  The @c begin iterators are advanced accordingly, they might not
 166    *  reach @c end, in contrast to the usual variant.
 167    *  Static switch on whether to use the conditional-move variant.
 168    *  @param begin1 Begin iterator of first sequence.
 169    *  @param end1 End iterator of first sequence.
 170    *  @param begin2 Begin iterator of second sequence.
 171    *  @param end2 End iterator of second sequence.
 172    *  @param target Target begin iterator.
 173    *  @param max_length Maximum number of elements to merge.
 174    *  @param comp Comparator.
 175    *  @return Output end iterator. */
 176   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
 177            typename OutputIterator, typename _DifferenceTp,
 178            typename Comparator>
 179     inline OutputIterator
 180     merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
 181                   RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
 182                   OutputIterator target, _DifferenceTp max_length,
 183                   Comparator comp)
 184     {
 185       _GLIBCXX_CALL(max_length)
 186
 187       return merge_advance_movc(begin1, end1, begin2, end2, target,
 188                                 max_length, comp);
 189     }
 190
 191   /** @brief Merge routine fallback to sequential in case the
 192       iterators of the two input sequences are of different type.
 193       *  @param begin1 Begin iterator of first sequence.
 194       *  @param end1 End iterator of first sequence.
 195       *  @param begin2 Begin iterator of second sequence.
 196       *  @param end2 End iterator of second sequence.
 197       *  @param target Target begin iterator.
 198       *  @param max_length Maximum number of elements to merge.
 199       *  @param comp Comparator.
 200       *  @return Output end iterator. */
 201   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
 202            typename RandomAccessIterator3, typename Comparator>
 203     inline RandomAccessIterator3
 204     parallel_merge_advance(RandomAccessIterator1& begin1,
 205                            RandomAccessIterator1 end1,
 206                            RandomAccessIterator2& begin2,
 207                            // different iterators, parallel implementation
 208                            // not available
 209                            RandomAccessIterator2 end2,
 210                            RandomAccessIterator3 target, typename
 211                            std::iterator_traits<RandomAccessIterator1>::
 212                            difference_type max_length, Comparator comp)
 213     { return merge_advance(begin1, end1, begin2, end2, target,
 214                            max_length, comp); }
 215
 216   /** @brief Parallel merge routine being able to merge only the @c
 217    * max_length smallest elements.
 218    *
 219    *  The @c begin iterators are advanced accordingly, they might not
 220    *  reach @c end, in contrast to the usual variant.
 221    *  The functionality is projected onto parallel_multiway_merge.
 222    *  @param begin1 Begin iterator of first sequence.
 223    *  @param end1 End iterator of first sequence.
 224    *  @param begin2 Begin iterator of second sequence.
 225    *  @param end2 End iterator of second sequence.
 226    *  @param target Target begin iterator.
 227    *  @param max_length Maximum number of elements to merge.
 228    *  @param comp Comparator.
 229    *  @return Output end iterator.
 230    */
 231   template<typename RandomAccessIterator1, typename RandomAccessIterator3,
 232            typename Comparator>
 233     inline RandomAccessIterator3
 234     parallel_merge_advance(RandomAccessIterator1& begin1,
 235                            RandomAccessIterator1 end1,
 236                            RandomAccessIterator1& begin2,
 237                            RandomAccessIterator1 end2,
 238                            RandomAccessIterator3 target, typename
 239                            std::iterator_traits<RandomAccessIterator1>::
 240                            difference_type max_length, Comparator comp)
 241     {
 242       typedef typename
 243           std::iterator_traits<RandomAccessIterator1>::value_type value_type;
 244       typedef typename std::iterator_traits<RandomAccessIterator1>::
 245         difference_type difference_type1 /* == difference_type2 */;
 246       typedef typename std::iterator_traits<RandomAccessIterator3>::
 247         difference_type difference_type3;
 248       typedef typename std::pair<RandomAccessIterator1, RandomAccessIterator1>
 249         iterator_pair;
 250
 251       iterator_pair
 252         seqs[2] = { std::make_pair(begin1, end1),
 253                     std::make_pair(begin2, end2) };
 254       RandomAccessIterator3
 255         target_end = parallel_multiway_merge
 256           < /* stable = */ true, /* sentinels = */ false>(
 257             seqs, seqs + 2, target,
 258             multiway_merge_exact_splitting
 259               < /* stable = */ true, iterator_pair*,
 260                 Comparator, difference_type1>,
 261             max_length, comp, omp_get_max_threads());
 262
 263       return target_end;
 264     }
 265 }       //namespace __gnu_parallel
 266
 267 #endif