lib/sorter/s-radix.h

   1 /*
   2  *      UCW Library -- Universal Sorter: Radix-Split Module
   3  *
   4  *      (c) 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 /* FIXME: This is a very trivial implementation so far. Use fbdirect and such things to speed up. */
  11
  12 #include <string.h>
  13
  14 static void P(radix_split)(struct sort_context *ctx UNUSED, struct sort_bucket *bin, struct sort_bucket **bouts, uns bitpos, uns numbits)
  15 {
  16   uns nbucks = 1 << numbits;
  17   uns mask = nbucks - 1;
  18   struct fastbuf *in = sbuck_read(bin);
  19   P(key) k;
  20
  21   struct fastbuf *outs[nbucks];
  22   bzero(outs, sizeof(outs));
  23
  24   while (P(read_key)(in, &k))
  25     {
  26       uns h = P(hash)(&k);
  27       uns i = (h >> bitpos) & mask;
  28       if (unlikely(!outs[i]))
  29         outs[i] = sbuck_write(bouts[i]);
  30       P(copy_data)(&k, in, outs[i]);
  31     }
  32 }