diff options
author | Zbigniew Kempczyński <zbigniew.kempczynski@intel.com> | 2020-01-22 12:05:48 +0100 |
---|---|---|
committer | Petri Latvala <petri.latvala@intel.com> | 2020-01-23 10:49:13 +0200 |
commit | 93bc97385ae25b112c34b11748a2b55fbfb0e87b (patch) | |
tree | 3016e7e147ef8add2fe890c4b944749cd3f6a0ce /lib/igt_collection.c | |
parent | 1e6cb3e75925cf623df04f78430ae9299632ec3f (diff) |
lib/igt_collection: Adding combinatorics facility
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@intel.com>
Cc: Petri Latvala <petri.latvala@intel.com>
Cc: Chris Wilson <chris@chris-wilson.co.uk>
Acked-by: Petri Latvala <petri.latvala@intel.com>
Diffstat (limited to 'lib/igt_collection.c')
-rw-r--r-- | lib/igt_collection.c | 538 |
1 files changed, 538 insertions, 0 deletions
diff --git a/lib/igt_collection.c b/lib/igt_collection.c new file mode 100644 index 00000000..35e09c89 --- /dev/null +++ b/lib/igt_collection.c @@ -0,0 +1,538 @@ +/* + * 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. + */ + +#include "igt.h" +#include "igt_collection.h" + +/** + * SECTION:igt_collection + * @short_description: Generic combinatorics library + * @title: Collection + * @include: igt.h + * + * # Generic combinatorics library. + * + * Supports: + * - subsets + * - combinations + * - variations with repetitions + * - variations without repetitions + * + * ## 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 } + * + * ## 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. + * + * ## 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 ) + * + * ## 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: + * + * ## iterator is manually controlled: + * + * |[<!-- language="C" --> + * 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); + * ]| + * + * ## iterator is created and destroyed inside helper macros: + * |[<!-- language="C" --> + * 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); + * ]| + */ + +struct igt_collection_iter { + const struct igt_collection *set; + enum igt_collection_iter_algo algorithm; + bool init; + int result_size; + struct igt_collection result; + + /* Algorithms state */ + struct { + uint32_t result_bits; + int current_result_size; + int idxs[IGT_COLLECTION_MAXSIZE]; + } data; +}; + +/** + * igt_collection_create + * @size: size of the collection, must be greater than 0 and less + * than #IGT_COLLECTION_MAXSIZE + * + * Function creates a collection (set) containing igt_collection_data elements. + * + * Returns: + * pointer to #igt_collection. Asserts on memory allocation failure. + */ +struct igt_collection *igt_collection_create(int size) +{ + struct igt_collection *set; + int i; + + igt_assert(size > 0 && size <= IGT_COLLECTION_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; +} + +/** + * igt_collection_duplicate + * @src: source collection + * + * Function duplicates collection. Useful to cover multithreading + * when different threads need to get it's own copy of the collection + * acquired during iteration. + * + * Returns: + * pointer to #igt_collection. Asserts on memory allocation failure. + */ +struct igt_collection * +igt_collection_duplicate(const struct igt_collection *src) +{ + struct igt_collection *set = malloc(sizeof(*set)); + + igt_assert(set); + memcpy(set, src, sizeof(*set)); + + return set; +} + +/** + * igt_collection_destroy + * @set: collection to be freed + * + * Function frees collection memory. + */ +void igt_collection_destroy(struct igt_collection *set) +{ + free(set); +} + +/** + * igt_collection_set_value + * @set: collection + * @index: index of value data to be set in the collection + * @value: new value + * + * Assign new value to the collection element at @index. + */ +void igt_collection_set_value(struct igt_collection *set, int index, int value) +{ + igt_assert(index >= 0 && index < set->size); + set->set[index].value = value; +} + +/** + * igt_collection_get_value + * @set: collection + * @index: index of value data to be get from the collection + * + * Returns: integer value at from the collection element at @index. + */ +int igt_collection_get_value(struct igt_collection *set, int index) +{ + igt_assert(index >= 0 && index < set->size); + return set->set[index].value; +} + +/** + * igt_collection_set_pointer + * @set: collection + * @index: index of pointer data to be set in the collection + * @ptr: new pointer + */ +void igt_collection_set_pointer(struct igt_collection *set, int index, void *ptr) +{ + igt_assert(index >= 0 && index < set->size); + set->set[index].ptr = ptr; +} + +/** + * igt_collection_get_pointer + * @set: collection + * @index: index of pointer data to be get from the collection + * + * Returns: pointer from the collection element at @index. + */ +void *igt_collection_get_pointer(struct igt_collection *set, int index) +{ + igt_assert(index >= 0 && index < set->size); + return set->set[index].ptr; +} + +/** + * igt_collection_iter_create + * @set: base collection + * @result_size: result collection size + * @algorithm: method of iterating over base collection + * + * Function creates iterator which contains result collection changed each time + * igt_collection_iter_next() is called. For variations without repetitions + * (VARIATION_R) result collection size can be larger than size of + * base collection (although still less or equal #IGT_COLLECTION_MAXSIZE). + * As result collection is a part of the iterator to be thread-safe + * igt_collection_duplicate() must be called to make result collection copy + * before passing it to the thread. + * + * Returns: + * pointer to #igt_collection_iter. Asserts on memory allocation failure. + */ +struct igt_collection_iter * +igt_collection_iter_create(const struct igt_collection *set, int result_size, + enum igt_collection_iter_algo algorithm) +{ + struct igt_collection_iter *iter; + + igt_assert(result_size > 0 && result_size <= IGT_COLLECTION_MAXSIZE); + if (algorithm != VARIATION_R) + 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; +} + +/** + * igt_collection_iter_destroy + * @iter: iterator to be freed + * + * Function frees iterator memory. + */ +void igt_collection_iter_destroy(struct igt_collection_iter *iter) +{ + free(iter); +} + +static struct igt_collection * +igt_collection_iter_subsets(struct igt_collection_iter *iter) +{ + const struct igt_collection *set = iter->set; + struct igt_collection *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 (igt_hweight(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_collection * +igt_collection_iter_combination(struct igt_collection_iter *iter) +{ + const struct igt_collection *set = iter->set; + struct igt_collection *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 (igt_hweight(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_collection * +igt_collection_iter_variation_r(struct igt_collection_iter *iter) +{ + const struct igt_collection *set = iter->set; + struct igt_collection *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; +} + +static struct igt_collection * +igt_collection_iter_variation_nr(struct igt_collection_iter *iter) +{ + const struct igt_collection *set = iter->set; + struct igt_collection *curr = &iter->result; + bool in_use[IGT_COLLECTION_MAXSIZE]; + bool skip; + 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; + } + + /* + * Simple naive algorithm checking does element index is already + * occupied. + */ +retry: + skip = false; + + 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]]; + + memset(in_use, 0, sizeof(in_use)); + for (i = 0; i < iter->result_size; i++) { + if (in_use[iter->data.idxs[i]]) { + skip = true; + break; + } + in_use[iter->data.idxs[i]] = true; + } + + 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; + } + } + + if (skip) + goto retry; + + return curr; +} + +/** + * igt_collection_iter_next + * @iter: collection iterator + * + * Function iterates over collection regarding to algorithm selected during + * iterator creation returning collection (subset or tuples (for variations)). + * + * Returns: pointer to the collection (it is a part of the iterator memory + * so to be thread-safe it must be duplicated by the caller when + * necessary) or NULL when there're no more elements. Iterator is no longer + * valid and must be then freed with igt_collection_iter_destroy(). + */ +struct igt_collection * +igt_collection_iter_next(struct igt_collection_iter *iter) +{ + struct igt_collection *ret_set = NULL; + + switch(iter->algorithm) { + case SUBSET: + ret_set = igt_collection_iter_subsets(iter); + break; + case COMBINATION: + ret_set = igt_collection_iter_combination(iter); + break; + case VARIATION_R: + ret_set = igt_collection_iter_variation_r(iter); + break; + case VARIATION_NR: + ret_set = igt_collection_iter_variation_nr(iter); + break; + default: + igt_assert_f(false, "Unknown algorithm\n"); + } + + return ret_set; +} + +/** + * igt_collection_iter_next_or_end + * @iter: collection iterator + * + * Function does the same as igt_collection_iter_next() but additionally + * checks when the iterator is no longer valid and frees it then. + * Useful for for_each_* macros to avoid necessity of manual handling + * the iterator. + */ +struct igt_collection * +igt_collection_iter_next_or_end(struct igt_collection_iter *iter) +{ + struct igt_collection *ret_set = + igt_collection_iter_next(iter); + + if (!ret_set) + igt_collection_iter_destroy(iter); + + return ret_set; +} |