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>, 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 <http://www.gnu.org/licenses/>.  */
17 
18 #include <config.h>
19 
20 #include "gl_linkedhash_list.h"
21 
22 #include <limits.h>
23 #include <stdlib.h>
24 #include <string.h>
25 
26 #include "gl_array_list.h"
27 #include "progname.h"
28 #include "macros.h"
29 
30 static const char *objects[15] =
31   {
32     "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o"
33   };
34 
35 #define SIZE_BITS (sizeof (size_t) * CHAR_BIT)
36 
37 static bool
string_equals(const void * x1,const void * x2)38 string_equals (const void *x1, const void *x2)
39 {
40   const char *s1 = x1;
41   const char *s2 = x2;
42   return strcmp (s1, s2) == 0;
43 }
44 
45 /* A hash function for NUL-terminated char* strings using
46    the method described by Bruno Haible.
47    See http://www.haible.de/bruno/hashfunc.html.  */
48 static size_t
string_hash(const void * x)49 string_hash (const void *x)
50 {
51   const char *s = x;
52   size_t h = 0;
53 
54   for (; *s; s++)
55     h = *s + ((h << 9) | (h >> (SIZE_BITS - 9)));
56 
57   return h;
58 }
59 
60 #define RANDOM(n) (rand () % (n))
61 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
62 
63 static void
check_equals(gl_list_t list1,gl_list_t list2)64 check_equals (gl_list_t list1, gl_list_t list2)
65 {
66   size_t n, i;
67 
68   n = gl_list_size (list1);
69   ASSERT (n == gl_list_size (list2));
70   for (i = 0; i < n; i++)
71     {
72       ASSERT (gl_list_get_at (list1, i) == gl_list_get_at (list2, i));
73     }
74 }
75 
76 static void
check_all(gl_list_t list1,gl_list_t list2,gl_list_t list3)77 check_all (gl_list_t list1, gl_list_t list2, gl_list_t list3)
78 {
79   check_equals (list1, list2);
80   check_equals (list1, list3);
81 }
82 
83 int
main(int argc,char * argv[])84 main (int argc, char *argv[])
85 {
86   gl_list_t list1, list2, list3;
87 
88   set_program_name (argv[0]);
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,
106                                string_equals, string_hash, NULL, true,
107                                initial_size, contents);
108     ASSERT (list1 != NULL);
109     /* Create list2.  */
110     list2 = gl_list_nx_create_empty (GL_LINKEDHASH_LIST,
111                                      string_equals, string_hash, NULL, true);
112     ASSERT (list2 != NULL);
113     for (i = 0; i < initial_size; i++)
114       ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL);
115 
116     /* Create list3.  */
117     list3 = gl_list_nx_create (GL_LINKEDHASH_LIST,
118                                string_equals, string_hash, NULL, true,
119                                initial_size, contents);
120     ASSERT (list3 != NULL);
121 
122     check_all (list1, list2, list3);
123 
124     for (repeat = 0; repeat < 10000; repeat++)
125       {
126         unsigned int operation = RANDOM (16);
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: case 12: /* remove 1 element */
358             if (gl_list_size (list1) > 0)
359               {
360                 size_t n = gl_list_size (list1);
361                 const char *obj = gl_list_get_at (list1, RANDOM (n));
362                 ASSERT (gl_list_remove (list1, obj));
363                 ASSERT (gl_list_remove (list2, obj));
364                 ASSERT (gl_list_remove (list3, obj));
365                 ASSERT (gl_list_size (list1) == n - 1);
366               }
367             break;
368           case 13:
369             if (gl_list_size (list1) > 0)
370               {
371                 size_t n = gl_list_size (list1);
372                 const char *obj = "xyzzy";
373                 ASSERT (!gl_list_remove (list1, obj));
374                 ASSERT (!gl_list_remove (list2, obj));
375                 ASSERT (!gl_list_remove (list3, obj));
376                 ASSERT (gl_list_size (list1) == n);
377               }
378             break;
379           case 14:
380             {
381               size_t n = gl_list_size (list1);
382               gl_list_iterator_t iter1, iter2, iter3;
383               const void *elt;
384               iter1 = gl_list_iterator (list1);
385               iter2 = gl_list_iterator (list2);
386               iter3 = gl_list_iterator (list3);
387               for (i = 0; i < n; i++)
388                 {
389                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
390                   ASSERT (gl_list_get_at (list1, i) == elt);
391                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
392                   ASSERT (gl_list_get_at (list2, i) == elt);
393                   ASSERT (gl_list_iterator_next (&iter3, &elt, NULL));
394                   ASSERT (gl_list_get_at (list3, i) == elt);
395                 }
396               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
397               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
398               ASSERT (!gl_list_iterator_next (&iter3, &elt, NULL));
399               gl_list_iterator_free (&iter1);
400               gl_list_iterator_free (&iter2);
401               gl_list_iterator_free (&iter3);
402             }
403             break;
404           case 15:
405             {
406               size_t end = RANDOM (gl_list_size (list1) + 1);
407               size_t start = RANDOM (end + 1);
408               gl_list_iterator_t iter1, iter2, iter3;
409               const void *elt;
410               iter1 = gl_list_iterator_from_to (list1, start, end);
411               iter2 = gl_list_iterator_from_to (list2, start, end);
412               iter3 = gl_list_iterator_from_to (list3, start, end);
413               for (i = start; i < end; i++)
414                 {
415                   ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
416                   ASSERT (gl_list_get_at (list1, i) == elt);
417                   ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
418                   ASSERT (gl_list_get_at (list2, i) == elt);
419                   ASSERT (gl_list_iterator_next (&iter3, &elt, NULL));
420                   ASSERT (gl_list_get_at (list3, i) == elt);
421                 }
422               ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
423               ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
424               ASSERT (!gl_list_iterator_next (&iter3, &elt, NULL));
425               gl_list_iterator_free (&iter1);
426               gl_list_iterator_free (&iter2);
427               gl_list_iterator_free (&iter3);
428             }
429             break;
430           }
431         check_all (list1, list2, list3);
432       }
433 
434     gl_list_free (list1);
435     gl_list_free (list2);
436     gl_list_free (list3);
437     free (contents);
438   }
439 
440   return 0;
441 }
442