lib/sorter.h

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