>From e48252d834bd28a491b8a007c962298fd4d0e716 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Mon, 10 Dec 2018 01:18:44 +0100 Subject: [PATCH 8/8] rbtree-omap: Add tests. * tests/test-rbtree_omap.c: New file. * modules/rbtree-omap-tests: New file. --- ChangeLog | 4 ++ modules/rbtree-omap-tests | 12 ++++ tests/test-rbtree_omap.c | 138 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 154 insertions(+) create mode 100644 modules/rbtree-omap-tests create mode 100644 tests/test-rbtree_omap.c diff --git a/ChangeLog b/ChangeLog index 9208907..a2da126 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,9 @@ 2018-12-09 Bruno Haible + rbtree-omap: Add tests. + * tests/test-rbtree_omap.c: New file. + * modules/rbtree-omap-tests: New file. + avltree-omap: Add tests. * tests/test-avltree_omap.c: New file. * modules/avltree-omap-tests: New file. diff --git a/modules/rbtree-omap-tests b/modules/rbtree-omap-tests new file mode 100644 index 0000000..8a03a2f --- /dev/null +++ b/modules/rbtree-omap-tests @@ -0,0 +1,12 @@ +Files: +tests/test-rbtree_omap.c +tests/macros.h + +Depends-on: +array-omap + +configure.ac: + +Makefile.am: +TESTS += test-rbtree_omap +check_PROGRAMS += test-rbtree_omap diff --git a/tests/test-rbtree_omap.c b/tests/test-rbtree_omap.c new file mode 100644 index 0000000..45e799f --- /dev/null +++ b/tests/test-rbtree_omap.c @@ -0,0 +1,138 @@ +/* Test of ordered map data type implementation. + Copyright (C) 2006-2018 Free Software Foundation, Inc. + Written by Bruno Haible , 2018. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . */ + +#include + +#include "gl_rbtree_omap.h" + +#include +#include + +#include "gl_array_omap.h" +#include "macros.h" + +extern void gl_rbtree_omap_check_invariants (gl_omap_t set); + +static const char *objects[30] = + { + "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", + "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "<", ">", "[", "]" + }; + +#define RANDOM(n) (rand () % (n)) +#define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))] + +static void +check_equals (gl_omap_t map1, gl_omap_t map2) +{ + size_t n = gl_omap_size (map1); + gl_omap_iterator_t iter1, iter2; + const void *key1; + const void *value1; + const void *key2; + const void *value2; + size_t i; + + iter1 = gl_omap_iterator (map1); + iter2 = gl_omap_iterator (map2); + for (i = 0; i < n; i++) + { + ASSERT (gl_omap_iterator_next (&iter1, &key1, &value1)); + ASSERT (gl_omap_iterator_next (&iter2, &key2, &value2)); + ASSERT (key1 == key2); + ASSERT (value1 == value2); + } + ASSERT (!gl_omap_iterator_next (&iter1, &key1, &value1)); + ASSERT (!gl_omap_iterator_next (&iter2, &key2, &value2)); + gl_omap_iterator_free (&iter1); + gl_omap_iterator_free (&iter2); +} + +static void +check_all (gl_omap_t map1, gl_omap_t map2) +{ + gl_rbtree_omap_check_invariants (map2); + check_equals (map1, map2); +} + +int +main (int argc, char *argv[]) +{ + gl_omap_t map1, map2; + + /* Allow the user to provide a non-default random seed on the command line. */ + if (argc > 1) + srand (atoi (argv[1])); + + { + size_t initial_size = RANDOM (20); + size_t i; + unsigned int repeat; + + /* Create map1. */ + map1 = gl_omap_nx_create_empty (GL_ARRAY_OMAP, (gl_mapkey_compar_fn) strcmp, NULL, NULL); + ASSERT (map1 != NULL); + + /* Create map2. */ + map2 = gl_omap_nx_create_empty (GL_RBTREE_OMAP, (gl_mapkey_compar_fn) strcmp, NULL, NULL); + ASSERT (map2 != NULL); + + check_all (map1, map2); + + /* Initialize them. */ + for (i = 0; i < initial_size; i++) + { + const char *key = RANDOM_OBJECT (); + const char *value = RANDOM_OBJECT (); + ASSERT (gl_omap_nx_put (map1, key, value) == gl_omap_nx_put (map2, key, value)); + check_all (map1, map2); + } + + for (repeat = 0; repeat < 100000; repeat++) + { + unsigned int operation = RANDOM (3); + switch (operation) + { + case 0: + { + const char *key = RANDOM_OBJECT (); + ASSERT (gl_omap_get (map1, key) == gl_omap_get (map2, key)); + } + break; + case 1: + { + const char *key = RANDOM_OBJECT (); + const char *value = RANDOM_OBJECT (); + ASSERT (gl_omap_nx_put (map1, key, value) == gl_omap_nx_put (map2, key, value)); + } + break; + case 2: + { + const char *key = RANDOM_OBJECT (); + ASSERT (gl_omap_remove (map1, key) == gl_omap_remove (map2, key)); + } + break; + } + check_all (map1, map2); + } + + gl_omap_free (map1); + gl_omap_free (map2); + } + + return 0; +} -- 2.7.4