lib/sorter/array.c

   1 /*
   2  *      UCW Library -- Optimized Array Sorter
   3  *
   4  *      (c) 2003--2007 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #define LOCAL_DEBUG
  11
  12 #include "lib/lib.h"
  13 #include "lib/sorter/common.h"
  14
  15 #include <string.h>
  16
  17 #define ASORT_MIN_RADIX 5000            // FIXME: var?
  18 #define ASORT_MIN_SHIFT 2
  19
  20 static void
  21 asort_radix(struct asort_context *ctx, void *array, void *buffer, uns num_elts, uns hash_bits, uns swapped_output)
  22 {
  23   uns buckets = (1 << ctx->radix_bits);
  24   uns shift = (hash_bits > ctx->radix_bits) ? (hash_bits - ctx->radix_bits) : 0;
  25   uns cnt[buckets];
  26
  27   DBG(">>> n=%d h=%d s=%d sw=%d", num_elts, hash_bits, shift, swapped_output);
  28
  29   bzero(cnt, sizeof(cnt));
  30   ctx->radix_count(array, num_elts, cnt, shift);
  31
  32   uns pos = 0;
  33   for (uns i=0; i<buckets; i++)
  34     {
  35       uns j = cnt[i];
  36       cnt[i] = pos;
  37       pos += j;
  38     }
  39   ASSERT(pos == num_elts);
  40
  41   ctx->radix_split(array, buffer, num_elts, cnt, shift);
  42   pos = 0;
  43   for (uns i=0; i<buckets; i++)
  44     {
  45       uns n = cnt[i] - pos;
  46       if (n < ASORT_MIN_RADIX || shift < ASORT_MIN_SHIFT)
  47         {
  48           ctx->quicksort(buffer, n);
  49           if (!swapped_output)
  50             memcpy(array, buffer, n * ctx->elt_size);
  51         }
  52       else
  53         asort_radix(ctx, buffer, array, n, shift, !swapped_output);
  54       array += n * ctx->elt_size;
  55       buffer += n * ctx->elt_size;
  56       pos = cnt[i];
  57     }
  58 }
  59
  60 void
  61 asort_run(struct asort_context *ctx)
  62 {
  63   SORT_XTRACE(10, "Array-sorting %d items per %d bytes, hash_bits=%d", ctx->num_elts, ctx->elt_size, ctx->hash_bits);
  64
  65   if (ctx->num_elts < ASORT_MIN_RADIX ||
  66       ctx->hash_bits <= ASORT_MIN_SHIFT ||
  67       !ctx->radix_split ||
  68       (sorter_debug & SORT_DEBUG_ASORT_NO_RADIX))
  69     {
  70       SORT_XTRACE(12, "Decided to use direct quicksort");
  71       ctx->quicksort(ctx->array, ctx->num_elts);
  72     }
  73   else
  74     {
  75       SORT_XTRACE(12, "Decided to use radix-sort");
  76       // FIXME: select dest buffer
  77       asort_radix(ctx, ctx->array, ctx->buffer, ctx->num_elts, ctx->hash_bits, 0);
  78     }
  79
  80   SORT_XTRACE(11, "Array-sort finished");
  81 }