lib/sorter/common.h

   1 /*
   2  *      UCW Library -- Universal Sorter: Common Declarations
   3  *
   4  *      (c) 2007 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 #ifndef _UCW_SORTER_COMMON_H
  11 #define _UCW_SORTER_COMMON_H
  12
  13 #include "lib/clists.h"
  14
  15 /* Configuration, some of the variables are used by the old sorter, too. */
  16 extern uns sorter_trace, sorter_presort_bufsize, sorter_stream_bufsize;
  17
  18 struct sort_bucket {
  19   cnode n;
  20   uns flags;
  21   struct fastbuf *fb;
  22   byte *name;
  23   u64 size;                             // Size in bytes
  24   uns runs;                             // Number of runs, 0 if unknown
  25   uns hash_bits;                        // Remaining bits of the hash function
  26   byte *ident;                          // Identifier used in debug messages
  27 };
  28
  29 enum sort_bucket_flags {
  30   SBF_FINAL = 1,                        // This bucket corresponds to the final output file
  31   SBF_SOURCE = 2,                       // Contains the source file
  32 };
  33
  34 struct sort_context {
  35   struct fastbuf *in_fb;
  36   struct fastbuf *out_fb;
  37   uns hash_bits;
  38
  39   struct mempool *pool;
  40   clist bucket_list;
  41   byte *big_buf, *big_buf_half;
  42   uns big_buf_size, big_buf_half_size;
  43
  44   struct fastbuf *(*custom_presort)(void);
  45   // Take as much as possible from the source bucket, sort it in memory and dump to destination bucket.
  46   // Return 1 if there is more data available in the source bucket.
  47   int (*internal_sort)(struct sort_context *ctx, struct sort_bucket *in, struct sort_bucket *out);
  48   // Two-way split/merge: merge up to 2 source buckets to up to 2 destination buckets.
  49   // Bucket arrays are NULL-terminated.
  50   void (*twoway_merge)(struct sort_context *ctx, struct sort_bucket **ins, struct sort_bucket **outs);
  51 };
  52
  53 void sorter_run(struct sort_context *ctx);
  54
  55 struct sort_bucket *sorter_new_bucket(struct sort_context *ctx);
  56 struct fastbuf *sorter_open_read(struct sort_bucket *b);
  57 struct fastbuf *sorter_open_write(struct sort_bucket *b);
  58 void sorter_close_read(struct sort_bucket *b);
  59 void sorter_close_write(struct sort_bucket *b);
  60
  61 #endif