l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/include/parallel/quicksort.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 /** @file parallel/quicksort.h
  32  *  @brief Implementation of a unbalanced parallel quicksort (in-place).
  33  *  This file is a GNU parallel extension to the Standard C++ Library.
  34  */
  35
  36 // Written by Johannes Singler.
  37
  38 #ifndef _GLIBCXX_PARALLEL_QUICKSORT_H
  39 #define _GLIBCXX_PARALLEL_QUICKSORT_H 1
  40
  41 #include <parallel/parallel.h>
  42 #include <parallel/partition.h>
  43
  44 namespace __gnu_parallel
  45 {
  46   /** @brief Unbalanced quicksort divide step.
  47    *  @param begin Begin iterator of subsequence.
  48    *  @param end End iterator of subsequence.
  49    *  @param comp Comparator.
  50    *  @param pivot_rank Desired rank of the pivot.
  51    *  @param num_samples Choose pivot from that many samples.
  52    *  @param num_threads Number of threads that are allowed to work on
  53    *  this part.
  54    */
  55   template<typename RandomAccessIterator, typename Comparator>
  56     typename std::iterator_traits<RandomAccessIterator>::difference_type
  57     parallel_sort_qs_divide(RandomAccessIterator begin,
  58                             RandomAccessIterator end,
  59                             Comparator comp, typename std::iterator_traits
  60                             <RandomAccessIterator>::difference_type pivot_rank,
  61                             typename std::iterator_traits
  62                             <RandomAccessIterator>::difference_type
  63                             num_samples, thread_index_t num_threads)
  64     {
  65       typedef std::iterator_traits<RandomAccessIterator> traits_type;
  66       typedef typename traits_type::value_type value_type;
  67       typedef typename traits_type::difference_type difference_type;
  68
  69       difference_type n = end - begin;
  70       num_samples = std::min(num_samples, n);
  71
  72       // Allocate uninitialized, to avoid default constructor.
  73       value_type* samples =
  74         static_cast<value_type*>(::operator new(num_samples
  75                                                 * sizeof(value_type)));
  76
  77       for (difference_type s = 0; s < num_samples; ++s)
  78         {
  79           const unsigned long long index = static_cast<unsigned long long>(s)
  80             * n / num_samples;
  81           ::new(&(samples[s])) value_type(begin[index]);
  82         }
  83
  84       __gnu_sequential::sort(samples, samples + num_samples, comp);
  85
  86       value_type& pivot = samples[pivot_rank * num_samples / n];
  87
  88       __gnu_parallel::binder2nd<Comparator, value_type, value_type, bool>
  89         pred(comp, pivot);
  90       difference_type split = parallel_partition(begin, end, pred, num_threads);
  91
  92       ::operator delete(samples);
  93
  94       return split;
  95     }
  96
  97   /** @brief Unbalanced quicksort conquer step.
  98    *  @param begin Begin iterator of subsequence.
  99    *  @param end End iterator of subsequence.
 100    *  @param comp Comparator.
 101    *  @param num_threads Number of threads that are allowed to work on
 102    *  this part.
 103    */
 104   template<typename RandomAccessIterator, typename Comparator>
 105     void
 106     parallel_sort_qs_conquer(RandomAccessIterator begin,
 107                              RandomAccessIterator end,
 108                              Comparator comp,
 109                              thread_index_t num_threads)
 110     {
 111       typedef std::iterator_traits<RandomAccessIterator> traits_type;
 112       typedef typename traits_type::value_type value_type;
 113       typedef typename traits_type::difference_type difference_type;
 114
 115       if (num_threads <= 1)
 116         {
 117           __gnu_sequential::sort(begin, end, comp);
 118           return;
 119         }
 120
 121       difference_type n = end - begin, pivot_rank;
 122
 123       if (n <= 1)
 124         return;
 125
 126       thread_index_t num_threads_left;
 127
 128       if ((num_threads % 2) == 1)
 129         num_threads_left = num_threads / 2 + 1;
 130       else
 131         num_threads_left = num_threads / 2;
 132
 133       pivot_rank = n * num_threads_left / num_threads;
 134
 135       difference_type split =
 136         parallel_sort_qs_divide(begin, end, comp, pivot_rank,
 137                                 _Settings::get().sort_qs_num_samples_preset,
 138                                 num_threads);
 139
 140 #pragma omp parallel sections num_threads(2)
 141       {
 142 #pragma omp section
 143         parallel_sort_qs_conquer(begin, begin + split,
 144                                  comp, num_threads_left);
 145 #pragma omp section
 146         parallel_sort_qs_conquer(begin + split, end,
 147                                  comp, num_threads - num_threads_left);
 148       }
 149     }
 150
 151
 152
 153   /** @brief Unbalanced quicksort main call.
 154    *  @param begin Begin iterator of input sequence.
 155    *  @param end End iterator input sequence, ignored.
 156    *  @param comp Comparator.
 157    *  @param n Length of input sequence.
 158    *  @param num_threads Number of threads that are allowed to work on
 159    *  this part.
 160    */
 161   template<typename RandomAccessIterator, typename Comparator>
 162     void
 163     parallel_sort_qs(RandomAccessIterator begin,
 164                      RandomAccessIterator end,
 165                      Comparator comp, typename std::iterator_traits
 166                      <RandomAccessIterator>::difference_type n,
 167                      int num_threads)
 168     {
 169       _GLIBCXX_CALL(n)
 170
 171       typedef std::iterator_traits<RandomAccessIterator> traits_type;
 172       typedef typename traits_type::value_type value_type;
 173       typedef typename traits_type::difference_type difference_type;
 174
 175       if (n == 0)
 176         return;
 177
 178       // At least one element per processor.
 179       if (num_threads > n)
 180         num_threads = static_cast<thread_index_t>(n);
 181
 182       parallel_sort_qs_conquer(begin, begin + n, comp, num_threads);
 183     }
 184
 185 } //namespace __gnu_parallel
 186
 187 #endif