Where Online Learning is simpler!

The C and C++ Include Header Files

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

     1	// -*- C++ -*-
     2	
     3	// Copyright (C) 2007-2025 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	#pragma GCC diagnostic push
    70	#pragma GCC diagnostic ignored "-Wlong-long" // LL literal
    71	      for (_DifferenceType __s = 0; __s < __num_samples; ++__s)
    72	        {
    73	          const unsigned long long __index = static_cast<unsigned long long>
    74		    (__s) * __n / __num_samples;
    75	          ::new(&(__samples[__s])) _ValueType(__begin[__index]);
    76	        }
    77	#pragma GCC diagnostic pop
    78	
    79	      __gnu_sequential::sort(__samples, __samples + __num_samples, __comp);
    80	
    81	      _ValueType& __pivot = __samples[__pivot_rank * __num_samples / __n];
    82	
    83	      __gnu_parallel::__binder2nd<_Compare, _ValueType, _ValueType, bool>
    84	        __pred(__comp, __pivot);
    85	      _DifferenceType __split = __parallel_partition(__begin, __end,
    86							     __pred, __num_threads);
    87	
    88	      for (_DifferenceType __s = 0; __s < __num_samples; ++__s)
    89		__samples[__s].~_ValueType();
    90	      ::operator delete(__samples);
    91	
    92	      return __split;
    93	    }
    94	
    95	  /** @brief Unbalanced quicksort conquer step.
    96	   *  @param __begin Begin iterator of subsequence.
    97	   *  @param __end End iterator of subsequence.
    98	   *  @param __comp Comparator.
    99	   *  @param __num_threads Number of threads that are allowed to work on
   100	   *  this part.
   101	   */
   102	  template<typename _RAIter, typename _Compare>
   103	    void
   104	    __parallel_sort_qs_conquer(_RAIter __begin, _RAIter __end,
   105				       _Compare __comp,
   106				       _ThreadIndex __num_threads)
   107	    {
   108	      typedef std::iterator_traits<_RAIter> _TraitsType;
   109	      typedef typename _TraitsType::value_type _ValueType;
   110	      typedef typename _TraitsType::difference_type _DifferenceType;
   111	
   112	      if (__num_threads <= 1)
   113	        {
   114	          __gnu_sequential::sort(__begin, __end, __comp);
   115	          return;
   116	        }
   117	
   118	      _DifferenceType __n = __end - __begin, __pivot_rank;
   119	
   120	      if (__n <= 1)
   121	        return;
   122	
   123	      _ThreadIndex __num_threads_left;
   124	
   125	      if ((__num_threads % 2) == 1)
   126	        __num_threads_left = __num_threads / 2 + 1;
   127	      else
   128	        __num_threads_left = __num_threads / 2;
   129	
   130	      __pivot_rank = __n * __num_threads_left / __num_threads;
   131	
   132	      _DifferenceType __split = __parallel_sort_qs_divide
   133		(__begin, __end, __comp, __pivot_rank,
   134		 _Settings::get().sort_qs_num_samples_preset, __num_threads);
   135	
   136	#pragma omp parallel sections num_threads(2)
   137	      {
   138	#pragma omp section
   139	        __parallel_sort_qs_conquer(__begin, __begin + __split,
   140					   __comp, __num_threads_left);
   141	#pragma omp section
   142	        __parallel_sort_qs_conquer(__begin + __split, __end,
   143					   __comp, __num_threads - __num_threads_left);
   144	      }
   145	    }
   146	
   147	
   148	  /** @brief Unbalanced quicksort main call.
   149	   *  @param __begin Begin iterator of input sequence.
   150	   *  @param __end End iterator input sequence, ignored.
   151	   *  @param __comp Comparator.
   152	   *  @param __num_threads Number of threads that are allowed to work on
   153	   *  this part.
   154	   */
   155	  template<typename _RAIter, typename _Compare>
   156	    void
   157	    __parallel_sort_qs(_RAIter __begin, _RAIter __end,
   158			       _Compare __comp,
   159			       _ThreadIndex __num_threads)
   160	    {
   161	      _GLIBCXX_CALL(__n)
   162	
   163	      typedef std::iterator_traits<_RAIter> _TraitsType;
   164	      typedef typename _TraitsType::value_type _ValueType;
   165	      typedef typename _TraitsType::difference_type _DifferenceType;
   166	
   167	      _DifferenceType __n = __end - __begin;
   168	
   169	      // At least one element per processor.
   170	      if (__num_threads > __n)
   171	        __num_threads = static_cast<_ThreadIndex>(__n);
   172	
   173	      __parallel_sort_qs_conquer(
   174	        __begin, __begin + __n, __comp, __num_threads);
   175	    }
   176	
   177	} //namespace __gnu_parallel
   178	
   179	#endif /* _GLIBCXX_PARALLEL_QUICKSORT_H */