[igt-dev] [PATCH i-g-t v3] lib/igt_collection: Adding combinatorics facility

[Petri Latvala]

On Mon, Jan 20, 2020 at 07:05:13PM +0100, Zbigniew Kempczyński wrote:
> Dynamic tests gives us new method to create tests depending on the
> hardware/software capabilities. To check coverage some tests require
> verification over some set of objects/data. To make life easier
> with combinatorics this patch introduces igt_collection. Currently it
> supports iterating over set to get subsets, combinations, variations
> with and without repetitions.
> Code has some limitation (set/subset cannot be larger than 16 elements,
> what is enough for most cases).
> 
> Signed-off-by: Zbigniew Kempczyński <zbigniew.kempczynski at intel.com>
> Cc: Petri Latvala <petri.latvala at intel.com>
> Cc: Chris Wilson <chris at chris-wilson.co.uk>
> ---
>  lib/Makefile.sources |   2 +
>  lib/igt_collection.c | 422 +++++++++++++++++++++++++++++++++++++++++++
>  lib/igt_collection.h |  99 ++++++++++
>  lib/meson.build      |   1 +
>  4 files changed, 524 insertions(+)
>  create mode 100644 lib/igt_collection.c
>  create mode 100644 lib/igt_collection.h
> 
> diff --git a/lib/Makefile.sources b/lib/Makefile.sources
> index feb8c20d..631d6714 100644
> --- a/lib/Makefile.sources
> +++ b/lib/Makefile.sources
> @@ -29,6 +29,8 @@ lib_source_list =	 	\
>  	igt_device_scan.h	\
>  	igt_aux.c		\
>  	igt_aux.h		\
> +	igt_collection.c	\
> +	igt_collection.h	\
>  	igt_color_encoding.c	\
>  	igt_color_encoding.h	\
>  	igt_edid.c		\
> diff --git a/lib/igt_collection.c b/lib/igt_collection.c
> new file mode 100644
> index 00000000..f0151f12
> --- /dev/null
> +++ b/lib/igt_collection.c
> @@ -0,0 +1,422 @@
> +#include "igt.h"
> +#include "igt_collection.h"
> +/**
> + * Generic combinatorics library.
> + *
> + * Supports:
> + * - subsets
> + * - combinations
> + * - variations with repetitions
> + * - variations without repetitions
> + *
> + * 1. Subsets
> + *
> + * Let A = { 1, 2, 3 }
> + *
> + * With subset size == 2 we got subsets with number of elements <= subset size:
> + * {}
> + * { 1 }
> + * { 2 }
> + * { 3 }
> + * { 1, 2 }
> + * { 1, 3 }
> + * { 2, 3 }
> + *
> + * 2. Combinations
> + *
> + * Let A = { 1, 2, 3 }
> + *
> + * With subset size == 2 we got subsets with number of elements == subset size:
> + * { 1, 2 }
> + * { 1, 3 }
> + * { 2, 3 }
> + *
> + * So it is similar to subset extraction but targeted to single subset size.
> + *
> + * 3. Variations with repetitions
> + *
> + * Let A = { 0, 1 }
> + *
> + * With result size == 3 we got result tuples:
> + *
> + * ( 0, 0, 0 )
> + * ( 0, 0, 1 )
> + * ( 0, 1, 0 )
> + * ( 0, 1, 1 )
> + * ( 1, 0, 0 )
> + * ( 1, 0, 1 )
> + * ( 1, 1, 0 )
> + * ( 1, 1, 1 )
> + *
> + * 4. Variations without repetitions
> + *
> + * Let A = { 1, 2, 3 }
> + *
> + * With subset size == 2 we got tuples:
> + *
> + * (1, 2)
> + * (1, 3)
> + * (2, 1)
> + * (2, 3)
> + * (3, 1)
> + * (3, 2)
> + *
> + * ===
> + *
> + * Usage examples:
> + *
> + * a) iterator is manually controlled:
> + *
> + * struct igt_collection *set;
> + * struct igt_collection *subset;
> + * struct igt_collection_iter *iter;
> + *
> + * int i;
> + * set = igt_collection_create(4);
> + * iter = igt_collection_iter_init(set, 2, SUBSET);
> + * //iter = igt_collection_iter_init(set, 2, COMBINATION);
> + * //iter = igt_collection_iter_init(set, 2, VARIATION_R);
> + * //iter = igt_collection_iter_init(set, 2, VARIATION_NR);
> + *
> + * for (i = 0; i < set->size; i++) {
> + *      igt_collection_set_value(set, i, i + 1);
> + *      igt_collection_set_pointer(set, i, &i + i);
> + * }
> + *
> + * while ((subset = igt_collection_iter_next(iter))) {
> + *      // --- do sth with subset ---
> + *      // --- subset is a part of iterator, so don't free it! ---
> + * }
> + *
> + * igt_collection_iter_destroy(iter);
> + * igt_collection_destroy(set);
> + *
> + * // -------------------------------------
> + * b) iterator is created and destroyed inside helper macros:
> + *
> + * struct igt_collection *set;
> + * struct igt_collection *subset, *result;
> + * struct igt_collection_data *data;
> + *
> + * for_each_subset(subset, subset_size, set)
> + *       // --- do sth with subset ---
> + *
> + * for_each_combination(subset, subset_size, set)
> + *       // --- do sth with subset ---
> + *
> + * for_each_variation_r(result, result_size, set)
> + *       // --- do sth with result ---
> + *
> + * for_each_variation_nr(result, result_size, set)
> + *       // --- do sth with result ---
> + *
> + * // macro for iteration over set data - for_each_collection_data()
> + * for_each_subset(subset, subset_size, set)
> + *       for_each_collection_data(data, subset)
> + *             printf("v: %d, p: %p\n", data->value, data->ptr);
> + */

Wonderfully documented. Did you check that this ends up in the docs though?


-- 
Petri Latvala