1 /* Test of sequential list data type implementation.
2 Copyright (C) 2006-2007 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 2, or (at your option)
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, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
23 #include "gl_array_list.h"
30 static const char *objects[15] =
32 "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o"
35 #define SIZEOF(array) (sizeof (array) / sizeof (array[0]))
36 #define ASSERT(expr) \
41 fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \
46 #define RANDOM(n) (rand () % (n))
47 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
50 check_equals (gl_list_t list1, gl_list_t list2)
54 n = gl_list_size (list1);
55 ASSERT (n == gl_list_size (list2));
56 for (i = 0; i < n; i++)
58 ASSERT (gl_list_get_at (list1, i) == gl_list_get_at (list2, i));
63 main (int argc, char *argv[])
65 gl_list_t list1, list2;
67 set_program_name (argv[0]);
69 /* Allow the user to provide a non-default random seed on the command line. */
71 srand (atoi (argv[1]));
74 size_t initial_size = RANDOM (50);
75 const void **contents =
76 (const void **) malloc (initial_size * sizeof (const void *));
80 for (i = 0; i < initial_size; i++)
81 contents[i] = RANDOM_OBJECT ();
84 list1 = gl_list_create (GL_ARRAY_LIST, NULL, NULL, NULL, true,
85 initial_size, contents);
87 list2 = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, true);
88 for (i = 0; i < initial_size; i++)
89 gl_list_add_last (list2, contents[i]);
91 check_equals (list1, list2);
93 for (repeat = 0; repeat < 10000; repeat++)
95 unsigned int operation = RANDOM (16);
99 if (gl_list_size (list1) > 0)
101 size_t index = RANDOM (gl_list_size (list1));
102 const char *obj = RANDOM_OBJECT ();
103 gl_list_node_t node1, node2;
105 node1 = gl_list_set_at (list1, index, obj);
106 ASSERT (gl_list_get_at (list1, index) == obj);
107 ASSERT (gl_list_node_value (list1, node1) == obj);
109 node2 = gl_list_set_at (list2, index, obj);
110 ASSERT (gl_list_get_at (list2, index) == obj);
111 ASSERT (gl_list_node_value (list2, node2) == obj);
115 ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
116 == gl_list_get_at (list1, index - 1));
118 if (index + 1 < gl_list_size (list1))
120 ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
121 == gl_list_get_at (list1, index + 1));
127 const char *obj = RANDOM_OBJECT ();
128 gl_list_node_t node1, node2;
129 node1 = gl_list_search (list1, obj);
130 node2 = gl_list_search (list2, obj);
133 ASSERT (node2 == NULL);
137 ASSERT (node2 != NULL);
138 ASSERT (gl_list_node_value (list1, node1) == obj);
139 ASSERT (gl_list_node_value (list2, node2) == obj);
145 const char *obj = RANDOM_OBJECT ();
146 size_t index1, index2;
147 index1 = gl_list_indexof (list1, obj);
148 index2 = gl_list_indexof (list2, obj);
149 if (index1 == (size_t)(-1))
151 ASSERT (index2 == (size_t)(-1));
155 ASSERT (index2 != (size_t)(-1));
156 ASSERT (gl_list_get_at (list1, index1) == obj);
157 ASSERT (gl_list_get_at (list2, index2) == obj);
158 ASSERT (index2 == index1);
162 case 3: /* add 1 element */
164 const char *obj = RANDOM_OBJECT ();
165 gl_list_node_t node1, node2;
166 node1 = gl_list_add_first (list1, obj);
167 node2 = gl_list_add_first (list2, obj);
168 ASSERT (gl_list_node_value (list1, node1) == obj);
169 ASSERT (gl_list_node_value (list2, node2) == obj);
170 ASSERT (gl_list_get_at (list1, 0) == obj);
171 ASSERT (gl_list_get_at (list2, 0) == obj);
174 case 4: /* add 1 element */
176 const char *obj = RANDOM_OBJECT ();
177 gl_list_node_t node1, node2;
178 node1 = gl_list_add_last (list1, obj);
179 node2 = gl_list_add_last (list2, obj);
180 ASSERT (gl_list_node_value (list1, node1) == obj);
181 ASSERT (gl_list_node_value (list2, node2) == obj);
182 ASSERT (gl_list_get_at (list1, gl_list_size (list1) - 1) == obj);
183 ASSERT (gl_list_get_at (list2, gl_list_size (list2) - 1) == obj);
186 case 5: /* add 3 elements */
188 const char *obj0 = RANDOM_OBJECT ();
189 const char *obj1 = RANDOM_OBJECT ();
190 const char *obj2 = RANDOM_OBJECT ();
191 gl_list_node_t node1, node2;
192 node1 = gl_list_add_first (list1, obj2);
193 node1 = gl_list_add_before (list1, node1, obj0);
194 node1 = gl_list_add_after (list1, node1, obj1);
195 node2 = gl_list_add_first (list2, obj2);
196 node2 = gl_list_add_before (list2, node2, obj0);
197 node2 = gl_list_add_after (list2, node2, obj1);
198 ASSERT (gl_list_node_value (list1, node1) == obj1);
199 ASSERT (gl_list_node_value (list2, node2) == obj1);
200 ASSERT (gl_list_get_at (list1, 0) == obj0);
201 ASSERT (gl_list_get_at (list1, 1) == obj1);
202 ASSERT (gl_list_get_at (list1, 2) == obj2);
203 ASSERT (gl_list_get_at (list2, 0) == obj0);
204 ASSERT (gl_list_get_at (list2, 1) == obj1);
205 ASSERT (gl_list_get_at (list2, 2) == obj2);
208 case 6: /* add 1 element */
210 size_t index = RANDOM (gl_list_size (list1) + 1);
211 const char *obj = RANDOM_OBJECT ();
212 gl_list_node_t node1, node2;
213 node1 = gl_list_add_at (list1, index, obj);
214 node2 = gl_list_add_at (list2, index, obj);
215 ASSERT (gl_list_get_at (list1, index) == obj);
216 ASSERT (gl_list_node_value (list1, node1) == obj);
217 ASSERT (gl_list_get_at (list2, index) == obj);
218 ASSERT (gl_list_node_value (list2, node2) == obj);
221 ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
222 == gl_list_get_at (list1, index - 1));
224 if (index + 1 < gl_list_size (list1))
226 ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
227 == gl_list_get_at (list1, index + 1));
231 case 7: case 8: /* remove 1 element */
232 if (gl_list_size (list1) > 0)
234 size_t n = gl_list_size (list1);
235 const char *obj = gl_list_get_at (list1, RANDOM (n));
236 gl_list_node_t node1, node2;
237 node1 = gl_list_search (list1, obj);
238 node2 = gl_list_search (list2, obj);
239 ASSERT (node1 != NULL);
240 ASSERT (node2 != NULL);
241 ASSERT (gl_list_remove_node (list1, node1));
242 ASSERT (gl_list_remove_node (list2, node2));
243 ASSERT (gl_list_size (list1) == n - 1);
246 case 9: case 10: /* remove 1 element */
247 if (gl_list_size (list1) > 0)
249 size_t n = gl_list_size (list1);
250 size_t index = RANDOM (n);
251 ASSERT (gl_list_remove_at (list1, index));
252 ASSERT (gl_list_remove_at (list2, index));
253 ASSERT (gl_list_size (list1) == n - 1);
256 case 11: case 12: /* remove 1 element */
257 if (gl_list_size (list1) > 0)
259 size_t n = gl_list_size (list1);
260 const char *obj = gl_list_get_at (list1, RANDOM (n));
261 ASSERT (gl_list_remove (list1, obj));
262 ASSERT (gl_list_remove (list2, obj));
263 ASSERT (gl_list_size (list1) == n - 1);
267 if (gl_list_size (list1) > 0)
269 size_t n = gl_list_size (list1);
270 const char *obj = "xyzzy";
271 ASSERT (!gl_list_remove (list1, obj));
272 ASSERT (!gl_list_remove (list2, obj));
273 ASSERT (gl_list_size (list1) == n);
278 size_t n = gl_list_size (list1);
279 gl_list_iterator_t iter1, iter2;
281 iter1 = gl_list_iterator (list1);
282 iter2 = gl_list_iterator (list2);
283 for (i = 0; i < n; i++)
285 ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
286 ASSERT (gl_list_get_at (list1, i) == elt);
287 ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
288 ASSERT (gl_list_get_at (list2, i) == elt);
290 ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
291 ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
292 gl_list_iterator_free (&iter1);
293 gl_list_iterator_free (&iter2);
298 size_t end = RANDOM (gl_list_size (list1) + 1);
299 size_t start = RANDOM (end + 1);
300 gl_list_iterator_t iter1, iter2;
302 iter1 = gl_list_iterator_from_to (list1, start, end);
303 iter2 = gl_list_iterator_from_to (list2, start, end);
304 for (i = start; i < end; i++)
306 ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
307 ASSERT (gl_list_get_at (list1, i) == elt);
308 ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
309 ASSERT (gl_list_get_at (list2, i) == elt);
311 ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
312 ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
313 gl_list_iterator_free (&iter1);
314 gl_list_iterator_free (&iter2);
318 check_equals (list1, list2);
321 gl_list_free (list1);
322 gl_list_free (list2);