[igt-dev] [PATCH i-g-t v2] lib/igt_collection: Adding combinatorics facility
Zbigniew Kempczyński
zbigniew.kempczynski at intel.com
Mon Jan 20 11:42:52 UTC 2020
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 | 412 +++++++++++++++++++++++++++++++++++++++++++
lib/igt_collection.h | 93 ++++++++++
lib/meson.build | 1 +
4 files changed, 508 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..22d6365e
--- /dev/null
+++ b/lib/igt_collection.c
@@ -0,0 +1,412 @@
+#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, false))) {
+ * // --- 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;
+ *
+ * igt_collection_foreach_subset(set, subset_size, subset)
+ * // --- do sth with subset ---
+ *
+ * igt_collection_foreach_combo(set, subset_size, subset)
+ * // --- do sth with subset ---
+ *
+ * igt_collection_foreach_variation_r(set, result_size, result)
+ * // --- do sth with result ---
+ *
+ * igt_collection_foreach_variation_nr(set, result_size, result)
+ * // --- do sth with result ---
+ *
+ * // macro for iteration over set data - igt_collection_foreach()
+ * igt_collection_foreach_subset(set, subset_size, subset)
+ * igt_collection_foreach(subset, data)
+ * printf("v: %d, p: %p\n", data->value, data->ptr);
+ */
+
+#if defined(__GNUC__)
+#define NUM_BITS(v) __builtin_popcount(v)
+#else
+/* Taken from Hacker's Delight, for non-gcc compiler */
+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;
+}
+#define NUM_BITS(v) num_bits_set(v)
+#endif
+
+struct igt_collection_iter {
+ struct igt_collection *set;
+ enum igt_collection_iter_algo algorithm;
+ bool init;
+ int result_size;
+ struct igt_collection result;
+
+ /* Algorithms state, to be used by iterators */
+ struct {
+ uint32_t result_bits;
+ int current_result_size;
+ int idxs[IGT_COLLECTION_MAXSIZE];
+ } data;
+};
+
+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;
+}
+
+void igt_collection_destroy(struct igt_collection *set)
+{
+ free(set);
+}
+
+void igt_collection_set_value(struct igt_collection *set, int index, int value)
+{
+ set->set[index].value = value;
+}
+
+int igt_collection_get_value(struct igt_collection *set, int index)
+{
+ return set->set[index].value;
+}
+
+void igt_collection_set_pointer(struct igt_collection *set, int index, void *ptr)
+{
+ set->set[index].ptr = ptr;
+}
+
+void *igt_collection_get_pointer(struct igt_collection *set, int index)
+{
+ return set->set[index].ptr;
+}
+
+struct igt_collection_iter *
+igt_collection_iter_create(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;
+}
+
+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)
+{
+ 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 (NUM_BITS(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)
+{
+ 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 (NUM_BITS(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)
+{
+ 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)
+{
+ 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;
+}
+
+struct igt_collection *igt_collection_iter_next(struct igt_collection_iter *iter,
+ bool automatic_free)
+{
+ 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");
+ }
+
+ /*
+ * Note: when iterator goes to the end this implicitly destroys
+ * memory it contains so it is not valid anymore. This ugly implicit
+ * memory free is reguired to do some foreach_... trick without
+ * necessity to keep it's reference and free when it goes to
+ * the end.
+ */
+ if (!ret_set && automatic_free) {
+ igt_debug("Freeing iterator [%p]\n", iter);
+ igt_collection_iter_destroy(iter);
+ }
+
+ return ret_set;
+}
diff --git a/lib/igt_collection.h b/lib/igt_collection.h
new file mode 100644
index 00000000..970bbd93
--- /dev/null
+++ b/lib/igt_collection.h
@@ -0,0 +1,93 @@
+/*
+ * 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_COLLECTION_H__
+#define __IGT_COLLECTION_H__
+
+#include <stdbool.h>
+
+/* Maximum collection size we support, don't change unless you understand
+ * the implementation */
+#define IGT_COLLECTION_MAXSIZE 16
+
+enum igt_collection_iter_algo {
+ SUBSET,
+ COMBINATION,
+ VARIATION_R, /* variations with repetition */
+ VARIATION_NR, /* variations without repetitions */
+};
+
+struct igt_collection_data {
+ int value;
+ void *ptr;
+};
+
+struct igt_collection {
+ int size;
+ struct igt_collection_data set[IGT_COLLECTION_MAXSIZE];
+};
+
+struct igt_collection_iter;
+
+struct igt_collection *igt_collection_create(int size);
+void igt_collection_destroy(struct igt_collection *set);
+void igt_collection_set_value(struct igt_collection *set, int index, int value);
+int igt_collection_get_value(struct igt_collection *set, int index);
+void igt_collection_set_pointer(struct igt_collection *set, int index, void *ptr);
+void *igt_collection_get_pointer(struct igt_collection *set, int index);
+
+struct igt_collection_iter *
+igt_collection_iter_create(struct igt_collection *set, int subset_size,
+ enum igt_collection_iter_algo algorithm);
+
+void igt_collection_iter_destroy(struct igt_collection_iter *iter);
+struct igt_collection *igt_collection_iter_next(struct igt_collection_iter *iter,
+ bool automatic_free);
+
+#define igt_collection_foreach_subset(__set, __size, __result) \
+ for (struct igt_collection_iter *igt_tokencat(__it, __LINE__) = \
+ igt_collection_iter_create(__set, __size, SUBSET); \
+ ((__result) = igt_collection_iter_next(igt_tokencat(__it, __LINE__), true)); )
+
+#define igt_collection_foreach_combo(__set, __size, __result) \
+ for (struct igt_collection_iter *igt_tokencat(__it, __LINE__) = \
+ igt_collection_iter_create(__set, __size, COMBINATION); \
+ ((__result) = igt_collection_iter_next(igt_tokencat(__it, __LINE__), true)); )
+
+#define igt_collection_foreach_variation_r(__set, __size, __result) \
+ for (struct igt_collection_iter *igt_tokencat(__it, __LINE__) = \
+ igt_collection_iter_create(__set, __size, VARIATION_R); \
+ ((__result) = igt_collection_iter_next(igt_tokencat(__it, __LINE__), true)); )
+
+#define igt_collection_foreach_variation_nr(__set, __size, __result) \
+ for (struct igt_collection_iter *igt_tokencat(__it, __LINE__) = \
+ igt_collection_iter_create(__set, __size, VARIATION_NR); \
+ ((__result) = igt_collection_iter_next(igt_tokencat(__it, __LINE__), true)); )
+
+#define igt_collection_foreach(__set, __data) \
+ for (int igt_tokencat(__i, __LINE__) = 0; \
+ (__data = (igt_tokencat(__i, __LINE__) < __set->size) ? \
+ &__set->set[igt_tokencat(__i, __LINE__)] : NULL); \
+ igt_tokencat(__i, __LINE__)++)
+
+#endif /* __IGT_COLLECTION_H__ */
diff --git a/lib/meson.build b/lib/meson.build
index 3bf39915..d8754618 100644
--- a/lib/meson.build
+++ b/lib/meson.build
@@ -7,6 +7,7 @@ lib_sources = [
'i915/gem_ring.c',
'i915/gem_mman.c',
'i915/gem_vm.c',
+ 'igt_collection.c',
'igt_color_encoding.c',
'igt_debugfs.c',
'igt_device.c',
--
2.23.0
More information about the igt-dev
mailing list