From 381c9a1f47c84273a700e5de9a88b8ffcdd8c74b Mon Sep 17 00:00:00 2001 From: Michal Vaner Date: Sun, 14 Dec 2008 11:17:28 +0100 Subject: [PATCH] ucw docs: Simple array sorter --- ucw/doc/Makefile | 2 +- ucw/doc/generic.txt | 1 + ucw/doc/index.txt | 3 +- ucw/doc/sort.txt | 89 +++++++++++++++++++++++++++++++++++++++ ucw/sorter/array-simple.h | 16 ++++--- 5 files changed, 102 insertions(+), 9 deletions(-) create mode 100644 ucw/doc/sort.txt diff --git a/ucw/doc/Makefile b/ucw/doc/Makefile index ecb22d5c..b1364848 100644 --- a/ucw/doc/Makefile +++ b/ucw/doc/Makefile @@ -2,7 +2,7 @@ DIRS+=ucw/doc -UCW_DOCS=fastbuf index config configure install basecode hash docsys conf mempool eltpool mainloop generic growbuf unaligned lists chartype unicode prime binsearch heap binheap compress +UCW_DOCS=fastbuf index config configure install basecode hash docsys conf mempool eltpool mainloop generic growbuf unaligned lists chartype unicode prime binsearch heap binheap compress sort UCW_INDEX=$(o)/ucw/doc/def_index.html UCW_DOCS_HTML=$(addprefix $(o)/ucw/doc/,$(addsuffix .html,$(UCW_DOCS))) diff --git a/ucw/doc/generic.txt b/ucw/doc/generic.txt index ff61488a..2c73f94d 100644 --- a/ucw/doc/generic.txt +++ b/ucw/doc/generic.txt @@ -11,6 +11,7 @@ libUCW, and also hints for use of these structures. - <> - Modules with generics * <> + * <> * <> // TODO The module list diff --git a/ucw/doc/index.txt b/ucw/doc/index.txt index 69823cd1..946aff67 100644 --- a/ucw/doc/index.txt +++ b/ucw/doc/index.txt @@ -27,6 +27,7 @@ Modules - <> - <> - <> +- <> - <> - <> - <> @@ -41,8 +42,6 @@ Other features Yet undocumented modules ------------------------ -- Sorting - * `sorter/` - Hash tables * `hashtable.h` - Trie diff --git a/ucw/doc/sort.txt b/ucw/doc/sort.txt new file mode 100644 index 00000000..0fbc1d2b --- /dev/null +++ b/ucw/doc/sort.txt @@ -0,0 +1,89 @@ +Sorting +======= + +A very common need is sorting data. Therefore libUCW contains few +routines to accomplish that task. They are much more universal than +qsort(), since they allow you to sort structures indexed by a macro, +sort data externally, if they do not fit into memory, merge data with +the same keys and sort data of variable length. + +All routines described below are <>. + +- <> + * <> + * <> + * <> +- <> +- <> + +[[array-simple]] +Simple array sorting +-------------------- + +If you want to sort some data in memory and you aren't too picky about +setting how, you just use the routine defined in +`sorter/array-simple.h`. It is an optimised hybrid +quick-sort/insert-sort algorithm (quick-sort is used to split the +input into small parts, each is then sorted by insert-sort). + +You need to define few macros and include the header. You get a +sorting function in return. It will be called +<>. + +[mandatory-simple] +Mandatory macros +~~~~~~~~~~~~~~~~ +- `ASORT_PREFIX(name)` -- The identifier generating macro. +- `ASORT_KEY_TYPE` -- Data type of a single array entry key. + +[optional-simple] +Optional macros +~~~~~~~~~~~~~~~ +- `ASORT_ELT(i)` -- Indexing macro. Returns the key of the + corresponding entry. If not provided, usual array with sequential + indexing is assumed. +- `ASORT_LT(x,y)` -- Comparing macro. If not provided, compares by the + `<` operator. +- `ASORT_SWAP(i,j)` -- Swap elements with indices `i` and `j`. If not + provided, it assumes `ASORT_ELT` is l-value and it just swaps keys. +- `ASORT_TRESHOLD` -- Sequences of at most this amount of elements are + sorted by quick-sort, smaller are sorted by insert-sort. Defaults to + `8` (result of experimentation). +- `ASORT_EXTRA_ARGS` -- Pass some extra arguments to the function. + They are visible from all the macros. Must start with a comma. + +!!ucw/sorter/array-simple.h ASORT_PREFIX + +[example-simple] +Example +~~~~~~~ + +Let's sort an array of integers, in the usual way. + + #define ASORT_PREFIX(X) intarr_##X + #define ASORT_TYPE int + #include + +This generates an intarr_sort(int *array, uns array_size) function that +can be used the obvious way. + +A more complicated example could be sorting a structure, where items +with odd indices are stored in one array, even in another. Each item +could be a structure containing a string and an integer. We would like +to sort them by the strings. + + struct elem { + char *string; + int integer; + }; + + #include // Because of strcmp + #define ASORT_PREFIX(X) complicated_##X + #define ASORT_TYPE struct elem + #define ASORT_ELT(i) ((i % 2 ? even_array : odd_array)[i / 2]) + #define ASORT_LT(x, y) (strcmp((x).string, (y).string) < 0) + #define ASORT_EXTRA_ARGS , struct elem *odd_array, struct elem *even_array + #include + +Now we got a complicated_sort(uns array_size, struct elem *odd_array, +struct *even_array) function to perform our sorting. diff --git a/ucw/sorter/array-simple.h b/ucw/sorter/array-simple.h index 393ebd93..5e442439 100644 --- a/ucw/sorter/array-simple.h +++ b/ucw/sorter/array-simple.h @@ -57,15 +57,19 @@ #endif #ifndef ASORT_ELT -#define ASORT_ARRAY_ARG +#define ASORT_ARRAY_ARG ASORT_KEY_TYPE *array, #define ASORT_ELT(i) array[i] +#else +#define ASORT_ARRAY_ARG #endif -static void ASORT_PREFIX(sort)( -#ifdef ASORT_ARRAY_ARG - ASORT_KEY_TYPE *array, -#endif - uns array_size ASORT_EXTRA_ARGS) +/** + * The generated sorting function. If `ASORT_ELT` macro is not provided, the + * @ASORT_ARRAY_ARG is equal to `ASORT_KEY_TYPE *array` and is the array to be + * sorted. If the macro is provided, this parameter is omitted. In that case, + * you can sort global variables or pass your structure by @ASORT_EXTRA_ARGS. + **/ +static void ASORT_PREFIX(sort)(ASORT_ARRAY_ARG uns array_size ASORT_EXTRA_ARGS) { struct stk { int l, r; } stack[8*sizeof(uns)]; int l, r, left, right, m; -- 2.39.5