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>, 2007.
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_array_list.h"
26 static const char *objects
[15] =
28 "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o"
31 #define RANDOM(n) (rand () % (n))
32 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
35 check_equals (gl_list_t list1
, gl_list_t list2
)
39 n
= gl_list_size (list1
);
40 ASSERT (n
== gl_list_size (list2
));
41 for (i
= 0; i
< n
; i
++)
43 ASSERT (gl_list_get_at (list1
, i
) == gl_list_get_at (list2
, i
));
48 check_equals_by_forward_iteration (gl_list_t list1
, gl_list_t list2
)
50 size_t n
= gl_list_size (list1
);
55 node2
= gl_list_first_node (list2
);
56 while (i
< n
&& node2
!= NULL
)
58 ASSERT (gl_list_get_at (list1
, i
) == gl_list_node_value (list2
, node2
));
60 node2
= gl_list_next_node (list2
, node2
);
62 ASSERT ((i
== n
) == (node2
== NULL
));
66 check_equals_by_backward_iteration (gl_list_t list1
, gl_list_t list2
)
68 size_t n
= gl_list_size (list1
);
73 node2
= gl_list_last_node (list2
);
74 while (i
!= (size_t)(-1) && node2
!= NULL
)
76 ASSERT (gl_list_get_at (list1
, i
) == gl_list_node_value (list2
, node2
));
78 node2
= gl_list_previous_node (list2
, node2
);
80 ASSERT ((i
== (size_t)(-1)) == (node2
== NULL
));
84 main (int argc
, char *argv
[])
86 gl_list_t list1
, list2
;
88 /* Allow the user to provide a non-default random seed on the command line. */
90 srand (atoi (argv
[1]));
93 size_t initial_size
= RANDOM (50);
94 const void **contents
=
95 (const void **) malloc (initial_size
* sizeof (const void *));
99 for (i
= 0; i
< initial_size
; i
++)
100 contents
[i
] = RANDOM_OBJECT ();
103 list1
= gl_list_nx_create (GL_ARRAY_LIST
, NULL
, NULL
, NULL
, true,
104 initial_size
, contents
);
105 ASSERT (list1
!= NULL
);
107 list2
= gl_list_nx_create_empty (GL_ARRAY_LIST
, NULL
, NULL
, NULL
, true);
108 ASSERT (list2
!= NULL
);
109 for (i
= 0; i
< initial_size
; i
++)
110 ASSERT (gl_list_nx_add_last (list2
, contents
[i
]) != NULL
);
112 check_equals (list1
, list2
);
114 check_equals_by_forward_iteration (list1
, list2
);
115 check_equals_by_backward_iteration (list1
, list2
);
117 for (repeat
= 0; repeat
< 10000; repeat
++)
119 unsigned int operation
= RANDOM (18);
123 if (gl_list_size (list1
) > 0)
125 size_t index
= RANDOM (gl_list_size (list1
));
126 const char *obj
= RANDOM_OBJECT ();
127 gl_list_node_t node1
, node2
;
129 node1
= gl_list_nx_set_at (list1
, index
, obj
);
130 ASSERT (node1
!= NULL
);
131 ASSERT (gl_list_get_at (list1
, index
) == obj
);
132 ASSERT (gl_list_node_value (list1
, node1
) == obj
);
134 node2
= gl_list_nx_set_at (list2
, index
, obj
);
135 ASSERT (node2
!= NULL
);
136 ASSERT (gl_list_get_at (list2
, index
) == obj
);
137 ASSERT (gl_list_node_value (list2
, node2
) == obj
);
141 ASSERT (gl_list_node_value (list1
, gl_list_previous_node (list1
, node1
))
142 == gl_list_get_at (list1
, index
- 1));
144 if (index
+ 1 < gl_list_size (list1
))
146 ASSERT (gl_list_node_value (list1
, gl_list_next_node (list1
, node1
))
147 == gl_list_get_at (list1
, index
+ 1));
153 const char *obj
= RANDOM_OBJECT ();
154 gl_list_node_t node1
, node2
;
155 node1
= gl_list_search (list1
, obj
);
156 node2
= gl_list_search (list2
, obj
);
159 ASSERT (node2
== NULL
);
163 ASSERT (node2
!= NULL
);
164 ASSERT (gl_list_node_value (list1
, node1
) == obj
);
165 ASSERT (gl_list_node_value (list2
, node2
) == obj
);
171 const char *obj
= RANDOM_OBJECT ();
172 size_t index1
, index2
;
173 index1
= gl_list_indexof (list1
, obj
);
174 index2
= gl_list_indexof (list2
, obj
);
175 if (index1
== (size_t)(-1))
177 ASSERT (index2
== (size_t)(-1));
181 ASSERT (index2
!= (size_t)(-1));
182 ASSERT (gl_list_get_at (list1
, index1
) == obj
);
183 ASSERT (gl_list_get_at (list2
, index2
) == obj
);
184 ASSERT (index2
== index1
);
188 case 3: /* add 1 element */
190 const char *obj
= RANDOM_OBJECT ();
191 gl_list_node_t node1
, node2
;
192 node1
= gl_list_nx_add_first (list1
, obj
);
193 ASSERT (node1
!= NULL
);
194 node2
= gl_list_nx_add_first (list2
, obj
);
195 ASSERT (node2
!= NULL
);
196 ASSERT (gl_list_node_value (list1
, node1
) == obj
);
197 ASSERT (gl_list_node_value (list2
, node2
) == obj
);
198 ASSERT (gl_list_get_at (list1
, 0) == obj
);
199 ASSERT (gl_list_get_at (list2
, 0) == obj
);
202 case 4: /* add 1 element */
204 const char *obj
= RANDOM_OBJECT ();
205 gl_list_node_t node1
, node2
;
206 node1
= gl_list_nx_add_last (list1
, obj
);
207 ASSERT (node1
!= NULL
);
208 node2
= gl_list_nx_add_last (list2
, obj
);
209 ASSERT (node2
!= NULL
);
210 ASSERT (gl_list_node_value (list1
, node1
) == obj
);
211 ASSERT (gl_list_node_value (list2
, node2
) == obj
);
212 ASSERT (gl_list_get_at (list1
, gl_list_size (list1
) - 1) == obj
);
213 ASSERT (gl_list_get_at (list2
, gl_list_size (list2
) - 1) == obj
);
216 case 5: /* add 3 elements */
218 const char *obj0
= RANDOM_OBJECT ();
219 const char *obj1
= RANDOM_OBJECT ();
220 const char *obj2
= RANDOM_OBJECT ();
221 gl_list_node_t node1
, node2
;
222 node1
= gl_list_nx_add_first (list1
, obj2
);
223 ASSERT (node1
!= NULL
);
224 node1
= gl_list_nx_add_before (list1
, node1
, obj0
);
225 ASSERT (node1
!= NULL
);
226 node1
= gl_list_nx_add_after (list1
, node1
, obj1
);
227 ASSERT (node1
!= NULL
);
228 node2
= gl_list_nx_add_first (list2
, obj2
);
229 ASSERT (node2
!= NULL
);
230 node2
= gl_list_nx_add_before (list2
, node2
, obj0
);
231 ASSERT (node2
!= NULL
);
232 node2
= gl_list_nx_add_after (list2
, node2
, obj1
);
233 ASSERT (node2
!= NULL
);
234 ASSERT (gl_list_node_value (list1
, node1
) == obj1
);
235 ASSERT (gl_list_node_value (list2
, node2
) == obj1
);
236 ASSERT (gl_list_get_at (list1
, 0) == obj0
);
237 ASSERT (gl_list_get_at (list1
, 1) == obj1
);
238 ASSERT (gl_list_get_at (list1
, 2) == obj2
);
239 ASSERT (gl_list_get_at (list2
, 0) == obj0
);
240 ASSERT (gl_list_get_at (list2
, 1) == obj1
);
241 ASSERT (gl_list_get_at (list2
, 2) == obj2
);
244 case 6: /* add 1 element */
246 size_t index
= RANDOM (gl_list_size (list1
) + 1);
247 const char *obj
= RANDOM_OBJECT ();
248 gl_list_node_t node1
, node2
;
249 node1
= gl_list_nx_add_at (list1
, index
, obj
);
250 ASSERT (node1
!= NULL
);
251 node2
= gl_list_nx_add_at (list2
, index
, obj
);
252 ASSERT (node2
!= NULL
);
253 ASSERT (gl_list_get_at (list1
, index
) == obj
);
254 ASSERT (gl_list_node_value (list1
, node1
) == obj
);
255 ASSERT (gl_list_get_at (list2
, index
) == obj
);
256 ASSERT (gl_list_node_value (list2
, node2
) == obj
);
259 ASSERT (gl_list_node_value (list1
, gl_list_previous_node (list1
, node1
))
260 == gl_list_get_at (list1
, index
- 1));
262 if (index
+ 1 < gl_list_size (list1
))
264 ASSERT (gl_list_node_value (list1
, gl_list_next_node (list1
, node1
))
265 == gl_list_get_at (list1
, index
+ 1));
269 case 7: case 8: /* remove 1 element */
270 if (gl_list_size (list1
) > 0)
272 size_t n
= gl_list_size (list1
);
273 const char *obj
= gl_list_get_at (list1
, RANDOM (n
));
274 gl_list_node_t node1
, node2
;
275 node1
= gl_list_search (list1
, obj
);
276 node2
= gl_list_search (list2
, obj
);
277 ASSERT (node1
!= NULL
);
278 ASSERT (node2
!= NULL
);
279 ASSERT (gl_list_remove_node (list1
, node1
));
280 ASSERT (gl_list_remove_node (list2
, node2
));
281 ASSERT (gl_list_size (list1
) == n
- 1);
284 case 9: case 10: /* remove 1 element */
285 if (gl_list_size (list1
) > 0)
287 size_t n
= gl_list_size (list1
);
288 size_t index
= RANDOM (n
);
289 ASSERT (gl_list_remove_at (list1
, index
));
290 ASSERT (gl_list_remove_at (list2
, index
));
291 ASSERT (gl_list_size (list1
) == n
- 1);
294 case 11: /* remove first element */
296 size_t n
= gl_list_size (list1
);
297 bool removed1
= gl_list_remove_first (list1
);
298 ASSERT (gl_list_remove_first (list2
) == removed1
);
299 ASSERT (gl_list_size (list1
) == n
- (int) removed1
);
302 case 12: /* remove last element */
304 size_t n
= gl_list_size (list1
);
305 bool removed1
= gl_list_remove_last (list1
);
306 ASSERT (gl_list_remove_last (list2
) == removed1
);
307 ASSERT (gl_list_size (list1
) == n
- (int) removed1
);
310 case 13: case 14: /* remove 1 element */
311 if (gl_list_size (list1
) > 0)
313 size_t n
= gl_list_size (list1
);
314 const char *obj
= gl_list_get_at (list1
, RANDOM (n
));
315 ASSERT (gl_list_remove (list1
, obj
));
316 ASSERT (gl_list_remove (list2
, obj
));
317 ASSERT (gl_list_size (list1
) == n
- 1);
321 if (gl_list_size (list1
) > 0)
323 size_t n
= gl_list_size (list1
);
324 const char *obj
= "xyzzy";
325 ASSERT (!gl_list_remove (list1
, obj
));
326 ASSERT (!gl_list_remove (list2
, obj
));
327 ASSERT (gl_list_size (list1
) == n
);
332 size_t n
= gl_list_size (list1
);
333 gl_list_iterator_t iter1
, iter2
;
335 iter1
= gl_list_iterator (list1
);
336 iter2
= gl_list_iterator (list2
);
337 for (i
= 0; i
< n
; i
++)
339 ASSERT (gl_list_iterator_next (&iter1
, &elt
, NULL
));
340 ASSERT (gl_list_get_at (list1
, i
) == elt
);
341 ASSERT (gl_list_iterator_next (&iter2
, &elt
, NULL
));
342 ASSERT (gl_list_get_at (list2
, i
) == elt
);
344 ASSERT (!gl_list_iterator_next (&iter1
, &elt
, NULL
));
345 ASSERT (!gl_list_iterator_next (&iter2
, &elt
, NULL
));
346 gl_list_iterator_free (&iter1
);
347 gl_list_iterator_free (&iter2
);
352 size_t end
= RANDOM (gl_list_size (list1
) + 1);
353 size_t start
= RANDOM (end
+ 1);
354 gl_list_iterator_t iter1
, iter2
;
356 iter1
= gl_list_iterator_from_to (list1
, start
, end
);
357 iter2
= gl_list_iterator_from_to (list2
, start
, end
);
358 for (i
= start
; i
< end
; i
++)
360 ASSERT (gl_list_iterator_next (&iter1
, &elt
, NULL
));
361 ASSERT (gl_list_get_at (list1
, i
) == elt
);
362 ASSERT (gl_list_iterator_next (&iter2
, &elt
, NULL
));
363 ASSERT (gl_list_get_at (list2
, i
) == elt
);
365 ASSERT (!gl_list_iterator_next (&iter1
, &elt
, NULL
));
366 ASSERT (!gl_list_iterator_next (&iter2
, &elt
, NULL
));
367 gl_list_iterator_free (&iter1
);
368 gl_list_iterator_free (&iter2
);
372 check_equals (list1
, list2
);
375 gl_list_free (list1
);
376 gl_list_free (list2
);
380 return test_exit_status
;