l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.6/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,
  99                     multiway_mergesort_exact_tag __parallelism)
 100     {
 101       _GLIBCXX_CALL(__end - __begin)
 102
 103       parallel_sort_mwms<__stable, true>
 104         (__begin, __end, __comp, __parallelism.__get_num_threads());
 105     }
 106
 107   /**
 108    *  @brief Choose multiway mergesort with splitting by sampling,
 109    *  for parallel sorting.
 110    *  @param __begin Begin iterator of input sequence.
 111    *  @param __end End iterator of input sequence.
 112    *  @param __comp Comparator.
 113    *  @callgraph
 114    */
 115   template<bool __stable, typename _RAIter, typename _Compare>
 116     inline void
 117     __parallel_sort(_RAIter __begin, _RAIter __end,
 118                     _Compare __comp,
 119                     multiway_mergesort_sampling_tag __parallelism)
 120     {
 121       _GLIBCXX_CALL(__end - __begin)
 122
 123       parallel_sort_mwms<__stable, false>
 124       (__begin, __end, __comp, __parallelism.__get_num_threads());
 125     }
 126
 127   /**
 128    *  @brief Choose quicksort for parallel sorting.
 129    *  @param __begin Begin iterator of input sequence.
 130    *  @param __end End iterator of input sequence.
 131    *  @param __comp Comparator.
 132    *  @callgraph
 133    */
 134   template<bool __stable, typename _RAIter, typename _Compare>
 135     inline void
 136     __parallel_sort(_RAIter __begin, _RAIter __end,
 137                     _Compare __comp, quicksort_tag __parallelism)
 138     {
 139       _GLIBCXX_CALL(__end - __begin)
 140
 141       _GLIBCXX_PARALLEL_ASSERT(__stable == false);
 142
 143       __parallel_sort_qs(__begin, __end, __comp,
 144                          __parallelism.__get_num_threads());
 145     }
 146
 147   /**
 148    *  @brief Choose balanced quicksort for parallel sorting.
 149    *  @param __begin Begin iterator of input sequence.
 150    *  @param __end End iterator of input sequence.
 151    *  @param __comp Comparator.
 152    *  @param __stable Sort __stable.
 153    *  @callgraph
 154    */
 155    template<bool __stable, typename _RAIter, typename _Compare>
 156      inline void
 157      __parallel_sort(_RAIter __begin, _RAIter __end,
 158                      _Compare __comp, balanced_quicksort_tag __parallelism)
 159      {
 160        _GLIBCXX_CALL(__end - __begin)
 161
 162        _GLIBCXX_PARALLEL_ASSERT(__stable == false);
 163
 164        __parallel_sort_qsb(__begin, __end, __comp,
 165                            __parallelism.__get_num_threads());
 166      }
 167
 168   /**
 169    *  @brief Choose multiway mergesort with exact splitting,
 170    *  for parallel sorting.
 171    *  @param __begin Begin iterator of input sequence.
 172    *  @param __end End iterator of input sequence.
 173    *  @param __comp Comparator.
 174    *  @callgraph
 175    */
 176   template<bool __stable, typename _RAIter, typename _Compare>
 177     inline void
 178     __parallel_sort(_RAIter __begin, _RAIter __end,
 179                     _Compare __comp, default_parallel_tag __parallelism)
 180     {
 181       _GLIBCXX_CALL(__end - __begin)
 182
 183       __parallel_sort<__stable>
 184         (__begin, __end, __comp,
 185          multiway_mergesort_exact_tag(__parallelism.__get_num_threads()));
 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 */