13 #ifndef STXXL_INTKSORT_HEADER
14 #define STXXL_INTKSORT_HEADER
16 #include <stxxl/bits/common/utils.h>
19 __STXXL_BEGIN_NAMESPACE
21 template <
typename type_key>
23 count(type_key * a, type_key * aEnd, int_type * bucket, int_type K,
typename type_key::key_type offset,
27 std::fill(bucket, bucket + K, 0);
30 for (type_key * p = a; p < aEnd; p++)
32 int_type i = (p->key - offset) >> shift;
46 exclusive_prefix_sum(int_type * bucket, int_type K)
49 for (int_type i = 0; i < K; i++)
51 int_type current = bucket[i];
59 template <
typename type_key>
61 classify(type_key * a, type_key * aEnd, type_key * b, int_type * bucket,
typename type_key::key_type offset,
unsigned shift)
63 for (type_key * p = a; p < aEnd; p++)
65 int_type i = (p->key - offset) >> shift;
66 int_type bi = bucket[i];
83 sort3(T & a, T & b, T & c)
130 sort4(T & a, T & b, T & c, T & d)
183 sort5(T & a, T & b, T & c, T & d, T & e)
230 insertion_sort(T * a, T * aEnd)
233 for (T * p = a + 1; p < aEnd; p++)
240 for (pp = p; pp != a; pp--)
249 for (pp = p; t < *(pp - 1); pp--)
263 cleanup(T * b, int_type * bucket, int_type K)
266 for (int_type i = 0; i < K; i++)
268 T * cEnd = b + bucket[i];
279 sort3(c[0], c[1], c[2]);
282 sort4(c[0], c[1], c[2], c[3]);
297 insertion_sort(c, cEnd);
312 template <
typename type_key>
316 type_key * b, int_type * bucket, int_type K,
typename type_key::key_type offset,
int shift)
318 count(a, aEnd, bucket, K, offset, shift);
319 exclusive_prefix_sum(bucket, K);
320 classify(a, aEnd, b, bucket, offset, shift);
321 cleanup(b, bucket, K);
324 template <
typename type,
typename type_key,
typename key_extractor>
325 void classify_block(type * begin, type * end, type_key * & out,
326 int_type * bucket,
typename key_extractor::key_type offset,
unsigned shift, key_extractor keyobj)
328 assert(shift < (
sizeof(
typename key_extractor::key_type) * 8 + 1));
329 for (type * p = begin; p < end; p++, out++)
332 typename key_extractor::key_type key = keyobj(*p);
333 int_type ibucket = (key - offset) >> shift;
338 template <
typename type,
typename type_key,
typename key_extractor>
339 void classify_block(type * begin, type * end, type_key * & out, int_type * bucket,
typename type::key_type offset,
unsigned shift,
340 const int_type K, key_extractor keyobj)
342 assert(shift < (
sizeof(
typename type::key_type) * 8 + 1));
343 for (type * p = begin; p < end; p++, out++)
346 typename type::key_type key = keyobj(*p);
347 int_type ibucket = (key - offset) >> shift;
360 __STXXL_END_NAMESPACE
362 #endif // !STXXL_INTKSORT_HEADER