libstdc++
quicksort.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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/quicksort.h
00026  *  @brief Implementation of a unbalanced parallel quicksort (in-place).
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_QUICKSORT_H
00033 #define _GLIBCXX_PARALLEL_QUICKSORT_H 1
00034 
00035 #include <parallel/parallel.h>
00036 #include <parallel/partition.h>
00037 
00038 namespace __gnu_parallel
00039 {
00040   /** @brief Unbalanced quicksort divide step.
00041    *  @param __begin Begin iterator of subsequence.
00042    *  @param __end End iterator of subsequence.
00043    *  @param __comp Comparator.
00044    *  @param __pivot_rank Desired __rank of the pivot.
00045    *  @param __num_samples Choose pivot from that many samples.
00046    *  @param __num_threads Number of threads that are allowed to work on
00047    *  this part.
00048    */
00049   template<typename _RAIter, typename _Compare>
00050     typename std::iterator_traits<_RAIter>::difference_type
00051     __parallel_sort_qs_divide(_RAIter __begin, _RAIter __end,
00052                   _Compare __comp, typename std::iterator_traits
00053                   <_RAIter>::difference_type __pivot_rank,
00054                   typename std::iterator_traits
00055                   <_RAIter>::difference_type
00056                   __num_samples, _ThreadIndex __num_threads)
00057     {
00058       typedef std::iterator_traits<_RAIter> _TraitsType;
00059       typedef typename _TraitsType::value_type _ValueType;
00060       typedef typename _TraitsType::difference_type _DifferenceType;
00061 
00062       _DifferenceType __n = __end - __begin;
00063       __num_samples = std::min(__num_samples, __n);
00064 
00065       // Allocate uninitialized, to avoid default constructor.
00066       _ValueType* __samples = static_cast<_ValueType*>
00067     (::operator new(__num_samples * sizeof(_ValueType)));
00068 
00069       for (_DifferenceType __s = 0; __s < __num_samples; ++__s)
00070         {
00071           const unsigned long long __index = static_cast<unsigned long long>
00072         (__s) * __n / __num_samples;
00073           ::new(&(__samples[__s])) _ValueType(__begin[__index]);
00074         }
00075 
00076       __gnu_sequential::sort(__samples, __samples + __num_samples, __comp);
00077 
00078       _ValueType& __pivot = __samples[__pivot_rank * __num_samples / __n];
00079 
00080       __gnu_parallel::__binder2nd<_Compare, _ValueType, _ValueType, bool>
00081         __pred(__comp, __pivot);
00082       _DifferenceType __split = __parallel_partition(__begin, __end,
00083                              __pred, __num_threads);
00084 
00085       for (_DifferenceType __s = 0; __s < __num_samples; ++__s)
00086     __samples[__s].~_ValueType();
00087       ::operator delete(__samples);
00088 
00089       return __split;
00090     }
00091 
00092   /** @brief Unbalanced quicksort conquer step.
00093    *  @param __begin Begin iterator of subsequence.
00094    *  @param __end End iterator of subsequence.
00095    *  @param __comp Comparator.
00096    *  @param __num_threads Number of threads that are allowed to work on
00097    *  this part.
00098    */
00099   template<typename _RAIter, typename _Compare>
00100     void
00101     __parallel_sort_qs_conquer(_RAIter __begin, _RAIter __end,
00102                    _Compare __comp,
00103                    _ThreadIndex __num_threads)
00104     {
00105       typedef std::iterator_traits<_RAIter> _TraitsType;
00106       typedef typename _TraitsType::value_type _ValueType;
00107       typedef typename _TraitsType::difference_type _DifferenceType;
00108 
00109       if (__num_threads <= 1)
00110         {
00111           __gnu_sequential::sort(__begin, __end, __comp);
00112           return;
00113         }
00114 
00115       _DifferenceType __n = __end - __begin, __pivot_rank;
00116 
00117       if (__n <= 1)
00118         return;
00119 
00120       _ThreadIndex __num_threads_left;
00121 
00122       if ((__num_threads % 2) == 1)
00123         __num_threads_left = __num_threads / 2 + 1;
00124       else
00125         __num_threads_left = __num_threads / 2;
00126 
00127       __pivot_rank = __n * __num_threads_left / __num_threads;
00128 
00129       _DifferenceType __split = __parallel_sort_qs_divide
00130     (__begin, __end, __comp, __pivot_rank,
00131      _Settings::get().sort_qs_num_samples_preset, __num_threads);
00132 
00133 #pragma omp parallel sections num_threads(2)
00134       {
00135 #pragma omp section
00136         __parallel_sort_qs_conquer(__begin, __begin + __split,
00137                    __comp, __num_threads_left);
00138 #pragma omp section
00139         __parallel_sort_qs_conquer(__begin + __split, __end,
00140                    __comp, __num_threads - __num_threads_left);
00141       }
00142     }
00143 
00144 
00145   /** @brief Unbalanced quicksort main call.
00146    *  @param __begin Begin iterator of input sequence.
00147    *  @param __end End iterator input sequence, ignored.
00148    *  @param __comp Comparator.
00149    *  @param __num_threads Number of threads that are allowed to work on
00150    *  this part.
00151    */
00152   template<typename _RAIter, typename _Compare>
00153     void
00154     __parallel_sort_qs(_RAIter __begin, _RAIter __end,
00155                _Compare __comp,
00156                _ThreadIndex __num_threads)
00157     {
00158       _GLIBCXX_CALL(__n)
00159 
00160       typedef std::iterator_traits<_RAIter> _TraitsType;
00161       typedef typename _TraitsType::value_type _ValueType;
00162       typedef typename _TraitsType::difference_type _DifferenceType;
00163 
00164       _DifferenceType __n = __end - __begin;
00165 
00166       // At least one element per processor.
00167       if (__num_threads > __n)
00168         __num_threads = static_cast<_ThreadIndex>(__n);
00169 
00170       __parallel_sort_qs_conquer(
00171         __begin, __begin + __n, __comp, __num_threads);
00172     }
00173 
00174 } //namespace __gnu_parallel
00175 
00176 #endif /* _GLIBCXX_PARALLEL_QUICKSORT_H */