libstdc++-v3/include/parallel/sort.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/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_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    *  @callgraph
  71    */
  72   template<bool __stable, typename _RAIter, typename _Compare>
  73   inline void
  74   parallel_sort(_RAIter __begin, _RAIter __end,
  75     _Compare __comp, multiway_mergesort_tag __parallelism)
  76   {
  77     _GLIBCXX_CALL(__end - __begin)
  78
  79     if(_Settings::get().sort_splitting == EXACT)
  80       parallel_sort_mwms<__stable, true>
  81         (__begin, __end, __comp, __parallelism.__get_num_threads());
  82     else
  83       parallel_sort_mwms<__stable, false>
  84         (__begin, __end, __comp, __parallelism.__get_num_threads());
  85   }
  86
  87   /**
  88    *  @brief Choose multiway mergesort with exact splitting,
  89    *  for parallel sorting.
  90    *  @param __begin Begin iterator of input sequence.
  91    *  @param __end End iterator of input sequence.
  92    *  @param __comp Comparator.
  93    *  @callgraph
  94    */
  95   template<bool __stable, typename _RAIter, typename _Compare>
  96   inline void
  97   parallel_sort(_RAIter __begin, _RAIter __end,
  98     _Compare __comp, multiway_mergesort_exact_tag __parallelism)
  99   {
 100     _GLIBCXX_CALL(__end - __begin)
 101
 102       parallel_sort_mwms<__stable, true>
 103         (__begin, __end, __comp, __parallelism.__get_num_threads());
 104   }
 105
 106   /**
 107    *  @brief Choose multiway mergesort with splitting by sampling,
 108    *  for parallel sorting.
 109    *  @param __begin Begin iterator of input sequence.
 110    *  @param __end End iterator of input sequence.
 111    *  @param __comp Comparator.
 112    *  @callgraph
 113    */
 114   template<bool __stable, typename _RAIter, typename _Compare>
 115   inline void
 116   parallel_sort(_RAIter __begin, _RAIter __end,
 117     _Compare __comp, multiway_mergesort_sampling_tag __parallelism)
 118   {
 119     _GLIBCXX_CALL(__end - __begin)
 120
 121     parallel_sort_mwms<__stable, false>
 122       (__begin, __end, __comp, __parallelism.__get_num_threads());
 123   }
 124
 125   /**
 126    *  @brief Choose quicksort for parallel sorting.
 127    *  @param __begin Begin iterator of input sequence.
 128    *  @param __end End iterator of input sequence.
 129    *  @param __comp Comparator.
 130    *  @callgraph
 131    */
 132   template<bool __stable, typename _RAIter, typename _Compare>
 133   inline void
 134   parallel_sort(_RAIter __begin, _RAIter __end,
 135     _Compare __comp, quicksort_tag __parallelism)
 136   {
 137     _GLIBCXX_CALL(__end - __begin)
 138
 139     _GLIBCXX_PARALLEL_ASSERT(__stable == false);
 140
 141     __parallel_sort_qs(__begin, __end, __comp,
 142                        __parallelism.__get_num_threads());
 143   }
 144
 145   /**
 146    *  @brief Choose balanced quicksort for parallel sorting.
 147    *  @param __begin Begin iterator of input sequence.
 148    *  @param __end End iterator of input sequence.
 149    *  @param __comp Comparator.
 150    *  @param __stable Sort __stable.
 151    *  @callgraph
 152    */
 153   template<bool __stable, typename _RAIter, typename _Compare>
 154   inline void
 155   parallel_sort(_RAIter __begin, _RAIter __end,
 156     _Compare __comp, balanced_quicksort_tag __parallelism)
 157   {
 158     _GLIBCXX_CALL(__end - __begin)
 159
 160     _GLIBCXX_PARALLEL_ASSERT(__stable == false);
 161
 162     __parallel_sort_qsb(__begin, __end, __comp,
 163                         __parallelism.__get_num_threads());
 164   }
 165
 166
 167   /**
 168    *  @brief Choose multiway mergesort with exact splitting,
 169    *  for parallel sorting.
 170    *  @param __begin Begin iterator of input sequence.
 171    *  @param __end End iterator of input sequence.
 172    *  @param __comp Comparator.
 173    *  @callgraph
 174    */
 175   template<bool __stable, typename _RAIter, typename _Compare>
 176   inline void
 177   parallel_sort(_RAIter __begin, _RAIter __end,
 178     _Compare __comp, default_parallel_tag __parallelism)
 179   {
 180     _GLIBCXX_CALL(__end - __begin)
 181
 182     parallel_sort<__stable>
 183       (__begin, __end, __comp,
 184         multiway_mergesort_exact_tag(__parallelism.__get_num_threads()));
 185   }
 186
 187
 188   /**
 189    *  @brief Choose a parallel sorting algorithm.
 190    *  @param __begin Begin iterator of input sequence.
 191    *  @param __end End iterator of input sequence.
 192    *  @param __comp Comparator.
 193    *  @param __stable Sort __stable.
 194    *  @callgraph
 195    */
 196   template<bool __stable, typename _RAIter, typename _Compare>
 197     inline void
 198     parallel_sort(_RAIter __begin, _RAIter __end,
 199                   _Compare __comp, parallel_tag __parallelism)
 200     {
 201       _GLIBCXX_CALL(__end - __begin)
 202       typedef std::iterator_traits<_RAIter> _TraitsType;
 203       typedef typename _TraitsType::value_type _ValueType;
 204       typedef typename _TraitsType::difference_type _DifferenceType;
 205
 206       if (false) ;
 207 #if _GLIBCXX_MERGESORT
 208       else if (__stable || _Settings::get().sort_algorithm == MWMS)
 209         {
 210           if(_Settings::get().sort_splitting == EXACT)
 211             parallel_sort_mwms<__stable, true>
 212               (__begin, __end, __comp, __parallelism.__get_num_threads());
 213           else
 214             parallel_sort_mwms<false, false>
 215               (__begin, __end, __comp, __parallelism.__get_num_threads());
 216         }
 217 #endif
 218 #if _GLIBCXX_QUICKSORT
 219       else if (_Settings::get().sort_algorithm == QS)
 220         __parallel_sort_qs(__begin, __end, __comp,
 221                            __parallelism.__get_num_threads());
 222 #endif
 223 #if _GLIBCXX_BAL_QUICKSORT
 224       else if (_Settings::get().sort_algorithm == QS_BALANCED)
 225         __parallel_sort_qsb(__begin, __end, __comp,
 226                             __parallelism.__get_num_threads());
 227 #endif
 228       else
 229         __gnu_sequential::sort(__begin, __end, __comp);
 230     }
 231 } // end namespace __gnu_parallel
 232
 233 #endif /* _GLIBCXX_PARALLEL_SORT_H */