From d98cfef742e6a57c2a0b0371725f84b337e18fe6 Mon Sep 17 00:00:00 2001 From: Michal Vaner Date: Sun, 14 Dec 2008 17:11:23 +0100 Subject: [PATCH] ucw docs: external sorter --- ucw/doc/sort.txt | 184 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 184 insertions(+) diff --git a/ucw/doc/sort.txt b/ucw/doc/sort.txt index 92b03ee7..0c6c8c7f 100644 --- a/ucw/doc/sort.txt +++ b/ucw/doc/sort.txt @@ -17,6 +17,15 @@ All routines described below are <>. * <> * <> - <> + * <> + * <> + * <> + * <> + * <> + * <> + * <> + * <> + * <> [[array-simple]] Simple array sorting @@ -101,6 +110,8 @@ optimised for huge arrays. It is used mostly by the <> machinery described below, but you can use it directly. +It is in the `sorter/array.h` header. + It differs in few details: - It supports only continuous arrays, no indexing macro can be provided. @@ -134,3 +145,176 @@ Optional macros architecture. !!ucw/sorter/array.h ASORT_PREFIX + +[[external]] +External sorting +---------------- + +If you have too much data to fit into memory, you need to employ +external sorting. This external sorter operates on +<> containing sequences of items. Each item +consists of a key, optionally followed by data. Both the keys and data +may be of variable length, but the keys must be represented by +fixed-size type in memory. The length of data must be computable from +the key. Data are just copied verbatim, unless you use the merging +mode, in which data with the same keys get merged together. + +All callbacks must be thread safe. + +The sorter resides in the `sorter/sorter.h` header file. + +[[basic-external]] +Basic macros +~~~~~~~~~~~~ + +You need to provide some basic macros. Some of them are optional. + +- `SORT_PREFIX(x)` -- Identifier generating macro. This one is + mandatory. +- `SORT_KEY` -- Data structure holding the key of item in memory. The + representation on disk may be different. Either this one or + `SORT_KEY_REGULAR` must be provided. +- `SORT_KEY_REGULAR` -- You may use this instead of `SORT_KEY`, when + the keys have the same representation both in memory and on disk. + Then the sorter uses <> and <> to + load and store them. It also assumes the keys are not very long. +- `SORT_KEY_SIZE(key)` -- Returns the real size of the key. The sorter + can use this to save space and truncate the key to the given number + of bytes, when the keys have variable lengths. If the keys have + fixed sizes, there is no need for this macro. +- `SORT_DATA_SIZE(key)` -- Returns the amount of data following this + key. If you do not provide this one, the sorter assumes there are + only keys and no data. + +[[callback-external]] +Callbacks +~~~~~~~~~ + +Furthermore, you need to provide these callback functions (make sure +they are thread safe): + +- `int SORT_PREFIX(compare)(SORT_KEY *a, SORT_KEY *b)` -- Comparing + function. It should act like strcmp(). Mandatory unless provided by + <>. +- `int SORT_PREFIX(read_key)(struct fastbuf *f, SORT_KEY *k)` -- + Should read a key from the provided <> @f and + store it into @k. Returns nonzero when ok and zero when an `EOF` was + met. Mandatory unless `SORT_KEY_REGULAR` is defined. +- `void SORT_PREFIX(write_key)(struct fastbuf *f, SORT_KEY *k)` -- + Should store key @k into @f. Mandatory unless `SORT_KEY_REGULAR` is + defined. + +[[integer-external]] +Integer sorting +~~~~~~~~~~~~~~~ + +If you sort by an integer value (either computed or available from +the key), you can use this to save yourself some functions. It also +activates the <> automatically. + +- `SORT_INT(key)` -- This macro returns the integer to sort by. When + you provide it, the compare function is automatically provided for + you and the sorting function gets another parameter specifying the + range of the integers. The better the range fits, the faster the + sorting runs. +- `SORT_INT64(key)` -- The same, but with 64-bit integers. + +[[hash-external]] +Hashing +~~~~~~~ + +If you have a monotone hash function for your keys, you may speed the +sorting up by providing it. Monotone hashing function must satisfy if +`hash(x) < hash(y)`, then `x < y`. It should be approximately +uniformly distributed. + +When you want to use it, define `SORT_HASH_BITS` and set it to the +number of significant bits the hashing function provides. Then provide +a callback function `uns SORT_PREFIX(hash)(SORT_KEY *key)`. + +[[merge-external]] +Merging items with identical keys +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +The sorter is able to merge items with the same keys (the compare +function returns `0` for them). To use it, define `SORT_UNIFY` macro +and provide these functions: + +- `void SORT_PREFIX(write_merged)(struct fastbuf \*dest, SORT_KEY + \*\*keys, void \*\*data, uns n, void *buf)` + -- This function takes @n records in memory and writes a single + record into the @dest <>. The @keys and @data are + just the records. The @buf parameter points to a workspace memory. + It is guaranteed to hold at last the sum of `SUM_UNIFY_WORKSPACE()` + macro over all the keys. The function is allowed to modify all its + parameters. +- `void SORT_PREFIX(copy_merged)(SORT_KEY \*\*keys, struct fastbuf +\*\*data, uns n, struct fastbuf \*dest)` + -- This one is similar to the above one, but the data are still in + the <> @data and no workspace is provided. This + is only used when `SORT_DATA_SIZE` or `SORT_UNIFY_WORKSPACE` is + provided. +- `SORT_UNIFY_WORKSPACE(key)` -- Returns the amount of workspace + needed when merging this record. Defaults to `0`. + +[[input-external]] +Specifying input +~~~~~~~~~~~~~~~~ + +To tell the sorter where is the input, you specify one of these +macros: + +- `SORT_INPUT_FILE` -- The function takes a filename. +- `SORT_INPUT_FB` -- The input is a seekable fastbuf stream. +- `SORT_INPUT_PIPE` -- The input is a non-seekable fastbuf stream. +- `SORT_INPUT_PRESORT` -- The input is a custom presorter. In this + case, you need to write a presorting function `int + SORT_PREFIX(presort)(struct fastbuf *dest, void *buf, size_t + bufsize)`. The function gets a buffer @buf of size @buf_size to + presort in and is supposed to write presorted bunch of data into the + @dest buffer. Should return `1` on success or `0` on `EOF` (all it + could was already written, no more data). In this case, you can + safely pass NULL as the input parameter. The function may be used to + generate the data on the fly. The function does not have to be + thread safe (it can access global variables). + +If you define `SORT_DELETE_INPUT` and it evaluates to true (nonzero), +the input files are deleted as soon as possible. + +[[output-external]] +Specifying output +~~~~~~~~~~~~~~~~~ + +You can configure the output in a similar way. Define one of macros: + +- `SORT_OUTPUT_FILE` -- The function takes a filename. +- `SORT_OUTPUT_FB` -- The function should be provided with NULL and + the fastbuf with data is returned. +- `SORT_THIS_FB` -- A fastbuf is provided to the function and it + writes into it. It can already contain some data. + +[[other-external]] +Other switches +~~~~~~~~~~~~~~ + +You may define the `SORT_UNIQUE` macro if all keys are distinct. It is +checked in debug mode. + +[[function-external]] +The generated function +~~~~~~~~~~~~~~~~~~~~~~ + +A `SORT_PREFIX(sort)()` function is generated after you include the +`sorter/sorter.h` header. It has up to three parameters: + +- Input. It is either a string (a filename) if you use + `SORT_INPUT_FILE` or a fastbuf (otherwise). It should be set to NULL + if you use the `SORT_INPUT_PRESORT` input. +- Output. It is either a string (a filename) if you defined the + `SORT_OUTPUT_FILE` or a fastbuf. It must be NULL if you defined + `SORT_OUTPUT_FB`. +- Integer range. The maximum value of integers that are used in the + <>. This parameter is here only + if you defined `SORT_INT` or `SORT_INT64`. + +The function returns a fastbuf you can read the data from. -- 2.39.2