lib/sorter/s-twoway.h

   1 /*
   2  *      UCW Library -- Universal Sorter: Two-Way Merge 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: There is a plenty of room for further optimization */
  11 /* FIXME: Swap outputs if there already are some runs? */
  12
  13 static void P(twoway_merge)(struct sort_context *ctx UNUSED, struct sort_bucket **ins, struct sort_bucket **outs)
  14 {
  15   struct fastbuf *fin1, *fin2, *fout1, *fout2, *ftmp;
  16   P(key) kbuf1, kbuf2, kbuf3, kbuf4;
  17   P(key) *kin1 = &kbuf1, *kprev1 = &kbuf2, *kin2 = &kbuf3, *kprev2 = &kbuf4;
  18   P(key) *kout = NULL, *ktmp;
  19   int next1, next2, run1, run2;
  20   int comp;
  21   uns run_count = 0;
  22
  23   fin1 = sbuck_read(ins[0]);
  24   next1 = P(read_key)(fin1, kin1);
  25   if (sbuck_have(ins[1]))
  26     {
  27       fin2 = sbuck_read(ins[1]);
  28       next2 = P(read_key)(fin2, kin2);
  29     }
  30   else
  31     {
  32       fin2 = NULL;
  33       next2 = 0;
  34     }
  35   fout1 = fout2 = NULL;
  36
  37   run1 = next1, run2 = next2;
  38   while (next1 || next2)
  39     {
  40       if (!run1)
  41         comp = 1;
  42       else if (!run2)
  43         comp = -1;
  44       else
  45         comp = P(compare)(kin1, kin2);
  46       ktmp = (comp <= 0) ? kin1 : kin2;
  47       if (!kout || !(P(compare)(kout, ktmp) LESS 0))
  48         {
  49           SWAP(fout1, fout2, ftmp);
  50           if (unlikely(!fout1))
  51             {
  52               if (!fout2)
  53                 fout1 = sbuck_write(outs[0]);
  54               else if (outs[1])
  55                 fout1 = sbuck_write(outs[1]);
  56               else
  57                 fout1 = fout2;
  58             }
  59           run_count++;
  60         }
  61 #ifdef SORT_ASSERT_UNIQUE
  62       ASSERT(comp != 0);
  63 #endif
  64       if (comp LESS 0)
  65         {
  66           P(copy_data)(kin1, fin1, fout1);
  67           SWAP(kin1, kprev1, ktmp);
  68           next1 = P(read_key)(fin1, kin1);
  69           run1 = next1 && (P(compare)(kprev1, kin1) LESS 0);
  70           kout = kprev1;
  71         }
  72 #ifdef SORT_UNIFY
  73       else if (comp == 0)
  74         {
  75           P(key) *mkeys[] = { kin1, kin2 };
  76           struct fastbuf *mfb[] = { fin1, fin2 };
  77           P(copy_merged)(mkeys, mfb, 2, fout1);
  78           SWAP(kin1, kprev1, ktmp);
  79           next1 = P(read_key)(fin1, kin1);
  80           run1 = next1 && (P(compare)(kprev1, kin1) LESS 0);
  81           SWAP(kin2, kprev2, ktmp);
  82           next2 = P(read_key)(fin2, kin2);
  83           run2 = next2 && (P(compare)(kprev2, kin2) LESS 0);
  84           kout = kprev2;
  85         }
  86 #endif
  87       else
  88         {
  89           P(copy_data)(kin2, fin2, fout1);
  90           SWAP(kin2, kprev2, ktmp);
  91           next2 = P(read_key)(fin2, kin2);
  92           run2 = next2 && (P(compare)(kprev2, kin2) LESS 0);
  93           kout = kprev2;
  94         }
  95       if (!run1 && !run2)
  96         {
  97           run1 = next1;
  98           run2 = next2;
  99         }
 100     }
 101
 102   if (fout2 && fout2 != fout1)
 103     outs[1]->runs += run_count / 2;
 104   if (fout1)
 105     outs[0]->runs += (run_count+1) / 2;
 106 }