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