1 /* Test of sequential list data type implementation.
2 Copyright (C) 2006-2021 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
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_linked_list.h"
21
22 #include <stdlib.h>
23
24 #include "gl_array_list.h"
25 #include "macros.h"
26
27 static const char *objects[15] =
28 {
29 "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o"
30 };
31
32 #define RANDOM(n) (rand () % (n))
33 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
34
35 static void
36 check_equals (gl_list_t list1, gl_list_t list2)
37 {
38 size_t n, i;
39
40 n = gl_list_size (list1);
41 ASSERT (n == gl_list_size (list2));
42 for (i = 0; i < n; i++)
43 {
44 ASSERT (gl_list_get_at (list1, i) == gl_list_get_at (list2, i));
45 }
46 }
47
48 static void
49 check_equals_by_forward_iteration (gl_list_t list1, gl_list_t list2)
50 {
51 gl_list_node_t node1 = gl_list_first_node (list1);
52 gl_list_node_t node2 = gl_list_first_node (list2);
53 while (node1 != NULL && node2 != NULL)
54 {
55 ASSERT (gl_list_node_value (list1, node1)
56 == gl_list_node_value (list2, node2));
57 node1 = gl_list_next_node (list1, node1);
58 node2 = gl_list_next_node (list2, node2);
59 }
60 ASSERT ((node1 == NULL) == (node2 == NULL));
61 }
62
63 static void
64 check_equals_by_backward_iteration (gl_list_t list1, gl_list_t list2)
65 {
66 gl_list_node_t node1 = gl_list_last_node (list1);
67 gl_list_node_t node2 = gl_list_last_node (list2);
68 while (node1 != NULL && node2 != NULL)
69 {
70 ASSERT (gl_list_node_value (list1, node1)
71 == gl_list_node_value (list2, node2));
72 node1 = gl_list_previous_node (list1, node1);
73 node2 = gl_list_previous_node (list2, node2);
74 }
75 ASSERT ((node1 == NULL) == (node2 == NULL));
76 }
77
78 static void
79 check_all (gl_list_t list1, gl_list_t list2, gl_list_t list3)
80 {
81 check_equals (list1, list2);
82 check_equals (list1, list3);
83 }
84
85 int
86 main (int argc, char *argv[])
87 {
88 gl_list_t list1, list2, list3;
89
90 /* Allow the user to provide a non-default random seed on the command line. */
91 if (argc > 1)
92 srand (atoi (argv[1]));
93
94 {
95 size_t initial_size = RANDOM (50);
96 const void **contents =
97 (const void **) malloc (initial_size * sizeof (const void *));
98 size_t i;
99 unsigned int repeat;
100
101 for (i = 0; i < initial_size; i++)
102 contents[i] = RANDOM_OBJECT ();
103
104 /* Create list1. */
105 list1 = gl_list_nx_create (GL_ARRAY_LIST, NULL, NULL, NULL, true,
106 initial_size, contents);
107 ASSERT (list1 != NULL);
108 /* Create list2. */
109 list2 = gl_list_nx_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
110 ASSERT (list2 != NULL);
111 for (i = 0; i < initial_size; i++)
112 ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL);
113
114 /* Create list3. */
115 list3 = gl_list_nx_create (GL_LINKED_LIST, NULL, NULL, NULL, true,
116 initial_size, contents);
117 ASSERT (list3 != NULL);
118
119 check_all (list1, list2, list3);
120
121 check_equals_by_forward_iteration (list1, list2);
122 check_equals_by_backward_iteration (list1, list2);
123
124 for (repeat = 0; repeat < 10000; repeat++)
125 {
126 unsigned int operation = RANDOM (18);
127 switch (operation)
128 {
129 case 0:
130 if (gl_list_size (list1) > 0)
131 {
132 size_t index = RANDOM (gl_list_size (list1));
133 const char *obj = RANDOM_OBJECT ();
134 gl_list_node_t node1, node2, node3;
135
136 node1 = gl_list_nx_set_at (list1, index, obj);
137 ASSERT (node1 != NULL);
138 ASSERT (gl_list_get_at (list1, index) == obj);
139 ASSERT (gl_list_node_value (list1, node1) == obj);
140
141 node2 = gl_list_nx_set_at (list2, index, obj);
142 ASSERT (node2 != NULL);
143 ASSERT (gl_list_get_at (list2, index) == obj);
144 ASSERT (gl_list_node_value (list2, node2) == obj);
145
146 node3 = gl_list_nx_set_at (list3, index, obj);
147 ASSERT (node3 != NULL);
148 ASSERT (gl_list_get_at (list3, index) == obj);
149 ASSERT (gl_list_node_value (list3, node3) == obj);
150
151 if (index > 0)
152 {
153 ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
154 == gl_list_get_at (list1, index - 1));
155 ASSERT (gl_list_node_value (list2, gl_list_previous_node (list3, node3))
156 == gl_list_get_at (list2, index - 1));
157 ASSERT (gl_list_node_value (list3, gl_list_previous_node (list3, node3))
158 == gl_list_get_at (list2, index - 1));
159 }
160 if (index + 1 < gl_list_size (list1))
161 {
162 ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
163 == gl_list_get_at (list1, index + 1));
164 ASSERT (gl_list_node_value (list2, gl_list_next_node (list3, node3))
165 == gl_list_get_at (list2, index + 1));
166 ASSERT (gl_list_node_value (list3, gl_list_next_node (list3, node3))
167 == gl_list_get_at (list2, index + 1));
168 }
169 }
170 break;
171 case 1:
172 {
173 const char *obj = RANDOM_OBJECT ();
174 gl_list_node_t node1, node2, node3;
175 node1 = gl_list_search (list1, obj);
176 node2 = gl_list_search (list2, obj);
177 node3 = gl_list_search (list3, obj);
178 if (node1 == NULL)
179 {
180 ASSERT (node2 == NULL);
181 ASSERT (node3 == NULL);
182 }
183 else
184 {
185 ASSERT (node2 != NULL);
186 ASSERT (node3 != NULL);
187 ASSERT (gl_list_node_value (list1, node1) == obj);
188 ASSERT (gl_list_node_value (list2, node2) == obj);
189 ASSERT (gl_list_node_value (list3, node3) == obj);
190 }
191 }
192 break;
193 case 2:
194 {
195 const char *obj = RANDOM_OBJECT ();
196 size_t index1, index2, index3;
197 index1 = gl_list_indexof (list1, obj);
198 index2 = gl_list_indexof (list2, obj);
199 index3 = gl_list_indexof (list3, obj);
200 if (index1 == (size_t)(-1))
201 {
202 ASSERT (index2 == (size_t)(-1));
203 ASSERT (index3 == (size_t)(-1));
204 }
205 else
206 {
207 ASSERT (index2 != (size_t)(-1));
208 ASSERT (index3 != (size_t)(-1));
209 ASSERT (gl_list_get_at (list1, index1) == obj);
210 ASSERT (gl_list_get_at (list2, index2) == obj);
211 ASSERT (gl_list_get_at (list3, index3) == obj);
212 ASSERT (index2 == index1);
213 ASSERT (index3 == index1);
214 }
215 }
216 break;
217 case 3: /* add 1 element */
218 {
219 const char *obj = RANDOM_OBJECT ();
220 gl_list_node_t node1, node2, node3;
221 node1 = gl_list_nx_add_first (list1, obj);
222 ASSERT (node1 != NULL);
223 node2 = gl_list_nx_add_first (list2, obj);
224 ASSERT (node2 != NULL);
225 node3 = gl_list_nx_add_first (list3, obj);
226 ASSERT (node3 != NULL);
227 ASSERT (gl_list_node_value (list1, node1) == obj);
228 ASSERT (gl_list_node_value (list2, node2) == obj);
229 ASSERT (gl_list_node_value (list3, node3) == obj);
230 ASSERT (gl_list_get_at (list1, 0) == obj);
231 ASSERT (gl_list_get_at (list2, 0) == obj);
232 ASSERT (gl_list_get_at (list3, 0) == obj);
233 }
234 break;
235 case 4: /* add 1 element */
236 {
237 const char *obj = RANDOM_OBJECT ();
238 gl_list_node_t node1, node2, node3;
239 node1 = gl_list_nx_add_last (list1, obj);
240 ASSERT (node1 != NULL);
241 node2 = gl_list_nx_add_last (list2, obj);
242 ASSERT (node2 != NULL);
243 node3 = gl_list_nx_add_last (list3, obj);
244 ASSERT (node3 != NULL);
245 ASSERT (gl_list_node_value (list1, node1) == obj);
246 ASSERT (gl_list_node_value (list2, node2) == obj);
247 ASSERT (gl_list_node_value (list3, node3) == obj);
248 ASSERT (gl_list_get_at (list1, gl_list_size (list1) - 1) == obj);
249 ASSERT (gl_list_get_at (list2, gl_list_size (list2) - 1) == obj);
250 ASSERT (gl_list_get_at (list3, gl_list_size (list3) - 1) == obj);
251 }
252 break;
253 case 5: /* add 3 elements */
254 {
255 const char *obj0 = RANDOM_OBJECT ();
256 const char *obj1 = RANDOM_OBJECT ();
257 const char *obj2 = RANDOM_OBJECT ();
258 gl_list_node_t node1, node2, node3;
259 node1 = gl_list_nx_add_first (list1, obj2);
260 ASSERT (node1 != NULL);
261 node1 = gl_list_nx_add_before (list1, node1, obj0);
262 ASSERT (node1 != NULL);
263 node1 = gl_list_nx_add_after (list1, node1, obj1);
264 ASSERT (node1 != NULL);
265 node2 = gl_list_nx_add_first (list2, obj2);
266 ASSERT (node2 != NULL);
267 node2 = gl_list_nx_add_before (list2, node2, obj0);
268 ASSERT (node2 != NULL);
269 node2 = gl_list_nx_add_after (list2, node2, obj1);
270 ASSERT (node2 != NULL);
271 node3 = gl_list_nx_add_first (list3, obj2);
272 ASSERT (node3 != NULL);
273 node3 = gl_list_nx_add_before (list3, node3, obj0);
274 ASSERT (node3 != NULL);
275 node3 = gl_list_nx_add_after (list3, node3, obj1);
276 ASSERT (node3 != NULL);
277 ASSERT (gl_list_node_value (list1, node1) == obj1);
278 ASSERT (gl_list_node_value (list2, node2) == obj1);
279 ASSERT (gl_list_node_value (list3, node3) == obj1);
280 ASSERT (gl_list_get_at (list1, 0) == obj0);
281 ASSERT (gl_list_get_at (list1, 1) == obj1);
282 ASSERT (gl_list_get_at (list1, 2) == obj2);
283 ASSERT (gl_list_get_at (list2, 0) == obj0);
284 ASSERT (gl_list_get_at (list2, 1) == obj1);
285 ASSERT (gl_list_get_at (list2, 2) == obj2);
286 ASSERT (gl_list_get_at (list3, 0) == obj0);
287 ASSERT (gl_list_get_at (list3, 1) == obj1);
288 ASSERT (gl_list_get_at (list3, 2) == obj2);
289 }
290 break;
291 case 6: /* add 1 element */
292 {
293 size_t index = RANDOM (gl_list_size (list1) + 1);
294 const char *obj = RANDOM_OBJECT ();
295 gl_list_node_t node1, node2, node3;
296 node1 = gl_list_nx_add_at (list1, index, obj);
297 ASSERT (node1 != NULL);
298 node2 = gl_list_nx_add_at (list2, index, obj);
299 ASSERT (node2 != NULL);
300 node3 = gl_list_nx_add_at (list3, index, obj);
301 ASSERT (node3 != NULL);
302 ASSERT (gl_list_get_at (list1, index) == obj);
303 ASSERT (gl_list_node_value (list1, node1) == obj);
304 ASSERT (gl_list_get_at (list2, index) == obj);
305 ASSERT (gl_list_node_value (list2, node2) == obj);
306 ASSERT (gl_list_get_at (list3, index) == obj);
307 ASSERT (gl_list_node_value (list3, node3) == obj);
308 if (index > 0)
309 {
310 ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
311 == gl_list_get_at (list1, index - 1));
312 ASSERT (gl_list_node_value (list2, gl_list_previous_node (list3, node3))
313 == gl_list_get_at (list2, index - 1));
314 ASSERT (gl_list_node_value (list3, gl_list_previous_node (list3, node3))
315 == gl_list_get_at (list2, index - 1));
316 }
317 if (index + 1 < gl_list_size (list1))
318 {
319 ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
320 == gl_list_get_at (list1, index + 1));
321 ASSERT (gl_list_node_value (list2, gl_list_next_node (list3, node3))
322 == gl_list_get_at (list2, index + 1));
323 ASSERT (gl_list_node_value (list3, gl_list_next_node (list3, node3))
324 == gl_list_get_at (list2, index + 1));
325 }
326 }
327 break;
328 case 7: case 8: /* remove 1 element */
329 if (gl_list_size (list1) > 0)
330 {
331 size_t n = gl_list_size (list1);
332 const char *obj = gl_list_get_at (list1, RANDOM (n));
333 gl_list_node_t node1, node2, node3;
334 node1 = gl_list_search (list1, obj);
335 node2 = gl_list_search (list2, obj);
336 node3 = gl_list_search (list3, obj);
337 ASSERT (node1 != NULL);
338 ASSERT (node2 != NULL);
339 ASSERT (node3 != NULL);
340 ASSERT (gl_list_remove_node (list1, node1));
341 ASSERT (gl_list_remove_node (list2, node2));
342 ASSERT (gl_list_remove_node (list3, node3));
343 ASSERT (gl_list_size (list1) == n - 1);
344 }
345 break;
346 case 9: case 10: /* remove 1 element */
347 if (gl_list_size (list1) > 0)
348 {
349 size_t n = gl_list_size (list1);
350 size_t index = RANDOM (n);
351 ASSERT (gl_list_remove_at (list1, index));
352 ASSERT (gl_list_remove_at (list2, index));
353 ASSERT (gl_list_remove_at (list3, index));
354 ASSERT (gl_list_size (list1) == n - 1);
355 }
356 break;
357 case 11: /* remove first element */
358 {
359 size_t n = gl_list_size (list1);
360 bool removed1 = gl_list_remove_first (list1);
361 ASSERT (gl_list_remove_first (list2) == removed1);
362 ASSERT (gl_list_remove_first (list3) == removed1);
363 ASSERT (gl_list_size (list1) == n - (int) removed1);
364 }
365 break;
366 case 12: /* remove last element */
367 {
368 size_t n = gl_list_size (list1);
369 bool removed1 = gl_list_remove_last (list1);
370 ASSERT (gl_list_remove_last (list2) == removed1);
371 ASSERT (gl_list_remove_last (list3) == removed1);
372 ASSERT (gl_list_size (list1) == n - (int) removed1);
373 }
374 break;
375 case 13: case 14: /* remove 1 element */
376 if (gl_list_size (list1) > 0)
377 {
378 size_t n = gl_list_size (list1);
379 const char *obj = gl_list_get_at (list1, RANDOM (n));
380 ASSERT (gl_list_remove (list1, obj));
381 ASSERT (gl_list_remove (list2, obj));
382 ASSERT (gl_list_remove (list3, obj));
383 ASSERT (gl_list_size (list1) == n - 1);
384 }
385 break;
386 case 15:
387 if (gl_list_size (list1) > 0)
388 {
389 size_t n = gl_list_size (list1);
390 const char *obj = "xyzzy";
391 ASSERT (!gl_list_remove (list1, obj));
392 ASSERT (!gl_list_remove (list2, obj));
393 ASSERT (!gl_list_remove (list3, obj));
394 ASSERT (gl_list_size (list1) == n);
395 }
396 break;
397 case 16:
398 {
399 size_t n = gl_list_size (list1);
400 gl_list_iterator_t iter1, iter2, iter3;
401 const void *elt;
402 iter1 = gl_list_iterator (list1);
403 iter2 = gl_list_iterator (list2);
404 iter3 = gl_list_iterator (list3);
405 for (i = 0; i < n; i++)
406 {
407 ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
408 ASSERT (gl_list_get_at (list1, i) == elt);
409 ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
410 ASSERT (gl_list_get_at (list2, i) == elt);
411 ASSERT (gl_list_iterator_next (&iter3, &elt, NULL));
412 ASSERT (gl_list_get_at (list3, i) == elt);
413 }
414 ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
415 ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
416 ASSERT (!gl_list_iterator_next (&iter3, &elt, NULL));
417 gl_list_iterator_free (&iter1);
418 gl_list_iterator_free (&iter2);
419 gl_list_iterator_free (&iter3);
420 }
421 break;
422 case 17:
423 {
424 size_t end = RANDOM (gl_list_size (list1) + 1);
425 size_t start = RANDOM (end + 1);
426 gl_list_iterator_t iter1, iter2, iter3;
427 const void *elt;
428 iter1 = gl_list_iterator_from_to (list1, start, end);
429 iter2 = gl_list_iterator_from_to (list2, start, end);
430 iter3 = gl_list_iterator_from_to (list3, start, end);
431 for (i = start; i < end; i++)
432 {
433 ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
434 ASSERT (gl_list_get_at (list1, i) == elt);
435 ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
436 ASSERT (gl_list_get_at (list2, i) == elt);
437 ASSERT (gl_list_iterator_next (&iter3, &elt, NULL));
438 ASSERT (gl_list_get_at (list3, i) == elt);
439 }
440 ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
441 ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
442 ASSERT (!gl_list_iterator_next (&iter3, &elt, NULL));
443 gl_list_iterator_free (&iter1);
444 gl_list_iterator_free (&iter2);
445 gl_list_iterator_free (&iter3);
446 }
447 break;
448 }
449 check_all (list1, list2, list3);
450 }
451
452 gl_list_free (list1);
453 gl_list_free (list2);
454 gl_list_free (list3);
455 free (contents);
456 }
457
458 return 0;
459 }