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 #undef 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 #if 0
  28   static int reported[64];
  29   if (!reported[hash_bits]++)
  30 #endif
  31   DBG(">>> n=%d h=%d s=%d sw=%d", num_elts, hash_bits, shift, swapped_output);
  32
  33   bzero(cnt, sizeof(cnt));
  34   ctx->radix_count(array, num_elts, cnt, shift);
  35
  36   uns pos = 0;
  37   for (uns i=0; i<buckets; i++)
  38     {
  39       uns j = cnt[i];
  40       cnt[i] = pos;
  41       pos += j;
  42     }
  43   ASSERT(pos == num_elts);
  44
  45   ctx->radix_split(array, buffer, num_elts, cnt, shift);
  46   pos = 0;
  47   for (uns i=0; i<buckets; i++)
  48     {
  49       uns n = cnt[i] - pos;
  50       if (n < ASORT_MIN_RADIX || shift < ASORT_MIN_SHIFT)
  51         {
  52           ctx->quicksort(buffer, n);
  53           if (!swapped_output)
  54             memcpy(array, buffer, n * ctx->elt_size);
  55         }
  56       else
  57         asort_radix(ctx, buffer, array, n, shift, !swapped_output);
  58       array += n * ctx->elt_size;
  59       buffer += n * ctx->elt_size;
  60       pos = cnt[i];
  61     }
  62 }
  63
  64 void
  65 asort_run(struct asort_context *ctx)
  66 {
  67   SORT_XTRACE(10, "Array-sorting %d items per %d bytes, hash_bits=%d", ctx->num_elts, ctx->elt_size, ctx->hash_bits);
  68
  69   if (ctx->num_elts < ASORT_MIN_RADIX ||
  70       ctx->hash_bits <= ASORT_MIN_SHIFT ||
  71       !ctx->radix_split ||
  72       (sorter_debug & SORT_DEBUG_ASORT_NO_RADIX))
  73     {
  74       SORT_XTRACE(12, "Decided to use direct quicksort");
  75       ctx->quicksort(ctx->array, ctx->num_elts);
  76     }
  77   else
  78     {
  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);
  82     }
  83
  84   SORT_XTRACE(11, "Array-sort finished");
  85 }