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