2 * UCW Library -- Optimized Array Sorter
4 * (c) 2003--2007 Martin Mares <mj@ucw.cz>
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
13 #include "lib/sorter/common.h"
17 #define ASORT_MIN_RADIX 5000 // FIXME: var?
18 #define ASORT_MIN_SHIFT 2
21 asort_radix(struct asort_context *ctx, void *array, void *buffer, uns num_elts, uns hash_bits, uns swapped_output)
23 uns buckets = (1 << ctx->radix_bits);
24 uns shift = (hash_bits > ctx->radix_bits) ? (hash_bits - ctx->radix_bits) : 0;
28 static int reported[64];
29 if (!reported[hash_bits]++)
31 DBG(">>> n=%d h=%d s=%d sw=%d", num_elts, hash_bits, shift, swapped_output);
33 bzero(cnt, sizeof(cnt));
34 ctx->radix_count(array, num_elts, cnt, shift);
37 for (uns i=0; i<buckets; i++)
43 ASSERT(pos == num_elts);
45 ctx->radix_split(array, buffer, num_elts, cnt, shift);
47 for (uns i=0; i<buckets; i++)
50 if (n < ASORT_MIN_RADIX || shift < ASORT_MIN_SHIFT)
52 ctx->quicksort(buffer, n);
54 memcpy(array, buffer, n * ctx->elt_size);
57 asort_radix(ctx, buffer, array, n, shift, !swapped_output);
58 array += n * ctx->elt_size;
59 buffer += n * ctx->elt_size;
65 asort_run(struct asort_context *ctx)
67 SORT_XTRACE(10, "Array-sorting %d items per %d bytes, hash_bits=%d", ctx->num_elts, ctx->elt_size, ctx->hash_bits);
69 if (ctx->num_elts < ASORT_MIN_RADIX ||
70 ctx->hash_bits <= ASORT_MIN_SHIFT ||
72 (sorter_debug & SORT_DEBUG_ASORT_NO_RADIX))
74 SORT_XTRACE(12, "Decided to use direct quicksort");
75 ctx->quicksort(ctx->array, ctx->num_elts);
79 SORT_XTRACE(12, "Decided to use radix-sort");
80 // FIXME: select dest buffer
81 asort_radix(ctx, ctx->array, ctx->buffer, ctx->num_elts, ctx->hash_bits, 0);
84 SORT_XTRACE(11, "Array-sort finished");