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