13 #ifndef STXXL_INTKSORT_HEADER
14 #define STXXL_INTKSORT_HEADER
18 #include <stxxl/bits/common/types.h>
19 #include <stxxl/bits/unused.h>
20 #include <stxxl/bits/parallel.h>
23 __STXXL_BEGIN_NAMESPACE
25 template <
typename type_key>
27 count(type_key * a, type_key * aEnd, int_type * bucket, int_type K,
typename type_key::key_type offset,
31 std::fill(bucket, bucket + K, 0);
34 for (type_key * p = a; p < aEnd; p++)
36 int_type i = (p->key - offset) >> shift;
50 exclusive_prefix_sum(int_type * bucket, int_type K)
53 for (int_type i = 0; i < K; i++)
55 int_type current = bucket[i];
63 template <
typename type_key>
65 classify(type_key * a, type_key * aEnd, type_key * b, int_type * bucket,
typename type_key::key_type offset,
unsigned shift)
67 for (type_key * p = a; p < aEnd; p++)
69 int_type i = (p->key - offset) >> shift;
70 int_type bi = bucket[i];
87 sort3(T & a, T & b, T & c)
134 sort4(T & a, T & b, T & c, T & d)
187 sort5(T & a, T & b, T & c, T & d, T & e)
234 insertion_sort(T * a, T * aEnd)
237 for (T * p = a + 1; p < aEnd; p++)
244 for (pp = p; pp != a; pp--)
253 for (pp = p; t < *(pp - 1); pp--)
267 cleanup(T * b, int_type * bucket, int_type K)
270 for (int_type i = 0; i < K; i++)
272 T * cEnd = b + bucket[i];
283 sort3(c[0], c[1], c[2]);
286 sort4(c[0], c[1], c[2], c[3]);
290 sort5(c[0], c[1], c[2], c[3], c[4]);
304 insertion_sort(c, cEnd);
320 template <
typename type_key>
324 type_key * b, int_type * bucket, int_type K,
typename type_key::key_type offset,
int shift)
326 count(a, aEnd, bucket, K, offset, shift);
327 exclusive_prefix_sum(bucket, K);
328 classify(a, aEnd, b, bucket, offset, shift);
329 cleanup(b, bucket, K);
332 template <
typename type,
typename type_key,
typename key_extractor>
333 void classify_block(type * begin, type * end, type_key * & out,
334 int_type * bucket,
typename key_extractor::key_type offset,
unsigned shift, key_extractor keyobj)
336 assert(shift < (
sizeof(
typename key_extractor::key_type) * 8 + 1));
337 for (type * p = begin; p < end; p++, out++)
340 typename key_extractor::key_type key = keyobj(*p);
341 int_type ibucket = (key - offset) >> shift;
346 template <
typename type,
typename type_key,
typename key_extractor>
347 void classify_block(type * begin, type * end, type_key * & out, int_type * bucket,
typename type::key_type offset,
unsigned shift,
348 const int_type K, key_extractor keyobj)
350 assert(shift < (
sizeof(
typename type::key_type) * 8 + 1));
351 for (type * p = begin; p < end; p++, out++)
354 typename type::key_type key = keyobj(*p);
355 int_type ibucket = (key - offset) >> shift;
369 __STXXL_END_NAMESPACE
371 #endif // !STXXL_INTKSORT_HEADER
void sort(ExtIterator_ first, ExtIterator_ last, StrictWeakOrdering_ cmp, unsigned_type M)
Sort records comparison-based.
Definition: sort.h:700