Mercurial > gnulib

annotate tests/test-avltree_oset.c @ 40196:e63f5d3edab5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
relocatable-prog: Update documentation. * doc/relocatable-maint.texi (Supporting Relocation): Update to match the recent changes.
author Bruno Haible <bruno@clisp.org>
date Sun, 24 Feb 2019 01:49:15 +0100
parents b06060465f09
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6982
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
1 /* Test of ordered set data type implementation.
40057
b06060465f09 maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents: 19484
diff changeset
2 Copyright (C) 2006-2019 Free Software Foundation, Inc.
6982
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
4
9309
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 8891
diff changeset
5 This program is free software: you can redistribute it and/or modify
6982
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
6 it under the terms of the GNU General Public License as published by
9309
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 8891
diff changeset
7 the Free Software Foundation; either version 3 of the License, or
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 8891
diff changeset
8 (at your option) any later version.
6982
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
9
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
10 This program is distributed in the hope that it will be useful,
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
13 GNU General Public License for more details.
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
14
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
15 You should have received a copy of the GNU General Public License
19190
9759915b2aca all: prefer https: URLs
Paul Eggert <eggert@cs.ucla.edu>
parents: 18626
diff changeset
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
6982
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
17
8891
633babea5f62 Unconditionally include <config.h> in unit tests.
Eric Blake <ebb9@byu.net>
parents: 8754
diff changeset
18 #include <config.h>
6982
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
19
8289
a24f55137420 Avoid link error due to program_name.
Bruno Haible <bruno@clisp.org>
parents: 6982
diff changeset
20 #include "gl_avltree_oset.h"
a24f55137420 Avoid link error due to program_name.
Bruno Haible <bruno@clisp.org>
parents: 6982
diff changeset
21
6982
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
22 #include <stdlib.h>
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
23 #include <string.h>
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
24
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
25 #include "gl_array_oset.h"
12496
a48d3d749ca5 Refactor common macros used in tests.
Bruno Haible <bruno@clisp.org>
parents: 12444
diff changeset
26 #include "macros.h"
6982
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
27
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
28 extern void gl_avltree_oset_check_invariants (gl_oset_t set);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
29
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
30 static const char *objects[30] =
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
31 {
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
32 "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o",
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
33 "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "<", ">", "[", "]"
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
34 };
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
35
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
36 #define RANDOM(n) (rand () % (n))
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
37 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
38
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
39 static void
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
40 check_equals (gl_oset_t set1, gl_oset_t set2)
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
41 {
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
42 size_t n = gl_oset_size (set1);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
43 gl_oset_iterator_t iter1, iter2;
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
44 const void *elt1;
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
45 const void *elt2;
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
46 size_t i;
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
47
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
48 iter1 = gl_oset_iterator (set1);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
49 iter2 = gl_oset_iterator (set2);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
50 for (i = 0; i < n; i++)
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
51 {
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
52 ASSERT (gl_oset_iterator_next (&iter1, &elt1));
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
53 ASSERT (gl_oset_iterator_next (&iter2, &elt2));
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
54 ASSERT (elt1 == elt2);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
55 }
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
56 ASSERT (!gl_oset_iterator_next (&iter1, &elt1));
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
57 ASSERT (!gl_oset_iterator_next (&iter2, &elt2));
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
58 gl_oset_iterator_free (&iter1);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
59 gl_oset_iterator_free (&iter2);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
60 }
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
61
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
62 static void
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
63 check_all (gl_oset_t set1, gl_oset_t set2)
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
64 {
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
65 gl_avltree_oset_check_invariants (set2);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
66 check_equals (set1, set2);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
67 }
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
68
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
69 int
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
70 main (int argc, char *argv[])
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
71 {
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
72 gl_oset_t set1, set2;
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
73
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
74 /* Allow the user to provide a non-default random seed on the command line. */
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
75 if (argc > 1)
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
76 srand (atoi (argv[1]));
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
77
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
78 {
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
79 size_t initial_size = RANDOM (20);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
80 size_t i;
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
81 unsigned int repeat;
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
82
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
83 /* Create set1. */
12444
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
84 set1 = gl_oset_nx_create_empty (GL_ARRAY_OSET, (gl_setelement_compar_fn) strcmp, NULL);
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
85 ASSERT (set1 != NULL);
6982
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
86
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
87 /* Create set2. */
12444
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
88 set2 = gl_oset_nx_create_empty (GL_AVLTREE_OSET, (gl_setelement_compar_fn) strcmp, NULL);
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
89 ASSERT (set2 != NULL);
6982
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
90
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
91 check_all (set1, set2);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
92
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
93 /* Initialize them. */
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
94 for (i = 0; i < initial_size; i++)
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
95 {
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
96 const char *obj = RANDOM_OBJECT ();
12444
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
97 ASSERT (gl_oset_nx_add (set1, obj) == gl_oset_nx_add (set2, obj));
6982
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
98 check_all (set1, set2);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
99 }
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
100
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
101 for (repeat = 0; repeat < 100000; repeat++)
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
102 {
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
103 unsigned int operation = RANDOM (3);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
104 switch (operation)
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
105 {
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
106 case 0:
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
107 {
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
108 const char *obj = RANDOM_OBJECT ();
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
109 ASSERT (gl_oset_search (set1, obj) == gl_oset_search (set2, obj));
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
110 }
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
111 break;
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
112 case 1:
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
113 {
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
114 const char *obj = RANDOM_OBJECT ();
12444
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'.
Bruno Haible <bruno@clisp.org>
parents: 12421
diff changeset
115 ASSERT (gl_oset_nx_add (set1, obj) == gl_oset_nx_add (set2, obj));
6982
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
116 }
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
117 break;
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
118 case 2:
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
119 {
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
120 const char *obj = RANDOM_OBJECT ();
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
121 ASSERT (gl_oset_remove (set1, obj) == gl_oset_remove (set2, obj));
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
122 }
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
123 break;
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
124 }
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
125 check_all (set1, set2);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
126 }
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
127
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
128 gl_oset_free (set1);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
129 gl_oset_free (set2);
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
130 }
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
131
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
132 return 0;
d88d781b8e7b Ordered set data type implemented by a binary tree.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
133 }