lib/sorter.h

   1 /*
   2  *      UCW Library -- Universal Sorter
   3  *
   4  *      (c) 2001--2004 Martin Mares <mj@ucw.cz>
   5  *      (c) 2004 Robert Spalek <robert@ucw.cz>
   6  *
   7  *      This software may be freely distributed and used according to the terms
   8  *      of the GNU Lesser General Public License.
   9  */
  10
  11 /*
  12  *  This is not a normal header file, it's a generator of sorting
  13  *  routines.  Each time you include it with parameters set in the
  14  *  corresponding preprocessor macros, it generates a file sorter
  15  *  with the parameters given.
  16  *
  17  *  Recognized parameter macros: (those marked with [*] are mandatory)
  18  *
  19  *  SORT_KEY        [*] data type capable of storing a single key
  20  *  SORT_PREFIX(x)  [*] add a name prefix (used on all global names
  21  *                      defined by the sorter)
  22  *  SORT_PRESORT        include an in-core pre-sorting pass. Beware, when in
  23  *                      the pre-sorting mode, it's quite possible that the
  24  *                      comparison function will be called with both arguments
  25  *                      identical.
  26  *  SORT_UP_TO          a C expression, if defined, sorting is stopped after the
  27  *                      average run length in the file exceeds the value of this
  28  *                      expression (in bytes)
  29  *  SORT_UNIFY          merge items with identical keys
  30  *  SORT_UNIQUE         all items have distinct keys (checked in debug mode)
  31  *  SORT_REGULAR        all items are equally long and they don't contain
  32  *                      anything else than the key. In this case, the sorter
  33  *                      automatically supplies fetch_key, copy_data, fetch_item
  34  *                      and store_item functions. Item size is also expected
  35  *                      to be small.
  36  *  SORT_DELETE_INPUT   a C expression, if true, the input files are
  37  *                      deleted as soon as possible
  38  *  SORT_INPUT_FILE     input is a file with this name
  39  *  SORT_INPUT_FB       input is a fastbuf stream
  40  *                      (can be safely NULL if you want to treat original
  41  *                      input in a different way by file read functions)
  42  *  SORT_INPUT_FBPAIR   input is a pair of fastbuf streams
  43  *                      (not supported by the presorter)
  44  *  SORT_OUTPUT_FILE    output is a file with this name
  45  *  SORT_OUTPUT_FB      output is a temporary fastbuf stream
  46  *
  47  *  You also need to define some (usually inline) functions which
  48  *  are called by the sorter to process your data:
  49  *
  50  *  int PREFIX_compare(SORT_KEY *a, *b)
  51  *                      compare two keys, result like strcmp
  52  *  int PREFIX_fetch_key(struct fastbuf *f, SORT_KEY *k)
  53  *                      fetch next key, returns nonzero=ok, 0=eof
  54  *  void PREFIX_copy_data(struct fastbuf *src, *dest, SORT_KEY *k)
  55  *                      write just fetched key k to dest and copy all data
  56  *                      belonging to this key from src to dest.
  57  *  void PREFIX_merge_data(struct fastbuf *src1, *src2, *dest, SORT_KEY *k1, *k2)
  58  *                      [used only in case SORT_UNIFY is defined]
  59  *                      write just fetched key k to dest and merge data from
  60  *                      two records with the same key (k1 and k2 are key occurences
  61  *                      in the corresponding streams).
  62  *  byte * PREFIX_fetch_item(struct fastbuf *f, SORT_KEY *k, byte *limit)
  63  *                      [used only with SORT_PRESORT]
  64  *                      fetch data belonging to a just fetched key and store
  65  *                      them to memory following the key, but not over limit.
  66  *                      Returns a pointer to first byte after the data
  67  *                      or NULL if the data don't fit. For variable-length
  68  *                      keys, it can use the rest of SORT_KEY and even return
  69  *                      pointer before end of the key.
  70  *                      Important: before PREFIX_fetch_item() succeeds, the key
  71  *                      must be position independent, the sorter can copy it.
  72  *  void PREFIX_store_item(struct fastbuf *f, SORT_KEY *k)
  73  *                      [used only with SORT_PRESORT]
  74  *                      write key and all its data read with PREFIX_fetch_data
  75  *                      to the stream given.
  76  *  SORT_KEY * PREFIX_merge_items(SORT_KEY *a, SORT_KEY *b)
  77  *                      [used only with SORT_PRESORT && SORT_UNIFY]
  78  *                      merge two items with the same key, returns pointer
  79  *                      to at most one of the items, the rest will be removed
  80  *                      from the list of items, but not deallocated, so
  81  *                      the remaining item can freely reference data of the
  82  *                      other one.
  83  *
  84  *  After including this file, all parameter macros are automatically
  85  *  undef'd.
  86  */
  87
  88 #include "lib/sorter-globals.h"
  89 #include "lib/fastbuf.h"
  90 #include <unistd.h>
  91 #include <fcntl.h>
  92 #include <string.h>
  93
  94 #if !defined(SORT_KEY) || !defined(SORT_PREFIX)
  95 #error Some of the mandatory configuration macros are missing.
  96 #endif
  97
  98 #define P(x) SORT_PREFIX(x)
  99 #define SWAP(x,y,z) do { z=x; x=y; y=z; } while(0)
 100
 101 #if defined(SORT_UNIFY) || defined(SORT_UNIQUE)
 102 #define LESS <
 103 #else
 104 #define LESS <=
 105 #endif
 106
 107 #if defined(SORT_UNIQUE) && defined(DEBUG_ASSERTS)
 108 #define SORT_ASSERT_UNIQUE
 109 #endif
 110
 111 #ifdef SORT_REGULAR
 112
 113 static inline int
 114 P(fetch_key)(struct fastbuf *in, SORT_KEY *x)
 115 {
 116   return breadb(in, x, sizeof(*x));
 117 }
 118
 119 static inline void
 120 P(copy_data)(struct fastbuf *in UNUSED, struct fastbuf *out, SORT_KEY *x)
 121 {
 122   bwrite(out, x, sizeof(*x));
 123 }
 124
 125 static inline byte *
 126 P(fetch_item)(struct fastbuf *in UNUSED, SORT_KEY *x UNUSED, byte *limit UNUSED)
 127 {
 128   return (byte *)(x+1);
 129 }
 130
 131 static inline void
 132 P(store_item)(struct fastbuf *out, SORT_KEY *x)
 133 {
 134   bwrite(out, x, sizeof(*x));
 135 }
 136
 137 #endif
 138
 139 static struct fastbuf *
 140 P(flush_out)(struct fastbuf *out)
 141 {
 142   if (out)
 143     brewind(out);
 144   return out;
 145 }
 146
 147 static uns
 148 P(pass)(struct fastbuf **fb1, struct fastbuf **fb2
 149 #ifdef SORT_UP_TO
 150     , uns stop_sorting
 151 #endif
 152 )
 153 {
 154   struct fastbuf *in1 = *fb1;
 155   struct fastbuf *in2 = *fb2;
 156   struct fastbuf *out1 = NULL;
 157   struct fastbuf *out2 = NULL;
 158   SORT_KEY kbuf1, kbuf2, kbuf3, kbuf4;
 159   SORT_KEY *kin1 = &kbuf1;
 160   SORT_KEY *kprev1 = &kbuf2;
 161   SORT_KEY *kin2 = &kbuf3;
 162   SORT_KEY *kprev2 = &kbuf4;
 163   SORT_KEY *kout = NULL;
 164   SORT_KEY *ktmp;
 165   int next1, next2, comp;
 166   int run1, run2;
 167   uns run_count = 0;
 168
 169   run1 = next1 = in1 ? P(fetch_key)(in1, kin1) : 0;
 170   run2 = next2 = in2 ? P(fetch_key)(in2, kin2) : 0;
 171   while (next1 || next2)
 172     {
 173       if (!run1)
 174         comp = 1;
 175       else if (!run2)
 176         comp = -1;
 177       else
 178         comp = P(compare)(kin1, kin2);
 179       ktmp = (comp <= 0) ? kin1 : kin2;
 180       if (!kout || !(P(compare)(kout, ktmp) LESS 0))
 181         {
 182           struct fastbuf *t;
 183 #ifdef SORT_UP_TO
 184           if (!stop_sorting)
 185 #endif
 186             SWAP(out1, out2, t);
 187           if (!out1)
 188             out1 = bopen_tmp(sorter_stream_bufsize);
 189           run_count++;
 190         }
 191       if (comp LESS 0)
 192         {
 193           P(copy_data)(in1, out1, kin1);
 194           SWAP(kin1, kprev1, ktmp);
 195           next1 = P(fetch_key)(in1, kin1);
 196           run1 = next1 && (P(compare)(kprev1, kin1) LESS 0);
 197           kout = kprev1;
 198         }
 199 #ifdef SORT_UNIFY
 200       else if (comp == 0)
 201         {
 202           P(merge_data)(in1, in2, out1, kin1, kin2);
 203           SWAP(kin1, kprev1, ktmp);
 204           next1 = P(fetch_key)(in1, kin1);
 205           run1 = next1 && (P(compare)(kprev1, kin1) LESS 0);
 206           SWAP(kin2, kprev2, ktmp);
 207           next2 = P(fetch_key)(in2, kin2);
 208           run2 = next2 && (P(compare)(kprev2, kin2) LESS 0);
 209           kout = kprev2;
 210         }
 211 #endif
 212 #ifdef SORT_ASSERT_UNIQUE
 213       else if (unlikely(comp == 0))
 214         ASSERT(0);
 215 #endif
 216       else
 217         {
 218           P(copy_data)(in2, out1, kin2);
 219           SWAP(kin2, kprev2, ktmp);
 220           next2 = P(fetch_key)(in2, kin2);
 221           run2 = next2 && (P(compare)(kprev2, kin2) LESS 0);
 222           kout = kprev2;
 223         }
 224       if (!run1 && !run2)
 225         {
 226           run1 = next1;
 227           run2 = next2;
 228         }
 229     }
 230   bclose(in1);
 231   bclose(in2);
 232   if (sorter_trace)
 233     log(L_INFO, "Pass %d: %d runs, %d+%d KB", sorter_pass_counter, run_count,
 234         (out1 ? (int)((btell(out1) + 1023) / 1024) : 0),
 235         (out2 ? (int)((btell(out2) + 1023) / 1024) : 0));
 236   *fb1 = P(flush_out)(out1);
 237   *fb2 = P(flush_out)(out2);
 238   sorter_pass_counter++;
 239   return run_count;
 240 }
 241
 242 #ifdef SORT_PRESORT
 243
 244 #if defined(SORT_REGULAR) && !defined(SORT_UNIFY)
 245
 246 /* If we are doing a simple sort on a regular file, we can use a faster presorting strategy */
 247
 248 static SORT_KEY *P(array);
 249
 250 #define ASORT_PREFIX(x) SORT_PREFIX(x##_array)
 251 #define ASORT_KEY_TYPE SORT_KEY
 252 #define ASORT_ELT(i) P(array)[i]
 253 #define ASORT_LT(x,y) (P(compare)(&(x),&(y)) < 0)
 254
 255 #include "lib/arraysort.h"
 256
 257 static void
 258 P(presort)(struct fastbuf **fb1, struct fastbuf **fb2)
 259 {
 260   struct fastbuf *in = *fb1;
 261   struct fastbuf *out1 = NULL;
 262   struct fastbuf *out2 = NULL;
 263   struct fastbuf *tbuf;
 264   uns buf_items = sorter_presort_bufsize / sizeof(SORT_KEY);
 265   uns run_count = 0;
 266   SORT_KEY last_out = { }, *array;
 267
 268   ASSERT(!*fb2);
 269   if (buf_items < 2)
 270     die("PresortBuffer set too low");
 271   P(array) = array = xmalloc(buf_items * sizeof(SORT_KEY));
 272
 273   for(;;)
 274     {
 275       uns s = bread(in, array, buf_items * sizeof(SORT_KEY));
 276       uns n = s / sizeof(SORT_KEY);
 277       ASSERT(!(s % sizeof(SORT_KEY)));
 278       if (!n)
 279         break;
 280       P(sort_array)(n);
 281 #ifdef SORT_ASSERT_UNIQUE
 282       for (uns i=0; i<n-1; i++)
 283         if (unlikely(P(compare)(&array[i], &array[i+1]) >= 0))
 284           ASSERT(0);
 285       ASSERT(!run_count || P(compare)(&last_out, &array[0]));
 286 #endif
 287       if (!run_count || P(compare)(&last_out, &array[0]) > 0)
 288         {
 289           run_count++;
 290 #ifdef SORT_UP_TO
 291           if (sorter_presort_bufsize < (uns) SORT_UP_TO)
 292 #endif
 293             SWAP(out1, out2, tbuf);
 294           if (!out1)
 295             out1 = bopen_tmp(sorter_stream_bufsize);
 296         }
 297       last_out = array[n-1];
 298       bwrite(out1, array, n * sizeof(SORT_KEY));
 299     }
 300
 301   bclose(in);
 302   if (sorter_trace)
 303     log(L_INFO, "Pass 0: %d runs, %d+%d KB",
 304         run_count,
 305         (out1 ? (int)((btell(out1) + 1023) / 1024) : 0),
 306         (out2 ? (int)((btell(out2) + 1023) / 1024) : 0));
 307   *fb1 = P(flush_out)(out1);
 308   *fb2 = P(flush_out)(out2);
 309   xfree(array);
 310 }
 311
 312 #else
 313
 314 #define SORT_NODE struct P(presort_node)
 315
 316 SORT_NODE {
 317   SORT_NODE *next;
 318   SORT_KEY key;
 319 };
 320
 321 static SORT_NODE *
 322 P(mergesort)(SORT_NODE *x)
 323 {
 324   SORT_NODE *f1, **l1, *f2, **l2, **l;
 325
 326   l1 = &f1;
 327   l2 = &f2;
 328   while (x)
 329     {
 330       *l1 = x;
 331       l1 = &x->next;
 332       x = x->next;
 333       if (!x)
 334         break;
 335       *l2 = x;
 336       l2 = &x->next;
 337       x = x->next;
 338     }
 339   *l1 = *l2 = NULL;
 340
 341   if (f1 && f1->next)
 342     f1 = P(mergesort)(f1);
 343   if (f2 && f2->next)
 344     f2 = P(mergesort)(f2);
 345   l = &x;
 346   while (f1 && f2)
 347     {
 348       if (P(compare)(&f1->key, &f2->key) <= 0)
 349         {
 350           *l = f1;
 351           l = &f1->next;
 352           f1 = f1->next;
 353         }
 354       else
 355         {
 356           *l = f2;
 357           l = &f2->next;
 358           f2 = f2->next;
 359         }
 360     }
 361   *l = f1 ? : f2;
 362   return x;
 363 }
 364
 365 static void
 366 P(presort)(struct fastbuf **fb1, struct fastbuf **fb2)
 367 {
 368   struct fastbuf *in = *fb1;
 369   struct fastbuf *out1 = NULL;
 370   struct fastbuf *out2 = NULL;
 371   struct fastbuf *tbuf;
 372   byte *buffer, *bufend, *current;
 373   SORT_NODE *first, **last, *this, *leftover;
 374   int cont = 1;
 375   uns run_count = 0;
 376   uns giant_count = 0;
 377   uns split_count = 0;
 378
 379   ASSERT(!*fb2);
 380   if (sorter_presort_bufsize < 2*sizeof(SORT_NODE))
 381     die("PresortBuffer set too low");
 382   buffer = xmalloc(sorter_presort_bufsize);
 383   bufend = buffer + sorter_presort_bufsize;
 384   leftover = NULL;
 385   while (cont)
 386     {
 387 #ifdef SORT_UP_TO
 388       if (sorter_presort_bufsize < SORT_UP_TO)
 389 #endif
 390         SWAP(out1, out2, tbuf);
 391       if (!out1)
 392         out1 = bopen_tmp(sorter_stream_bufsize);
 393       current = buffer;
 394       last = &first;
 395       if (leftover)
 396         {
 397           memmove(buffer, leftover, sizeof(SORT_NODE));
 398           this = leftover = (SORT_NODE *) buffer;
 399           split_count++;
 400           goto get_data;
 401         }
 402       for(;;)
 403         {
 404           current = (byte *) ALIGN_TO((uintptr_t) current, CPU_STRUCT_ALIGN);
 405           if (current + sizeof(*this) > bufend)
 406             break;
 407           this = (SORT_NODE *) current;
 408           cont = P(fetch_key)(in, &this->key);
 409           if (!cont)
 410             break;
 411         get_data:
 412           current = P(fetch_item)(in, &this->key, bufend);
 413           if (!current)
 414             {
 415               if (leftover)             /* Single node too large */
 416                 {
 417                   P(copy_data)(in, out1, &leftover->key);
 418                   leftover = NULL;
 419                   run_count++;
 420                   giant_count++;
 421                 }
 422               else                      /* Node will be left over to the next phase */
 423                 leftover = this;
 424               break;
 425             }
 426           *last = this;
 427           last = &this->next;
 428           leftover = NULL;
 429         }
 430       *last = NULL;
 431       if (!first)
 432         continue;
 433
 434       first = P(mergesort)(first);
 435       run_count++;
 436       while (first)
 437         {
 438 #ifdef SORT_UNIFY
 439           SORT_NODE *second = first->next;
 440           if (second && !P(compare)(&first->key, &second->key))
 441             {
 442               SORT_KEY *n = P(merge_items)(&first->key, &second->key);
 443               if (n == &first->key)
 444                 first->next = second->next;
 445               else if (n)
 446                 first = first->next;
 447               else
 448                 first = second->next;
 449               continue;
 450             }
 451 #endif
 452 #ifdef SORT_ASSERT_UNIQUE
 453           ASSERT(!first->next || P(compare)(&first->key, &first->next->key));
 454 #endif
 455           P(store_item)(out1, &first->key);
 456           first = first->next;
 457         }
 458     }
 459
 460   bclose(in);
 461   if (sorter_trace)
 462     log(L_INFO, "Pass 0: %d runs (%d giants, %d splits), %d+%d KB",
 463         run_count, giant_count, split_count,
 464         (out1 ? (int)((btell(out1) + 1023) / 1024) : 0),
 465         (out2 ? (int)((btell(out2) + 1023) / 1024) : 0));
 466   *fb1 = P(flush_out)(out1);
 467   *fb2 = P(flush_out)(out2);
 468   xfree(buffer);
 469 }
 470
 471 #endif          /* SORT_REGULAR && !SORT_UNIFY */
 472
 473 #endif          /* SORT_PRESORT */
 474
 475 static
 476 #ifdef SORT_OUTPUT_FB
 477 struct fastbuf *
 478 #elif defined(SORT_OUTPUT_FILE)
 479 void
 480 #else
 481 #error No output defined.
 482 #endif
 483 P(sort)(
 484 #ifdef SORT_INPUT_FILE
 485 byte *inname
 486 #elif defined(SORT_INPUT_FB)
 487 struct fastbuf *fb1
 488 #elif defined(SORT_INPUT_FBPAIR)
 489 struct fastbuf *fb1, struct fastbuf *fb2
 490 #else
 491 #error No input defined.
 492 #endif
 493 #ifdef SORT_OUTPUT_FILE
 494 ,byte *outname
 495 #endif
 496 )
 497 {
 498 #ifdef SORT_INPUT_FILE
 499   struct fastbuf *fb1, *fb2;
 500   fb1 = bopen(inname, O_RDONLY, sorter_stream_bufsize);
 501   fb2 = NULL;
 502 #elif defined(SORT_INPUT_FB)
 503   struct fastbuf *fb2 = NULL;
 504 #endif
 505
 506 #ifdef SORT_DELETE_INPUT
 507   bconfig(fb1, BCONFIG_IS_TEMP_FILE, SORT_DELETE_INPUT);
 508 #endif
 509   sorter_pass_counter = 1;
 510 #ifdef SORT_PRESORT
 511   P(presort)(&fb1, &fb2);
 512   if (fb2)
 513 #endif
 514 #ifndef SORT_UP_TO
 515     do P(pass)(&fb1, &fb2); while (fb1 && fb2);
 516 #else
 517     {
 518       sh_off_t run_count, max_run_count = 0;
 519       if (fb1)
 520         max_run_count += bfilesize(fb1);
 521       if (fb2)
 522         max_run_count += bfilesize(fb2);
 523 #ifdef SORT_PRESORT
 524       run_count = max_run_count / sorter_presort_bufsize;
 525 #else
 526       run_count = max_run_count;
 527 #endif
 528       if (SORT_UP_TO)
 529         max_run_count /= SORT_UP_TO;
 530       do
 531         run_count = P(pass)(&fb1, &fb2, (run_count+1)/2 <= max_run_count);
 532       while (fb1 && fb2);
 533     }
 534 #endif
 535   if (!fb1)
 536     fb1 = bopen_tmp(sorter_stream_bufsize);
 537
 538 #ifdef SORT_OUTPUT_FB
 539   return fb1;
 540 #else
 541   bconfig(fb1, BCONFIG_IS_TEMP_FILE, 0);
 542   if (rename(fb1->name, outname) < 0)
 543     die("rename(%s,%s): %m", fb1->name, outname);
 544   bclose(fb1);
 545 #endif
 546 }
 547
 548 #undef P
 549 #undef LESS
 550 #undef SWAP
 551 #undef SORT_NODE
 552 #undef SORT_KEY
 553 #undef SORT_PREFIX
 554 #undef SORT_UNIFY
 555 #undef SORT_UNIQUE
 556 #undef SORT_ASSERT_UNIQUE
 557 #undef SORT_REGULAR
 558 #undef SORT_DELETE_INPUT
 559 #undef SORT_INPUT_FILE
 560 #undef SORT_INPUT_FB
 561 #undef SORT_INPUT_FBPAIR
 562 #undef SORT_OUTPUT_FILE
 563 #undef SORT_OUTPUT_FB
 564 #undef SORT_PRESORT
 565 #undef SORT_UP_TO