list_partition.h
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 InputIterator>
00049 void
00050 shrink_and_double(std::vector<InputIterator>& os_starts,
00051 size_t& count_to_two, size_t& range_length,
00052 const bool make_twice)
00053 {
00054 ++count_to_two;
00055 if (not make_twice or 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 InputIterator>
00069 void
00070 shrink(std::vector<InputIterator>& os_starts, size_t& count_to_two,
00071 size_t& range_length)
00072 {
00073 for (typename std::vector<InputIterator>::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 template<typename InputIterator, typename FunctorType>
00099 size_t
00100 list_partition(const InputIterator begin, const InputIterator end,
00101 InputIterator* starts, size_t* lengths, const int num_parts,
00102 FunctorType& f, int oversampling = 0)
00103 {
00104 bool make_twice = false;
00105
00106
00107 if (oversampling == 0)
00108 {
00109 make_twice = true;
00110 oversampling = 1;
00111 }
00112
00113 std::vector<InputIterator> os_starts(2 * oversampling * num_parts + 1);
00114
00115 os_starts[0]= begin;
00116 InputIterator prev = begin, it = begin;
00117 size_t dist_limit = 0, dist = 0;
00118 size_t cur = 1, next = 1;
00119 size_t range_length = 1;
00120 size_t count_to_two = 0;
00121 while (it != end)
00122 {
00123 cur = next;
00124 for (; cur < os_starts.size() and it != end; ++cur)
00125 {
00126 for (dist_limit += range_length;
00127 dist < dist_limit and it != end; ++dist)
00128 {
00129 f(it);
00130 ++it;
00131 }
00132 os_starts[cur] = it;
00133 }
00134
00135
00136
00137 if (it == end)
00138 break;
00139
00140 shrink_and_double(os_starts, count_to_two, range_length, make_twice);
00141 next = os_starts.size() / 2 + 1;
00142 }
00143
00144
00145
00146
00147 size_t size_part = (cur - 1) / num_parts;
00148 int size_greater = static_cast<int>((cur - 1) % num_parts);
00149 starts[0] = os_starts[0];
00150
00151 size_t index = 0;
00152
00153
00154 for (int i = 1; i < (num_parts + 1 - size_greater); ++i)
00155 {
00156 lengths[i - 1] = size_part * range_length;
00157 index += size_part;
00158 starts[i] = os_starts[index];
00159 }
00160
00161
00162 for (int i = num_parts + 1 - size_greater; i <= num_parts; ++i)
00163 {
00164 lengths[i - 1] = (size_part+1) * range_length;
00165 index += (size_part+1);
00166 starts[i] = os_starts[index];
00167 }
00168
00169
00170 lengths[num_parts - 1] -= (dist_limit - dist);
00171
00172 return dist;
00173 }
00174 }
00175
00176 #endif