Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare > Class Template Reference

Range used in quicksort to split elements into subranges based on a value. More...

#include <parallel_sort.h>

Inheritance diagram for tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >:
Collaboration diagram for tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >:

Public Member Functions

 quick_sort_range (RandomAccessIterator begin_, size_t size_, const Compare &comp_)
 
bool empty () const
 
bool is_divisible () const
 
 quick_sort_range (quick_sort_range &range, split)
 

Public Attributes

const Compare & comp
 
size_t size
 
RandomAccessIterator begin
 

Static Public Attributes

static const size_t grainsize = 500
 

Private Member Functions

size_t median_of_three (const RandomAccessIterator &array, size_t l, size_t m, size_t r) const
 
size_t pseudo_median_of_nine (const RandomAccessIterator &array, const quick_sort_range &range) const
 
size_t split_range (quick_sort_range &range)
 

Detailed Description

template<typename RandomAccessIterator, typename Compare>
class tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >

Range used in quicksort to split elements into subranges based on a value.

The split operation selects a splitter and places all elements less than or equal to the value in the first range and the remaining elements in the second range.

Definition at line 43 of file parallel_sort.h.

Constructor & Destructor Documentation

◆ quick_sort_range() [1/2]

template<typename RandomAccessIterator, typename Compare>
tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::quick_sort_range ( RandomAccessIterator  begin_,
size_t  size_,
const Compare &  comp_ 
)
inline

Definition at line 103 of file parallel_sort.h.

◆ quick_sort_range() [2/2]

template<typename RandomAccessIterator, typename Compare>
tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::quick_sort_range ( quick_sort_range< RandomAccessIterator, Compare > &  range,
split   
)
inline

Definition at line 109 of file parallel_sort.h.

110  : comp(range.comp)
111  , size(split_range(range))
112  // +1 accounts for the pivot element, which is at its correct place
113  // already and, therefore, is not included into subranges.
114  , begin(range.begin+range.size+1) {}
size_t split_range(quick_sort_range &range)
Definition: parallel_sort.h:59

Member Function Documentation

◆ empty()

template<typename RandomAccessIterator, typename Compare>
bool tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::empty ( ) const
inline

◆ is_divisible()

template<typename RandomAccessIterator, typename Compare>
bool tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::is_divisible ( ) const
inline

◆ median_of_three()

template<typename RandomAccessIterator, typename Compare>
size_t tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::median_of_three ( const RandomAccessIterator &  array,
size_t  l,
size_t  m,
size_t  r 
) const
inlineprivate

Definition at line 45 of file parallel_sort.h.

45  {
46  return comp(array[l], array[m]) ? ( comp(array[m], array[r]) ? m : ( comp( array[l], array[r]) ? r : l ) )
47  : ( comp(array[r], array[m]) ? m : ( comp( array[r], array[l] ) ? r : l ) );
48  }

References tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::comp.

Referenced by tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::pseudo_median_of_nine().

Here is the caller graph for this function:

◆ pseudo_median_of_nine()

template<typename RandomAccessIterator, typename Compare>
size_t tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::pseudo_median_of_nine ( const RandomAccessIterator &  array,
const quick_sort_range< RandomAccessIterator, Compare > &  range 
) const
inlineprivate

Definition at line 50 of file parallel_sort.h.

50  {
51  size_t offset = range.size/8u;
52  return median_of_three(array,
53  median_of_three(array, 0, offset, offset*2),
54  median_of_three(array, offset*3, offset*4, offset*5),
55  median_of_three(array, offset*6, offset*7, range.size - 1) );
56 
57  }
size_t median_of_three(const RandomAccessIterator &array, size_t l, size_t m, size_t r) const
Definition: parallel_sort.h:45

References tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::median_of_three(), and tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::size.

Referenced by tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::split_range().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ split_range()

template<typename RandomAccessIterator, typename Compare>
size_t tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::split_range ( quick_sort_range< RandomAccessIterator, Compare > &  range)
inlineprivate

Definition at line 59 of file parallel_sort.h.

59  {
60  using std::iter_swap;
61  RandomAccessIterator array = range.begin;
62  RandomAccessIterator key0 = range.begin;
63  size_t m = pseudo_median_of_nine(array, range);
64  if (m) iter_swap ( array, array+m );
65 
66  size_t i=0;
67  size_t j=range.size;
68  // Partition interval [i+1,j-1] with key *key0.
69  for(;;) {
70  __TBB_ASSERT( i<j, NULL );
71  // Loop must terminate since array[l]==*key0.
72  do {
73  --j;
74  __TBB_ASSERT( i<=j, "bad ordering relation?" );
75  } while( comp( *key0, array[j] ));
76  do {
77  __TBB_ASSERT( i<=j, NULL );
78  if( i==j ) goto partition;
79  ++i;
80  } while( comp( array[i],*key0 ));
81  if( i==j ) goto partition;
82  iter_swap( array+i, array+j );
83  }
84 partition:
85  // Put the partition key were it belongs
86  iter_swap( array+j, key0 );
87  // array[l..j) is less or equal to key.
88  // array(j..r) is greater or equal to key.
89  // array[j] is equal to key
90  i=j+1;
91  size_t new_range_size = range.size-i;
92  range.size = j;
93  return new_range_size;
94  }
size_t pseudo_median_of_nine(const RandomAccessIterator &array, const quick_sort_range &range) const
Definition: parallel_sort.h:50
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165

References __TBB_ASSERT, tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::begin, tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::comp, tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::pseudo_median_of_nine(), and tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::size.

Here is the call graph for this function:

Member Data Documentation

◆ begin

template<typename RandomAccessIterator, typename Compare>
RandomAccessIterator tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::begin

◆ comp

◆ grainsize

template<typename RandomAccessIterator, typename Compare>
const size_t tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::grainsize = 500
static

◆ size


The documentation for this class was generated from the following file:

Copyright © 2005-2019 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.