[Mesa-dev] [PATCH] util/tests/rb_tree: add unit test
Lionel Landwerlin
lionel.g.landwerlin at intel.com
Thu Jul 5 11:00:15 UTC 2018
Test written by Jason :
https://github.com/jekstrand/rb-tree
Signed-off-by: Lionel Landwerlin <lionel.g.landwerlin at intel.com>
---
src/util/Makefile.am | 1 +
src/util/meson.build | 1 +
src/util/tests/rb_tree/Makefile.am | 39 ++++++
src/util/tests/rb_tree/meson.build | 29 ++++
src/util/tests/rb_tree/rb_tree_test.c | 184 ++++++++++++++++++++++++++
5 files changed, 254 insertions(+)
create mode 100644 src/util/tests/rb_tree/Makefile.am
create mode 100644 src/util/tests/rb_tree/meson.build
create mode 100644 src/util/tests/rb_tree/rb_tree_test.c
diff --git a/src/util/Makefile.am b/src/util/Makefile.am
index 65794338c5b..b4182219f1d 100644
--- a/src/util/Makefile.am
+++ b/src/util/Makefile.am
@@ -22,6 +22,7 @@
SUBDIRS = . \
xmlpool \
tests/hash_table \
+ tests/rb_tree \
tests/string_buffer
if HAVE_STD_CXX11
diff --git a/src/util/meson.build b/src/util/meson.build
index 1838719d271..d45478ffe2b 100644
--- a/src/util/meson.build
+++ b/src/util/meson.build
@@ -162,6 +162,7 @@ if with_tests
)
subdir('tests/hash_table')
+ subdir('tests/rb_tree')
subdir('tests/string_buffer')
subdir('tests/vma')
endif
diff --git a/src/util/tests/rb_tree/Makefile.am b/src/util/tests/rb_tree/Makefile.am
new file mode 100644
index 00000000000..6c10806c495
--- /dev/null
+++ b/src/util/tests/rb_tree/Makefile.am
@@ -0,0 +1,39 @@
+# Copyright © 2018 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.
+
+AM_CPPFLAGS = \
+ -I$(top_srcdir)/include \
+ -I$(top_srcdir)/src/util \
+ $(DEFINES)
+
+TESTS = rb_tree_random_test
+
+check_PROGRAMS = $(TESTS)
+
+vma_random_test_SOURCES = \
+ rb_tree_test.c
+
+vma_random_test_LDADD = \
+ $(top_builddir)/src/util/libmesautil.la
+
+vma_random_test_CXXFLAGS = $(CXX11_CXXFLAGS)
+
+EXTRA_DIST = meson.build
diff --git a/src/util/tests/rb_tree/meson.build b/src/util/tests/rb_tree/meson.build
new file mode 100644
index 00000000000..3b4e4c7449f
--- /dev/null
+++ b/src/util/tests/rb_tree/meson.build
@@ -0,0 +1,29 @@
+# Copyright © 2018 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 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.
+
+test(
+ 'rb_tree',
+ executable(
+ 'rb_tree_test',
+ 'rb_tree_test.c',
+ include_directories : [inc_include, inc_util],
+ link_with : [libmesa_util],
+ )
+)
diff --git a/src/util/tests/rb_tree/rb_tree_test.c b/src/util/tests/rb_tree/rb_tree_test.c
new file mode 100644
index 00000000000..db247958918
--- /dev/null
+++ b/src/util/tests/rb_tree/rb_tree_test.c
@@ -0,0 +1,184 @@
+/*
+ * Copyright © 2017 Jason Ekstrand
+ *
+ * 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 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 "rb_tree.h"
+
+#include <assert.h>
+#include <limits.h>
+
+#include "macros.h"
+
+/* A list of 100 random numbers from 1 to 100. The number 30 is explicitly
+ * missing from this list.
+ */
+unsigned test_numbers[] = {
+ 26, 12, 35, 15, 48, 11, 39, 23, 40, 18,
+ 39, 15, 40, 11, 42, 2, 5, 2, 28, 8,
+ 10, 22, 23, 38, 47, 12, 31, 22, 26, 39,
+ 9, 42, 32, 18, 36, 8, 32, 29, 9, 3,
+ 32, 49, 23, 11, 43, 41, 22, 42, 6, 35,
+ 38, 48, 5, 35, 39, 44, 22, 16, 16, 32,
+ 31, 50, 48, 5, 50, 8, 2, 32, 27, 34,
+ 42, 48, 22, 47, 10, 48, 39, 36, 28, 40,
+ 32, 33, 21, 17, 14, 38, 27, 6, 25, 18,
+ 32, 38, 19, 22, 20, 47, 50, 41, 29, 50,
+};
+
+#define NON_EXISTANT_NUMBER 30
+
+struct rb_test_node {
+ unsigned key;
+ struct rb_node node;
+};
+
+static int
+rb_test_node_cmp_void(const struct rb_node *n, const void *v)
+{
+ struct rb_test_node *tn = rb_node_data(struct rb_test_node, n, node);
+ return tn->key - *(unsigned *)v;
+}
+
+static int
+rb_test_node_cmp(const struct rb_node *a, const struct rb_node *b)
+{
+ struct rb_test_node *ta = rb_node_data(struct rb_test_node, a, node);
+ struct rb_test_node *tb = rb_node_data(struct rb_test_node, b, node);
+
+ return ta->key - tb->key;
+}
+
+static void
+validate_tree_order(struct rb_tree *tree, unsigned expected_count)
+{
+ struct rb_test_node *prev = NULL;
+ unsigned max_val = 0;
+ unsigned count = 0;
+ rb_tree_foreach(struct rb_test_node, n, tree, node) {
+ /* Everything should be in increasing order */
+ assert(n->key >= max_val);
+ if (n->key > max_val) {
+ max_val = n->key;
+ } else {
+ /* Things should be stable, i.e., given equal keys, they should
+ * show up in the list in order of insertion. We insert them
+ * in the order they are in in the array.
+ */
+ if (prev == NULL || prev < n);
+ }
+
+ prev = n;
+ count++;
+ }
+ assert(count == expected_count);
+
+ prev = NULL;
+ unsigned min_val = UINT_MAX;
+ count = 0;
+ rb_tree_foreach_rev(struct rb_test_node, n, tree, node) {
+ /* Everything should be in increasing order */
+ assert(n->key <= min_val);
+ if (n->key < min_val) {
+ min_val = n->key;
+ } else {
+ /* Things should be stable, i.e., given equal keys, they should
+ * show up in the list in order of insertion. We insert them
+ * in the order they are in in the array.
+ */
+ if (prev == NULL || prev > n);
+ }
+
+ prev = n;
+ count++;
+ }
+ assert(count == expected_count);
+}
+
+static void
+validate_search(struct rb_tree *tree, unsigned first_number,
+ unsigned last_number)
+{
+ struct rb_node *n;
+ struct rb_test_node *tn;
+
+ /* Search for all of the values */
+ for (unsigned i = first_number; i <= last_number; i++) {
+ n = rb_tree_search(tree, &test_numbers[i], rb_test_node_cmp_void);
+ tn = rb_node_data(struct rb_test_node, n, node);
+ assert(tn->key == test_numbers[i]);
+
+ n = rb_tree_search_sloppy(tree, &test_numbers[i],
+ rb_test_node_cmp_void);
+ tn = rb_node_data(struct rb_test_node, n, node);
+ assert(tn->key == test_numbers[i]);
+ }
+
+ unsigned missing_key = NON_EXISTANT_NUMBER;
+ n = rb_tree_search(tree, &missing_key, rb_test_node_cmp_void);
+ assert(n == NULL);
+
+ n = rb_tree_search_sloppy(tree, &missing_key, rb_test_node_cmp_void);
+ if (rb_tree_is_empty(tree)) {
+ assert(n == NULL);
+ } else {
+ assert(n != NULL);
+ tn = rb_node_data(struct rb_test_node, n, node);
+ assert(tn->key != missing_key);
+ if (tn->key < missing_key) {
+ struct rb_node *next = rb_node_next(n);
+ if (next != NULL) {
+ struct rb_test_node *tnext =
+ rb_node_data(struct rb_test_node, next, node);
+ assert(missing_key < tnext->key);
+ }
+ } else {
+ struct rb_node *prev = rb_node_prev(n);
+ if (prev != NULL) {
+ struct rb_test_node *tprev =
+ rb_node_data(struct rb_test_node, prev, node);
+ assert(missing_key > tprev->key);
+ }
+ }
+ }
+}
+
+int main()
+{
+ struct rb_test_node nodes[ARRAY_SIZE(test_numbers)];
+ struct rb_tree tree;
+
+ rb_tree_init(&tree);
+
+ for (unsigned i = 0; i < ARRAY_SIZE(test_numbers); i++) {
+ nodes[i].key = test_numbers[i];
+ rb_tree_insert(&tree, &nodes[i].node, rb_test_node_cmp);
+ rb_tree_validate(&tree);
+ validate_tree_order(&tree, i + 1);
+ validate_search(&tree, 0, i);
+ }
+
+ for (unsigned i = 0; i < ARRAY_SIZE(test_numbers); i++) {
+ rb_tree_remove(&tree, &nodes[i].node);
+ rb_tree_validate(&tree);
+ validate_tree_order(&tree, ARRAY_SIZE(test_numbers) - i - 1);
+ validate_search(&tree, i + 1, ARRAY_SIZE(test_numbers) - 1);
+ }
+}
--
2.18.0
More information about the mesa-dev
mailing list