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    *  @tparam __stable Sort stable.
00071    *  @callgraph 
00072    */
00073   template<bool __stable, typename _RAIter, typename _Compare>
00074     inline void
00075     __parallel_sort(_RAIter __begin, _RAIter __end,
00076             _Compare __comp, multiway_mergesort_tag __parallelism)
00077     {
00078       _GLIBCXX_CALL(__end - __begin)
00079 
00080       if(_Settings::get().sort_splitting == EXACT)
00081     parallel_sort_mwms<__stable, true>
00082       (__begin, __end, __comp, __parallelism.__get_num_threads());
00083       else
00084     parallel_sort_mwms<__stable, false>
00085       (__begin, __end, __comp, __parallelism.__get_num_threads());
00086     }
00087 
00088   /** 
00089    *  @brief Choose multiway mergesort with exact splitting,
00090    *  for parallel sorting.
00091    *  @param __begin Begin iterator of input sequence.
00092    *  @param __end End iterator of input sequence.
00093    *  @param __comp Comparator.
00094    *  @tparam __stable Sort stable.
00095    *  @callgraph 
00096    */
00097   template<bool __stable, typename _RAIter, typename _Compare>
00098     inline void
00099     __parallel_sort(_RAIter __begin, _RAIter __end,
00100             _Compare __comp,
00101             multiway_mergesort_exact_tag __parallelism)
00102     {
00103       _GLIBCXX_CALL(__end - __begin)
00104 
00105       parallel_sort_mwms<__stable, true>
00106         (__begin, __end, __comp, __parallelism.__get_num_threads());
00107     }
00108 
00109   /** 
00110    *  @brief Choose multiway mergesort with splitting by sampling,
00111    *  for parallel sorting.
00112    *  @param __begin Begin iterator of input sequence.
00113    *  @param __end End iterator of input sequence.
00114    *  @param __comp Comparator.
00115    *  @tparam __stable Sort stable.
00116    *  @callgraph 
00117    */
00118   template<bool __stable, typename _RAIter, typename _Compare>
00119     inline void
00120     __parallel_sort(_RAIter __begin, _RAIter __end,
00121             _Compare __comp,
00122             multiway_mergesort_sampling_tag __parallelism)
00123     {
00124       _GLIBCXX_CALL(__end - __begin)
00125 
00126       parallel_sort_mwms<__stable, false>
00127       (__begin, __end, __comp, __parallelism.__get_num_threads());
00128     }
00129 
00130   /**
00131    *  @brief Choose quicksort for parallel sorting.
00132    *  @param __begin Begin iterator of input sequence.
00133    *  @param __end End iterator of input sequence.
00134    *  @param __comp Comparator.
00135    *  @tparam __stable Sort stable.
00136    *  @callgraph 
00137    */
00138   template<bool __stable, typename _RAIter, typename _Compare>
00139     inline void
00140     __parallel_sort(_RAIter __begin, _RAIter __end,
00141             _Compare __comp, quicksort_tag __parallelism)
00142     {
00143       _GLIBCXX_CALL(__end - __begin)
00144 
00145       _GLIBCXX_PARALLEL_ASSERT(__stable == false);
00146 
00147       __parallel_sort_qs(__begin, __end, __comp,
00148              __parallelism.__get_num_threads());
00149     }
00150 
00151   /**
00152    *  @brief Choose balanced quicksort for parallel sorting.
00153    *  @param __begin Begin iterator of input sequence.
00154    *  @param __end End iterator of input sequence.
00155    *  @param __comp Comparator.
00156    *  @tparam __stable Sort stable.
00157    *  @callgraph 
00158    */
00159    template<bool __stable, typename _RAIter, typename _Compare>
00160      inline void
00161      __parallel_sort(_RAIter __begin, _RAIter __end,
00162              _Compare __comp, balanced_quicksort_tag __parallelism)
00163      {
00164        _GLIBCXX_CALL(__end - __begin)
00165 
00166        _GLIBCXX_PARALLEL_ASSERT(__stable == false);
00167 
00168        __parallel_sort_qsb(__begin, __end, __comp,
00169                __parallelism.__get_num_threads());
00170      }
00171 
00172   /** 
00173    *  @brief Choose multiway mergesort with exact splitting,
00174    *  for parallel sorting.
00175    *  @param __begin Begin iterator of input sequence.
00176    *  @param __end End iterator of input sequence.
00177    *  @param __comp Comparator.
00178    *  @tparam __stable Sort stable.
00179    *  @callgraph 
00180    */
00181   template<bool __stable, typename _RAIter, typename _Compare>
00182     inline void
00183     __parallel_sort(_RAIter __begin, _RAIter __end,
00184             _Compare __comp, default_parallel_tag __parallelism)
00185     {
00186       _GLIBCXX_CALL(__end - __begin)
00187 
00188       __parallel_sort<__stable>
00189     (__begin, __end, __comp,
00190      multiway_mergesort_exact_tag(__parallelism.__get_num_threads()));
00191     }
00192 
00193   /**
00194    *  @brief Choose a parallel sorting algorithm.
00195    *  @param __begin Begin iterator of input sequence.
00196    *  @param __end End iterator of input sequence.
00197    *  @param __comp Comparator.
00198    *  @tparam __stable Sort stable.
00199    *  @callgraph 
00200    */
00201   template<bool __stable, typename _RAIter, typename _Compare>
00202     inline void
00203     __parallel_sort(_RAIter __begin, _RAIter __end,
00204             _Compare __comp, parallel_tag __parallelism)
00205     {
00206       _GLIBCXX_CALL(__end - __begin)
00207       typedef std::iterator_traits<_RAIter> _TraitsType;
00208       typedef typename _TraitsType::value_type _ValueType;
00209       typedef typename _TraitsType::difference_type _DifferenceType;
00210 
00211       if (false) ;
00212 #if _GLIBCXX_MERGESORT
00213       else if (__stable || _Settings::get().sort_algorithm == MWMS)
00214         {
00215           if(_Settings::get().sort_splitting == EXACT)
00216             parallel_sort_mwms<__stable, true>
00217               (__begin, __end, __comp, __parallelism.__get_num_threads());
00218           else
00219             parallel_sort_mwms<false, false>
00220               (__begin, __end, __comp, __parallelism.__get_num_threads());
00221         }
00222 #endif
00223 #if _GLIBCXX_QUICKSORT
00224       else if (_Settings::get().sort_algorithm == QS)
00225         __parallel_sort_qs(__begin, __end, __comp,
00226                            __parallelism.__get_num_threads());
00227 #endif
00228 #if _GLIBCXX_BAL_QUICKSORT
00229       else if (_Settings::get().sort_algorithm == QS_BALANCED)
00230         __parallel_sort_qsb(__begin, __end, __comp,
00231                             __parallelism.__get_num_threads());
00232 #endif
00233       else
00234         __gnu_sequential::sort(__begin, __end, __comp);
00235     }
00236 } // end namespace __gnu_parallel
00237 
00238 #endif /* _GLIBCXX_PARALLEL_SORT_H */