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 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_ASSERTS)
 124 #define SORT_ASSERT_UNIQUE
 125 #endif
 126
 127 #ifdef SORT_REGULAR
 128
 129 static inline int
 130 P(fetch_key)(struct fastbuf *in, SORT_KEY *x)
 131 {
 132   return breadb(in, x, sizeof(*x));
 133 }
 134
 135 static inline void
 136 P(copy_data)(struct fastbuf *in UNUSED, struct fastbuf *out, SORT_KEY *x)
 137 {
 138   bwrite(out, x, sizeof(*x));
 139 }
 140
 141 static inline byte *
 142 P(fetch_item)(struct fastbuf *in UNUSED, SORT_KEY *x UNUSED, byte *limit UNUSED)
 143 {
 144   return (byte *)(x+1);
 145 }
 146
 147 static inline void
 148 P(store_item)(struct fastbuf *out, SORT_KEY *x)
 149 {
 150   bwrite(out, x, sizeof(*x));
 151 }
 152
 153 #endif
 154
 155 static struct fastbuf *
 156 P(flush_out)(struct fastbuf *out)
 157 {
 158   if (out)
 159     brewind(out);
 160   return out;
 161 }
 162
 163 static uns
 164 P(pass)(struct fastbuf **fb1, struct fastbuf **fb2
 165 #ifdef SORT_UP_TO
 166     , uns stop_sorting
 167 #endif
 168 )
 169 {
 170   struct fastbuf *in1 = *fb1;
 171   struct fastbuf *in2 = *fb2;
 172   struct fastbuf *out1 = NULL;
 173   struct fastbuf *out2 = NULL;
 174   SORT_KEY kbuf1, kbuf2, kbuf3, kbuf4;
 175   SORT_KEY *kin1 = &kbuf1;
 176   SORT_KEY *kprev1 = &kbuf2;
 177   SORT_KEY *kin2 = &kbuf3;
 178   SORT_KEY *kprev2 = &kbuf4;
 179   SORT_KEY *kout = NULL;
 180   SORT_KEY *ktmp;
 181   int next1, next2, comp;
 182   int run1, run2;
 183   uns run_count = 0;
 184
 185   run1 = next1 = in1 ? P(fetch_key)(in1, kin1) : 0;
 186   run2 = next2 = in2 ? P(fetch_key)(in2, kin2) : 0;
 187   while (next1 || next2)
 188     {
 189       if (!run1)
 190         comp = 1;
 191       else if (!run2)
 192         comp = -1;
 193       else
 194         comp = P(compare)(kin1, kin2);
 195       ktmp = (comp <= 0) ? kin1 : kin2;
 196       if (!kout || !(P(compare)(kout, ktmp) LESS 0))
 197         {
 198           struct fastbuf *t;
 199 #ifdef SORT_UP_TO
 200           if (!stop_sorting)
 201 #endif
 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   return run_count;
 256 }
 257
 258 #ifdef SORT_PRESORT
 259
 260 #if defined(SORT_REGULAR) && !defined(SORT_UNIFY)
 261
 262 /* If we are doing a simple sort on a regular file, we can use a faster presorting strategy */
 263
 264 static SORT_KEY *P(array);
 265
 266 #define ASORT_PREFIX(x) SORT_PREFIX(x##_array)
 267 #define ASORT_KEY_TYPE SORT_KEY
 268 #define ASORT_ELT(i) P(array)[i]
 269 #define ASORT_LT(x,y) (P(compare)(&(x),&(y)) < 0)
 270
 271 #include "lib/arraysort.h"
 272
 273 static void
 274 P(presort)(struct fastbuf **fb1, struct fastbuf **fb2)
 275 {
 276   struct fastbuf *in = *fb1;
 277   struct fastbuf *out1 = NULL;
 278   struct fastbuf *out2 = NULL;
 279   struct fastbuf *tbuf;
 280   uns buf_items = sorter_presort_bufsize / sizeof(SORT_KEY);
 281   uns run_count = 0;
 282   SORT_KEY last_out = { }, *array;
 283
 284   ASSERT(!*fb2);
 285   if (buf_items < 2)
 286     die("PresortBuffer set too low");
 287   P(array) = array = xmalloc(buf_items * sizeof(SORT_KEY));
 288
 289   for(;;)
 290     {
 291       uns s = bread(in, array, buf_items * sizeof(SORT_KEY));
 292       uns n = s / sizeof(SORT_KEY);
 293       ASSERT(!(s % sizeof(SORT_KEY)));
 294       if (!n)
 295         break;
 296       P(sort_array)(n);
 297 #ifdef SORT_ASSERT_UNIQUE
 298       for (uns i=0; i<n-1; i++)
 299         if (unlikely(P(compare)(&array[i], &array[i+1]) >= 0))
 300           ASSERT(0);
 301       ASSERT(!run_count || P(compare)(&last_out, &array[0]));
 302 #endif
 303       if (!run_count || P(compare)(&last_out, &array[0]) > 0)
 304         {
 305           run_count++;
 306 #ifdef SORT_UP_TO
 307           if (sorter_presort_bufsize < (uns) SORT_UP_TO)
 308 #endif
 309             SWAP(out1, out2, tbuf);
 310           if (!out1)
 311             out1 = bopen_tmp(sorter_stream_bufsize);
 312         }
 313       last_out = array[n-1];
 314       bwrite(out1, array, n * sizeof(SORT_KEY));
 315     }
 316
 317   bclose(in);
 318   if (sorter_trace)
 319     log(L_INFO, "Pass 0: %d runs, %d+%d KB",
 320         run_count,
 321         (out1 ? (int)((btell(out1) + 1023) / 1024) : 0),
 322         (out2 ? (int)((btell(out2) + 1023) / 1024) : 0));
 323   *fb1 = P(flush_out)(out1);
 324   *fb2 = P(flush_out)(out2);
 325   xfree(array);
 326 }
 327
 328 #else
 329
 330 #define SORT_NODE struct P(presort_node)
 331
 332 SORT_NODE {
 333   SORT_NODE *next;
 334   SORT_KEY key;
 335 };
 336
 337 static SORT_NODE *
 338 P(mergesort)(SORT_NODE *x)
 339 {
 340   SORT_NODE *f1, **l1, *f2, **l2, **l;
 341
 342   l1 = &f1;
 343   l2 = &f2;
 344   while (x)
 345     {
 346       *l1 = x;
 347       l1 = &x->next;
 348       x = x->next;
 349       if (!x)
 350         break;
 351       *l2 = x;
 352       l2 = &x->next;
 353       x = x->next;
 354     }
 355   *l1 = *l2 = NULL;
 356
 357   if (f1 && f1->next)
 358     f1 = P(mergesort)(f1);
 359   if (f2 && f2->next)
 360     f2 = P(mergesort)(f2);
 361   l = &x;
 362   while (f1 && f2)
 363     {
 364       if (P(compare)(&f1->key, &f2->key) <= 0)
 365         {
 366           *l = f1;
 367           l = &f1->next;
 368           f1 = f1->next;
 369         }
 370       else
 371         {
 372           *l = f2;
 373           l = &f2->next;
 374           f2 = f2->next;
 375         }
 376     }
 377   *l = f1 ? : f2;
 378   return x;
 379 }
 380
 381 static void
 382 P(presort)(struct fastbuf **fb1, struct fastbuf **fb2)
 383 {
 384   struct fastbuf *in = *fb1;
 385   struct fastbuf *out1 = NULL;
 386   struct fastbuf *out2 = NULL;
 387   struct fastbuf *tbuf;
 388   byte *buffer, *bufend, *current;
 389   SORT_NODE *first, **last, *this, *leftover;
 390   int cont = 1;
 391   uns run_count = 0;
 392   uns giant_count = 0;
 393   uns split_count = 0;
 394
 395   ASSERT(!*fb2);
 396   if (sorter_presort_bufsize < 2*sizeof(SORT_NODE))
 397     die("PresortBuffer set too low");
 398   buffer = xmalloc(sorter_presort_bufsize);
 399   bufend = buffer + sorter_presort_bufsize;
 400   leftover = NULL;
 401   while (cont)
 402     {
 403 #ifdef SORT_UP_TO
 404       if (sorter_presort_bufsize < SORT_UP_TO)
 405 #endif
 406         SWAP(out1, out2, tbuf);
 407       if (!out1)
 408         out1 = bopen_tmp(sorter_stream_bufsize);
 409       current = buffer;
 410       last = &first;
 411       if (leftover)
 412         {
 413           memmove(buffer, leftover, sizeof(SORT_NODE));
 414           this = leftover = (SORT_NODE *) buffer;
 415           split_count++;
 416           goto get_data;
 417         }
 418       for(;;)
 419         {
 420           current = (byte *) ALIGN((addr_int_t) current, CPU_STRUCT_ALIGN);
 421           if (current + sizeof(*this) > bufend)
 422             break;
 423           this = (SORT_NODE *) current;
 424           cont = P(fetch_key)(in, &this->key);
 425           if (!cont)
 426             break;
 427         get_data:
 428           current = P(fetch_item)(in, &this->key, bufend);
 429           if (!current)
 430             {
 431               if (leftover)             /* Single node too large */
 432                 {
 433                   P(copy_data)(in, out1, &leftover->key);
 434                   leftover = NULL;
 435                   run_count++;
 436                   giant_count++;
 437                 }
 438               else                      /* Node will be left over to the next phase */
 439                 leftover = this;
 440               break;
 441             }
 442           *last = this;
 443           last = &this->next;
 444           leftover = NULL;
 445         }
 446       *last = NULL;
 447       if (!first)
 448         continue;
 449
 450       first = P(mergesort)(first);
 451       run_count++;
 452       while (first)
 453         {
 454 #ifdef SORT_UNIFY
 455           SORT_NODE *second = first->next;
 456           if (second && !P(compare)(&first->key, &second->key))
 457             {
 458               SORT_KEY *n = P(merge_items)(&first->key, &second->key);
 459               if (n == &first->key)
 460                 first->next = second->next;
 461               else if (n)
 462                 first = first->next;
 463               else
 464                 first = second->next;
 465               continue;
 466             }
 467 #endif
 468 #ifdef SORT_ASSERT_UNIQUE
 469           ASSERT(!first->next || P(compare)(&first->key, &first->next->key));
 470 #endif
 471           P(store_item)(out1, &first->key);
 472           first = first->next;
 473         }
 474     }
 475
 476   bclose(in);
 477   if (sorter_trace)
 478     log(L_INFO, "Pass 0: %d runs (%d giants, %d splits), %d+%d KB",
 479         run_count, giant_count, split_count,
 480         (out1 ? (int)((btell(out1) + 1023) / 1024) : 0),
 481         (out2 ? (int)((btell(out2) + 1023) / 1024) : 0));
 482   *fb1 = P(flush_out)(out1);
 483   *fb2 = P(flush_out)(out2);
 484   xfree(buffer);
 485 }
 486
 487 #endif          /* SORT_REGULAR && !SORT_UNIFY */
 488
 489 #endif          /* SORT_PRESORT */
 490
 491 static
 492 #ifdef SORT_OUTPUT_FB
 493 struct fastbuf *
 494 #elif defined(SORT_OUTPUT_FILE)
 495 void
 496 #else
 497 #error No output defined.
 498 #endif
 499 P(sort)(
 500 #ifdef SORT_INPUT_FILE
 501 byte *inname
 502 #elif defined(SORT_INPUT_FB)
 503 struct fastbuf *fb1
 504 #elif defined(SORT_INPUT_FBPAIR)
 505 struct fastbuf *fb1, struct fastbuf *fb2
 506 #else
 507 #error No input defined.
 508 #endif
 509 #ifdef SORT_OUTPUT_FILE
 510 ,byte *outname
 511 #endif
 512 )
 513 {
 514 #ifdef SORT_INPUT_FILE
 515   struct fastbuf *fb1, *fb2;
 516   fb1 = bopen(inname, O_RDONLY, sorter_stream_bufsize);
 517   fb2 = NULL;
 518 #elif defined(SORT_INPUT_FB)
 519   struct fastbuf *fb2 = NULL;
 520 #endif
 521
 522 #ifdef SORT_DELETE_INPUT
 523   bconfig(fb1, BCONFIG_IS_TEMP_FILE, SORT_DELETE_INPUT);
 524 #endif
 525   sorter_pass_counter = 1;
 526 #ifdef SORT_PRESORT
 527   P(presort)(&fb1, &fb2);
 528   if (fb2)
 529 #endif
 530 #ifndef SORT_UP_TO
 531     do P(pass)(&fb1, &fb2); while (fb1 && fb2);
 532 #else
 533     {
 534       sh_off_t run_count, max_run_count = 0;
 535       if (fb1)
 536         max_run_count += bfilesize(fb1);
 537       if (fb2)
 538         max_run_count += bfilesize(fb2);
 539 #ifdef SORT_PRESORT
 540       run_count = max_run_count / sorter_presort_bufsize;
 541 #else
 542       run_count = max_run_count;
 543 #endif
 544       if (SORT_UP_TO)
 545         max_run_count /= SORT_UP_TO;
 546       do
 547         run_count = P(pass)(&fb1, &fb2, (run_count+1)/2 <= max_run_count);
 548       while (fb1 && fb2);
 549     }
 550 #endif
 551   if (!fb1)
 552     fb1 = bopen_tmp(sorter_stream_bufsize);
 553
 554 #ifdef SORT_OUTPUT_FB
 555   return fb1;
 556 #else
 557   bconfig(fb1, BCONFIG_IS_TEMP_FILE, 0);
 558   if (rename(fb1->name, outname) < 0)
 559     die("rename(%s,%s): %m", fb1->name, outname);
 560   bclose(fb1);
 561 #endif
 562 }
 563
 564 #undef P
 565 #undef LESS
 566 #undef SWAP
 567 #undef SORT_NODE
 568 #undef SORT_KEY
 569 #undef SORT_PREFIX
 570 #undef SORT_UNIFY
 571 #undef SORT_UNIQUE
 572 #undef SORT_ASSERT_UNIQUE
 573 #undef SORT_REGULAR
 574 #undef SORT_DELETE_INPUT
 575 #undef SORT_INPUT_FILE
 576 #undef SORT_INPUT_FB
 577 #undef SORT_INPUT_FBPAIR
 578 #undef SORT_OUTPUT_FILE
 579 #undef SORT_OUTPUT_FB
 580 #undef SORT_PRESORT
 581 #undef SORT_UP_TO
 582
 583 #endif          /* !SORT_DECLARE_ONLY */