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)
Private Member Functions inherited from tbb::internal::no_assign
void	operator= (const no_assign &)=delete
	no_assign (const no_assign &)=default
	no_assign ()=default

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 46 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 106 of file parallel_sort.h.

                                                                                        :
        comp(comp_), size(size_), begin(begin_) {}

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 112 of file parallel_sort.h.

        : comp(range.comp)
        , size(split_range(range))
          // +1 accounts for the pivot element, which is at its correct place
          // already and, therefore, is not included into subranges.
        , begin(range.begin+range.size+1) {}

Member Function Documentation

empty()

template<typename RandomAccessIterator, typename Compare>

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

inline

Definition at line 109 of file parallel_sort.h.

{return size==0;}

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

is_divisible()

template<typename RandomAccessIterator, typename Compare>

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

inline

Definition at line 110 of file parallel_sort.h.

{return size>=grainsize;}

References tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::grainsize, and tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::size.

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 48 of file parallel_sort.h.

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

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 53 of file parallel_sort.h.

                                                                                                                  {
        size_t offset = range.size/8u;
        return median_of_three(array,
                               median_of_three(array, 0, offset, offset*2),
                               median_of_three(array, offset*3, offset*4, offset*5),
                               median_of_three(array, offset*6, offset*7, range.size - 1) );

    }

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 62 of file parallel_sort.h.

                                                  {
        using std::iter_swap;
        RandomAccessIterator array = range.begin;
        RandomAccessIterator key0 = range.begin;
        size_t m = pseudo_median_of_nine(array, range);
        if (m) iter_swap ( array, array+m );

        size_t i=0;
        size_t j=range.size;
        // Partition interval [i+1,j-1] with key *key0.
        for(;;) {
            __TBB_ASSERT( i<j, NULL );
            // Loop must terminate since array[l]==*key0.
            do {
                --j;
                __TBB_ASSERT( i<=j, "bad ordering relation?" );
            } while( comp( *key0, array[j] ));
            do {
                __TBB_ASSERT( i<=j, NULL );
                if( i==j ) goto partition;
                ++i;
            } while( comp( array[i],*key0 ));
            if( i==j ) goto partition;
            iter_swap( array+i, array+j );
        }
partition:
        // Put the partition key were it belongs
        iter_swap( array+j, key0 );
        // array[l..j) is less or equal to key.
        // array(j..r) is greater or equal to key.
        // array[j] is equal to key
        i=j+1;
        size_t new_range_size = range.size-i;
        range.size = j;
        return new_range_size;
    }

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

Definition at line 104 of file parallel_sort.h.

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

comp

template<typename RandomAccessIterator, typename Compare>

const Compare& tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::comp

Definition at line 102 of file parallel_sort.h.

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

grainsize

template<typename RandomAccessIterator, typename Compare>

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

static

Definition at line 101 of file parallel_sort.h.

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

size

template<typename RandomAccessIterator, typename Compare>

size_t tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::size

Definition at line 103 of file parallel_sort.h.

Referenced by tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::empty(), tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::is_divisible(), tbb::interface9::internal::quick_sort_body< RandomAccessIterator, Compare >::operator()(), tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::pseudo_median_of_nine(), and tbb::interface9::internal::quick_sort_range< RandomAccessIterator, Compare >::split_range().

---

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

• parallel_sort.h