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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007-2019 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/sort.h
  26  *  @brief Parallel sorting algorithm switch.
  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_SORT_H
  33 #define _GLIBCXX_PARALLEL_SORT_H 1
  34
  35 #include <parallel/basic_iterator.h>
  36 #include <parallel/features.h>
  37 #include <parallel/parallel.h>
  38
  39 #if _GLIBCXX_PARALLEL_ASSERTIONS
  40 #include <parallel/checkers.h>
  41 #endif
  42
  43 #if _GLIBCXX_MERGESORT
  44 #include <parallel/multiway_mergesort.h>
  45 #endif
  46
  47 #if _GLIBCXX_QUICKSORT
  48 #include <parallel/quicksort.h>
  49 #endif
  50
  51 #if _GLIBCXX_BAL_QUICKSORT
  52 #include <parallel/balanced_quicksort.h>
  53 #endif
  54
  55 namespace __gnu_parallel
  56 {
  57   //prototype
  58   template<bool __stable, typename _RAIter,
  59            typename _Compare, typename _Parallelism>
  60     void
  61     __parallel_sort(_RAIter __begin, _RAIter __end,
  62                     _Compare __comp, _Parallelism __parallelism);
  63
  64   /**
  65    *  @brief Choose multiway mergesort, splitting variant at run-time,
  66    *  for parallel sorting.
  67    *  @param __begin Begin iterator of input sequence.
  68    *  @param __end End iterator of input sequence.
  69    *  @param __comp Comparator.
  70    *  @tparam __stable Sort stable.
  71    *  @callgraph
  72    */
  73   template<bool __stable, typename _RAIter, typename _Compare>
  74     inline void
  75     __parallel_sort(_RAIter __begin, _RAIter __end,
  76                     _Compare __comp, multiway_mergesort_tag __parallelism)
  77     {
  78       _GLIBCXX_CALL(__end - __begin)
  79
  80       if(_Settings::get().sort_splitting == EXACT)
  81         parallel_sort_mwms<__stable, true>
  82           (__begin, __end, __comp, __parallelism.__get_num_threads());
  83       else
  84         parallel_sort_mwms<__stable, false>
  85           (__begin, __end, __comp, __parallelism.__get_num_threads());
  86     }
  87
  88   /**
  89    *  @brief Choose multiway mergesort with exact splitting,
  90    *  for parallel sorting.
  91    *  @param __begin Begin iterator of input sequence.
  92    *  @param __end End iterator of input sequence.
  93    *  @param __comp Comparator.
  94    *  @tparam __stable Sort stable.
  95    *  @callgraph
  96    */
  97   template<bool __stable, typename _RAIter, typename _Compare>
  98     inline void
  99     __parallel_sort(_RAIter __begin, _RAIter __end,
 100                     _Compare __comp,
 101                     multiway_mergesort_exact_tag __parallelism)
 102     {
 103       _GLIBCXX_CALL(__end - __begin)
 104
 105       parallel_sort_mwms<__stable, true>
 106         (__begin, __end, __comp, __parallelism.__get_num_threads());
 107     }
 108
 109   /**
 110    *  @brief Choose multiway mergesort with splitting by sampling,
 111    *  for parallel sorting.
 112    *  @param __begin Begin iterator of input sequence.
 113    *  @param __end End iterator of input sequence.
 114    *  @param __comp Comparator.
 115    *  @tparam __stable Sort stable.
 116    *  @callgraph
 117    */
 118   template<bool __stable, typename _RAIter, typename _Compare>
 119     inline void
 120     __parallel_sort(_RAIter __begin, _RAIter __end,
 121                     _Compare __comp,
 122                     multiway_mergesort_sampling_tag __parallelism)
 123     {
 124       _GLIBCXX_CALL(__end - __begin)
 125
 126       parallel_sort_mwms<__stable, false>
 127       (__begin, __end, __comp, __parallelism.__get_num_threads());
 128     }
 129
 130   /**
 131    *  @brief Choose quicksort for parallel sorting.
 132    *  @param __begin Begin iterator of input sequence.
 133    *  @param __end End iterator of input sequence.
 134    *  @param __comp Comparator.
 135    *  @tparam __stable Sort stable.
 136    *  @callgraph
 137    */
 138   template<bool __stable, typename _RAIter, typename _Compare>
 139     inline void
 140     __parallel_sort(_RAIter __begin, _RAIter __end,
 141                     _Compare __comp, quicksort_tag __parallelism)
 142     {
 143       _GLIBCXX_CALL(__end - __begin)
 144
 145       _GLIBCXX_PARALLEL_ASSERT(__stable == false);
 146
 147       __parallel_sort_qs(__begin, __end, __comp,
 148                          __parallelism.__get_num_threads());
 149     }
 150
 151   /**
 152    *  @brief Choose balanced quicksort for parallel sorting.
 153    *  @param __begin Begin iterator of input sequence.
 154    *  @param __end End iterator of input sequence.
 155    *  @param __comp Comparator.
 156    *  @tparam __stable Sort stable.
 157    *  @callgraph
 158    */
 159    template<bool __stable, typename _RAIter, typename _Compare>
 160      inline void
 161      __parallel_sort(_RAIter __begin, _RAIter __end,
 162                      _Compare __comp, balanced_quicksort_tag __parallelism)
 163      {
 164        _GLIBCXX_CALL(__end - __begin)
 165
 166        _GLIBCXX_PARALLEL_ASSERT(__stable == false);
 167
 168        __parallel_sort_qsb(__begin, __end, __comp,
 169                            __parallelism.__get_num_threads());
 170      }
 171
 172   /**
 173    *  @brief Choose multiway mergesort with exact splitting,
 174    *  for parallel sorting.
 175    *  @param __begin Begin iterator of input sequence.
 176    *  @param __end End iterator of input sequence.
 177    *  @param __comp Comparator.
 178    *  @tparam __stable Sort stable.
 179    *  @callgraph
 180    */
 181   template<bool __stable, typename _RAIter, typename _Compare>
 182     inline void
 183     __parallel_sort(_RAIter __begin, _RAIter __end,
 184                     _Compare __comp, default_parallel_tag __parallelism)
 185     {
 186       _GLIBCXX_CALL(__end - __begin)
 187
 188       __parallel_sort<__stable>
 189         (__begin, __end, __comp,
 190          multiway_mergesort_exact_tag(__parallelism.__get_num_threads()));
 191     }
 192
 193   /**
 194    *  @brief Choose a parallel sorting algorithm.
 195    *  @param __begin Begin iterator of input sequence.
 196    *  @param __end End iterator of input sequence.
 197    *  @param __comp Comparator.
 198    *  @tparam __stable Sort stable.
 199    *  @callgraph
 200    */
 201   template<bool __stable, typename _RAIter, typename _Compare>
 202     inline void
 203     __parallel_sort(_RAIter __begin, _RAIter __end,
 204                     _Compare __comp, parallel_tag __parallelism)
 205     {
 206       _GLIBCXX_CALL(__end - __begin)
 207       typedef std::iterator_traits<_RAIter> _TraitsType;
 208       typedef typename _TraitsType::value_type _ValueType;
 209       typedef typename _TraitsType::difference_type _DifferenceType;
 210
 211       if (false) ;
 212 #if _GLIBCXX_MERGESORT
 213       else if (__stable || _Settings::get().sort_algorithm == MWMS)
 214         {
 215           if(_Settings::get().sort_splitting == EXACT)
 216             parallel_sort_mwms<__stable, true>
 217               (__begin, __end, __comp, __parallelism.__get_num_threads());
 218           else
 219             parallel_sort_mwms<false, false>
 220               (__begin, __end, __comp, __parallelism.__get_num_threads());
 221         }
 222 #endif
 223 #if _GLIBCXX_QUICKSORT
 224       else if (_Settings::get().sort_algorithm == QS)
 225         __parallel_sort_qs(__begin, __end, __comp,
 226                            __parallelism.__get_num_threads());
 227 #endif
 228 #if _GLIBCXX_BAL_QUICKSORT
 229       else if (_Settings::get().sort_algorithm == QS_BALANCED)
 230         __parallel_sort_qsb(__begin, __end, __comp,
 231                             __parallelism.__get_num_threads());
 232 #endif
 233       else
 234         __gnu_sequential::sort(__begin, __end, __comp);
 235     }
 236 } // end namespace __gnu_parallel
 237
 238 #endif /* _GLIBCXX_PARALLEL_SORT_H */