lib/sorter/sorter.h

   1 /*
   2  *      UCW Library -- Universal Sorter
   3  *
   4  *      (c) 2001--2007 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, but 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  *  FIXME: explain the basics (keys and data, callbacks etc.)
  18  *
  19  *  Basic parameters and callbacks:
  20  *
  21  *  SORT_PREFIX(x)      add a name prefix (used on all global names
  22  *                      defined by the sorter)
  23  *
  24  *  SORT_KEY            data type capable of storing a single key.
  25  *  SORT_KEY_REGULAR    data type holding a single key both in memory and on disk;
  26  *                      in this case, bread() and bwrite() is used to read/write keys
  27  *                      and it's also assumed that the keys are not very long.
  28  *  int PREFIX_compare(SORT_KEY *a, SORT_KEY *b)
  29  *                      compares two keys, result like strcmp(). Mandatory.
  30  *  int PREFIX_read_key(struct fastbuf *f, SORT_KEY *k)
  31  *                      reads a key from a fastbuf, returns nonzero=ok, 0=EOF.
  32  *                      Mandatory unless SORT_KEY_REGULAR is defined.
  33  *  void PREFIX_write_key(struct fastbuf *f, SORT_KEY *k)
  34  *                      writes a key to a fastbuf. Mandatory unless SORT_KEY_REGULAR.
  35  *
  36  *  SORT_KEY_SIZE(key)  returns the real size of a key (a SORT_KEY type in memory
  37  *                      can be truncated to this number of bytes without any harm;
  38  *                      used to save memory when the keys have variable sizes).
  39  *                      Default: always store the whole SORT_KEY.
  40  *  SORT_DATA_SIZE(key) gets a key and returns the amount of data following it.
  41  *                      Default: records consist of keys only.
  42  *
  43  *  Integer sorting:
  44  *
  45  *  SORT_INT(key)       We are sorting by an integer value. In this mode, PREFIX_compare
  46  *                      is supplied automatically and the sorting function gets an extra
  47  *                      parameter specifying a range of the integers. The better the range
  48  *                      fits, the faster we sort. Sets up SORT_HASH_xxx automatically.
  49  *
  50  *  Hashing (optional, but it can speed sorting up):
  51  *
  52  *  SORT_HASH_BITS      signals that a monotone hashing function returning a given number of
  53  *                      bits is available. Monotone hash is a function f such that f(x) < f(y)
  54  *                      implies x < y and which is approximately uniformly distributed.
  55  *  uns PREFIX_hash(SORT_KEY *a)
  56  *
  57  *  Unification:
  58  *
  59  *  SORT_UNIFY          merge items with identical keys, needs the following functions:
  60  *  void PREFIX_write_merged(struct fastbuf *f, SORT_KEY **keys, void **data, uns n, void *buf)
  61  *                      takes n records in memory with keys which compare equal and writes
  62  *                      a single record to the given fastbuf. `buf' points to a buffer which
  63  *                      is guaranteed to hold the sum of workspace requirements (see below)
  64  *                      over all given records. The function is allowed to modify all its inputs.
  65  *  void PREFIX_copy_merged(SORT_KEY **keys, struct fastbuf **data, uns n, struct fastbuf *dest)
  66  *                      takes n records with keys in memory and data in fastbufs and writes
  67  *                      a single record. Used only if SORT_DATA_SIZE or SORT_UNIFY_WORKSPACE is defined.
  68  *  SORT_UNIFY_WORKSPACE(key)
  69  *                      gets a key and returns the amount of workspace required when merging
  70  *                      the given record. Defaults to 0.
  71  *
  72  *  Input (choose one of these):
  73  *
  74  *  SORT_INPUT_FILE     file of a given name
  75  *  SORT_INPUT_FB       seekable fastbuf stream
  76  *  SORT_INPUT_PIPE     non-seekable fastbuf stream
  77  *  SORT_INPUT_PRESORT  custom presorter. Calls function
  78  *  int PREFIX_presort(struct fastbuf *dest, void *buf, size_t bufsize)
  79  *                      to get successive batches of pre-sorted data.
  80  *                      The function is passed a page-aligned presorting buffer.
  81  *                      It returns 1 on success or 0 on EOF.
  82  *  SORT_DELETE_INPUT   A C expression, if true, then the input files are deleted
  83  *                      as soon as possible.
  84  *
  85  *  Output (chose one of these):
  86  *
  87  *  SORT_OUTPUT_FILE    file of a given name
  88  *  SORT_OUTPUT_FB      temporary fastbuf stream
  89  *  SORT_OUTPUT_THIS_FB a given fastbuf stream which can already contain a header
  90  *
  91  *  Other switches:
  92  *
  93  *  SORT_UNIQUE         all items have distinct keys (checked in debug mode)
  94  *
  95  *  The function generated:
  96  *
  97  *  <outfb> PREFIX_sort(<in>, <out> [,<range>]), where:
  98  *                      <in> = input file name/fastbuf or NULL
  99  *                      <out> = output file name/fastbuf or NULL
 100  *                      <range> = maximum integer value for the SORT_INT mode
 101  *                      <outfb> = output fastbuf (in SORT_OUTPUT_FB mode)
 102  *
 103  *  After including this file, all parameter macros are automatically
 104  *  undef'd.
 105  */
 106
 107 #include "lib/sorter/common.h"
 108 #include "lib/fastbuf.h"
 109
 110 #include <fcntl.h>
 111
 112 #define P(x) SORT_PREFIX(x)
 113
 114 #ifdef SORT_KEY_REGULAR
 115 typedef SORT_KEY_REGULAR P(key);
 116 static inline int P(read_key) (struct fastbuf *f, P(key) *k)
 117 {
 118   return breadb(f, k, sizeof(P(key)));
 119 }
 120 static inline void P(write_key) (struct fastbuf *f, P(key) *k)
 121 {
 122   bwrite(f, k, sizeof(P(key)));
 123 }
 124 #elif defined(SORT_KEY)
 125 typedef SORT_KEY P(key);
 126 #else
 127 #error Missing definition of sorting key.
 128 #endif
 129
 130 #ifdef SORT_INT
 131 static inline int P(compare) (P(key) *x, P(key) *y)
 132 {
 133   if (SORT_INT(*x) < SORT_INT(*y))
 134     return -1;
 135   if (SORT_INT(*x) > SORT_INT(*y))
 136     return 1;
 137   return 0;
 138 }
 139
 140 #ifndef SORT_HASH_BITS
 141 static inline int P(hash) (P(key) *x)
 142 {
 143   return SORT_INT((*x));
 144 }
 145 #endif
 146 #endif
 147
 148 #ifdef SORT_UNIFY
 149 #define LESS <
 150 #else
 151 #define LESS <=
 152 #endif
 153 #define SWAP(x,y,z) do { z=x; x=y; y=z; } while(0)
 154
 155 #if defined(SORT_UNIQUE) && defined(DEBUG_ASSERTS)
 156 #define SORT_ASSERT_UNIQUE
 157 #endif
 158
 159 #ifdef SORT_KEY_SIZE
 160 #define SORT_VAR_KEY
 161 #else
 162 #define SORT_KEY_SIZE(key) sizeof(key)
 163 #endif
 164
 165 #ifdef SORT_DATA_SIZE
 166 #define SORT_VAR_DATA
 167 #else
 168 #define SORT_DATA_SIZE(key) 0
 169 #endif
 170
 171 static inline void P(copy_data)(P(key) *key, struct fastbuf *in, struct fastbuf *out)
 172 {
 173   P(write_key)(out, key);
 174 #ifdef SORT_VAR_DATA
 175   bbcopy(in, out, SORT_DATA_SIZE(*key));
 176 #else
 177   (void) in;
 178 #endif
 179 }
 180
 181 #if defined(SORT_UNIFY) && !defined(SORT_VAR_DATA) && !defined(SORT_UNIFY_WORKSPACE)
 182 static inline void P(copy_merged)(P(key) **keys, struct fastbuf **data UNUSED, uns n, struct fastbuf *dest)
 183 {
 184   P(write_merged)(dest, keys, NULL, n, NULL);
 185 }
 186 #endif
 187
 188 #if defined(SORT_VAR_KEY) || defined(SORT_VAR_DATA) || defined(SORT_UNIFY_WORKSPACE)
 189 #include "lib/sorter/s-internal.h"
 190 #else
 191 #include "lib/sorter/s-fixint.h"
 192 #endif
 193
 194 #include "lib/sorter/s-twoway.h"
 195
 196 #if defined(SORT_HASH_BITS) || defined(SORT_INT)
 197 #include "lib/sorter/s-radix.h"
 198 #endif
 199
 200 static struct fastbuf *P(sort)(
 201 #ifdef SORT_INPUT_FILE
 202                                byte *in,
 203 #else
 204                                struct fastbuf *in,
 205 #endif
 206 #ifdef SORT_OUTPUT_FILE
 207                                byte *out
 208 #else
 209                                struct fastbuf *out
 210 #endif
 211 #ifdef SORT_INT
 212                                , uns int_range
 213 #endif
 214                                )
 215 {
 216   struct sort_context ctx;
 217   bzero(&ctx, sizeof(ctx));
 218
 219 #ifdef SORT_INPUT_FILE
 220   ctx.in_fb = bopen(in, O_RDONLY, sorter_stream_bufsize);
 221   ctx.in_size = bfilesize(ctx.in_fb);
 222 #elif defined(SORT_INPUT_FB)
 223   ctx.in_fb = in;
 224   ctx.in_size = bfilesize(in);
 225 #elif defined(SORT_INPUT_PIPE)
 226   ctx.in_fb = in;
 227   ctx.in_size = ~(u64)0;
 228 #elif defined(SORT_INPUT_PRESORT)
 229   ASSERT(!in);
 230   ctx.custom_presort = P(presort);
 231   ctx.in_size = ~(u64)0;
 232 #else
 233 #error No input given.
 234 #endif
 235 #ifdef SORT_DELETE_INPUT
 236   if (SORT_DELETE_INPUT)
 237     bconfig(ctx.in_fb, BCONFIG_IS_TEMP_FILE, 1);
 238 #endif
 239
 240 #ifdef SORT_OUTPUT_FB
 241   ASSERT(!out);
 242 #elif defined(SORT_OUTPUT_THIS_FB)
 243   ctx.out_fb = out;
 244 #elif defined(SORT_OUTPUT_FILE)
 245   /* Just assume fastbuf output and rename the fastbuf later */
 246 #else
 247 #error No output given.
 248 #endif
 249
 250 #ifdef SORT_HASH_BITS
 251   ctx.hash_bits = SORT_HASH_BITS;
 252   ctx.radix_split = P(radix_split);
 253 #elif defined(SORT_INT)
 254   ctx.hash_bits = 0;
 255   while (ctx.hash_bits < 32 && (int_range >> ctx.hash_bits))
 256     ctx.hash_bits++;
 257   ctx.radix_split = P(radix_split);
 258 #endif
 259
 260   ctx.internal_sort = P(internal);
 261   ctx.internal_estimate = P(internal_estimate);
 262   ctx.twoway_merge = P(twoway_merge);
 263
 264   sorter_run(&ctx);
 265
 266 #ifdef SORT_OUTPUT_FILE
 267   if (rename(ctx.out_fb->name, out) < 0)
 268     die("Cannot rename %s to %s: %m", ctx.out_fb->name, out);
 269   bconfig(ctx.out_fb, BCONFIG_IS_TEMP_FILE, 0);
 270   bclose(ctx.out_fb);
 271   ctx.out_fb = NULL;
 272 #endif
 273   return ctx.out_fb;
 274 }
 275
 276 #undef SORT_PREFIX
 277 #undef SORT_KEY
 278 #undef SORT_KEY_REGULAR
 279 #undef SORT_KEY_SIZE
 280 #undef SORT_DATA_SIZE
 281 #undef SORT_VAR_KEY
 282 #undef SORT_VAR_DATA
 283 #undef SORT_INT
 284 #undef SORT_HASH_BITS
 285 #undef SORT_UNIFY
 286 #undef SORT_UNIFY_WORKSPACE
 287 #undef SORT_INPUT_FILE
 288 #undef SORT_INPUT_FB
 289 #undef SORT_INPUT_PRESORT
 290 #undef SORT_OUTPUT_FILE
 291 #undef SORT_OUTPUT_FB
 292 #undef SORT_OUTPUT_THIS_FB
 293 #undef SORT_UNIQUE
 294 #undef SORT_ASSERT_UNIQUE
 295 #undef SORT_DELETE_INPUT
 296 #undef SWAP
 297 #undef LESS
 298 #undef P
 299 /* FIXME: Check that we undef everything we should. */