Subversion Repositories altor32

// -*- C++ -*-

// Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the terms

// of the GNU General Public License as published by the Free Software

// Foundation; either version 3, or (at your option) any later

// version.

// This library is distributed in the hope that it will be useful, but

// WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

// General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// <http://www.gnu.org/licenses/>.

/** @file parallel/partition.h

 *  @brief Parallel implementation of std::partition(),

 *  std::nth_element(), and std::partial_sort().

 *  This file is a GNU parallel extension to the Standard C++ Library.

 */

// Written by Johannes Singler and Felix Putze.

#ifndef _GLIBCXX_PARALLEL_PARTITION_H

#define _GLIBCXX_PARALLEL_PARTITION_H 1

#include <parallel/basic_iterator.h>

#include <parallel/sort.h>

#include <parallel/random_number.h>

#include <bits/stl_algo.h>

#include <parallel/parallel.h>

/** @brief Decide whether to declare certain variables volatile. */

#define _GLIBCXX_VOLATILE volatile

namespace __gnu_parallel

{

  /** @brief Parallel implementation of std::partition.

    *  @param __begin Begin iterator of input sequence to split.

    *  @param __end End iterator of input sequence to split.

    *  @param __pred Partition predicate, possibly including some kind

    *         of pivot.

    *  @param __num_threads Maximum number of threads to use for this task.

    *  @return Number of elements not fulfilling the predicate. */

  template<typename _RAIter, typename _Predicate>

    typename std::iterator_traits<_RAIter>::difference_type

    __parallel_partition(_RAIter __begin, _RAIter __end,

                         _Predicate __pred, _ThreadIndex __num_threads)

    {

      typedef std::iterator_traits<_RAIter> _TraitsType;

      typedef typename _TraitsType::value_type _ValueType;

      typedef typename _TraitsType::difference_type _DifferenceType;

      _DifferenceType __n = __end - __begin;

      _GLIBCXX_CALL(__n)

      const _Settings& __s = _Settings::get();

      // shared

      _GLIBCXX_VOLATILE _DifferenceType __left = 0, __right = __n - 1,

                                        __dist = __n,

                                        __leftover_left, __leftover_right,

                                        __leftnew, __rightnew;

      // just 0 or 1, but int to allow atomic operations

      int* __reserved_left = 0, * __reserved_right = 0;

      _DifferenceType __chunk_size = __s.partition_chunk_size;

      //at least two chunks per thread

      if (__dist >= 2 * __num_threads * __chunk_size)

#       pragma omp parallel num_threads(__num_threads)

        {

#         pragma omp single

          {

            __num_threads = omp_get_num_threads();

            __reserved_left = new int[__num_threads];

            __reserved_right = new int[__num_threads];

            if (__s.partition_chunk_share > 0.0)

              __chunk_size = std::max<_DifferenceType>

                (__s.partition_chunk_size, (double)__n

                 * __s.partition_chunk_share / (double)__num_threads);

            else

              __chunk_size = __s.partition_chunk_size;

          }

          while (__dist >= 2 * __num_threads * __chunk_size)

            {

#             pragma omp single

              {

                _DifferenceType __num_chunks = __dist / __chunk_size;

                for (_ThreadIndex __r = 0; __r < __num_threads; ++__r)

                  {

                    __reserved_left [__r] = 0; // false

                    __reserved_right[__r] = 0; // false

                  }

                __leftover_left = 0;

                __leftover_right = 0;

              } //implicit barrier

              // Private.

              _DifferenceType __thread_left, __thread_left_border,

                              __thread_right, __thread_right_border;

              __thread_left = __left + 1;

              // Just to satisfy the condition below.

              __thread_left_border = __thread_left - 1;

              __thread_right = __n - 1;

             // Just to satisfy the condition below.

              __thread_right_border = __thread_right + 1;

              bool __iam_finished = false;

              while (!__iam_finished)

                {

                  if (__thread_left > __thread_left_border)

                    {

                      _DifferenceType __former_dist =

                              __fetch_and_add(&__dist, -__chunk_size);

                      if (__former_dist < __chunk_size)

                        {

                          __fetch_and_add(&__dist, __chunk_size);

                          __iam_finished = true;

                          break;

                        }

                      else

                        {

                          __thread_left =

                                  __fetch_and_add(&__left, __chunk_size);

                          __thread_left_border =

                                  __thread_left + (__chunk_size - 1);

                        }

                    }

                  if (__thread_right < __thread_right_border)

                    {

                      _DifferenceType __former_dist =

                              __fetch_and_add(&__dist, -__chunk_size);

                      if (__former_dist < __chunk_size)

                        {

                          __fetch_and_add(&__dist, __chunk_size);

                          __iam_finished = true;

                          break;

                        }

                      else

                        {

                          __thread_right =

                                  __fetch_and_add(&__right, -__chunk_size);

                          __thread_right_border =

                                  __thread_right - (__chunk_size - 1);

                        }

                    }

                  // Swap as usual.

                  while (__thread_left < __thread_right)

                    {

                      while (__pred(__begin[__thread_left])

                             && __thread_left <= __thread_left_border)

                        ++__thread_left;

                      while (!__pred(__begin[__thread_right])

                             && __thread_right >= __thread_right_border)

                        --__thread_right;

                      if (__thread_left > __thread_left_border

                          || __thread_right < __thread_right_border)

                        // Fetch new chunk(__s).

                        break;

                      std::iter_swap(__begin + __thread_left,

                             __begin + __thread_right);

                      ++__thread_left;

                      --__thread_right;

                    }

                }

              // Now swap the leftover chunks to the right places.

              if (__thread_left <= __thread_left_border)

#               pragma omp atomic

                ++__leftover_left;

              if (__thread_right >= __thread_right_border)

#               pragma omp atomic

                ++__leftover_right;

#             pragma omp barrier

              _DifferenceType

                    __leftold = __left,

                    __leftnew = __left - __leftover_left * __chunk_size,

                    __rightold = __right,

                    __rightnew = __right + __leftover_right * __chunk_size;

              // <=> __thread_left_border + (__chunk_size - 1) >= __leftnew

              if (__thread_left <= __thread_left_border

                  && __thread_left_border >= __leftnew)

                {

                  // Chunk already in place, reserve spot.

                __reserved_left[(__left - (__thread_left_border + 1))

                                / __chunk_size] = 1;

                }

              // <=> __thread_right_border - (__chunk_size - 1) <= __rightnew

              if (__thread_right >= __thread_right_border

                  && __thread_right_border <= __rightnew)

                {

                  // Chunk already in place, reserve spot.

                  __reserved_right[((__thread_right_border - 1) - __right)

                                   / __chunk_size] = 1;

                }

#             pragma omp barrier

              if (__thread_left <= __thread_left_border

                  && __thread_left_border < __leftnew)

                {

                  // Find spot and swap.

                  _DifferenceType __swapstart = -1;

                  for (int __r = 0; __r < __leftover_left; ++__r)

                    if (__reserved_left[__r] == 0

                        && __compare_and_swap(&(__reserved_left[__r]), 0, 1))

                      {

                        __swapstart = __leftold - (__r + 1) * __chunk_size;

                        break;

                      }

#if _GLIBCXX_ASSERTIONS

                  _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);

#endif

                  std::swap_ranges(__begin + __thread_left_border

                                   - (__chunk_size - 1),

                                   __begin + __thread_left_border + 1,

                                   __begin + __swapstart);

                }

              if (__thread_right >= __thread_right_border

                  && __thread_right_border > __rightnew)

                {

                  // Find spot and swap

                  _DifferenceType __swapstart = -1;

                  for (int __r = 0; __r < __leftover_right; ++__r)

                    if (__reserved_right[__r] == 0

                        && __compare_and_swap(&(__reserved_right[__r]), 0, 1))

                      {

                        __swapstart = __rightold + __r * __chunk_size + 1;

                        break;

                      }

#if _GLIBCXX_ASSERTIONS

                  _GLIBCXX_PARALLEL_ASSERT(__swapstart != -1);

#endif

                  std::swap_ranges(__begin + __thread_right_border,

                                   __begin + __thread_right_border

                                   + __chunk_size, __begin + __swapstart);

              }

#if _GLIBCXX_ASSERTIONS

#             pragma omp barrier

#             pragma omp single

              {

                for (_DifferenceType __r = 0; __r < __leftover_left; ++__r)

                  _GLIBCXX_PARALLEL_ASSERT(__reserved_left[__r] == 1);

                for (_DifferenceType __r = 0; __r < __leftover_right; ++__r)

                  _GLIBCXX_PARALLEL_ASSERT(__reserved_right[__r] == 1);

              }

#endif

              __left = __leftnew;

              __right = __rightnew;

              __dist = __right - __left + 1;

            }

#           pragma omp flush(__left, __right)

        } // end "recursion" //parallel

        _DifferenceType __final_left = __left, __final_right = __right;

        while (__final_left < __final_right)

          {

            // Go right until key is geq than pivot.

            while (__pred(__begin[__final_left])

                   && __final_left < __final_right)

              ++__final_left;

            // Go left until key is less than pivot.

            while (!__pred(__begin[__final_right])

                   && __final_left < __final_right)

              --__final_right;

            if (__final_left == __final_right)

              break;

            std::iter_swap(__begin + __final_left, __begin + __final_right);

            ++__final_left;

            --__final_right;

          }

        // All elements on the left side are < piv, all elements on the

        // right are >= piv

        delete[] __reserved_left;

        delete[] __reserved_right;

        // Element "between" __final_left and __final_right might not have

        // been regarded yet

        if (__final_left < __n && !__pred(__begin[__final_left]))

          // Really swapped.

          return __final_left;

        else

          return __final_left + 1;

    }

  /**

    *  @brief Parallel implementation of std::nth_element().

    *  @param __begin Begin iterator of input sequence.

    *  @param __nth _Iterator of element that must be in position afterwards.

    *  @param __end End iterator of input sequence.

    *  @param __comp Comparator.

    */

  template<typename _RAIter, typename _Compare>

    void

    __parallel_nth_element(_RAIter __begin, _RAIter __nth,

                           _RAIter __end, _Compare __comp)

    {

      typedef std::iterator_traits<_RAIter> _TraitsType;

      typedef typename _TraitsType::value_type _ValueType;

      typedef typename _TraitsType::difference_type _DifferenceType;

      _GLIBCXX_CALL(__end - __begin)

      _RAIter __split;

      _RandomNumber __rng;

      const _Settings& __s = _Settings::get();

      _DifferenceType __minimum_length = std::max<_DifferenceType>(2,

        std::max(__s.nth_element_minimal_n, __s.partition_minimal_n));

      // Break if input range to small.

      while (static_cast<_SequenceIndex>(__end - __begin) >= __minimum_length)

        {

          _DifferenceType __n = __end - __begin;

          _RAIter __pivot_pos = __begin + __rng(__n);

          // Swap __pivot_pos value to end.

          if (__pivot_pos != (__end - 1))

            std::iter_swap(__pivot_pos, __end - 1);

          __pivot_pos = __end - 1;

          // _Compare must have first_value_type, second_value_type,

          // result_type

          // _Compare ==

          // __gnu_parallel::_Lexicographic<S, int,

          //                                __gnu_parallel::_Less<S, S> >

          // __pivot_pos == std::pair<S, int>*

          __gnu_parallel::__binder2nd<_Compare, _ValueType, _ValueType, bool>

            __pred(__comp, *__pivot_pos);

          // Divide, leave pivot unchanged in last place.

          _RAIter __split_pos1, __split_pos2;

          __split_pos1 = __begin + __parallel_partition(__begin, __end - 1,

                                                        __pred,

                                                        __get_max_threads());

          // Left side: < __pivot_pos; __right side: >= __pivot_pos

          // Swap pivot back to middle.

          if (__split_pos1 != __pivot_pos)

            std::iter_swap(__split_pos1, __pivot_pos);

          __pivot_pos = __split_pos1;

          // In case all elements are equal, __split_pos1 == 0

          if ((__split_pos1 + 1 - __begin) < (__n >> 7)

              || (__end - __split_pos1) < (__n >> 7))

            {

              // Very unequal split, one part smaller than one 128th

              // elements not strictly larger than the pivot.

              __gnu_parallel::__unary_negate<__gnu_parallel::

                __binder1st<_Compare, _ValueType,

                            _ValueType, bool>, _ValueType>

                __pred(__gnu_parallel::__binder1st<_Compare, _ValueType,

                       _ValueType, bool>(__comp, *__pivot_pos));

              // Find other end of pivot-equal range.

              __split_pos2 = __gnu_sequential::partition(__split_pos1 + 1,

                                                         __end, __pred);

            }

          else

            // Only skip the pivot.

            __split_pos2 = __split_pos1 + 1;

          // Compare iterators.

          if (__split_pos2 <= __nth)

            __begin = __split_pos2;

          else if (__nth < __split_pos1)

            __end = __split_pos1;

          else

            break;

        }

      // Only at most _Settings::partition_minimal_n __elements __left.

      __gnu_sequential::nth_element(__begin, __nth, __end, __comp);

    }

  /** @brief Parallel implementation of std::partial_sort().

  *  @param __begin Begin iterator of input sequence.

  *  @param __middle Sort until this position.

  *  @param __end End iterator of input sequence.

  *  @param __comp Comparator. */

  template<typename _RAIter, typename _Compare>

    void

    __parallel_partial_sort(_RAIter __begin,

                            _RAIter __middle,

                            _RAIter __end, _Compare __comp)

    {

      __parallel_nth_element(__begin, __middle, __end, __comp);

      std::sort(__begin, __middle, __comp);

    }

} //namespace __gnu_parallel

#undef _GLIBCXX_VOLATILE

#endif /* _GLIBCXX_PARALLEL_PARTITION_H */