00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef STXXL_INTKSORT_HEADER
00014 #define STXXL_INTKSORT_HEADER
00015
00016 #include <algorithm>
00017 #include <cassert>
00018 #include <stxxl/bits/common/types.h>
00019 #include <stxxl/bits/unused.h>
00020 #include <stxxl/bits/parallel.h>
00021
00022
00023 __STXXL_BEGIN_NAMESPACE
00024
00025 template <typename type_key>
00026 static void
00027 count(type_key * a, type_key * aEnd, int_type * bucket, int_type K, typename type_key::key_type offset,
00028 unsigned shift)
00029 {
00030
00031 std::fill(bucket, bucket + K, 0);
00032
00033
00034 for (type_key * p = a; p < aEnd; p++)
00035 {
00036 int_type i = (p->key - offset) >> shift;
00037
00038
00039
00040
00041
00042
00043
00044 bucket[i]++;
00045 }
00046 }
00047
00048
00049 static void
00050 exclusive_prefix_sum(int_type * bucket, int_type K)
00051 {
00052 int_type sum = 0;
00053 for (int_type i = 0; i < K; i++)
00054 {
00055 int_type current = bucket[i];
00056 bucket[i] = sum;
00057 sum += current;
00058 }
00059 }
00060
00061
00062
00063 template <typename type_key>
00064 static void
00065 classify(type_key * a, type_key * aEnd, type_key * b, int_type * bucket, typename type_key::key_type offset, unsigned shift)
00066 {
00067 for (type_key * p = a; p < aEnd; p++)
00068 {
00069 int_type i = (p->key - offset) >> shift;
00070 int_type bi = bucket[i];
00071 b[bi] = *p;
00072 bucket[i] = bi + 1;
00073 }
00074 }
00075
00076
00077 template <class T>
00078 inline void
00079 sort2(T & a, T & b)
00080 {
00081 if (b < a)
00082 std::swap(a, b);
00083 }
00084
00085 template <class T>
00086 inline void
00087 sort3(T & a, T & b, T & c)
00088 {
00089 T temp;
00090 if (b < a)
00091 {
00092 if (c < a)
00093 {
00094 if (b < c)
00095 {
00096 temp = a;
00097 a = b;
00098 b = c;
00099 c = temp;
00100 }
00101 else
00102 {
00103 std::swap(c, a);
00104 }
00105 }
00106 else
00107 {
00108 std::swap(a, b);
00109 }
00110 }
00111 else
00112 {
00113 if (c < a)
00114 {
00115 temp = a;
00116 a = c;
00117 c = b;
00118 b = temp;
00119 }
00120 else
00121 {
00122 if (c < b)
00123 {
00124 std::swap(b, c);
00125 }
00126 }
00127 }
00128
00129 }
00130
00131
00132 template <class T>
00133 inline void
00134 sort4(T & a, T & b, T & c, T & d)
00135 {
00136 sort2(a, b);
00137 sort2(c, d);
00138 if (c < a)
00139 {
00140 if (d < a)
00141 {
00142 std::swap(a, c);
00143 std::swap(b, d);
00144 }
00145 else
00146 {
00147 if (d < b)
00148 {
00149 T temp = a;
00150 a = c;
00151 c = d;
00152 d = b;
00153 b = temp;
00154 }
00155 else
00156 {
00157 T temp = a;
00158 a = c;
00159 c = b;
00160 b = temp;
00161 }
00162 }
00163 }
00164 else
00165 {
00166 if (c < b)
00167 {
00168 if (d < b)
00169 {
00170 T temp = b;
00171 b = c;
00172 c = d;
00173 d = temp;
00174 }
00175 else
00176 {
00177 std::swap(b, c);
00178 }
00179 }
00180 }
00181
00182 }
00183
00184
00185 template <class T>
00186 inline void
00187 sort5(T & a, T & b, T & c, T & d, T & e)
00188 {
00189 sort2(a, b);
00190 sort2(d, e);
00191 if (d < a)
00192 {
00193 std::swap(a, d);
00194 std::swap(b, e);
00195 }
00196 if (d < c)
00197 {
00198 std::swap(c, d);
00199 sort2(d, e);
00200 }
00201 else
00202 {
00203 sort2(a, c);
00204 }
00205
00206 if (d < b)
00207 {
00208 if (e < b)
00209 {
00210 T temp = b;
00211 b = c;
00212 c = d;
00213 d = e;
00214 e = temp;
00215 }
00216 else
00217 {
00218 T temp = b;
00219 b = c;
00220 c = d;
00221 d = temp;
00222 }
00223 }
00224 else
00225 {
00226 sort2(b, c);
00227 }
00228
00229 }
00230
00231
00232 template <class T>
00233 inline void
00234 insertion_sort(T * a, T * aEnd)
00235 {
00236 T * pp;
00237 for (T * p = a + 1; p < aEnd; p++)
00238 {
00239
00240 T t = *p;
00241 if (t < *a)
00242 {
00243
00244 for (pp = p; pp != a; pp--)
00245 {
00246 *pp = *(pp - 1);
00247 }
00248 *pp = t;
00249 }
00250 else
00251 {
00252
00253 for (pp = p; t < *(pp - 1); pp--)
00254 {
00255 *pp = *(pp - 1);
00256 }
00257 *pp = t;
00258 }
00259 }
00260 }
00261
00262
00263
00264
00265 template <class T>
00266 static void
00267 cleanup(T * b, int_type * bucket, int_type K)
00268 {
00269 T * c = b;
00270 for (int_type i = 0; i < K; i++)
00271 {
00272 T * cEnd = b + bucket[i];
00273 switch (cEnd - c)
00274 {
00275 case 0:
00276 break;
00277 case 1:
00278 break;
00279 case 2:
00280 sort2(c[0], c[1]);
00281 break;
00282 case 3:
00283 sort3(c[0], c[1], c[2]);
00284 break;
00285 case 4:
00286 sort4(c[0], c[1], c[2], c[3]);
00287 break;
00288 case 5:
00289 #if 0
00290 sort5(c[0], c[1], c[2], c[3], c[4]);
00291 break;
00292 #endif
00293 case 6:
00294 case 7:
00295 case 8:
00296 case 9:
00297 case 10:
00298 case 11:
00299 case 12:
00300 case 13:
00301 case 14:
00302 case 15:
00303 case 16:
00304 insertion_sort(c, cEnd);
00305 break;
00306 default:
00307 potentially_parallel::
00308 sort(c, cEnd);
00309 }
00310 c = cEnd;
00311 }
00312 }
00313
00314
00315
00316
00317
00318
00319
00320 template <typename type_key>
00321 void
00322 l1sort(type_key * a,
00323 type_key * aEnd,
00324 type_key * b, int_type * bucket, int_type K, typename type_key::key_type offset, int shift)
00325 {
00326 count(a, aEnd, bucket, K, offset, shift);
00327 exclusive_prefix_sum(bucket, K);
00328 classify(a, aEnd, b, bucket, offset, shift);
00329 cleanup(b, bucket, K);
00330 }
00331
00332 template <typename type, typename type_key, typename key_extractor>
00333 void classify_block(type * begin, type * end, type_key * & out,
00334 int_type * bucket, typename key_extractor::key_type offset, unsigned shift, key_extractor keyobj)
00335 {
00336 assert(shift < (sizeof(typename key_extractor::key_type) * 8 + 1));
00337 for (type * p = begin; p < end; p++, out++)
00338 {
00339 out->ptr = p;
00340 typename key_extractor::key_type key = keyobj(*p);
00341 int_type ibucket = (key - offset) >> shift;
00342 out->key = key;
00343 bucket[ibucket]++;
00344 }
00345 }
00346 template <typename type, typename type_key, typename key_extractor>
00347 void classify_block(type * begin, type * end, type_key * & out, int_type * bucket, typename type::key_type offset, unsigned shift,
00348 const int_type K, key_extractor keyobj)
00349 {
00350 assert(shift < (sizeof(typename type::key_type) * 8 + 1));
00351 for (type * p = begin; p < end; p++, out++)
00352 {
00353 out->ptr = p;
00354 typename type::key_type key = keyobj(*p);
00355 int_type ibucket = (key - offset) >> shift;
00356
00357
00358
00359
00360
00361
00362
00363 out->key = key;
00364 bucket[ibucket]++;
00365 }
00366 STXXL_UNUSED(K);
00367 }
00368
00369 __STXXL_END_NAMESPACE
00370
00371 #endif // !STXXL_INTKSORT_HEADER