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

* [igt-dev] [PATCH i-g-t] lib/igt_set: Adding combinatorics facility
@ 2020-01-17  7:54 Zbigniew Kempczyński
  2020-01-17  8:46 ` [igt-dev] ✓ Fi.CI.BAT: success for " Patchwork
                   ` (3 more replies)
  0 siblings, 4 replies; 6+ messages in thread
From: Zbigniew Kempczyński @ 2020-01-17  7:54 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_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@intel.com>
Cc: Petri Latvala <petri.latvala@intel.com>
Cc: Chris Wilson <chris@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);
+ * }
+ *
+ * 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;
+}
+
+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
+
+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);
+
+#endif /* __IGT_SET_H__ */
diff --git a/lib/meson.build b/lib/meson.build
index 57eb7d93..98806914 100644
--- a/lib/meson.build
+++ b/lib/meson.build
@@ -19,6 +19,7 @@ lib_sources = [
 	'igt_primes.c',
 	'igt_rand.c',
 	'igt_rapl.c',
+	'igt_set.c',
 	'igt_stats.c',
 	'igt_syncobj.c',
 	'igt_sysfs.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] 6+ messages in thread