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.landwer...@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@lists.freedesktop.org > https://lists.freedesktop.org/mailman/listinfo/mesa-dev _______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/mesa-dev