ucw/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 <ucw/clists.h>
  14
  15 #ifdef CONFIG_UCW_CLEAN_ABI
  16 #define asort_run ucw_asort_run
  17 #define asort_start_threads ucw_asort_start_threads
  18 #define asort_stop_threads ucw_asort_stop_threads
  19 #define sbuck_drop ucw_sbuck_drop
  20 #define sbuck_has_file ucw_sbuck_has_file
  21 #define sbuck_have ucw_sbuck_have
  22 #define sbuck_new ucw_sbuck_new
  23 #define sbuck_read ucw_sbuck_read
  24 #define sbuck_size ucw_sbuck_size
  25 #define sbuck_swap_out ucw_sbuck_swap_out
  26 #define sbuck_write ucw_sbuck_write
  27 #define sorter_add_radix_bits ucw_sorter_add_radix_bits
  28 #define sorter_alloc ucw_sorter_alloc
  29 #define sorter_alloc_buf ucw_sorter_alloc_buf
  30 #define sorter_bufsize ucw_sorter_bufsize
  31 #define sorter_debug ucw_sorter_debug
  32 #define sorter_fb_params ucw_sorter_fb_params
  33 #define sorter_free_buf ucw_sorter_free_buf
  34 #define sorter_max_multiway_bits ucw_sorter_max_multiway_bits
  35 #define sorter_max_radix_bits ucw_sorter_max_radix_bits
  36 #define sorter_min_multiway_bits ucw_sorter_min_multiway_bits
  37 #define sorter_min_radix_bits ucw_sorter_min_radix_bits
  38 #define sorter_prepare_buf ucw_sorter_prepare_buf
  39 #define sorter_radix_threshold ucw_sorter_radix_threshold
  40 #define sorter_run ucw_sorter_run
  41 #define sorter_small_fb_params ucw_sorter_small_fb_params
  42 #define sorter_small_input ucw_sorter_small_input
  43 #define sorter_stream_bufsize ucw_sorter_stream_bufsize
  44 #define sorter_thread_chunk ucw_sorter_thread_chunk
  45 #define sorter_thread_threshold ucw_sorter_thread_threshold
  46 #define sorter_threads ucw_sorter_threads
  47 #define sorter_trace ucw_sorter_trace
  48 #define sorter_trace_array ucw_sorter_trace_array
  49 #endif
  50
  51 /* Configuration variables */
  52 extern uns sorter_trace, sorter_trace_array, sorter_stream_bufsize;
  53 extern uns sorter_debug, sorter_min_radix_bits, sorter_max_radix_bits, sorter_add_radix_bits;
  54 extern uns sorter_min_multiway_bits, sorter_max_multiway_bits;
  55 extern uns sorter_threads;
  56 extern u64 sorter_bufsize, sorter_small_input;
  57 extern u64 sorter_thread_threshold, sorter_thread_chunk, sorter_radix_threshold;
  58 extern struct fb_params sorter_fb_params, sorter_small_fb_params;
  59
  60 #define SORT_TRACE(x...) do { if (sorter_trace) msg(L_DEBUG, x); } while(0)
  61 #define SORT_XTRACE(level, x...) do { if (sorter_trace >= level) msg(L_DEBUG, x); } while(0)
  62
  63 enum sort_debug {
  64   SORT_DEBUG_NO_PRESORT = 1,
  65   SORT_DEBUG_NO_JOIN = 2,
  66   SORT_DEBUG_KEEP_BUCKETS = 4,
  67   SORT_DEBUG_NO_RADIX = 8,
  68   SORT_DEBUG_NO_MULTIWAY = 16,
  69   SORT_DEBUG_ASORT_NO_RADIX = 32,
  70   SORT_DEBUG_ASORT_NO_THREADS = 64
  71 };
  72
  73 struct sort_bucket;
  74
  75 struct sort_context {
  76   struct fastbuf *in_fb;
  77   struct fastbuf *out_fb;
  78   uns hash_bits;
  79   u64 in_size;
  80   struct fb_params *fb_params;
  81
  82   struct mempool *pool;
  83   clist bucket_list;
  84   void *big_buf;
  85   size_t big_buf_size;
  86
  87   int (*custom_presort)(struct fastbuf *dest, void *buf, size_t bufsize);
  88
  89   // Take as much as possible from the source bucket, sort it in memory and dump to destination bucket.
  90   // Return 1 if there is more data available in the source bucket.
  91   int (*internal_sort)(struct sort_context *ctx, struct sort_bucket *in, struct sort_bucket *out, struct sort_bucket *out_only);
  92
  93   // Estimate how much input data from `b' will fit in the internal sorting buffer.
  94   u64 (*internal_estimate)(struct sort_context *ctx, struct sort_bucket *b);
  95
  96   // Two-way split/merge: merge up to 2 source buckets to up to 2 destination buckets.
  97   // Bucket arrays are NULL-terminated.
  98   void (*twoway_merge)(struct sort_context *ctx, struct sort_bucket **ins, struct sort_bucket **outs);
  99
 100   // Multi-way merge: merge an arbitrary number of source buckets to a single destination bucket.
 101   void (*multiway_merge)(struct sort_context *ctx, struct sort_bucket **ins, struct sort_bucket *out);
 102
 103   // Radix split according to hash function
 104   void (*radix_split)(struct sort_context *ctx, struct sort_bucket *in, struct sort_bucket **outs, uns bitpos, uns numbits);
 105
 106   // State variables of internal_sort
 107   void *key_buf;
 108   int more_keys;
 109
 110   // Timing
 111   timestamp_t start_time;
 112   uns last_pass_time;
 113   uns total_int_time, total_pre_time, total_ext_time;
 114 };
 115
 116 void sorter_run(struct sort_context *ctx);
 117
 118 /* Buffers */
 119
 120 void *sorter_alloc(struct sort_context *ctx, uns size);
 121 void sorter_prepare_buf(struct sort_context *ctx);
 122 void sorter_alloc_buf(struct sort_context *ctx);
 123 void sorter_free_buf(struct sort_context *ctx);
 124
 125 /* Buckets */
 126
 127 struct sort_bucket {
 128   cnode n;
 129   struct sort_context *ctx;
 130   uns flags;
 131   struct fastbuf *fb;
 132   byte *filename;
 133   u64 size;                             // Size in bytes (not valid when writing)
 134   uns runs;                             // Number of runs, 0 if not sorted
 135   uns hash_bits;                        // Remaining bits of the hash function
 136   byte *ident;                          // Identifier used in debug messages
 137 };
 138
 139 enum sort_bucket_flags {
 140   SBF_FINAL = 1,                        // This bucket corresponds to the final output file (always 1 run)
 141   SBF_SOURCE = 2,                       // Contains the source file (always 0 runs)
 142   SBF_CUSTOM_PRESORT = 4,               // Contains source to read via custom presorter
 143   SBF_OPEN_WRITE = 256,                 // We are currently writing to the fastbuf
 144   SBF_OPEN_READ = 512,                  // We are reading from the fastbuf
 145   SBF_DESTROYED = 1024,                 // Already done with, no further references allowed
 146   SBF_SWAPPED_OUT = 2048,               // Swapped out to a named file
 147 };
 148
 149 struct sort_bucket *sbuck_new(struct sort_context *ctx);
 150 void sbuck_drop(struct sort_bucket *b);
 151 int sbuck_have(struct sort_bucket *b);
 152 int sbuck_has_file(struct sort_bucket *b);
 153 ucw_off_t sbuck_size(struct sort_bucket *b);
 154 struct fastbuf *sbuck_read(struct sort_bucket *b);
 155 struct fastbuf *sbuck_write(struct sort_bucket *b);
 156 void sbuck_swap_out(struct sort_bucket *b);
 157
 158 /* Contexts and helper functions for the array sorter */
 159
 160 struct asort_context {
 161   // Interface between generic code in array.c and functions generated by array.h
 162   void *array;                          // Array to sort
 163   void *buffer;                         // Auxiliary buffer (required when radix-sorting)
 164   uns num_elts;                         // Number of elements in the array
 165   uns elt_size;                         // Bytes per element
 166   uns hash_bits;                        // Remaining bits of the hash function
 167   uns radix_bits;                       // How many bits to process in a single radix-sort pass
 168   void (*quicksort)(void *array_ptr, uns num_elts);
 169   void (*quicksplit)(void *array_ptr, uns num_elts, int *leftp, int *rightp);
 170   void (*radix_count)(void *src_ptr, uns num_elts, uns *cnt, uns shift);
 171   void (*radix_split)(void *src_ptr, void *dest_ptr, uns num_elts, uns *ptrs, uns shift);
 172
 173   // Used internally by array.c
 174   struct rs_work **rs_works;
 175   struct work_queue *rs_work_queue;
 176   struct eltpool *eltpool;
 177
 178   // Configured limits translated from bytes to elements
 179   uns thread_threshold;
 180   uns thread_chunk;
 181   uns radix_threshold;
 182 };
 183
 184 void asort_run(struct asort_context *ctx);
 185 void asort_start_threads(uns run);
 186 void asort_stop_threads(void);
 187
 188 #endif