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