lib/sorter.h

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