contrib/gcc-4.4/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 RandomAccessIterator,
  59            typename Comparator, typename Parallelism>
  60   void
  61   parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
  62   Comparator 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 RandomAccessIterator, typename Comparator>
  73   inline void
  74   parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
  75     Comparator 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 RandomAccessIterator, typename Comparator>
  96   inline void
  97   parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
  98     Comparator 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 RandomAccessIterator, typename Comparator>
 115   inline void
 116   parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
 117     Comparator 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 RandomAccessIterator, typename Comparator>
 133   inline void
 134   parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
 135     Comparator 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, parallelism.get_num_threads());
 142   }
 143
 144   /**
 145    *  @brief Choose balanced quicksort for parallel sorting.
 146    *  @param begin Begin iterator of input sequence.
 147    *  @param end End iterator of input sequence.
 148    *  @param comp Comparator.
 149    *  @param stable Sort stable.
 150    *  @callgraph
 151    */
 152   template<bool stable, typename RandomAccessIterator, typename Comparator>
 153   inline void
 154   parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
 155     Comparator comp, balanced_quicksort_tag parallelism)
 156   {
 157     _GLIBCXX_CALL(end - begin)
 158
 159     _GLIBCXX_PARALLEL_ASSERT(stable == false);
 160
 161     parallel_sort_qsb(begin, end, comp, parallelism.get_num_threads());
 162   }
 163
 164
 165   /**
 166    *  @brief Choose multiway mergesort with exact splitting,
 167    *  for parallel sorting.
 168    *  @param begin Begin iterator of input sequence.
 169    *  @param end End iterator of input sequence.
 170    *  @param comp Comparator.
 171    *  @callgraph
 172    */
 173   template<bool stable, typename RandomAccessIterator, typename Comparator>
 174   inline void
 175   parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
 176     Comparator comp, default_parallel_tag parallelism)
 177   {
 178     _GLIBCXX_CALL(end - begin)
 179
 180     parallel_sort<stable>
 181       (begin, end, comp,
 182         multiway_mergesort_exact_tag(parallelism.get_num_threads()));
 183   }
 184
 185
 186   /**
 187    *  @brief Choose a parallel sorting algorithm.
 188    *  @param begin Begin iterator of input sequence.
 189    *  @param end End iterator of input sequence.
 190    *  @param comp Comparator.
 191    *  @param stable Sort stable.
 192    *  @callgraph
 193    */
 194   template<bool stable, typename RandomAccessIterator, typename Comparator>
 195     inline void
 196     parallel_sort(RandomAccessIterator begin, RandomAccessIterator end,
 197                   Comparator comp, parallel_tag parallelism)
 198     {
 199       _GLIBCXX_CALL(end - begin)
 200       typedef std::iterator_traits<RandomAccessIterator> traits_type;
 201       typedef typename traits_type::value_type value_type;
 202       typedef typename traits_type::difference_type difference_type;
 203
 204       if (false) ;
 205 #if _GLIBCXX_MERGESORT
 206       else if (stable || _Settings::get().sort_algorithm == MWMS)
 207         {
 208           if(_Settings::get().sort_splitting == EXACT)
 209             parallel_sort_mwms<stable, true>
 210               (begin, end, comp, parallelism.get_num_threads());
 211           else
 212             parallel_sort_mwms<false, false>
 213               (begin, end, comp, parallelism.get_num_threads());
 214         }
 215 #endif
 216 #if _GLIBCXX_QUICKSORT
 217       else if (_Settings::get().sort_algorithm == QS)
 218         parallel_sort_qs(begin, end, comp, parallelism.get_num_threads());
 219 #endif
 220 #if _GLIBCXX_BAL_QUICKSORT
 221       else if (_Settings::get().sort_algorithm == QS_BALANCED)
 222         parallel_sort_qsb(begin, end, comp, parallelism.get_num_threads());
 223 #endif
 224       else
 225         __gnu_sequential::sort(begin, end, comp);
 226     }
 227 } // end namespace __gnu_parallel
 228
 229 #endif /* _GLIBCXX_PARALLEL_SORT_H */