libstdc++
sort.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file parallel/sort.h
00026  *  @brief Parallel sorting algorithm switch.
00027  *  This file is a GNU parallel extension to the Standard C++ Library.
00028  */
00029 
00030 // Written by Johannes Singler.
00031 
00032 #ifndef _GLIBCXX_PARALLEL_SORT_H
00033 #define _GLIBCXX_PARALLEL_SORT_H 1
00034 
00035 #include <parallel/basic_iterator.h>
00036 #include <parallel/features.h>
00037 #include <parallel/parallel.h>
00038 
00039 #if _GLIBCXX_ASSERTIONS
00040 #include <parallel/checkers.h>
00041 #endif
00042 
00043 #if _GLIBCXX_MERGESORT
00044 #include <parallel/multiway_mergesort.h>
00045 #endif
00046 
00047 #if _GLIBCXX_QUICKSORT
00048 #include <parallel/quicksort.h>
00049 #endif
00050 
00051 #if _GLIBCXX_BAL_QUICKSORT
00052 #include <parallel/balanced_quicksort.h>
00053 #endif
00054 
00055 namespace __gnu_parallel
00056 {
00057   //prototype
00058   template<bool __stable, typename _RAIter,
00059            typename _Compare, typename _Parallelism>
00060     void
00061     __parallel_sort(_RAIter __begin, _RAIter __end,
00062             _Compare __comp, _Parallelism __parallelism);
00063         
00064   /** 
00065    *  @brief Choose multiway mergesort, splitting variant at run-time,
00066    *  for parallel sorting.
00067    *  @param __begin Begin iterator of input sequence.
00068    *  @param __end End iterator of input sequence.
00069    *  @param __comp Comparator.
00070    *  @callgraph 
00071    */
00072   template<bool __stable, typename _RAIter, typename _Compare>
00073     inline void
00074     __parallel_sort(_RAIter __begin, _RAIter __end,
00075             _Compare __comp, multiway_mergesort_tag __parallelism)
00076     {
00077       _GLIBCXX_CALL(__end - __begin)
00078 
00079       if(_Settings::get().sort_splitting == EXACT)
00080     parallel_sort_mwms<__stable, true>
00081       (__begin, __end, __comp, __parallelism.__get_num_threads());
00082       else
00083     parallel_sort_mwms<__stable, false>
00084       (__begin, __end, __comp, __parallelism.__get_num_threads());
00085     }
00086 
00087   /** 
00088    *  @brief Choose multiway mergesort with exact splitting,
00089    *  for parallel sorting.
00090    *  @param __begin Begin iterator of input sequence.
00091    *  @param __end End iterator of input sequence.
00092    *  @param __comp Comparator.
00093    *  @callgraph 
00094    */
00095   template<bool __stable, typename _RAIter, typename _Compare>
00096     inline void
00097     __parallel_sort(_RAIter __begin, _RAIter __end,
00098             _Compare __comp,
00099             multiway_mergesort_exact_tag __parallelism)
00100     {
00101       _GLIBCXX_CALL(__end - __begin)
00102 
00103       parallel_sort_mwms<__stable, true>
00104         (__begin, __end, __comp, __parallelism.__get_num_threads());
00105     }
00106 
00107   /** 
00108    *  @brief Choose multiway mergesort with splitting by sampling,
00109    *  for parallel sorting.
00110    *  @param __begin Begin iterator of input sequence.
00111    *  @param __end End iterator of input sequence.
00112    *  @param __comp Comparator.
00113    *  @callgraph 
00114    */
00115   template<bool __stable, typename _RAIter, typename _Compare>
00116     inline void
00117     __parallel_sort(_RAIter __begin, _RAIter __end,
00118             _Compare __comp,
00119             multiway_mergesort_sampling_tag __parallelism)
00120     {
00121       _GLIBCXX_CALL(__end - __begin)
00122 
00123       parallel_sort_mwms<__stable, false>
00124       (__begin, __end, __comp, __parallelism.__get_num_threads());
00125     }
00126 
00127   /**
00128    *  @brief Choose quicksort for parallel sorting.
00129    *  @param __begin Begin iterator of input sequence.
00130    *  @param __end End iterator of input sequence.
00131    *  @param __comp Comparator.
00132    *  @callgraph 
00133    */
00134   template<bool __stable, typename _RAIter, typename _Compare>
00135     inline void
00136     __parallel_sort(_RAIter __begin, _RAIter __end,
00137             _Compare __comp, quicksort_tag __parallelism)
00138     {
00139       _GLIBCXX_CALL(__end - __begin)
00140 
00141       _GLIBCXX_PARALLEL_ASSERT(__stable == false);
00142 
00143       __parallel_sort_qs(__begin, __end, __comp,
00144              __parallelism.__get_num_threads());
00145     }
00146 
00147   /**
00148    *  @brief Choose balanced quicksort for parallel sorting.
00149    *  @param __begin Begin iterator of input sequence.
00150    *  @param __end End iterator of input sequence.
00151    *  @param __comp Comparator.
00152    *  @param __stable Sort __stable.
00153    *  @callgraph 
00154    */
00155    template<bool __stable, typename _RAIter, typename _Compare>
00156      inline void
00157      __parallel_sort(_RAIter __begin, _RAIter __end,
00158              _Compare __comp, balanced_quicksort_tag __parallelism)
00159      {
00160        _GLIBCXX_CALL(__end - __begin)
00161 
00162        _GLIBCXX_PARALLEL_ASSERT(__stable == false);
00163 
00164        __parallel_sort_qsb(__begin, __end, __comp,
00165                __parallelism.__get_num_threads());
00166      }
00167 
00168   /** 
00169    *  @brief Choose multiway mergesort with exact splitting,
00170    *  for parallel sorting.
00171    *  @param __begin Begin iterator of input sequence.
00172    *  @param __end End iterator of input sequence.
00173    *  @param __comp Comparator.
00174    *  @callgraph 
00175    */
00176   template<bool __stable, typename _RAIter, typename _Compare>
00177     inline void
00178     __parallel_sort(_RAIter __begin, _RAIter __end,
00179             _Compare __comp, default_parallel_tag __parallelism)
00180     {
00181       _GLIBCXX_CALL(__end - __begin)
00182 
00183       __parallel_sort<__stable>
00184     (__begin, __end, __comp,
00185      multiway_mergesort_exact_tag(__parallelism.__get_num_threads()));
00186     }
00187 
00188   /**
00189    *  @brief Choose a parallel sorting algorithm.
00190    *  @param __begin Begin iterator of input sequence.
00191    *  @param __end End iterator of input sequence.
00192    *  @param __comp Comparator.
00193    *  @param __stable Sort __stable.
00194    *  @callgraph 
00195    */
00196   template<bool __stable, typename _RAIter, typename _Compare>
00197     inline void
00198     __parallel_sort(_RAIter __begin, _RAIter __end,
00199             _Compare __comp, parallel_tag __parallelism)
00200     {
00201       _GLIBCXX_CALL(__end - __begin)
00202       typedef std::iterator_traits<_RAIter> _TraitsType;
00203       typedef typename _TraitsType::value_type _ValueType;
00204       typedef typename _TraitsType::difference_type _DifferenceType;
00205 
00206       if (false) ;
00207 #if _GLIBCXX_MERGESORT
00208       else if (__stable || _Settings::get().sort_algorithm == MWMS)
00209         {
00210           if(_Settings::get().sort_splitting == EXACT)
00211             parallel_sort_mwms<__stable, true>
00212               (__begin, __end, __comp, __parallelism.__get_num_threads());
00213           else
00214             parallel_sort_mwms<false, false>
00215               (__begin, __end, __comp, __parallelism.__get_num_threads());
00216         }
00217 #endif
00218 #if _GLIBCXX_QUICKSORT
00219       else if (_Settings::get().sort_algorithm == QS)
00220         __parallel_sort_qs(__begin, __end, __comp,
00221                            __parallelism.__get_num_threads());
00222 #endif
00223 #if _GLIBCXX_BAL_QUICKSORT
00224       else if (_Settings::get().sort_algorithm == QS_BALANCED)
00225         __parallel_sort_qsb(__begin, __end, __comp,
00226                             __parallelism.__get_num_threads());
00227 #endif
00228       else
00229         __gnu_sequential::sort(__begin, __end, __comp);
00230     }
00231 } // end namespace __gnu_parallel
00232 
00233 #endif /* _GLIBCXX_PARALLEL_SORT_H */