Where Online Learning is simpler!

The C and C++ Include Header Files

/usr/include/c++/13/parallel/quicksort.h

$ cat -n /usr/include/c++/13/parallel/quicksort.h

     1	// -*- C++ -*-
     2	
     3	// Copyright (C) 2007-2023 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 3, 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	// Under Section 7 of GPL version 3, you are granted additional
    17	// permissions described in the GCC Runtime Library Exception, version
    18	// 3.1, as published by the Free Software Foundation.
    19	
    20	// You should have received a copy of the GNU General Public License and
    21	// a copy of the GCC Runtime Library Exception along with this program;
    22	// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
    23	// <http://www.gnu.org/licenses/>.
    24	
    25	/** @file parallel/quicksort.h
    26	 *  @brief Implementation of a unbalanced parallel quicksort (in-place).
    27	 *  This file is a GNU parallel extension to the Standard C++ Library.
    28	 */
    29	
    30	// Written by Johannes Singler.
    31	
    32	#ifndef _GLIBCXX_PARALLEL_QUICKSORT_H
    33	#define _GLIBCXX_PARALLEL_QUICKSORT_H 1
    34	
    35	#include <parallel/parallel.h>
    36	#include <parallel/partition.h>
    37	
    38	namespace __gnu_parallel
    39	{
    40	  /** @brief Unbalanced quicksort divide step.
    41	   *  @param __begin Begin iterator of subsequence.
    42	   *  @param __end End iterator of subsequence.
    43	   *  @param __comp Comparator.
    44	   *  @param __pivot_rank Desired __rank of the pivot.
    45	   *  @param __num_samples Choose pivot from that many samples.
    46	   *  @param __num_threads Number of threads that are allowed to work on
    47	   *  this part.
    48	   */
    49	  template<typename _RAIter, typename _Compare>
    50	    typename std::iterator_traits<_RAIter>::difference_type
    51	    __parallel_sort_qs_divide(_RAIter __begin, _RAIter __end,
    52				      _Compare __comp, typename std::iterator_traits
    53				      <_RAIter>::difference_type __pivot_rank,
    54				      typename std::iterator_traits
    55				      <_RAIter>::difference_type
    56				      __num_samples, _ThreadIndex __num_threads)
    57	    {
    58	      typedef std::iterator_traits<_RAIter> _TraitsType;
    59	      typedef typename _TraitsType::value_type _ValueType;
    60	      typedef typename _TraitsType::difference_type _DifferenceType;
    61	
    62	      _DifferenceType __n = __end - __begin;
    63	      __num_samples = std::min(__num_samples, __n);
    64	
    65	      // Allocate uninitialized, to avoid default constructor.
    66	      _ValueType* __samples = static_cast<_ValueType*>
    67		(::operator new(__num_samples * sizeof(_ValueType)));
    68	
    69	      for (_DifferenceType __s = 0; __s < __num_samples; ++__s)
    70	        {
    71	          const unsigned long long __index = static_cast<unsigned long long>
    72		    (__s) * __n / __num_samples;
    73	          ::new(&(__samples[__s])) _ValueType(__begin[__index]);
    74	        }
    75	
    76	      __gnu_sequential::sort(__samples, __samples + __num_samples, __comp);
    77	
    78	      _ValueType& __pivot = __samples[__pivot_rank * __num_samples / __n];
    79	
    80	      __gnu_parallel::__binder2nd<_Compare, _ValueType, _ValueType, bool>
    81	        __pred(__comp, __pivot);
    82	      _DifferenceType __split = __parallel_partition(__begin, __end,
    83							     __pred, __num_threads);
    84	
    85	      for (_DifferenceType __s = 0; __s < __num_samples; ++__s)
    86		__samples[__s].~_ValueType();
    87	      ::operator delete(__samples);
    88	
    89	      return __split;
    90	    }
    91	
    92	  /** @brief Unbalanced quicksort conquer step.
    93	   *  @param __begin Begin iterator of subsequence.
    94	   *  @param __end End iterator of subsequence.
    95	   *  @param __comp Comparator.
    96	   *  @param __num_threads Number of threads that are allowed to work on
    97	   *  this part.
    98	   */
    99	  template<typename _RAIter, typename _Compare>
   100	    void
   101	    __parallel_sort_qs_conquer(_RAIter __begin, _RAIter __end,
   102				       _Compare __comp,
   103				       _ThreadIndex __num_threads)
   104	    {
   105	      typedef std::iterator_traits<_RAIter> _TraitsType;
   106	      typedef typename _TraitsType::value_type _ValueType;
   107	      typedef typename _TraitsType::difference_type _DifferenceType;
   108	
   109	      if (__num_threads <= 1)
   110	        {
   111	          __gnu_sequential::sort(__begin, __end, __comp);
   112	          return;
   113	        }
   114	
   115	      _DifferenceType __n = __end - __begin, __pivot_rank;
   116	
   117	      if (__n <= 1)
   118	        return;
   119	
   120	      _ThreadIndex __num_threads_left;
   121	
   122	      if ((__num_threads % 2) == 1)
   123	        __num_threads_left = __num_threads / 2 + 1;
   124	      else
   125	        __num_threads_left = __num_threads / 2;
   126	
   127	      __pivot_rank = __n * __num_threads_left / __num_threads;
   128	
   129	      _DifferenceType __split = __parallel_sort_qs_divide
   130		(__begin, __end, __comp, __pivot_rank,
   131		 _Settings::get().sort_qs_num_samples_preset, __num_threads);
   132	
   133	#pragma omp parallel sections num_threads(2)
   134	      {
   135	#pragma omp section
   136	        __parallel_sort_qs_conquer(__begin, __begin + __split,
   137					   __comp, __num_threads_left);
   138	#pragma omp section
   139	        __parallel_sort_qs_conquer(__begin + __split, __end,
   140					   __comp, __num_threads - __num_threads_left);
   141	      }
   142	    }
   143	
   144	
   145	  /** @brief Unbalanced quicksort main call.
   146	   *  @param __begin Begin iterator of input sequence.
   147	   *  @param __end End iterator input sequence, ignored.
   148	   *  @param __comp Comparator.
   149	   *  @param __num_threads Number of threads that are allowed to work on
   150	   *  this part.
   151	   */
   152	  template<typename _RAIter, typename _Compare>
   153	    void
   154	    __parallel_sort_qs(_RAIter __begin, _RAIter __end,
   155			       _Compare __comp,
   156			       _ThreadIndex __num_threads)
   157	    {
   158	      _GLIBCXX_CALL(__n)
   159	
   160	      typedef std::iterator_traits<_RAIter> _TraitsType;
   161	      typedef typename _TraitsType::value_type _ValueType;
   162	      typedef typename _TraitsType::difference_type _DifferenceType;
   163	
   164	      _DifferenceType __n = __end - __begin;
   165	
   166	      // At least one element per processor.
   167	      if (__num_threads > __n)
   168	        __num_threads = static_cast<_ThreadIndex>(__n);
   169	
   170	      __parallel_sort_qs_conquer(
   171	        __begin, __begin + __n, __comp, __num_threads);
   172	    }
   173	
   174	} //namespace __gnu_parallel
   175	
   176	#endif /* _GLIBCXX_PARALLEL_QUICKSORT_H */
Welcome to MyWebUniversity on April 15, 2025.
