1
/* Test of sequential list data type implementation.
2
Copyright (C) 2006-2010 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 <http://www.gnu.org/licenses/>. */
20
#include "gl_linkedhash_list.h"
26
#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 SIZE_BITS (sizeof (size_t) * CHAR_BIT)
38
string_equals (const void *x1, const void *x2)
42
return strcmp (s1, s2) == 0;
45
/* A hash function for NUL-terminated char* strings using
46
the method described by Bruno Haible.
47
See http://www.haible.de/bruno/hashfunc.html. */
49
string_hash (const void *x)
55
h = *s + ((h << 9) | (h >> (SIZE_BITS - 9)));
60
#define RANDOM(n) (rand () % (n))
61
#define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
64
check_equals (gl_list_t list1, gl_list_t list2)
68
n = gl_list_size (list1);
69
ASSERT (n == gl_list_size (list2));
70
for (i = 0; i < n; i++)
72
ASSERT (gl_list_get_at (list1, i) == gl_list_get_at (list2, i));
77
check_all (gl_list_t list1, gl_list_t list2, gl_list_t list3)
79
check_equals (list1, list2);
80
check_equals (list1, list3);
84
main (int argc, char *argv[])
86
gl_list_t list1, list2, list3;
88
set_program_name (argv[0]);
90
/* Allow the user to provide a non-default random seed on the command line. */
92
srand (atoi (argv[1]));
95
size_t initial_size = RANDOM (50);
96
const void **contents =
97
(const void **) malloc (initial_size * sizeof (const void *));
101
for (i = 0; i < initial_size; i++)
102
contents[i] = RANDOM_OBJECT ();
105
list1 = gl_list_nx_create (GL_ARRAY_LIST,
106
string_equals, string_hash, NULL, true,
107
initial_size, contents);
108
ASSERT (list1 != NULL);
110
list2 = gl_list_nx_create_empty (GL_LINKEDHASH_LIST,
111
string_equals, string_hash, NULL, true);
112
ASSERT (list2 != NULL);
113
for (i = 0; i < initial_size; i++)
114
ASSERT (gl_list_nx_add_last (list2, contents[i]) != NULL);
117
list3 = gl_list_nx_create (GL_LINKEDHASH_LIST,
118
string_equals, string_hash, NULL, true,
119
initial_size, contents);
120
ASSERT (list3 != NULL);
122
check_all (list1, list2, list3);
124
for (repeat = 0; repeat < 10000; repeat++)
126
unsigned int operation = RANDOM (16);
130
if (gl_list_size (list1) > 0)
132
size_t index = RANDOM (gl_list_size (list1));
133
const char *obj = RANDOM_OBJECT ();
134
gl_list_node_t node1, node2, node3;
136
node1 = gl_list_nx_set_at (list1, index, obj);
137
ASSERT (node1 != NULL);
138
ASSERT (gl_list_get_at (list1, index) == obj);
139
ASSERT (gl_list_node_value (list1, node1) == obj);
141
node2 = gl_list_nx_set_at (list2, index, obj);
142
ASSERT (node2 != NULL);
143
ASSERT (gl_list_get_at (list2, index) == obj);
144
ASSERT (gl_list_node_value (list2, node2) == obj);
146
node3 = gl_list_nx_set_at (list3, index, obj);
147
ASSERT (node3 != NULL);
148
ASSERT (gl_list_get_at (list3, index) == obj);
149
ASSERT (gl_list_node_value (list3, node3) == obj);
153
ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
154
== gl_list_get_at (list1, index - 1));
155
ASSERT (gl_list_node_value (list2, gl_list_previous_node (list3, node3))
156
== gl_list_get_at (list2, index - 1));
157
ASSERT (gl_list_node_value (list3, gl_list_previous_node (list3, node3))
158
== gl_list_get_at (list2, index - 1));
160
if (index + 1 < gl_list_size (list1))
162
ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
163
== gl_list_get_at (list1, index + 1));
164
ASSERT (gl_list_node_value (list2, gl_list_next_node (list3, node3))
165
== gl_list_get_at (list2, index + 1));
166
ASSERT (gl_list_node_value (list3, gl_list_next_node (list3, node3))
167
== gl_list_get_at (list2, index + 1));
173
const char *obj = RANDOM_OBJECT ();
174
gl_list_node_t node1, node2, node3;
175
node1 = gl_list_search (list1, obj);
176
node2 = gl_list_search (list2, obj);
177
node3 = gl_list_search (list3, obj);
180
ASSERT (node2 == NULL);
181
ASSERT (node3 == NULL);
185
ASSERT (node2 != NULL);
186
ASSERT (node3 != NULL);
187
ASSERT (gl_list_node_value (list1, node1) == obj);
188
ASSERT (gl_list_node_value (list2, node2) == obj);
189
ASSERT (gl_list_node_value (list3, node3) == obj);
195
const char *obj = RANDOM_OBJECT ();
196
size_t index1, index2, index3;
197
index1 = gl_list_indexof (list1, obj);
198
index2 = gl_list_indexof (list2, obj);
199
index3 = gl_list_indexof (list3, obj);
200
if (index1 == (size_t)(-1))
202
ASSERT (index2 == (size_t)(-1));
203
ASSERT (index3 == (size_t)(-1));
207
ASSERT (index2 != (size_t)(-1));
208
ASSERT (index3 != (size_t)(-1));
209
ASSERT (gl_list_get_at (list1, index1) == obj);
210
ASSERT (gl_list_get_at (list2, index2) == obj);
211
ASSERT (gl_list_get_at (list3, index3) == obj);
212
ASSERT (index2 == index1);
213
ASSERT (index3 == index1);
217
case 3: /* add 1 element */
219
const char *obj = RANDOM_OBJECT ();
220
gl_list_node_t node1, node2, node3;
221
node1 = gl_list_nx_add_first (list1, obj);
222
ASSERT (node1 != NULL);
223
node2 = gl_list_nx_add_first (list2, obj);
224
ASSERT (node2 != NULL);
225
node3 = gl_list_nx_add_first (list3, obj);
226
ASSERT (node3 != NULL);
227
ASSERT (gl_list_node_value (list1, node1) == obj);
228
ASSERT (gl_list_node_value (list2, node2) == obj);
229
ASSERT (gl_list_node_value (list3, node3) == obj);
230
ASSERT (gl_list_get_at (list1, 0) == obj);
231
ASSERT (gl_list_get_at (list2, 0) == obj);
232
ASSERT (gl_list_get_at (list3, 0) == obj);
235
case 4: /* add 1 element */
237
const char *obj = RANDOM_OBJECT ();
238
gl_list_node_t node1, node2, node3;
239
node1 = gl_list_nx_add_last (list1, obj);
240
ASSERT (node1 != NULL);
241
node2 = gl_list_nx_add_last (list2, obj);
242
ASSERT (node2 != NULL);
243
node3 = gl_list_nx_add_last (list3, obj);
244
ASSERT (node3 != NULL);
245
ASSERT (gl_list_node_value (list1, node1) == obj);
246
ASSERT (gl_list_node_value (list2, node2) == obj);
247
ASSERT (gl_list_node_value (list3, node3) == obj);
248
ASSERT (gl_list_get_at (list1, gl_list_size (list1) - 1) == obj);
249
ASSERT (gl_list_get_at (list2, gl_list_size (list2) - 1) == obj);
250
ASSERT (gl_list_get_at (list3, gl_list_size (list3) - 1) == obj);
253
case 5: /* add 3 elements */
255
const char *obj0 = RANDOM_OBJECT ();
256
const char *obj1 = RANDOM_OBJECT ();
257
const char *obj2 = RANDOM_OBJECT ();
258
gl_list_node_t node1, node2, node3;
259
node1 = gl_list_nx_add_first (list1, obj2);
260
ASSERT (node1 != NULL);
261
node1 = gl_list_nx_add_before (list1, node1, obj0);
262
ASSERT (node1 != NULL);
263
node1 = gl_list_nx_add_after (list1, node1, obj1);
264
ASSERT (node1 != NULL);
265
node2 = gl_list_nx_add_first (list2, obj2);
266
ASSERT (node2 != NULL);
267
node2 = gl_list_nx_add_before (list2, node2, obj0);
268
ASSERT (node2 != NULL);
269
node2 = gl_list_nx_add_after (list2, node2, obj1);
270
ASSERT (node2 != NULL);
271
node3 = gl_list_nx_add_first (list3, obj2);
272
ASSERT (node3 != NULL);
273
node3 = gl_list_nx_add_before (list3, node3, obj0);
274
ASSERT (node3 != NULL);
275
node3 = gl_list_nx_add_after (list3, node3, obj1);
276
ASSERT (node3 != NULL);
277
ASSERT (gl_list_node_value (list1, node1) == obj1);
278
ASSERT (gl_list_node_value (list2, node2) == obj1);
279
ASSERT (gl_list_node_value (list3, node3) == obj1);
280
ASSERT (gl_list_get_at (list1, 0) == obj0);
281
ASSERT (gl_list_get_at (list1, 1) == obj1);
282
ASSERT (gl_list_get_at (list1, 2) == obj2);
283
ASSERT (gl_list_get_at (list2, 0) == obj0);
284
ASSERT (gl_list_get_at (list2, 1) == obj1);
285
ASSERT (gl_list_get_at (list2, 2) == obj2);
286
ASSERT (gl_list_get_at (list3, 0) == obj0);
287
ASSERT (gl_list_get_at (list3, 1) == obj1);
288
ASSERT (gl_list_get_at (list3, 2) == obj2);
291
case 6: /* add 1 element */
293
size_t index = RANDOM (gl_list_size (list1) + 1);
294
const char *obj = RANDOM_OBJECT ();
295
gl_list_node_t node1, node2, node3;
296
node1 = gl_list_nx_add_at (list1, index, obj);
297
ASSERT (node1 != NULL);
298
node2 = gl_list_nx_add_at (list2, index, obj);
299
ASSERT (node2 != NULL);
300
node3 = gl_list_nx_add_at (list3, index, obj);
301
ASSERT (node3 != NULL);
302
ASSERT (gl_list_get_at (list1, index) == obj);
303
ASSERT (gl_list_node_value (list1, node1) == obj);
304
ASSERT (gl_list_get_at (list2, index) == obj);
305
ASSERT (gl_list_node_value (list2, node2) == obj);
306
ASSERT (gl_list_get_at (list3, index) == obj);
307
ASSERT (gl_list_node_value (list3, node3) == obj);
310
ASSERT (gl_list_node_value (list1, gl_list_previous_node (list1, node1))
311
== gl_list_get_at (list1, index - 1));
312
ASSERT (gl_list_node_value (list2, gl_list_previous_node (list3, node3))
313
== gl_list_get_at (list2, index - 1));
314
ASSERT (gl_list_node_value (list3, gl_list_previous_node (list3, node3))
315
== gl_list_get_at (list2, index - 1));
317
if (index + 1 < gl_list_size (list1))
319
ASSERT (gl_list_node_value (list1, gl_list_next_node (list1, node1))
320
== gl_list_get_at (list1, index + 1));
321
ASSERT (gl_list_node_value (list2, gl_list_next_node (list3, node3))
322
== gl_list_get_at (list2, index + 1));
323
ASSERT (gl_list_node_value (list3, gl_list_next_node (list3, node3))
324
== gl_list_get_at (list2, index + 1));
328
case 7: case 8: /* remove 1 element */
329
if (gl_list_size (list1) > 0)
331
size_t n = gl_list_size (list1);
332
const char *obj = gl_list_get_at (list1, RANDOM (n));
333
gl_list_node_t node1, node2, node3;
334
node1 = gl_list_search (list1, obj);
335
node2 = gl_list_search (list2, obj);
336
node3 = gl_list_search (list3, obj);
337
ASSERT (node1 != NULL);
338
ASSERT (node2 != NULL);
339
ASSERT (node3 != NULL);
340
ASSERT (gl_list_remove_node (list1, node1));
341
ASSERT (gl_list_remove_node (list2, node2));
342
ASSERT (gl_list_remove_node (list3, node3));
343
ASSERT (gl_list_size (list1) == n - 1);
346
case 9: case 10: /* remove 1 element */
347
if (gl_list_size (list1) > 0)
349
size_t n = gl_list_size (list1);
350
size_t index = RANDOM (n);
351
ASSERT (gl_list_remove_at (list1, index));
352
ASSERT (gl_list_remove_at (list2, index));
353
ASSERT (gl_list_remove_at (list3, index));
354
ASSERT (gl_list_size (list1) == n - 1);
357
case 11: case 12: /* remove 1 element */
358
if (gl_list_size (list1) > 0)
360
size_t n = gl_list_size (list1);
361
const char *obj = gl_list_get_at (list1, RANDOM (n));
362
ASSERT (gl_list_remove (list1, obj));
363
ASSERT (gl_list_remove (list2, obj));
364
ASSERT (gl_list_remove (list3, obj));
365
ASSERT (gl_list_size (list1) == n - 1);
369
if (gl_list_size (list1) > 0)
371
size_t n = gl_list_size (list1);
372
const char *obj = "xyzzy";
373
ASSERT (!gl_list_remove (list1, obj));
374
ASSERT (!gl_list_remove (list2, obj));
375
ASSERT (!gl_list_remove (list3, obj));
376
ASSERT (gl_list_size (list1) == n);
381
size_t n = gl_list_size (list1);
382
gl_list_iterator_t iter1, iter2, iter3;
384
iter1 = gl_list_iterator (list1);
385
iter2 = gl_list_iterator (list2);
386
iter3 = gl_list_iterator (list3);
387
for (i = 0; i < n; i++)
389
ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
390
ASSERT (gl_list_get_at (list1, i) == elt);
391
ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
392
ASSERT (gl_list_get_at (list2, i) == elt);
393
ASSERT (gl_list_iterator_next (&iter3, &elt, NULL));
394
ASSERT (gl_list_get_at (list3, i) == elt);
396
ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
397
ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
398
ASSERT (!gl_list_iterator_next (&iter3, &elt, NULL));
399
gl_list_iterator_free (&iter1);
400
gl_list_iterator_free (&iter2);
401
gl_list_iterator_free (&iter3);
406
size_t end = RANDOM (gl_list_size (list1) + 1);
407
size_t start = RANDOM (end + 1);
408
gl_list_iterator_t iter1, iter2, iter3;
410
iter1 = gl_list_iterator_from_to (list1, start, end);
411
iter2 = gl_list_iterator_from_to (list2, start, end);
412
iter3 = gl_list_iterator_from_to (list3, start, end);
413
for (i = start; i < end; i++)
415
ASSERT (gl_list_iterator_next (&iter1, &elt, NULL));
416
ASSERT (gl_list_get_at (list1, i) == elt);
417
ASSERT (gl_list_iterator_next (&iter2, &elt, NULL));
418
ASSERT (gl_list_get_at (list2, i) == elt);
419
ASSERT (gl_list_iterator_next (&iter3, &elt, NULL));
420
ASSERT (gl_list_get_at (list3, i) == elt);
422
ASSERT (!gl_list_iterator_next (&iter1, &elt, NULL));
423
ASSERT (!gl_list_iterator_next (&iter2, &elt, NULL));
424
ASSERT (!gl_list_iterator_next (&iter3, &elt, NULL));
425
gl_list_iterator_free (&iter1);
426
gl_list_iterator_free (&iter2);
427
gl_list_iterator_free (&iter3);
431
check_all (list1, list2, list3);
434
gl_list_free (list1);
435
gl_list_free (list2);
436
gl_list_free (list3);