[Mesa-dev] [PATCH] util/tests/rb_tree: add unit test
Eric Engestrom
eric.engestrom at intel.com
Thu Jul 5 11:28:05 UTC 2018
On Thursday, 2018-07-05 12:00:15 +0100, Lionel Landwerlin wrote:
> 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)
Looks like a copy/paste mistake; s/vma_random_test/rb_tree_random_test/g
> +
> +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);
> + }
+ return EXIT_SUCCESS;
This test will also not test anything if built with NDEBUG; how about
this at the top?
#ifdef NDEBUG
#define assert(cond) do { if (!cond) exit(EXIT_FAILURE); } while(0)
#endif
> +}
> --
> 2.18.0
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
More information about the mesa-dev
mailing list