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

* [igt-dev] [PATCH i-g-t v4] lib/igt_collection: Adding combinatorics facility
@ 2020-01-21 16:10 Zbigniew Kempczyński
  2020-01-21 16:52 ` [igt-dev] ✓ Fi.CI.BAT: success for lib/igt_collection: Adding combinatorics facility (rev3) Patchwork
                   ` (2 more replies)
  0 siblings, 3 replies; 4+ messages in thread
From: Zbigniew Kempczyński @ 2020-01-21 16:10 UTC (permalink / raw)
  To: igt-dev; +Cc: Petri Latvala

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>
---
 .../igt-gpu-tools/igt-gpu-tools-docs.xml      |   1 +
 lib/Makefile.sources                          |   2 +
 lib/igt_collection.c                          | 515 ++++++++++++++++++
 lib/igt_collection.h                          |  99 ++++
 lib/meson.build                               |   1 +
 5 files changed, 618 insertions(+)
 create mode 100644 lib/igt_collection.c
 create mode 100644 lib/igt_collection.h

diff --git a/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml b/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml
index aa9fef20..9c9aa8f1 100644
--- a/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml
+++ b/docs/reference/igt-gpu-tools/igt-gpu-tools-docs.xml
@@ -20,6 +20,7 @@
     <xi:include href="xml/igt_audio.xml"/>
     <xi:include href="xml/igt_aux.xml"/>
     <xi:include href="xml/igt_chamelium.xml"/>
+    <xi:include href="xml/igt_collection.xml"/>
     <xi:include href="xml/igt_core.xml"/>
     <xi:include href="xml/igt_debugfs.xml"/>
     <xi:include href="xml/igt_device.xml"/>
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..c3e585c7
--- /dev/null
+++ b/lib/igt_collection.c
@@ -0,0 +1,515 @@
+#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;
+}
diff --git a/lib/igt_collection.h b/lib/igt_collection.h
new file mode 100644
index 00000000..5da661f8
--- /dev/null
+++ b/lib/igt_collection.h
@@ -0,0 +1,99 @@
+/*
+ * 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);
+struct igt_collection *igt_collection_duplicate(const struct igt_collection *src);
+
+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(const 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);
+struct igt_collection *igt_collection_iter_next_or_end(struct igt_collection_iter *iter);
+
+#define for_each_subset(__result, __size, __set) \
+	for (struct igt_collection_iter *igt_tokencat(__it, __LINE__) = \
+		igt_collection_iter_create(__set, __size, SUBSET); \
+		((__result) = igt_collection_iter_next_or_end(\
+			igt_tokencat(__it, __LINE__))); )
+
+#define for_each_combination(__result, __size, __set) \
+	for (struct igt_collection_iter *igt_tokencat(__it, __LINE__) = \
+		igt_collection_iter_create(__set, __size, COMBINATION); \
+		((__result) = igt_collection_iter_next_or_end(\
+			igt_tokencat(__it, __LINE__))); )
+
+#define for_each_variation_r(__result, __size, __set) \
+	for (struct igt_collection_iter *igt_tokencat(__it, __LINE__) = \
+		igt_collection_iter_create(__set, __size, VARIATION_R); \
+		((__result) = igt_collection_iter_next_or_end(\
+			igt_tokencat(__it, __LINE__))); )
+
+#define for_each_variation_nr(__result, __size, __set) \
+	for (struct igt_collection_iter *igt_tokencat(__it, __LINE__) = \
+		igt_collection_iter_create(__set, __size, VARIATION_NR); \
+		((__result) = igt_collection_iter_next_or_end(\
+			igt_tokencat(__it, __LINE__))); )
+
+#define for_each_collection_data(__data, __set) \
+	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

_______________________________________________
igt-dev mailing list
igt-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/igt-dev

^ permalink raw reply related	[flat|nested] 4+ messages in thread