Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033 #ifndef _GLIBCXX_PARALLEL_LIST_PARTITION_H
00034 #define _GLIBCXX_PARALLEL_LIST_PARTITION_H 1
00035
00036 #include <parallel/parallel.h>
00037 #include <vector>
00038
00039 namespace __gnu_parallel
00040 {
00041
00042
00043
00044
00045
00046
00047
00048 template<typename _IIter>
00049 void
00050 __shrink_and_double(std::vector<_IIter>& __os_starts,
00051 size_t& __count_to_two, size_t& __range_length,
00052 const bool __make_twice)
00053 {
00054 ++__count_to_two;
00055 if (!__make_twice || __count_to_two < 2)
00056 __shrink(__os_starts, __count_to_two, __range_length);
00057 else
00058 {
00059 __os_starts.resize((__os_starts.size() - 1) * 2 + 1);
00060 __count_to_two = 0;
00061 }
00062 }
00063
00064
00065
00066
00067
00068 template<typename _IIter>
00069 void
00070 __shrink(std::vector<_IIter>& __os_starts, size_t& __count_to_two,
00071 size_t& __range_length)
00072 {
00073 for (typename std::vector<_IIter>::size_type __i = 0;
00074 __i <= (__os_starts.size() / 2); ++__i)
00075 __os_starts[__i] = __os_starts[__i * 2];
00076 __range_length *= 2;
00077 }
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099 template<typename _IIter, typename _FunctorType>
00100 size_t
00101 list_partition(const _IIter __begin, const _IIter __end,
00102 _IIter* __starts, size_t* __lengths, const int __num_parts,
00103 _FunctorType& __f, int __oversampling = 0)
00104 {
00105 bool __make_twice = false;
00106
00107
00108 if (__oversampling == 0)
00109 {
00110 __make_twice = true;
00111 __oversampling = 1;
00112 }
00113
00114 std::vector<_IIter> __os_starts(2 * __oversampling * __num_parts + 1);
00115
00116 __os_starts[0] = __begin;
00117 _IIter __prev = __begin, __it = __begin;
00118 size_t __dist_limit = 0, __dist = 0;
00119 size_t __cur = 1, __next = 1;
00120 size_t __range_length = 1;
00121 size_t __count_to_two = 0;
00122 while (__it != __end)
00123 {
00124 __cur = __next;
00125 for (; __cur < __os_starts.size() and __it != __end; ++__cur)
00126 {
00127 for (__dist_limit += __range_length;
00128 __dist < __dist_limit and __it != __end; ++__dist)
00129 {
00130 __f(__it);
00131 ++__it;
00132 }
00133 __os_starts[__cur] = __it;
00134 }
00135
00136
00137
00138 if (__it == __end)
00139 break;
00140
00141 __shrink_and_double(__os_starts, __count_to_two, __range_length,
00142 __make_twice);
00143 __next = __os_starts.size() / 2 + 1;
00144 }
00145
00146
00147
00148
00149 size_t __size_part = (__cur - 1) / __num_parts;
00150 int __size_greater = static_cast<int>((__cur - 1) % __num_parts);
00151 __starts[0] = __os_starts[0];
00152
00153 size_t __index = 0;
00154
00155
00156 for (int __i = 1; __i < (__num_parts + 1 - __size_greater); ++__i)
00157 {
00158 __lengths[__i - 1] = __size_part * __range_length;
00159 __index += __size_part;
00160 __starts[__i] = __os_starts[__index];
00161 }
00162
00163
00164 for (int __i = __num_parts + 1 - __size_greater; __i <= __num_parts;
00165 ++__i)
00166 {
00167 __lengths[__i - 1] = (__size_part+1) * __range_length;
00168 __index += (__size_part+1);
00169 __starts[__i] = __os_starts[__index];
00170 }
00171
00172
00173 __lengths[__num_parts - 1] -= (__dist_limit - __dist);
00174
00175 return __dist;
00176 }
00177 }
00178
00179 #endif