1 /* Test of sequential list data type implementation.
2 Copyright (C) 2006-2024 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
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.
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.
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/>. */
20 #include "gl_linkedhash_list.h"
26 #include "gl_array_list.h"
29 static const char *objects
[15] =
31 "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o"
34 #define SIZE_BITS (sizeof (size_t) * CHAR_BIT)
37 string_equals (const void *x1
, const void *x2
)
41 return strcmp (s1
, s2
) == 0;
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. */
48 string_hash (const void *x
)
54 h
= *s
+ ((h
<< 9) | (h
>> (SIZE_BITS
- 9)));
59 #define RANDOM(n) (rand () % (n))
60 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
63 check_equals (gl_list_t list1
, gl_list_t list2
)
67 n
= gl_list_size (list1
);
68 ASSERT (n
== gl_list_size (list2
));
69 for (i
= 0; i
< n
; i
++)
71 ASSERT (gl_list_get_at (list1
, i
) == gl_list_get_at (list2
, i
));
76 check_equals_by_forward_iteration (gl_list_t list1
, gl_list_t list2
)
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
)
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
);
87 ASSERT ((node1
== NULL
) == (node2
== NULL
));
91 check_equals_by_backward_iteration (gl_list_t list1
, gl_list_t list2
)
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
)
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
);
102 ASSERT ((node1
== NULL
) == (node2
== NULL
));
106 check_all (gl_list_t list1
, gl_list_t list2
, gl_list_t list3
)
108 check_equals (list1
, list2
);
109 check_equals (list1
, list3
);
113 main (int argc
, char *argv
[])
115 gl_list_t list1
, list2
, list3
;
117 /* Allow the user to provide a non-default random seed on the command line. */
119 srand (atoi (argv
[1]));
122 size_t initial_size
= RANDOM (50);
123 const void **contents
=
124 (const void **) malloc (initial_size
* sizeof (const void *));
128 for (i
= 0; i
< initial_size
; i
++)
129 contents
[i
] = RANDOM_OBJECT ();
132 list1
= gl_list_nx_create (GL_ARRAY_LIST
,
133 string_equals
, string_hash
, NULL
, true,
134 initial_size
, contents
);
135 ASSERT (list1
!= NULL
);
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
);
144 list3
= gl_list_nx_create (GL_LINKEDHASH_LIST
,
145 string_equals
, string_hash
, NULL
, true,
146 initial_size
, contents
);
147 ASSERT (list3
!= NULL
);
149 check_all (list1
, list2
, list3
);
151 check_equals_by_forward_iteration (list1
, list2
);
152 check_equals_by_backward_iteration (list1
, list2
);
154 for (repeat
= 0; repeat
< 10000; repeat
++)
156 unsigned int operation
= RANDOM (18);
160 if (gl_list_size (list1
) > 0)
162 size_t index
= RANDOM (gl_list_size (list1
));
163 const char *obj
= RANDOM_OBJECT ();
164 gl_list_node_t node1
, node2
, node3
;
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
);
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
);
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
);
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));
190 if (index
+ 1 < gl_list_size (list1
))
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));
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
);
210 ASSERT (node2
== NULL
);
211 ASSERT (node3
== NULL
);
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
);
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))
232 ASSERT (index2
== (size_t)(-1));
233 ASSERT (index3
== (size_t)(-1));
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
);
247 case 3: /* add 1 element */
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
);
265 case 4: /* add 1 element */
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
);
283 case 5: /* add 3 elements */
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
);
321 case 6: /* add 1 element */
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
);
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));
347 if (index
+ 1 < gl_list_size (list1
))
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));
358 case 7: case 8: /* remove 1 element */
359 if (gl_list_size (list1
) > 0)
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);
376 case 9: case 10: /* remove 1 element */
377 if (gl_list_size (list1
) > 0)
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);
387 case 11: /* remove first element */
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
);
396 case 12: /* remove last element */
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
);
405 case 13: case 14: /* remove 1 element */
406 if (gl_list_size (list1
) > 0)
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);
417 if (gl_list_size (list1
) > 0)
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
);
429 size_t n
= gl_list_size (list1
);
430 gl_list_iterator_t iter1
, iter2
, iter3
;
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
++)
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
);
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
);
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
;
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
++)
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
);
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
);
479 check_all (list1
, list2
, list3
);
482 gl_list_free (list1
);
483 gl_list_free (list2
);
484 gl_list_free (list3
);
488 return test_exit_status
;