1 /* Test of sequential list data type implementation.
2    Copyright (C) 2006-2014 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 <http://www.gnu.org/licenses/>.  */
17 
18 #include <config.h>
19 
20 #include "gl_array_list.h"
21 
22 #include <stdlib.h>
23 
24 #include "progname.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 int
main(int argc,char * argv[])49 main (int argc, char *argv[])
50 {
51   gl_list_t list1, list2;
52 
53   set_program_name (argv[0]);
54 
55   /* Allow the user to provide a non-default random seed on the command line.  */
56   if (argc > 1)
57     srand (atoi (argv[1]));
58 
59   {
60     size_t initial_size = RANDOM (50);
61     const void **contents =
62       (const void **) malloc (initial_size * sizeof (const void *));
63     size_t i;
64     unsigned int repeat;
65 
66     for (i = 0; i < initial_size; i++)
67       contents[i] = RANDOM_OBJECT ();
68 
69     /* Create list1.  */
70     list1 = gl_list_nx_create (GL_ARRAY_LIST, NULL, NULL, NULL, true,
71                                initial_size, contents);
72     ASSERT (list1 != NULL);
73     /* Create list2.  */
74     list2 = gl_list_nx_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true);
75     ASSERT (list2 != NULL);
76     for (i = 0; i < initial_size; i++)
77       ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL);
78 
79     check_equals (list1, list2);
80 
81     for (repeat = 0; repeat < 10000; repeat++)
82       {
83         unsigned int operation = RANDOM (16);
84         switch (operation)
85           {
86           case 0:
87             if (gl_list_size (list1) > 0)
88               {
89                 size_t index = RANDOM (gl_list_size (list1));
90                 const char *obj = RANDOM_OBJECT ();
91                 gl_list_node_t node1, node2;
92 
93                 node1 = gl_list_nx_set_at (list1, index, obj);
94                 ASSERT (node1 != NULL);
95                 ASSERT (gl_list_get_at (list1, index) == obj);
96                 ASSERT (gl_list_node_value (list1, node1) == obj);
97 
98                 node2 = gl_list_nx_set_at (list2, index, obj);
99                 ASSERT (node2 != NULL);
100                 ASSERT (gl_list_get_at (list2, index) == obj);
101                 ASSERT (gl_list_node_value (list2, node2) == obj);
102 
103                 if (index > 0)
104                   {
105                     ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
106                             == gl_list_get_at (list1, index - 1));
107                   }
108                 if (index + 1 < gl_list_size (list1))
109                   {
110                     ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
111                             == gl_list_get_at (list1, index + 1));
112                   }
113               }
114             break;
115           case 1:
116             {
117               const char *obj = RANDOM_OBJECT ();
118               gl_list_node_t node1, node2;
119               node1 = gl_list_search (list1, obj);
120               node2 = gl_list_search (list2, obj);
121               if (node1 == NULL)
122                 {
123                   ASSERT (node2 == NULL);
124                 }
125               else
126                 {
127                   ASSERT (node2 != NULL);
128                   ASSERT (gl_list_node_value (list1, node1) == obj);
129                   ASSERT (gl_list_node_value (list2, node2) == obj);
130                 }
131             }
132             break;
133           case 2:
134             {
135               const char *obj = RANDOM_OBJECT ();
136               size_t index1, index2;
137               index1 = gl_list_indexof (list1, obj);
138               index2 = gl_list_indexof (list2, obj);
139               if (index1 == (size_t)(-1))
140                 {
141                   ASSERT (index2 == (size_t)(-1));
142                 }
143               else
144                 {
145                   ASSERT (index2 != (size_t)(-1));
146                   ASSERT (gl_list_get_at (list1, index1) == obj);
147                   ASSERT (gl_list_get_at (list2, index2) == obj);
148                   ASSERT (index2 == index1);
149                 }
150             }
151             break;
152           case 3: /* add 1 element */
153             {
154               const char *obj = RANDOM_OBJECT ();
155               gl_list_node_t node1, node2;
156               node1 = gl_list_nx_add_first (list1, obj);
157               ASSERT (node1 != NULL);
158               node2 = gl_list_nx_add_first (list2, obj);
159               ASSERT (node2 != NULL);
160               ASSERT (gl_list_node_value (list1, node1) == obj);
161               ASSERT (gl_list_node_value (list2, node2) == obj);
162               ASSERT (gl_list_get_at (list1, 0) == obj);
163               ASSERT (gl_list_get_at (list2, 0) == obj);
164             }
165             break;
166           case 4: /* add 1 element */
167             {
168               const char *obj = RANDOM_OBJECT ();
169               gl_list_node_t node1, node2;
170               node1 = gl_list_nx_add_last (list1, obj);
171               ASSERT (node1 != NULL);
172               node2 = gl_list_nx_add_last (list2, obj);
173               ASSERT (node2 != NULL);
174               ASSERT (gl_list_node_value (list1, node1) == obj);
175               ASSERT (gl_list_node_value (list2, node2) == obj);
176               ASSERT (gl_list_get_at (list1, gl_list_size (list1) - 1) == obj);
177               ASSERT (gl_list_get_at (list2, gl_list_size (list2) - 1) == obj);
178             }
179             break;
180           case 5: /* add 3 elements */
181             {
182               const char *obj0 = RANDOM_OBJECT ();
183               const char *obj1 = RANDOM_OBJECT ();
184               const char *obj2 = RANDOM_OBJECT ();
185               gl_list_node_t node1, node2;
186               node1 = gl_list_nx_add_first (list1, obj2);
187               ASSERT (node1 != NULL);
188               node1 = gl_list_nx_add_before (list1, node1, obj0);
189               ASSERT (node1 != NULL);
190               node1 = gl_list_nx_add_after (list1, node1, obj1);
191               ASSERT (node1 != NULL);
192               node2 = gl_list_nx_add_first (list2, obj2);
193               ASSERT (node2 != NULL);
194               node2 = gl_list_nx_add_before (list2, node2, obj0);
195               ASSERT (node2 != NULL);
196               node2 = gl_list_nx_add_after (list2, node2, obj1);
197               ASSERT (node2 != NULL);
198               ASSERT (gl_list_node_value (list1, node1) == obj1);
199               ASSERT (gl_list_node_value (list2, node2) == obj1);
200               ASSERT (gl_list_get_at (list1, 0) == obj0);
201               ASSERT (gl_list_get_at (list1, 1) == obj1);
202               ASSERT (gl_list_get_at (list1, 2) == obj2);
203               ASSERT (gl_list_get_at (list2, 0) == obj0);
204               ASSERT (gl_list_get_at (list2, 1) == obj1);
205               ASSERT (gl_list_get_at (list2, 2) == obj2);
206             }
207             break;
208           case 6: /* add 1 element */
209             {
210               size_t index = RANDOM (gl_list_size (list1) + 1);
211               const char *obj = RANDOM_OBJECT ();
212               gl_list_node_t node1, node2;
213               node1 = gl_list_nx_add_at (list1, index, obj);
214               ASSERT (node1 != NULL);
215               node2 = gl_list_nx_add_at (list2, index, obj);
216               ASSERT (node2 != NULL);
217               ASSERT (gl_list_get_at (list1, index) == obj);
218               ASSERT (gl_list_node_value (list1, node1) == obj);
219               ASSERT (gl_list_get_at (list2, index) == obj);
220               ASSERT (gl_list_node_value (list2, node2) == obj);
221               if (index > 0)
222                 {
223                   ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
224                           == gl_list_get_at (list1, index - 1));
225                 }
226               if (index + 1 < gl_list_size (list1))
227                 {
228                   ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
229                           == gl_list_get_at (list1, index + 1));
230                 }
231             }
232             break;
233           case 7: case 8: /* remove 1 element */
234             if (gl_list_size (list1) > 0)
235               {
236                 size_t n = gl_list_size (list1);
237                 const char *obj = gl_list_get_at (list1, RANDOM (n));
238                 gl_list_node_t node1, node2;
239                 node1 = gl_list_search (list1, obj);
240                 node2 = gl_list_search (list2, obj);
241                 ASSERT (node1 != NULL);
242                 ASSERT (node2 != NULL);
243                 ASSERT (gl_list_remove_node (list1, node1));
244                 ASSERT (gl_list_remove_node (list2, node2));
245                 ASSERT (gl_list_size (list1) == n - 1);
246               }
247             break;
248           case 9: case 10: /* remove 1 element */
249             if (gl_list_size (list1) > 0)
250               {
251                 size_t n = gl_list_size (list1);
252                 size_t index = RANDOM (n);
253                 ASSERT (gl_list_remove_at (list1, index));
254                 ASSERT (gl_list_remove_at (list2, index));
255                 ASSERT (gl_list_size (list1) == n - 1);
256               }
257             break;
258           case 11: case 12: /* remove 1 element */
259             if (gl_list_size (list1) > 0)
260               {
261                 size_t n = gl_list_size (list1);
262                 const char *obj = gl_list_get_at (list1, RANDOM (n));
263                 ASSERT (gl_list_remove (list1, obj));
264                 ASSERT (gl_list_remove (list2, obj));
265                 ASSERT (gl_list_size (list1) == n - 1);
266               }
267             break;
268           case 13:
269             if (gl_list_size (list1) > 0)
270               {
271                 size_t n = gl_list_size (list1);
272                 const char *obj = "xyzzy";
273                 ASSERT (!gl_list_remove (list1, obj));
274                 ASSERT (!gl_list_remove (list2, obj));
275                 ASSERT (gl_list_size (list1) == n);
276               }
277             break;
278           case 14:
279             {
280               size_t n = gl_list_size (list1);
281               gl_list_iterator_t iter1, iter2;
282               const void *elt;
283               iter1 = gl_list_iterator (list1);
284               iter2 = gl_list_iterator (list2);
285               for (i = 0; i < n; i++)
286                 {
287                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
288                   ASSERT (gl_list_get_at (list1, i) == elt);
289                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
290                   ASSERT (gl_list_get_at (list2, i) == elt);
291                 }
292               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
293               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
294               gl_list_iterator_free (&iter1);
295               gl_list_iterator_free (&iter2);
296             }
297             break;
298           case 15:
299             {
300               size_t end = RANDOM (gl_list_size (list1) + 1);
301               size_t start = RANDOM (end + 1);
302               gl_list_iterator_t iter1, iter2;
303               const void *elt;
304               iter1 = gl_list_iterator_from_to (list1, start, end);
305               iter2 = gl_list_iterator_from_to (list2, start, end);
306               for (i = start; i < end; i++)
307                 {
308                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
309                   ASSERT (gl_list_get_at (list1, i) == elt);
310                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
311                   ASSERT (gl_list_get_at (list2, i) == elt);
312                 }
313               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
314               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
315               gl_list_iterator_free (&iter1);
316               gl_list_iterator_free (&iter2);
317             }
318             break;
319           }
320         check_equals (list1, list2);
321       }
322 
323     gl_list_free (list1);
324     gl_list_free (list2);
325     free (contents);
326   }
327 
328   return 0;
329 }
330