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