lib/sorter.h

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