contrib/gcc-4.4/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 RandomAccessIterator1, typename RandomAccessIterator2,
  54            typename OutputIterator, typename _DifferenceTp,
  55            typename Comparator>
  56     OutputIterator
  57     merge_advance_usual(RandomAccessIterator1& begin1,
  58                         RandomAccessIterator1 end1,
  59                         RandomAccessIterator2& begin2,
  60                         RandomAccessIterator2 end2, OutputIterator target,
  61                         _DifferenceTp max_length, Comparator comp)
  62     {
  63       typedef _DifferenceTp difference_type;
  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 RandomAccessIterator1, typename RandomAccessIterator2,
 103            typename OutputIterator, typename _DifferenceTp,
 104            typename Comparator>
 105     OutputIterator
 106     merge_advance_movc(RandomAccessIterator1& begin1,
 107                        RandomAccessIterator1 end1,
 108                        RandomAccessIterator2& begin2,
 109                        RandomAccessIterator2 end2,
 110                        OutputIterator target,
 111                        _DifferenceTp max_length, Comparator comp)
 112     {
 113       typedef _DifferenceTp difference_type;
 114       typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
 115         value_type1;
 116       typedef typename std::iterator_traits<RandomAccessIterator2>::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           RandomAccessIterator1 next1 = begin1 + 1;
 126           RandomAccessIterator2 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 RandomAccessIterator1, typename RandomAccessIterator2,
 171            typename OutputIterator, typename _DifferenceTp,
 172            typename Comparator>
 173     inline OutputIterator
 174     merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
 175                   RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
 176                   OutputIterator target, _DifferenceTp max_length,
 177                   Comparator 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 RandomAccessIterator1, typename RandomAccessIterator2,
 196            typename RandomAccessIterator3, typename Comparator>
 197     inline RandomAccessIterator3
 198     parallel_merge_advance(RandomAccessIterator1& begin1,
 199                            RandomAccessIterator1 end1,
 200                            RandomAccessIterator2& begin2,
 201                            // different iterators, parallel implementation
 202                            // not available
 203                            RandomAccessIterator2 end2,
 204                            RandomAccessIterator3 target, typename
 205                            std::iterator_traits<RandomAccessIterator1>::
 206                            difference_type max_length, Comparator 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 RandomAccessIterator1, typename RandomAccessIterator3,
 226            typename Comparator>
 227     inline RandomAccessIterator3
 228     parallel_merge_advance(RandomAccessIterator1& begin1,
 229                            RandomAccessIterator1 end1,
 230                            RandomAccessIterator1& begin2,
 231                            RandomAccessIterator1 end2,
 232                            RandomAccessIterator3 target, typename
 233                            std::iterator_traits<RandomAccessIterator1>::
 234                            difference_type max_length, Comparator comp)
 235     {
 236       typedef typename
 237           std::iterator_traits<RandomAccessIterator1>::value_type value_type;
 238       typedef typename std::iterator_traits<RandomAccessIterator1>::
 239         difference_type difference_type1 /* == difference_type2 */;
 240       typedef typename std::iterator_traits<RandomAccessIterator3>::
 241         difference_type difference_type3;
 242       typedef typename std::pair<RandomAccessIterator1, RandomAccessIterator1>
 243         iterator_pair;
 244
 245       iterator_pair
 246         seqs[2] = { std::make_pair(begin1, end1),
 247                     std::make_pair(begin2, end2) };
 248       RandomAccessIterator3
 249         target_end = parallel_multiway_merge
 250           < /* stable = */ true, /* sentinels = */ false>(
 251             seqs, seqs + 2, target,
 252             multiway_merge_exact_splitting
 253               < /* stable = */ true, iterator_pair*,
 254                 Comparator, difference_type1>,
 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 */