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_open_read(ins[0]);
  24   next1 = P(read_key)(fin1, kin1);
  25   if (sbuck_can_read(ins[1]))
  26     {
  27       fin2 = sbuck_open_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_open_write(outs[0]);
  54               else if (outs[1])
  55                 fout1 = sbuck_open_write(outs[1]);
  56               else
  57                 fout1 = fout2;
  58             }
  59           run_count++;
  60         }
  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_MERGE
  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 #ifdef SORT_ASSERT_UNIQUE
  85       else if (unlikely(comp == 0))
  86         ASSERT(0);
  87 #endif
  88       else
  89         {
  90           P(copy_data)(kin2, fin2, fout1);
  91           SWAP(kin2, kprev2, ktmp);
  92           next2 = P(read_key)(fin2, kin2);
  93           run2 = next2 && (P(compare)(kprev2, kin2) LESS 0);
  94           kout = kprev2;
  95         }
  96       if (!run1 && !run2)
  97         {
  98           run1 = next1;
  99           run2 = next2;
 100         }
 101     }
 102
 103   sbuck_close_read(ins[0]);
 104   sbuck_close_read(ins[1]);
 105   if (fout2 && fout2 != fout1)
 106     outs[1]->runs += run_count / 2;
 107   if (fout1)
 108     outs[0]->runs += (run_count+1) / 2;
 109 }