[igt-dev] [PATCH i-g-t] lib/igt_set: Adding combinatorics facility
Chris Wilson
chris at chris-wilson.co.uk
Fri Jan 17 10:58:37 UTC 2020
Quoting Zbigniew Kempczyński (2020-01-17 07:54:49)
> 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_set. Currently it supports
> iterating over set to get subsets, combinations and multicombinations.
> 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_set.c | 250 +++++++++++++++++++++++++++++++++++++++++++
> lib/igt_set.h | 62 +++++++++++
> lib/meson.build | 1 +
> 4 files changed, 315 insertions(+)
> create mode 100644 lib/igt_set.c
> create mode 100644 lib/igt_set.h
>
> diff --git a/lib/Makefile.sources b/lib/Makefile.sources
> index 5dd3962e..7852d52a 100644
> --- a/lib/Makefile.sources
> +++ b/lib/Makefile.sources
> @@ -52,6 +52,8 @@ lib_source_list = \
> igt_rapl.c \
> igt_rapl.h \
> igt_rc.h \
> + igt_set.c \
> + igt_set.h \
> igt_stats.c \
> igt_stats.h \
> igt_sysfs.c \
> diff --git a/lib/igt_set.c b/lib/igt_set.c
> new file mode 100644
> index 00000000..797c51ad
> --- /dev/null
> +++ b/lib/igt_set.c
> @@ -0,0 +1,250 @@
> +#include "igt.h"
> +#include "igt_set.h"
> +
> +/**
> + * Generic combinatorics library.
> + *
> + * Supports: subsets, combinations and multicombinations.
> + *
> + * Usage example:
> + *
> + * struct igt_set *set;
> + * struct igt_set *subset;
> + * struct igt_set_iterator *iter;
> + *
> + * int i;
> + * set = igt_set_init(4);
> + * iter = igt_set_iterator_init(set, 2, IGT_SET_SUBSETS);
> + * //iter = igt_set_iterator_init(set, 2, IGT_SET_MULTICOMBINATION);
> + * //iter = igt_set_iterator_init(set, 2, IGT_SET_COMBINATION);
> + *
> + * for (i = 0; i < set->size; i++) {
> + * igt_set_setvalue(set, i, i * 2);
> + * igt_set_setptr(set, i, &i + i);
set_setX, meh.
igt_collection_set_value()
igt_collection_set_pointer()
iter = igt_collection_iter();
[it's not an init as it allocates ;]
> + * }
> + *
> + * while ((subset = igt_set_iterate_next(iter))) {
> + * // --- do sth with subset ---
> + * // --- subset is a part of iterator, so don't free it! ---
> + * }
> + *
> + * igt_set_iterator_free(iter);
> + * igt_set_free(set);
> + */
> +
> +/* Taken from Hacker's Delight */
> +static inline int num_bits_set(uint32_t x)
> +{
> + x = x - ((x >> 1) & 0x55555555);
> + x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
> + x = (x + (x >> 4)) & 0x0F0F0F0F;
> + x = x + (x >> 8);
> + x = x + (x >> 16);
> + return x & 0x0000003F;
> +}
-> __builtin_popcount()
> +
> +struct igt_set_iterator {
> + struct igt_set *set;
> + enum igt_set_iteration_algorithm algorithm;
> + bool init;
> + int result_size;
> + struct igt_set result;
> +
> + /* Algorithms state, to be used by iterators */
> + struct {
> + uint32_t result_bits;
> + int current_result_size;
> + int idxs[IGT_SET_MAXSIZE];
> + } data;
> +};
> +
> +struct igt_set *igt_set_init(int size)
> +{
> + struct igt_set *set;
> + int i;
> +
> + igt_assert(size > 0 && size <= IGT_SET_MAXSIZE);
> +
> + set = calloc(1, sizeof(*set));
> + igt_assert(set);
> +
> + set->size = size;
> + for (i = 0; i < size; i++)
> + set->set[i].value = i; /* set to index as default */
> +
> + return set;
> +}
> +
> +void igt_set_free(struct igt_set *set)
> +{
> + free(set);
> +}
> +
> +void igt_set_setvalue(struct igt_set *set, int index, int value)
> +{
> + set->set[index].value = value;
> +}
> +
> +int igt_set_getvalue(struct igt_set *set, int index)
> +{
> + return set->set[index].value;
> +}
> +
> +void igt_set_setptr(struct igt_set *set, int index, void *ptr)
> +{
> + set->set[index].ptr = ptr;
> +}
> +
> +void *igt_set_getptr(struct igt_set *set, int index)
> +{
> + return set->set[index].ptr;
> +}
> +
> +struct igt_set_iterator *igt_set_iterator_init(struct igt_set *set,
> + int result_size,
> + enum igt_set_iteration_algorithm algorithm)
> +{
> + struct igt_set_iterator *iter;
> +
> + igt_assert(result_size > 0 && result_size <= IGT_SET_MAXSIZE);
> + if (algorithm != IGT_SET_MULTICOMBINATION)
> + igt_assert(result_size <= set->size);
> +
> + iter = calloc(1, sizeof(*iter));
> + igt_assert(iter);
> +
> + iter->set = set;
> + iter->result_size = result_size;
> + iter->algorithm = algorithm;
> + iter->init = true;
> +
> + return iter;
> +}
> +
> +void igt_set_iterator_free(struct igt_set_iterator *iter)
> +{
> + free(iter);
> +}
> +
> +static struct igt_set *igt_set_iter_subsets(struct igt_set_iterator *iter)
> +{
> + struct igt_set *set = iter->set;
> + struct igt_set *curr = &iter->result;
> + int i, pos = 0;
> +
> + if (iter->init) {
> + iter->init = false;
> + iter->data.result_bits = 0;
> + iter->data.current_result_size = 0;
> + curr->size = 0;
> + } else {
> + iter->data.result_bits++;
> + if (iter->data.result_bits & (1 << iter->set->size)) {
> + iter->data.current_result_size++;
> + iter->data.result_bits = 0;
> + }
> + if (iter->data.current_result_size > iter->result_size)
> + return NULL;
> + }
> +
> + while (num_bits_set(iter->data.result_bits) != iter->data.current_result_size) {
> + iter->data.result_bits++;
> + if (iter->data.result_bits & (1 << iter->set->size)) {
> + iter->data.current_result_size++;
> + iter->data.result_bits = 0;
> + }
> + }
> +
> + if (iter->data.current_result_size > iter->result_size)
> + return NULL;
> +
> + for (i = 0; i < set->size; i++) {
> + if (!(iter->data.result_bits & (1 << i)))
> + continue;
> + curr->set[pos++] = set->set[i];
> + curr->size = pos;
> + }
> +
> + return curr;
> +}
> +
> +static struct igt_set *igt_set_iter_combination(struct igt_set_iterator *iter)
> +{
> + struct igt_set *set = iter->set;
> + struct igt_set *curr = &iter->result;
> + int i, pos = 0;
> +
> + if (iter->init) {
> + iter->init = false;
> + iter->data.result_bits = 0;
> + iter->result.size = iter->result_size;
> + } else {
> + iter->data.result_bits++;
> + }
> +
> + while (num_bits_set(iter->data.result_bits) != iter->result_size)
> + iter->data.result_bits++;
> +
> + if (iter->data.result_bits & (1 << set->size))
> + return NULL;
> +
> + for (i = 0; i < set->size; i++) {
> + if (!(iter->data.result_bits & (1 << i)))
> + continue;
> + curr->set[pos++] = set->set[i];
> + curr->size = pos;
> + }
> +
> + return curr;
> +}
> +
> +static struct igt_set *igt_set_iter_multicombination(struct igt_set_iterator *iter)
> +{
> + struct igt_set *set = iter->set;
> + struct igt_set *curr = &iter->result;
> + int i;
> +
> + if (iter->init) {
> + iter->init = false;
> + iter->result.size = iter->result_size;
> + for (i = 0; i < iter->result_size; i++)
> + iter->data.idxs[i] = 0;
> + }
> +
> + if (iter->data.idxs[0] == iter->set->size)
> + return NULL;
> +
> + for (i = 0; i < iter->result_size; i++)
> + curr->set[i] = set->set[iter->data.idxs[i]];
> +
> + for (i = iter->result_size-1; i >= 0; i--) {
> + if (++iter->data.idxs[i] == iter->set->size && i > 0) {
> + iter->data.idxs[i] %= iter->set->size;
> + } else {
> + break;
> + }
> + }
> +
> + return curr;
> +}
> +
> +struct igt_set *igt_set_iterate_next(struct igt_set_iterator *iter)
> +{
> + struct igt_set *ret_set = NULL;
> +
> + switch(iter->algorithm) {
> + case IGT_SET_SUBSETS:
> + ret_set = igt_set_iter_subsets(iter);
> + break;
> + case IGT_SET_COMBINATION:
> + ret_set = igt_set_iter_combination(iter);
> + break;
> + case IGT_SET_MULTICOMBINATION:
> + ret_set = igt_set_iter_multicombination(iter);
> + break;
> + default:
> + igt_assert_f(false, "Unknown algorithm\n");
> + }
> +
> + return ret_set;
> +}
> diff --git a/lib/igt_set.h b/lib/igt_set.h
> new file mode 100644
> index 00000000..238c226a
> --- /dev/null
> +++ b/lib/igt_set.h
> @@ -0,0 +1,62 @@
> +/*
> + * Copyright © 2020 Intel Corporation
> + *
> + * Permission is hereby granted, free of charge, to any person obtaining a
> + * copy of this software and associated documentation files (the "Software"),
> + * to deal in the Software without restriction, including without limitation
> + * the rights to use, copy, modify, merge, publish, distribute, sublicense,
> + * and/or sell copies of the Software, and to permit persons to whom the
> + * Software is furnished to do so, subject to the following conditions:
> + *
> + * The above copyright notice and this permission notice (including the next
> + * paragraph) shall be included in all copies or substantial portions of the
> + * Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
> + * IN THE SOFTWARE.
> + */
> +
> +#ifndef __IGT_SET_H__
> +#define __IGT_SET_H__
> +
> +/* Maximum set size we support, don't change unless you understand
> + * the implementation */
> +#define IGT_SET_MAXSIZE 16
igt_bitmap awaits. ;)
> +enum igt_set_iteration_algorithm {
> + IGT_SET_SUBSETS,
> + IGT_SET_COMBINATION,
> + IGT_SET_MULTICOMBINATION,
> +};
> +
> +struct igt_set_data {
> + int value;
> + void *ptr;
> +};
> +
> +struct igt_set {
> + int size;
> + struct igt_set_data set[IGT_SET_MAXSIZE];
> +};
> +
> +struct igt_set_iterator;
> +
> +struct igt_set *igt_set_init(int size);
> +void igt_set_free(struct igt_set *set);
> +void igt_set_setvalue(struct igt_set *set, int index, int value);
> +int igt_set_getvalue(struct igt_set *set, int index);
> +void igt_set_setptr(struct igt_set *set, int index, void *ptr);
> +void *igt_set_getptr(struct igt_set *set, int index);
> +
> +struct igt_set_iterator *igt_set_iterator_init(struct igt_set *set,
> + int subset_size,
> + enum igt_set_iteration_algorithm algorithm);
> +void igt_set_iterator_free(struct igt_set_iterator *iter);
> +struct igt_set *igt_set_iterate_next(struct igt_set_iterator *iter);
Bonus points for:
#define igt_collection_foreach_subset(it, set, size) \
for (struct igt_set_iteration *it = iter(set, size, SUBSET); iter_next(it); )
(igt_collection_foreach_combo, foreach_multicombo ?)
and definitely a igt_collection_foreach(key, value, set), we we can
write something like
igt_collection_foreach_subset(it, &myset, 4) {
igt_collection_foreach(key, value, it->set) {
}
}
igt_collection_foreach_combination(it, &myset, 4) {
igt_collection_foreach(key, value, it->set) {
}
}
And they definitely need a short description of their different
permutations.
-Chris
More information about the igt-dev
mailing list