00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #ifndef __TBB_parallel_sort_H
00022 #define __TBB_parallel_sort_H
00023
00024 #include "parallel_for.h"
00025 #include <algorithm>
00026 #include <iterator>
00027 #include <functional>
00028
00029 namespace tbb {
00030
00032 namespace internal {
00033
00035
00037 template<typename RandomAccessIterator, typename Compare>
00038 struct quick_sort_range {
00039 static const size_t grainsize = 500;
00040 const Compare ∁
00041 RandomAccessIterator begin;
00042 size_t size;
00043
00044 quick_sort_range( RandomAccessIterator begin_, size_t size_, const Compare &comp_ ) :
00045 comp(comp_), begin(begin_), size(size_) {}
00046
00047 bool empty() const {return size==0;}
00048 bool is_divisible() const {return size>=grainsize;}
00049
00050 quick_sort_range( quick_sort_range& range, split ) : comp(range.comp) {
00051 RandomAccessIterator array = range.begin;
00052 RandomAccessIterator key0 = range.begin;
00053 size_t m = range.size/2u;
00054 std::swap ( array[0], array[m] );
00055
00056 size_t i=0;
00057 size_t j=range.size;
00058
00059 for(;;) {
00060 __TBB_ASSERT( i<j, NULL );
00061
00062 do {
00063 --j;
00064 __TBB_ASSERT( i<=j, "bad ordering relation?" );
00065 } while( comp( *key0, array[j] ));
00066 do {
00067 __TBB_ASSERT( i<=j, NULL );
00068 if( i==j ) goto partition;
00069 ++i;
00070 } while( comp( array[i],*key0 ));
00071 if( i==j ) goto partition;
00072 std::swap( array[i], array[j] );
00073 }
00074 partition:
00075
00076 std::swap( array[j], *key0 );
00077
00078
00079
00080 i=j+1;
00081 begin = array+i;
00082 size = range.size-i;
00083 range.size = j;
00084 }
00085 };
00086
00088
00089 template<typename RandomAccessIterator, typename Compare>
00090 struct quick_sort_body {
00091 void operator()( const quick_sort_range<RandomAccessIterator,Compare>& range ) const {
00092
00093 std::sort( range.begin, range.begin + range.size, range.comp );
00094 }
00095 };
00096
00098
00099 template<typename RandomAccessIterator, typename Compare>
00100 void parallel_quick_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp ) {
00101 parallel_for( quick_sort_range<RandomAccessIterator,Compare>(begin, end-begin, comp ), quick_sort_body<RandomAccessIterator,Compare>() );
00102 }
00103
00104 }
00106
00117
00119
00122 template<typename RandomAccessIterator, typename Compare>
00123 void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp) {
00124 const int min_parallel_size = 500;
00125 if( end > begin ) {
00126 if (end - begin < min_parallel_size) {
00127 std::sort(begin, end, comp);
00128 } else {
00129 internal::parallel_quick_sort(begin, end, comp);
00130 }
00131 }
00132 }
00133
00135
00136 template<typename RandomAccessIterator>
00137 inline void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end ) {
00138 parallel_sort( begin, end, std::less< typename std::iterator_traits<RandomAccessIterator>::value_type >() );
00139 }
00140
00142
00143 template<typename T>
00144 inline void parallel_sort( T * begin, T * end ) {
00145 parallel_sort( begin, end, std::less< T >() );
00146 }
00148
00149
00150 }
00151
00152 #endif
00153