libstdc++

quicksort.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009, 2010 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       ::operator delete(__samples);
00086 
00087       return __split;
00088     }
00089 
00090   /** @brief Unbalanced quicksort conquer step.
00091    *  @param __begin Begin iterator of subsequence.
00092    *  @param __end End iterator of subsequence.
00093    *  @param __comp Comparator.
00094    *  @param __num_threads Number of threads that are allowed to work on
00095    *  this part.
00096    */
00097   template<typename _RAIter, typename _Compare>
00098     void
00099     __parallel_sort_qs_conquer(_RAIter __begin, _RAIter __end,
00100                    _Compare __comp,
00101                    _ThreadIndex __num_threads)
00102     {
00103       typedef std::iterator_traits<_RAIter> _TraitsType;
00104       typedef typename _TraitsType::value_type _ValueType;
00105       typedef typename _TraitsType::difference_type _DifferenceType;
00106 
00107       if (__num_threads <= 1)
00108         {
00109           __gnu_sequential::sort(__begin, __end, __comp);
00110           return;
00111         }
00112 
00113       _DifferenceType __n = __end - __begin, __pivot_rank;
00114 
00115       if (__n <= 1)
00116         return;
00117 
00118       _ThreadIndex __num_threads_left;
00119 
00120       if ((__num_threads % 2) == 1)
00121         __num_threads_left = __num_threads / 2 + 1;
00122       else
00123         __num_threads_left = __num_threads / 2;
00124 
00125       __pivot_rank = __n * __num_threads_left / __num_threads;
00126 
00127       _DifferenceType __split = __parallel_sort_qs_divide
00128     (__begin, __end, __comp, __pivot_rank,
00129      _Settings::get().sort_qs_num_samples_preset, __num_threads);
00130 
00131 #pragma omp parallel sections num_threads(2)
00132       {
00133 #pragma omp section
00134         __parallel_sort_qs_conquer(__begin, __begin + __split,
00135                    __comp, __num_threads_left);
00136 #pragma omp section
00137         __parallel_sort_qs_conquer(__begin + __split, __end,
00138                    __comp, __num_threads - __num_threads_left);
00139       }
00140     }
00141 
00142 
00143   /** @brief Unbalanced quicksort main call.
00144    *  @param __begin Begin iterator of input sequence.
00145    *  @param __end End iterator input sequence, ignored.
00146    *  @param __comp Comparator.
00147    *  @param __num_threads Number of threads that are allowed to work on
00148    *  this part.
00149    */
00150   template<typename _RAIter, typename _Compare>
00151     void
00152     __parallel_sort_qs(_RAIter __begin, _RAIter __end,
00153                _Compare __comp,
00154                _ThreadIndex __num_threads)
00155     {
00156       _GLIBCXX_CALL(__n)
00157 
00158       typedef std::iterator_traits<_RAIter> _TraitsType;
00159       typedef typename _TraitsType::value_type _ValueType;
00160       typedef typename _TraitsType::difference_type _DifferenceType;
00161 
00162       _DifferenceType __n = __end - __begin;
00163 
00164       // At least one element per processor.
00165       if (__num_threads > __n)
00166         __num_threads = static_cast<_ThreadIndex>(__n);
00167 
00168       __parallel_sort_qs_conquer(
00169         __begin, __begin + __n, __comp, __num_threads);
00170     }
00171 
00172 } //namespace __gnu_parallel
00173 
00174 #endif /* _GLIBCXX_PARALLEL_QUICKSORT_H */