lib/sorter.h

   1 /*
   2  *      Sherlock Library -- Universal Sorter
   3  *
   4  *      (c) 2001--2004 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 /*
  11  *  This is not a normal header file, it's a generator of sorting
  12  *  routines.  Each time you include it with parameters set in the
  13  *  corresponding preprocessor macros, it generates a file sorter
  14  *  with the parameters given.
  15  *
  16  *  Recognized parameter macros: (those marked with [*] are mandatory)
  17  *
  18  *  SORT_KEY        [*] data type capable of storing a single key
  19  *  SORT_PREFIX(x)  [*] add a name prefix (used on all global names
  20  *                      defined by the sorter)
  21  *  SORT_PRESORT        include an in-core pre-sorting pass. Beware, when in
  22  *                      the pre-sorting mode, it's quite possible that the
  23  *                      comparison function will be called with both arguments
  24  *                      identical.
  25  *  SORT_PRESORT_ONLY   a C expression which, if evaluated to non-zero, makes
  26  *                      the sorter stop after the pre-sorting pass, resulting
  27  *                      in a file which is not necessarily sorted, but which
  28  *                      contains long runs. Implies SORT_PRESORT.
  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 1=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 /* Declarations of externals from sorter.c */
  89
  90 #ifndef SORT_DECLS_READ
  91 #define SORT_DECLS_READ
  92
  93 extern uns sorter_trace;
  94 extern uns sorter_presort_bufsize;
  95 extern uns sorter_stream_bufsize;
  96
  97 extern uns sorter_pass_counter;
  98
  99 #endif          /* !SORT_DECLS_READ */
 100
 101 /* The sorter proper */
 102
 103 #ifndef SORT_DECLARE_ONLY
 104
 105 #include "lib/fastbuf.h"
 106 #include <unistd.h>
 107 #include <fcntl.h>
 108 #include <string.h>
 109
 110 #if !defined(SORT_KEY) || !defined(SORT_PREFIX)
 111 #error Some of the mandatory configuration macros are missing.
 112 #endif
 113
 114 #define P(x) SORT_PREFIX(x)
 115 #define SWAP(x,y,z) do { z=x; x=y; y=z; } while(0)
 116
 117 #if defined(SORT_UNIFY) || defined(SORT_UNIQUE)
 118 #define LESS <
 119 #else
 120 #define LESS <=
 121 #endif
 122
 123 #if defined(SORT_UNIQUE) && defined(DEBUG)
 124 #define SORT_ASSERT_UNIQUE
 125 #endif
 126
 127 #ifdef SORT_PRESORT_ONLY
 128 #undef SORT_PRESORT
 129 #define SORT_PRESORT
 130 #else
 131 #define SORT_PRESORT_ONLY 0
 132 #endif
 133
 134 #ifdef SORT_REGULAR
 135
 136 static inline int
 137 P(fetch_key)(struct fastbuf *in, SORT_KEY *x)
 138 {
 139   return breadb(in, x, sizeof(*x));
 140 }
 141
 142 static inline void
 143 P(copy_data)(struct fastbuf *in UNUSED, struct fastbuf *out, SORT_KEY *x)
 144 {
 145   bwrite(out, x, sizeof(*x));
 146 }
 147
 148 static inline byte *
 149 P(fetch_item)(struct fastbuf *in UNUSED, SORT_KEY *x UNUSED, byte *limit UNUSED)
 150 {
 151   return (byte *)(x+1);
 152 }
 153
 154 static inline void
 155 P(store_item)(struct fastbuf *out, SORT_KEY *x)
 156 {
 157   bwrite(out, x, sizeof(*x));
 158 }
 159
 160 #endif
 161
 162 static struct fastbuf *
 163 P(flush_out)(struct fastbuf *out)
 164 {
 165   if (out)
 166     brewind(out);
 167   return out;
 168 }
 169
 170 static void
 171 P(pass)(struct fastbuf **fb1, struct fastbuf **fb2)
 172 {
 173   struct fastbuf *in1 = *fb1;
 174   struct fastbuf *in2 = *fb2;
 175   struct fastbuf *out1 = NULL;
 176   struct fastbuf *out2 = NULL;
 177   SORT_KEY kbuf1, kbuf2, kbuf3, kbuf4;
 178   SORT_KEY *kin1 = &kbuf1;
 179   SORT_KEY *kprev1 = &kbuf2;
 180   SORT_KEY *kin2 = &kbuf3;
 181   SORT_KEY *kprev2 = &kbuf4;
 182   SORT_KEY *kout = NULL;
 183   SORT_KEY *ktmp;
 184   int next1, next2, comp;
 185   int run1, run2;
 186   uns run_count = 0;
 187
 188   run1 = next1 = in1 ? P(fetch_key)(in1, kin1) : 0;
 189   run2 = next2 = in2 ? P(fetch_key)(in2, kin2) : 0;
 190   while (next1 || next2)
 191     {
 192       if (!run1)
 193         comp = 1;
 194       else if (!run2)
 195         comp = -1;
 196       else
 197         comp = P(compare)(kin1, kin2);
 198       ktmp = (comp <= 0) ? kin1 : kin2;
 199       if (!kout || !(P(compare)(kout, ktmp) LESS 0))
 200         {
 201           struct fastbuf *t;
 202           SWAP(out1, out2, t);
 203           if (!out1)
 204             out1 = bopen_tmp(sorter_stream_bufsize);
 205           run_count++;
 206         }
 207       if (comp LESS 0)
 208         {
 209           P(copy_data)(in1, out1, kin1);
 210           SWAP(kin1, kprev1, ktmp);
 211           next1 = P(fetch_key)(in1, kin1);
 212           run1 = next1 && (P(compare)(kprev1, kin1) LESS 0);
 213           kout = kprev1;
 214         }
 215 #ifdef SORT_UNIFY
 216       else if (comp == 0)
 217         {
 218           P(merge_data)(in1, in2, out1, kin1, kin2);
 219           SWAP(kin1, kprev1, ktmp);
 220           next1 = P(fetch_key)(in1, kin1);
 221           run1 = next1 && (P(compare)(kprev1, kin1) LESS 0);
 222           SWAP(kin2, kprev2, ktmp);
 223           next2 = P(fetch_key)(in2, kin2);
 224           run2 = next2 && (P(compare)(kprev2, kin2) LESS 0);
 225           kout = kprev2;
 226         }
 227 #endif
 228 #ifdef SORT_ASSERT_UNIQUE
 229       else if (unlikely(comp == 0))
 230         ASSERT(0);
 231 #endif
 232       else
 233         {
 234           P(copy_data)(in2, out1, kin2);
 235           SWAP(kin2, kprev2, ktmp);
 236           next2 = P(fetch_key)(in2, kin2);
 237           run2 = next2 && (P(compare)(kprev2, kin2) LESS 0);
 238           kout = kprev2;
 239         }
 240       if (!run1 && !run2)
 241         {
 242           run1 = next1;
 243           run2 = next2;
 244         }
 245     }
 246   bclose(in1);
 247   bclose(in2);
 248   if (sorter_trace)
 249     log(L_INFO, "Pass %d: %d runs, %d+%d KB", sorter_pass_counter, run_count,
 250         (out1 ? (int)((btell(out1) + 1023) / 1024) : 0),
 251         (out2 ? (int)((btell(out2) + 1023) / 1024) : 0));
 252   *fb1 = P(flush_out)(out1);
 253   *fb2 = P(flush_out)(out2);
 254   sorter_pass_counter++;
 255 }
 256
 257 #ifdef SORT_PRESORT
 258
 259 #if defined(SORT_REGULAR) && !defined(SORT_UNIFY)
 260
 261 /* If we are doing a simple sort on a regular file, we can use a faster presorting strategy */
 262
 263 static SORT_KEY *P(array);
 264
 265 #define ASORT_PREFIX(x) SORT_PREFIX(x##_array)
 266 #define ASORT_KEY_TYPE SORT_KEY
 267 #define ASORT_ELT(i) P(array)[i]
 268 #define ASORT_LT(x,y) (P(compare)(&(x),&(y)) < 0)
 269
 270 #include "lib/arraysort.h"
 271
 272 static void
 273 P(presort)(struct fastbuf **fb1, struct fastbuf **fb2)
 274 {
 275   struct fastbuf *in = *fb1;
 276   struct fastbuf *out1 = NULL;
 277   struct fastbuf *out2 = NULL;
 278   struct fastbuf *tbuf;
 279   uns buf_items = sorter_presort_bufsize / sizeof(SORT_KEY);
 280   uns run_count = 0;
 281   SORT_KEY last_out, *array;
 282
 283   ASSERT(!*fb2);
 284   if (buf_items < 2)
 285     die("PresortBuffer set too low");
 286   P(array) = array = xmalloc(buf_items * sizeof(SORT_KEY));
 287
 288   for(;;)
 289     {
 290       uns s = bread(in, array, buf_items * sizeof(SORT_KEY));
 291       uns n = s / sizeof(SORT_KEY);
 292       ASSERT(!(s % sizeof(SORT_KEY)));
 293       if (!n)
 294         break;
 295       P(sort_array)(n);
 296 #ifdef SORT_ASSERT_UNIQUE
 297       for (uns i=0; i<n-1; i++)
 298         if (unlikely(P(compare)(&array[i], &array[i+1]) >= 0))
 299           ASSERT(0);
 300       ASSERT(!run_count || P(compare)(&last_out, &array[0]));
 301 #endif
 302       if (!run_count || P(compare)(&last_out, &array[0]) > 0)
 303         {
 304           run_count++;
 305           SWAP(out1, out2, tbuf);
 306           if (!out1)
 307             out1 = bopen_tmp(sorter_stream_bufsize);
 308         }
 309       last_out = array[n-1];
 310       bwrite(out1, array, n * sizeof(SORT_KEY));
 311     }
 312
 313   bclose(in);
 314   if (sorter_trace)
 315     log(L_INFO, "Pass 0: %d runs, %d+%d KB",
 316         run_count,
 317         (out1 ? (int)((btell(out1) + 1023) / 1024) : 0),
 318         (out2 ? (int)((btell(out2) + 1023) / 1024) : 0));
 319   *fb1 = P(flush_out)(out1);
 320   *fb2 = P(flush_out)(out2);
 321   xfree(array);
 322 }
 323
 324 #else
 325
 326 #define SORT_NODE struct P(presort_node)
 327
 328 SORT_NODE {
 329   SORT_NODE *next;
 330   SORT_KEY key;
 331 };
 332
 333 static SORT_NODE *
 334 P(mergesort)(SORT_NODE *x)
 335 {
 336   SORT_NODE *f1, **l1, *f2, **l2, **l;
 337
 338   l1 = &f1;
 339   l2 = &f2;
 340   while (x)
 341     {
 342       *l1 = x;
 343       l1 = &x->next;
 344       x = x->next;
 345       if (!x)
 346         break;
 347       *l2 = x;
 348       l2 = &x->next;
 349       x = x->next;
 350     }
 351   *l1 = *l2 = NULL;
 352
 353   if (f1 && f1->next)
 354     f1 = P(mergesort)(f1);
 355   if (f2 && f2->next)
 356     f2 = P(mergesort)(f2);
 357   l = &x;
 358   while (f1 && f2)
 359     {
 360       if (P(compare)(&f1->key, &f2->key) <= 0)
 361         {
 362           *l = f1;
 363           l = &f1->next;
 364           f1 = f1->next;
 365         }
 366       else
 367         {
 368           *l = f2;
 369           l = &f2->next;
 370           f2 = f2->next;
 371         }
 372     }
 373   *l = f1 ? : f2;
 374   return x;
 375 }
 376
 377 static void
 378 P(presort)(struct fastbuf **fb1, struct fastbuf **fb2)
 379 {
 380   struct fastbuf *in = *fb1;
 381   struct fastbuf *out1 = NULL;
 382   struct fastbuf *out2 = NULL;
 383   struct fastbuf *tbuf;
 384   byte *buffer, *bufend, *current;
 385   SORT_NODE *first, **last, *this, *leftover;
 386   int cont = 1;
 387   uns run_count = 0;
 388   uns giant_count = 0;
 389   uns split_count = 0;
 390
 391   ASSERT(!*fb2);
 392   if (sorter_presort_bufsize < 2*sizeof(SORT_NODE))
 393     die("PresortBuffer set too low");
 394   buffer = xmalloc(sorter_presort_bufsize);
 395   bufend = buffer + sorter_presort_bufsize;
 396   leftover = NULL;
 397   while (cont)
 398     {
 399       if (!(SORT_PRESORT_ONLY))
 400         SWAP(out1, out2, tbuf);
 401       if (!out1)
 402         out1 = bopen_tmp(sorter_stream_bufsize);
 403       current = buffer;
 404       last = &first;
 405       if (leftover)
 406         {
 407           memmove(buffer, leftover, sizeof(SORT_NODE));
 408           this = leftover = (SORT_NODE *) buffer;
 409           split_count++;
 410           goto get_data;
 411         }
 412       for(;;)
 413         {
 414           current = (byte *) ALIGN((addr_int_t) current, CPU_STRUCT_ALIGN);
 415           if (current + sizeof(*this) > bufend)
 416             break;
 417           this = (SORT_NODE *) current;
 418           cont = P(fetch_key)(in, &this->key);
 419           if (!cont)
 420             break;
 421         get_data:
 422           current = P(fetch_item)(in, &this->key, bufend);
 423           if (!current)
 424             {
 425               if (leftover)             /* Single node too large */
 426                 {
 427                   P(copy_data)(in, out1, &leftover->key);
 428                   leftover = NULL;
 429                   run_count++;
 430                   giant_count++;
 431                 }
 432               else                      /* Node will be left over to the next phase */
 433                 leftover = this;
 434               break;
 435             }
 436           *last = this;
 437           last = &this->next;
 438           leftover = NULL;
 439         }
 440       *last = NULL;
 441       if (!first)
 442         continue;
 443
 444       first = P(mergesort)(first);
 445       run_count++;
 446       while (first)
 447         {
 448 #ifdef SORT_UNIFY
 449           SORT_NODE *second = first->next;
 450           if (second && !P(compare)(&first->key, &second->key))
 451             {
 452               SORT_KEY *n = P(merge_items)(&first->key, &second->key);
 453               if (n == &first->key)
 454                 first->next = second->next;
 455               else if (n)
 456                 first = first->next;
 457               else
 458                 first = second->next;
 459               continue;
 460             }
 461 #endif
 462 #ifdef SORT_ASSERT_UNIQUE
 463           ASSERT(!first->next || P(compare)(&first->key, &first->next->key));
 464 #endif
 465           P(store_item)(out1, &first->key);
 466           first = first->next;
 467         }
 468     }
 469
 470   bclose(in);
 471   if (sorter_trace)
 472     log(L_INFO, "Pass 0: %d runs (%d giants, %d splits), %d+%d KB",
 473         run_count, giant_count, split_count,
 474         (out1 ? (int)((btell(out1) + 1023) / 1024) : 0),
 475         (out2 ? (int)((btell(out2) + 1023) / 1024) : 0));
 476   *fb1 = P(flush_out)(out1);
 477   *fb2 = P(flush_out)(out2);
 478   xfree(buffer);
 479 }
 480
 481 #endif          /* SORT_REGULAR && !SORT_UNIFY */
 482
 483 #endif          /* SORT_PRESORT */
 484
 485 static
 486 #ifdef SORT_OUTPUT_FB
 487 struct fastbuf *
 488 #elif defined(SORT_OUTPUT_FILE)
 489 void
 490 #else
 491 #error No output defined.
 492 #endif
 493 P(sort)(
 494 #ifdef SORT_INPUT_FILE
 495 byte *inname
 496 #elif defined(SORT_INPUT_FB)
 497 struct fastbuf *fb1
 498 #elif defined(SORT_INPUT_FBPAIR)
 499 struct fastbuf *fb1, struct fastbuf *fb2
 500 #else
 501 #error No input defined.
 502 #endif
 503 #ifdef SORT_OUTPUT_FILE
 504 ,byte *outname
 505 #endif
 506 )
 507 {
 508 #ifdef SORT_INPUT_FILE
 509   struct fastbuf *fb1, *fb2;
 510   fb1 = bopen(inname, O_RDONLY, sorter_stream_bufsize);
 511   fb2 = NULL;
 512 #elif defined(SORT_INPUT_FB)
 513   struct fastbuf *fb2 = NULL;
 514 #endif
 515
 516 #ifdef SORT_DELETE_INPUT
 517   bconfig(fb1, BCONFIG_IS_TEMP_FILE, SORT_DELETE_INPUT);
 518 #endif
 519   sorter_pass_counter = 1;
 520 #ifdef SORT_PRESORT
 521   P(presort)(&fb1, &fb2);
 522   if (fb2)
 523 #endif
 524     do P(pass)(&fb1, &fb2); while (fb1 && fb2);
 525   if (!fb1)
 526     fb1 = bopen_tmp(sorter_stream_bufsize);
 527
 528 #ifdef SORT_OUTPUT_FB
 529   return fb1;
 530 #else
 531   bconfig(fb1, BCONFIG_IS_TEMP_FILE, 0);
 532   if (rename(fb1->name, outname) < 0)
 533     die("rename(%s,%s): %m", fb1->name, outname);
 534   bclose(fb1);
 535 #endif
 536 }
 537
 538 #undef P
 539 #undef LESS
 540 #undef SWAP
 541 #undef SORT_NODE
 542 #undef SORT_KEY
 543 #undef SORT_PREFIX
 544 #undef SORT_UNIFY
 545 #undef SORT_UNIQUE
 546 #undef SORT_ASSERT_UNIQUE
 547 #undef SORT_REGULAR
 548 #undef SORT_DELETE_INPUT
 549 #undef SORT_INPUT_FILE
 550 #undef SORT_INPUT_FB
 551 #undef SORT_INPUT_FBPAIR
 552 #undef SORT_OUTPUT_FILE
 553 #undef SORT_OUTPUT_FB
 554 #undef SORT_PRESORT
 555 #undef SORT_PRESORT_ONLY
 556
 557 #endif          /* !SORT_DECLARE_ONLY */