ucw/doc/sort.txt

   1 Sorting
   2 =======
   3
   4 A very common need is sorting data. Therefore libUCW contains few
   5 routines to accomplish that task. They are much more universal than
   6 qsort(), since they allow you to sort structures indexed by a macro,
   7 sort data externally, if they do not fit into memory, merge data with
   8 the same keys and sort data of variable length.
   9
  10 All routines described below are <<generic:,generic algorithms>>.
  11
  12 - <<array-simple,Simple array sorting>>
  13   * <<mandatory-simple,Mandatory macros>>
  14   * <<optional-simple,Optional macros>>
  15   * <<example-simple,Example>>
  16 - <<array,Huge array sorting>>
  17   * <<mandatory-array,Mandatory macros>>
  18   * <<optional-array,Optional macros>>
  19 - <<external,External sorting>>
  20   * <<basic-external,Basic macros>>
  21   * <<callback-external,Callbacks>>
  22   * <<integer-external,Integer sorting>>
  23   * <<hash-external,Hashing>>
  24   * <<merge-external,Merging>>
  25   * <<input-external,Input>>
  26   * <<output-external,Output>>
  27   * <<other-external,Other switches>>
  28   * <<function-external,Generated function>>
  29
  30 [[array-simple]]
  31 Simple array sorting
  32 --------------------
  33
  34 If you want to sort some data in memory and you aren't too picky about
  35 setting how, you just use the routine defined in
  36 `sorter/array-simple.h`. It is an optimised hybrid
  37 quick-sort/insert-sort algorithm (quick-sort is used to split the
  38 input into small parts, each is then sorted by insert-sort). It is
  39 more than 2 times faster than stdlib's qsort(), mostly because of
  40 inlining.
  41
  42 You need to define few macros and include the header. You get a
  43 sorting function in return. It will be called
  44 <<fun__GENERIC_LINK_|ASORT_PREFIX|sort|,`ASORT_PREFIX(sort)`>>.
  45
  46 [[mandatory-simple]]
  47 Mandatory macros
  48 ~~~~~~~~~~~~~~~~
  49 - `ASORT_PREFIX(name)` -- The identifier generating macro.
  50 - `ASORT_KEY_TYPE` -- Data type of a single array entry key.
  51
  52 [[optional-simple]]
  53 Optional macros
  54 ~~~~~~~~~~~~~~~
  55 - `ASORT_ELT(i)` -- Indexing macro. Returns the key of the
  56   corresponding entry. If not provided, usual array with sequential
  57   indexing is assumed.
  58 - `ASORT_LT(x,y)` -- Comparing macro. If not provided, compares by the
  59   `<` operator.
  60 - `ASORT_SWAP(i,j)` -- Swap elements with indices `i` and `j`. If not
  61   provided, it assumes `ASORT_ELT` is l-value and it just swaps keys.
  62 - `ASORT_TRESHOLD` -- Sequences of at most this amount of elements are
  63   sorted by quick-sort, smaller are sorted by insert-sort. Defaults to
  64   `8` (result of experimentation).
  65 - `ASORT_EXTRA_ARGS` -- Pass some extra arguments to the function.
  66   They are visible from all the macros. Must start with a comma.
  67
  68 !!ucw/sorter/array-simple.h ASORT_PREFIX
  69
  70 [[example-simple]]
  71 Example
  72 ~~~~~~~
  73
  74 Let's sort an array of integers, in the usual way.
  75
  76   #define ASORT_PREFIX(X) intarr_##X
  77   #define ASORT_TYPE int
  78   #include <ucw/sorter/array-simple.h>
  79
  80 This generates an intarr_sort(int *array, uns array_size) function that
  81 can be used the obvious way.
  82
  83 A more complicated example could be sorting a structure, where items
  84 with odd indices are stored in one array, even in another. Each item
  85 could be a structure containing a string and an integer. We would like
  86 to sort them by the strings.
  87
  88   struct elem {
  89     char *string;
  90     int integer;
  91   };
  92
  93   #include <string.h>   // Because of strcmp
  94   #define ASORT_PREFIX(X) complicated_##X
  95   #define ASORT_TYPE struct elem
  96   #define ASORT_ELT(i) ((i % 2 ? even_array : odd_array)[i / 2])
  97   #define ASORT_LT(x, y) (strcmp((x).string, (y).string) < 0)
  98   #define ASORT_EXTRA_ARGS , struct elem *odd_array, struct elem *even_array
  99   #include <ucw/sorter/sorter/array-simple.h>
 100
 101 Now we got a complicated_sort(uns array_size, struct elem *odd_array,
 102 struct *even_array) function to perform our sorting.
 103
 104 [[array]]
 105 Huge array sorting
 106 ------------------
 107
 108 This one is very similar to the simple array sorter, but it is
 109 optimised for huge arrays. It is used mostly by the
 110 <<external,external sorter>> machinery described below, but you can
 111 use it directly.
 112
 113 It is in the `sorter/array.h` header.
 114
 115 It differs in few details:
 116 - It supports only continuous arrays, no indexing macro can be
 117   provided.
 118 - It is able to sort in parallel on SMP systems. It assumes all
 119   callbacks you provide are thread-safe.
 120 - If you provide a monotone hash function (if `hash(x) < hash(y)`, then
 121   `x < y`, but `x` and `y` may differ when `hash(x) == hash(y)`), it
 122   will use it to gain some more speed by radix-sort.
 123
 124 [[mandatory-array]]
 125 Mandatory macros
 126 ~~~~~~~~~~~~~~~~
 127
 128 - `ASORT_PREFIX(x)` -- The identifier generating macro.
 129 - `ASORT_KEY_TYPE` -- Type of elements in the array.
 130
 131 [[optional-array]]
 132 Optional macros
 133 ~~~~~~~~~~~~~~~
 134
 135 - `ASORT_LT(x,y)` -- Comparing macro. Uses the `<` operator if not
 136   provided.
 137 - `ASORT_HASH(x)` -- A monotone hash function (or macro). Should
 138   return `uns`.
 139 - `ASORT_LONG_HASH(x)` -- Like `ASORT_HASH(x)`, but returns 64-bit
 140   number instead of 32-bit.
 141 - `ASORT_TRESHOLD` -- How small should a chunk of data be to be sorted
 142   by insert-sort? Defaults to `8` elements.
 143 - `ASORT_RADIX_BITS` -- How many bits of the hash function should be
 144   used at once for radix-sort? The default is guessed from your
 145   architecture.
 146
 147 !!ucw/sorter/array.h ASORT_PREFIX
 148
 149 [[external]]
 150 External sorting
 151 ----------------
 152
 153 If you have too much data to fit into memory, you need to employ
 154 external sorting. This external sorter operates on
 155 <<fastbuf:,fastbufs>> containing sequences of items. Each item
 156 consists of a key, optionally followed by data. Both the keys and data
 157 may be of variable length, but the keys must be represented by
 158 fixed-size type in memory. The length of data must be computable from
 159 the key. Data are just copied verbatim, unless you use the merging
 160 mode, in which data with the same keys get merged together.
 161
 162 All callbacks must be thread safe.
 163
 164 The sorter resides in the `sorter/sorter.h` header file.
 165
 166 [[basic-external]]
 167 Basic macros
 168 ~~~~~~~~~~~~
 169
 170 You need to provide some basic macros. Some of them are optional.
 171
 172 - `SORT_PREFIX(x)` -- Identifier generating macro. This one is
 173   mandatory.
 174 - `SORT_KEY` -- Data structure holding the key of item in memory. The
 175   representation on disk may be different. Either this one or
 176   `SORT_KEY_REGULAR` must be provided.
 177 - `SORT_KEY_REGULAR` -- You may use this instead of `SORT_KEY`, when
 178   the keys have the same representation both in memory and on disk.
 179   Then the sorter uses <<fastbuf:bread()>> and <<fastbuf:bwrite()>> to
 180   load and store them. It also assumes the keys are not very long.
 181 - `SORT_KEY_SIZE(key)` -- Returns the real size of the key. The sorter
 182   can use this to save space and truncate the key to the given number
 183   of bytes, when the keys have variable lengths. If the keys have
 184   fixed sizes, there is no need for this macro.
 185 - `SORT_DATA_SIZE(key)` -- Returns the amount of data following this
 186   key. If you do not provide this one, the sorter assumes there are
 187   only keys and no data.
 188
 189 [[callback-external]]
 190 Callbacks
 191 ~~~~~~~~~
 192
 193 Furthermore, you need to provide these callback functions (make sure
 194 they are thread safe):
 195
 196 - `int SORT_PREFIX(compare)(SORT_KEY *a, SORT_KEY *b)` -- Comparing
 197   function. It should act like strcmp(). Mandatory unless provided by
 198   <<integer-external,integer sorting>>.
 199 - `int SORT_PREFIX(read_key)(struct fastbuf *f, SORT_KEY *k)` --
 200   Should read a key from the provided <<fastbuf:,fastbuf>> @f and
 201   store it into @k. Returns nonzero when ok and zero when an `EOF` was
 202   met. Mandatory unless `SORT_KEY_REGULAR` is defined.
 203 - `void SORT_PREFIX(write_key)(struct fastbuf *f, SORT_KEY *k)` --
 204   Should store key @k into @f. Mandatory unless `SORT_KEY_REGULAR` is
 205   defined.
 206
 207 [[integer-external]]
 208 Integer sorting
 209 ~~~~~~~~~~~~~~~
 210
 211 If you sort by an integer value (either computed or available from
 212 the key), you can use this to save yourself some functions. It also
 213 activates the <<hash-external,hashing>> automatically.
 214
 215 - `SORT_INT(key)` -- This macro returns the integer to sort by. When
 216   you provide it, the compare function is automatically provided for
 217   you and the sorting function gets another parameter specifying the
 218   range of the integers. The better the range fits, the faster the
 219   sorting runs.
 220 - `SORT_INT64(key)` -- The same, but with 64-bit integers.
 221
 222 [[hash-external]]
 223 Hashing
 224 ~~~~~~~
 225
 226 If you have a monotone hash function for your keys, you may speed the
 227 sorting up by providing it. Monotone hashing function must satisfy if
 228 `hash(x) < hash(y)`, then `x < y`. It should be approximately
 229 uniformly distributed.
 230
 231 When you want to use it, define `SORT_HASH_BITS` and set it to the
 232 number of significant bits the hashing function provides. Then provide
 233 a callback function `uns SORT_PREFIX(hash)(SORT_KEY *key)`.
 234
 235 [[merge-external]]
 236 Merging items with identical keys
 237 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 238
 239 The sorter is able to merge items with the same keys (the compare
 240 function returns `0` for them). To use it, define `SORT_UNIFY` macro
 241 and provide these functions:
 242
 243 - `void SORT_PREFIX(write_merged)(struct fastbuf \*dest, SORT_KEY
 244   \*\*keys, void \*\*data, uns n, void *buf)`
 245   -- This function takes @n records in memory and writes a single
 246   record into the @dest <<fastbuf:,fastbuf>>. The @keys and @data are
 247   just the records. The @buf parameter points to a workspace memory.
 248   It is guaranteed to hold at last the sum of `SUM_UNIFY_WORKSPACE()`
 249   macro over all the keys. The function is allowed to modify all its
 250   parameters.
 251 - `void SORT_PREFIX(copy_merged)(SORT_KEY \*\*keys, struct fastbuf
 252 \*\*data, uns n, struct fastbuf \*dest)`
 253   -- This one is similar to the above one, but the data are still in
 254   the <<fastbuf:,fastbufs>> @data and no workspace is provided. This
 255   is only used when `SORT_DATA_SIZE` or `SORT_UNIFY_WORKSPACE` is
 256   provided.
 257 - `SORT_UNIFY_WORKSPACE(key)` -- Returns the amount of workspace
 258   needed when merging this record. Defaults to `0`.
 259
 260 [[input-external]]
 261 Specifying input
 262 ~~~~~~~~~~~~~~~~
 263
 264 To tell the sorter where is the input, you specify one of these
 265 macros:
 266
 267 - `SORT_INPUT_FILE` -- The function takes a filename.
 268 - `SORT_INPUT_FB` -- The input is a seekable fastbuf stream.
 269 - `SORT_INPUT_PIPE` -- The input is a non-seekable fastbuf stream.
 270 - `SORT_INPUT_PRESORT` -- The input is a custom presorter. In this
 271   case, you need to write a presorting function `int
 272   SORT_PREFIX(presort)(struct fastbuf *dest, void *buf, size_t
 273   bufsize)`. The function gets a buffer @buf of size @buf_size to
 274   presort in and is supposed to write presorted bunch of data into the
 275   @dest buffer. Should return `1` on success or `0` on `EOF` (all it
 276   could was already written, no more data). In this case, you can
 277   safely pass NULL as the input parameter. The function may be used to
 278   generate the data on the fly. The function does not have to be
 279   thread safe (it can access global variables).
 280
 281 If you define `SORT_DELETE_INPUT` and it evaluates to true (nonzero),
 282 the input files are deleted as soon as possible.
 283
 284 [[output-external]]
 285 Specifying output
 286 ~~~~~~~~~~~~~~~~~
 287
 288 You can configure the output in a similar way. Define one of macros:
 289
 290 - `SORT_OUTPUT_FILE` -- The function takes a filename.
 291 - `SORT_OUTPUT_FB` -- The function should be provided with NULL and
 292   the fastbuf with data is returned.
 293 - `SORT_THIS_FB` -- A fastbuf is provided to the function and it
 294   writes into it. It can already contain some data.
 295
 296 [[other-external]]
 297 Other switches
 298 ~~~~~~~~~~~~~~
 299
 300 You may define the `SORT_UNIQUE` macro if all keys are distinct. It is
 301 checked in debug mode.
 302
 303 [[function-external]]
 304 The generated function
 305 ~~~~~~~~~~~~~~~~~~~~~~
 306
 307 A `SORT_PREFIX(sort)()` function is generated after you include the
 308 `sorter/sorter.h` header. It has up to three parameters:
 309
 310 - Input. It is either a string (a filename) if you use
 311   `SORT_INPUT_FILE` or a fastbuf (otherwise). It should be set to NULL
 312   if you use the `SORT_INPUT_PRESORT` input.
 313 - Output. It is either a string (a filename) if you defined the
 314   `SORT_OUTPUT_FILE` or a fastbuf. It must be NULL if you defined
 315   `SORT_OUTPUT_FB`.
 316 - Integer range. The maximum value of integers that are used in the
 317   <<integer-external,integer sorting>>. This parameter is  here only
 318   if you defined `SORT_INT` or `SORT_INT64`.
 319
 320 The function returns a fastbuf you can read the data from.