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