1 /* Test of sequential list data type implementation.
2 Copyright (C) 2006-2020 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2007.
4
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 #include <config.h>
19
20 #include "gl_array_list.h"
21
22 #include <stdlib.h>
23
24 #include "macros.h"
25
26 static const char *objects[15] =
27 {
28 "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o"
29 };
30
31 #define RANDOM(n) (rand () % (n))
32 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
33
34 static void
check_equals(gl_list_t list1,gl_list_t list2)35 check_equals (gl_list_t list1, gl_list_t list2)
36 {
37 size_t n, i;
38
39 n = gl_list_size (list1);
40 ASSERT (n == gl_list_size (list2));
41 for (i = 0; i < n; i++)
42 {
43 ASSERT (gl_list_get_at (list1, i) == gl_list_get_at (list2, i));
44 }
45 }
46
47 int
main(int argc,char * argv[])48 main (int argc, char *argv[])
49 {
50 gl_list_t list1, list2;
51
52 /* Allow the user to provide a non-default random seed on the command line. */
53 if (argc > 1)
54 srand (atoi (argv[1]));
55
56 {
57 size_t initial_size = RANDOM (50);
58 const void **contents =
59 (const void **) malloc (initial_size * sizeof (const void *));
60 size_t i;
61 unsigned int repeat;
62
63 for (i = 0; i < initial_size; i++)
64 contents[i] = RANDOM_OBJECT ();
65
66 /* Create list1. */
67 list1 = gl_list_nx_create (GL_ARRAY_LIST, NULL, NULL, NULL, true,
68 initial_size, contents);
69 ASSERT (list1 != NULL);
70 /* Create list2. */
71 list2 = gl_list_nx_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true);
72 ASSERT (list2 != NULL);
73 for (i = 0; i < initial_size; i++)
74 ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL);
75
76 check_equals (list1, list2);
77
78 for (repeat = 0; repeat < 10000; repeat++)
79 {
80 unsigned int operation = RANDOM (18);
81 switch (operation)
82 {
83 case 0:
84 if (gl_list_size (list1) > 0)
85 {
86 size_t index = RANDOM (gl_list_size (list1));
87 const char *obj = RANDOM_OBJECT ();
88 gl_list_node_t node1, node2;
89
90 node1 = gl_list_nx_set_at (list1, index, obj);
91 ASSERT (node1 != NULL);
92 ASSERT (gl_list_get_at (list1, index) == obj);
93 ASSERT (gl_list_node_value (list1, node1) == obj);
94
95 node2 = gl_list_nx_set_at (list2, index, obj);
96 ASSERT (node2 != NULL);
97 ASSERT (gl_list_get_at (list2, index) == obj);
98 ASSERT (gl_list_node_value (list2, node2) == obj);
99
100 if (index > 0)
101 {
102 ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
103 == gl_list_get_at (list1, index - 1));
104 }
105 if (index + 1 < gl_list_size (list1))
106 {
107 ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
108 == gl_list_get_at (list1, index + 1));
109 }
110 }
111 break;
112 case 1:
113 {
114 const char *obj = RANDOM_OBJECT ();
115 gl_list_node_t node1, node2;
116 node1 = gl_list_search (list1, obj);
117 node2 = gl_list_search (list2, obj);
118 if (node1 == NULL)
119 {
120 ASSERT (node2 == NULL);
121 }
122 else
123 {
124 ASSERT (node2 != NULL);
125 ASSERT (gl_list_node_value (list1, node1) == obj);
126 ASSERT (gl_list_node_value (list2, node2) == obj);
127 }
128 }
129 break;
130 case 2:
131 {
132 const char *obj = RANDOM_OBJECT ();
133 size_t index1, index2;
134 index1 = gl_list_indexof (list1, obj);
135 index2 = gl_list_indexof (list2, obj);
136 if (index1 == (size_t)(-1))
137 {
138 ASSERT (index2 == (size_t)(-1));
139 }
140 else
141 {
142 ASSERT (index2 != (size_t)(-1));
143 ASSERT (gl_list_get_at (list1, index1) == obj);
144 ASSERT (gl_list_get_at (list2, index2) == obj);
145 ASSERT (index2 == index1);
146 }
147 }
148 break;
149 case 3: /* add 1 element */
150 {
151 const char *obj = RANDOM_OBJECT ();
152 gl_list_node_t node1, node2;
153 node1 = gl_list_nx_add_first (list1, obj);
154 ASSERT (node1 != NULL);
155 node2 = gl_list_nx_add_first (list2, obj);
156 ASSERT (node2 != NULL);
157 ASSERT (gl_list_node_value (list1, node1) == obj);
158 ASSERT (gl_list_node_value (list2, node2) == obj);
159 ASSERT (gl_list_get_at (list1, 0) == obj);
160 ASSERT (gl_list_get_at (list2, 0) == obj);
161 }
162 break;
163 case 4: /* add 1 element */
164 {
165 const char *obj = RANDOM_OBJECT ();
166 gl_list_node_t node1, node2;
167 node1 = gl_list_nx_add_last (list1, obj);
168 ASSERT (node1 != NULL);
169 node2 = gl_list_nx_add_last (list2, obj);
170 ASSERT (node2 != NULL);
171 ASSERT (gl_list_node_value (list1, node1) == obj);
172 ASSERT (gl_list_node_value (list2, node2) == obj);
173 ASSERT (gl_list_get_at (list1, gl_list_size (list1) - 1) == obj);
174 ASSERT (gl_list_get_at (list2, gl_list_size (list2) - 1) == obj);
175 }
176 break;
177 case 5: /* add 3 elements */
178 {
179 const char *obj0 = RANDOM_OBJECT ();
180 const char *obj1 = RANDOM_OBJECT ();
181 const char *obj2 = RANDOM_OBJECT ();
182 gl_list_node_t node1, node2;
183 node1 = gl_list_nx_add_first (list1, obj2);
184 ASSERT (node1 != NULL);
185 node1 = gl_list_nx_add_before (list1, node1, obj0);
186 ASSERT (node1 != NULL);
187 node1 = gl_list_nx_add_after (list1, node1, obj1);
188 ASSERT (node1 != NULL);
189 node2 = gl_list_nx_add_first (list2, obj2);
190 ASSERT (node2 != NULL);
191 node2 = gl_list_nx_add_before (list2, node2, obj0);
192 ASSERT (node2 != NULL);
193 node2 = gl_list_nx_add_after (list2, node2, obj1);
194 ASSERT (node2 != NULL);
195 ASSERT (gl_list_node_value (list1, node1) == obj1);
196 ASSERT (gl_list_node_value (list2, node2) == obj1);
197 ASSERT (gl_list_get_at (list1, 0) == obj0);
198 ASSERT (gl_list_get_at (list1, 1) == obj1);
199 ASSERT (gl_list_get_at (list1, 2) == obj2);
200 ASSERT (gl_list_get_at (list2, 0) == obj0);
201 ASSERT (gl_list_get_at (list2, 1) == obj1);
202 ASSERT (gl_list_get_at (list2, 2) == obj2);
203 }
204 break;
205 case 6: /* add 1 element */
206 {
207 size_t index = RANDOM (gl_list_size (list1) + 1);
208 const char *obj = RANDOM_OBJECT ();
209 gl_list_node_t node1, node2;
210 node1 = gl_list_nx_add_at (list1, index, obj);
211 ASSERT (node1 != NULL);
212 node2 = gl_list_nx_add_at (list2, index, obj);
213 ASSERT (node2 != NULL);
214 ASSERT (gl_list_get_at (list1, index) == obj);
215 ASSERT (gl_list_node_value (list1, node1) == obj);
216 ASSERT (gl_list_get_at (list2, index) == obj);
217 ASSERT (gl_list_node_value (list2, node2) == obj);
218 if (index > 0)
219 {
220 ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
221 == gl_list_get_at (list1, index - 1));
222 }
223 if (index + 1 < gl_list_size (list1))
224 {
225 ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
226 == gl_list_get_at (list1, index + 1));
227 }
228 }
229 break;
230 case 7: case 8: /* remove 1 element */
231 if (gl_list_size (list1) > 0)
232 {
233 size_t n = gl_list_size (list1);
234 const char *obj = gl_list_get_at (list1, RANDOM (n));
235 gl_list_node_t node1, node2;
236 node1 = gl_list_search (list1, obj);
237 node2 = gl_list_search (list2, obj);
238 ASSERT (node1 != NULL);
239 ASSERT (node2 != NULL);
240 ASSERT (gl_list_remove_node (list1, node1));
241 ASSERT (gl_list_remove_node (list2, node2));
242 ASSERT (gl_list_size (list1) == n - 1);
243 }
244 break;
245 case 9: case 10: /* remove 1 element */
246 if (gl_list_size (list1) > 0)
247 {
248 size_t n = gl_list_size (list1);
249 size_t index = RANDOM (n);
250 ASSERT (gl_list_remove_at (list1, index));
251 ASSERT (gl_list_remove_at (list2, index));
252 ASSERT (gl_list_size (list1) == n - 1);
253 }
254 break;
255 case 11: /* remove first element */
256 {
257 size_t n = gl_list_size (list1);
258 bool removed1 = gl_list_remove_first (list1);
259 ASSERT (gl_list_remove_first (list2) == removed1);
260 ASSERT (gl_list_size (list1) == n - (int) removed1);
261 }
262 break;
263 case 12: /* remove last element */
264 {
265 size_t n = gl_list_size (list1);
266 bool removed1 = gl_list_remove_last (list1);
267 ASSERT (gl_list_remove_last (list2) == removed1);
268 ASSERT (gl_list_size (list1) == n - (int) removed1);
269 }
270 break;
271 case 13: case 14: /* remove 1 element */
272 if (gl_list_size (list1) > 0)
273 {
274 size_t n = gl_list_size (list1);
275 const char *obj = gl_list_get_at (list1, RANDOM (n));
276 ASSERT (gl_list_remove (list1, obj));
277 ASSERT (gl_list_remove (list2, obj));
278 ASSERT (gl_list_size (list1) == n - 1);
279 }
280 break;
281 case 15:
282 if (gl_list_size (list1) > 0)
283 {
284 size_t n = gl_list_size (list1);
285 const char *obj = "xyzzy";
286 ASSERT (!gl_list_remove (list1, obj));
287 ASSERT (!gl_list_remove (list2, obj));
288 ASSERT (gl_list_size (list1) == n);
289 }
290 break;
291 case 16:
292 {
293 size_t n = gl_list_size (list1);
294 gl_list_iterator_t iter1, iter2;
295 const void *elt;
296 iter1 = gl_list_iterator (list1);
297 iter2 = gl_list_iterator (list2);
298 for (i = 0; i < n; i++)
299 {
300 ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
301 ASSERT (gl_list_get_at (list1, i) == elt);
302 ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
303 ASSERT (gl_list_get_at (list2, i) == elt);
304 }
305 ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
306 ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
307 gl_list_iterator_free (&iter1);
308 gl_list_iterator_free (&iter2);
309 }
310 break;
311 case 17:
312 {
313 size_t end = RANDOM (gl_list_size (list1) + 1);
314 size_t start = RANDOM (end + 1);
315 gl_list_iterator_t iter1, iter2;
316 const void *elt;
317 iter1 = gl_list_iterator_from_to (list1, start, end);
318 iter2 = gl_list_iterator_from_to (list2, start, end);
319 for (i = start; i < end; i++)
320 {
321 ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
322 ASSERT (gl_list_get_at (list1, i) == elt);
323 ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
324 ASSERT (gl_list_get_at (list2, i) == elt);
325 }
326 ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
327 ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
328 gl_list_iterator_free (&iter1);
329 gl_list_iterator_free (&iter2);
330 }
331 break;
332 }
333 check_equals (list1, list2);
334 }
335
336 gl_list_free (list1);
337 gl_list_free (list2);
338 free (contents);
339 }
340
341 return 0;
342 }
343