1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2009, 2010 Free Software Foundation, Inc.
3
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
16
17 /* This is a test program for the sparse array routines defined
18 in sparse-array.c. This test program aims to be as
19 comprehensive as possible. "gcov -b" should report 100%
20 coverage of lines and branches in sparse-array.c when compiled
21 with -DNDEBUG and BITS_PER_LEVEL is greater than the number of
22 bits in a long. "valgrind --leak-check=yes
23 --show-reachable=yes" should give a clean report. */
24
25 #ifdef HAVE_CONFIG_H
26 #include <config.h>
27 #endif
28
29 #include <libpspp/sparse-array.h>
30 #include <assert.h>
31 #include <limits.h>
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <string.h>
35
36 /* Support preliminaries. */
37 #if __GNUC__ >= 2 && !defined UNUSED
38 #define UNUSED __attribute__ ((unused))
39 #else
40 #define UNUSED
41 #endif
42
43 /* Exit with a failure code.
44 (Place a breakpoint on this function while debugging.) */
45 static void
check_die(void)46 check_die (void)
47 {
48 exit (EXIT_FAILURE);
49 }
50
51 /* If OK is not true, prints a message about failure on the
52 current source file and the given LINE and terminates. */
53 static void
check_func(bool ok,int line)54 check_func (bool ok, int line)
55 {
56 if (!ok)
57 {
58 fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
59 check_die ();
60 }
61 }
62
63 /* Verifies that EXPR evaluates to true.
64 If not, prints a message citing the calling line number and
65 terminates. */
66 #define check(EXPR) check_func ((EXPR), __LINE__)
67
68 /* Prints a message about memory exhaustion and exits with a
69 failure code. */
70 static void
xalloc_die(void)71 xalloc_die (void)
72 {
73 printf ("virtual memory exhausted\n");
74 exit (EXIT_FAILURE);
75 }
76
77 /* Allocates and returns N bytes of memory. */
78 static void *
xmalloc(size_t n)79 xmalloc (size_t n)
80 {
81 if (n != 0)
82 {
83 void *p = malloc (n);
84 if (p == NULL)
85 xalloc_die ();
86
87 return p;
88 }
89 else
90 return NULL;
91 }
92
93 /* Returns a malloc()'d duplicate of the N bytes starting at
94 P. */
95 static void *
xmemdup(const void * p,size_t n)96 xmemdup (const void *p, size_t n)
97 {
98 void *q = xmalloc (n);
99 memcpy (q, p, n);
100 return q;
101 }
102
103 /* Allocates and returns N * M bytes of memory. */
104 static void *
xnmalloc(size_t n,size_t m)105 xnmalloc (size_t n, size_t m)
106 {
107 if ((size_t) -1 / m <= n)
108 xalloc_die ();
109 return xmalloc (n * m);
110 }
111
112 /* Compares A and B and returns a strcmp-type return value. */
113 static int
compare_unsigned_longs_noaux(const void * a_,const void * b_)114 compare_unsigned_longs_noaux (const void *a_, const void *b_)
115 {
116 const unsigned long *a = a_;
117 const unsigned long *b = b_;
118
119 return *a < *b ? -1 : *a > *b;
120 }
121
122 /* Checks that SPAR contains the CNT ints in DATA, that its
123 structure is correct, and that certain operations on SPAR
124 produce the expected results. */
125 static void
check_sparse_array(struct sparse_array * spar,const unsigned long data[],size_t cnt)126 check_sparse_array (struct sparse_array *spar,
127 const unsigned long data[], size_t cnt)
128 {
129 unsigned long idx;
130 unsigned long *order;
131 unsigned long *p;
132 size_t i;
133
134 check (sparse_array_count (spar) == cnt);
135
136 for (i = 0; i < cnt; i++)
137 {
138 p = sparse_array_get (spar, data[i]);
139 check (p != NULL);
140 check (*p == data[i]);
141 }
142
143 order = xmemdup (data, cnt * sizeof *data);
144 qsort (order, cnt, sizeof *order, compare_unsigned_longs_noaux);
145
146 for (i = 0; i < cnt; i++)
147 {
148 p = sparse_array_get (spar, order[i]);
149 check (p != NULL);
150 check (*p == order[i]);
151 }
152
153 if (cnt > 0 && order[0] - 1 != order[cnt - 1])
154 {
155 check (sparse_array_get (spar, order[0] - 1) == NULL);
156 check (!sparse_array_remove (spar, order[0] - 1));
157 }
158 if (cnt > 0 && order[0] != order[cnt - 1] + 1)
159 {
160 check (sparse_array_get (spar, order[cnt - 1] + 1) == NULL);
161 check (!sparse_array_remove (spar, order[cnt - 1] + 1));
162 }
163
164 for (i = 0, p = sparse_array_first (spar, &idx); i < cnt;
165 i++, p = sparse_array_next (spar, idx, &idx))
166 {
167 check (p != NULL);
168 check (idx == order[i]);
169 check (*p == order[i]);
170 }
171 check (p == NULL);
172
173 for (i = 0, p = sparse_array_last (spar, &idx); i < cnt;
174 i++, p = sparse_array_prev (spar, idx, &idx))
175 {
176 check (p != NULL);
177 check (idx == order[cnt - i - 1]);
178 check (*p == order[cnt - i - 1]);
179 }
180 check (p == NULL);
181
182 free (order);
183 }
184
185 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into a
186 sparse array in the order specified by INSERTIONS, then
187 deletes them in the order specified by DELETIONS, checking the
188 array's contents for correctness after each operation. */
189 static void
test_insert_delete(const unsigned long insertions[],const unsigned long deletions[],size_t cnt)190 test_insert_delete (const unsigned long insertions[],
191 const unsigned long deletions[],
192 size_t cnt)
193 {
194 struct sparse_array *spar;
195 size_t i;
196
197 spar = sparse_array_create (sizeof *insertions);
198 for (i = 0; i < cnt; i++)
199 {
200 unsigned long *p = sparse_array_insert (spar, insertions[i]);
201 *p = insertions[i];
202 check_sparse_array (spar, insertions, i + 1);
203 }
204 for (i = 0; i < cnt; i++)
205 {
206 bool deleted = sparse_array_remove (spar, deletions[i]);
207 check (deleted);
208 check_sparse_array (spar, deletions + i + 1, cnt - (i + 1));
209 }
210 check_sparse_array (spar, NULL, 0);
211 sparse_array_destroy (spar);
212 }
213
214 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into a
215 sparse array in the order specified by INSERTIONS, then
216 destroys the sparse array, to check that sparse_cases_destroy
217 properly frees all the nodes. */
218 static void
test_destroy(const unsigned long insertions[],size_t cnt)219 test_destroy (const unsigned long insertions[], size_t cnt)
220 {
221 struct sparse_array *spar;
222 size_t i;
223
224 spar = sparse_array_create (sizeof *insertions);
225 for (i = 0; i < cnt; i++)
226 {
227 unsigned long *p = sparse_array_insert (spar, insertions[i]);
228 *p = insertions[i];
229 check_sparse_array (spar, insertions, i + 1);
230 }
231 sparse_array_destroy (spar);
232 }
233
234 /* Randomly shuffles the CNT elements in ARRAY, each of which is
235 SIZE bytes in size. */
236 static void
random_shuffle(void * array_,size_t cnt,size_t size)237 random_shuffle (void *array_, size_t cnt, size_t size)
238 {
239 char *array = array_;
240 char *tmp = xmalloc (size);
241 size_t i;
242
243 for (i = 0; i < cnt; i++)
244 {
245 size_t j = rand () % (cnt - i) + i;
246 if (i != j)
247 {
248 memcpy (tmp, array + j * size, size);
249 memcpy (array + j * size, array + i * size, size);
250 memcpy (array + i * size, tmp, size);
251 }
252 }
253
254 free (tmp);
255 }
256
257 /* Tests inserting and deleting elements whose values are
258 determined by starting from various offsets and skipping
259 across various strides, and doing so in various orders. */
260 static void
test_insert_delete_strides(void)261 test_insert_delete_strides (void)
262 {
263 static const unsigned long strides[] =
264 {
265 1, 2, 4, 16, 64, 4096, 262144, 16777216,
266 3, 5, 17, 67, 4099, 262147, 16777259,
267 };
268 const size_t stride_cnt = sizeof strides / sizeof *strides;
269
270 static const unsigned long offsets[] =
271 {
272 0,
273 1024ul * 1024 + 1,
274 1024ul * 1024 * 512 + 23,
275 ULONG_MAX - 59,
276 };
277 const size_t offset_cnt = sizeof offsets / sizeof *offsets;
278
279 int cnt = 100;
280 unsigned long *insertions, *deletions;
281 const unsigned long *stride, *offset;
282
283 insertions = xnmalloc (cnt, sizeof *insertions);
284 deletions = xnmalloc (cnt, sizeof *deletions);
285 for (stride = strides; stride < strides + stride_cnt; stride++)
286 {
287 printf ("%lu\n", *stride);
288 for (offset = offsets; offset < offsets + offset_cnt; offset++)
289 {
290 int k;
291
292 for (k = 0; k < cnt; k++)
293 insertions[k] = *stride * k + *offset;
294
295 test_insert_delete (insertions, insertions, cnt);
296 test_destroy (insertions, cnt);
297
298 for (k = 0; k < cnt; k++)
299 deletions[k] = insertions[cnt - k - 1];
300 test_insert_delete (insertions, deletions, cnt);
301
302 random_shuffle (insertions, cnt, sizeof *insertions);
303 test_insert_delete (insertions, insertions, cnt);
304 test_insert_delete (insertions, deletions, cnt);
305 }
306 }
307 free (insertions);
308 free (deletions);
309 }
310
311 /* Returns the index in ARRAY of the (CNT+1)th element that has
312 the TARGET value. */
313 static int
scan_bools(bool target,bool array[],size_t cnt)314 scan_bools (bool target, bool array[], size_t cnt)
315 {
316 size_t i;
317
318 for (i = 0; ; i++)
319 if (array[i] == target && cnt-- == 0)
320 return i;
321 }
322
323 /* Performs a random sequence of insertions and deletions in a
324 sparse array. */
325 static void
test_random_insert_delete(void)326 test_random_insert_delete (void)
327 {
328 unsigned long int values[] =
329 {
330 0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096,
331 8192, 16384, 32768, 65536, 131072, 262144, 4194304, 8388608,
332 16777216, 33554432, 67108864, 134217728, 268435456, 536870912,
333 1073741824, 2147483648,
334
335 3, 7, 15, 31, 63, 127, 257, 511, 1023, 2047, 4095,
336 8191, 16383, 32767, 65535, 131071, 262143, 4194303, 8388607,
337 16777215, 33554431, 67108863, 134217727, 268435455, 536870911,
338 1073741823, 2147483647, 4294967295,
339 };
340 const int max_values = sizeof values / sizeof *values;
341
342 const int num_actions = 250000;
343 struct sparse_array *spar;
344 bool *has_values;
345 int cnt;
346 int insert_chance;
347 int i;
348
349 has_values = xnmalloc (max_values, sizeof *has_values);
350 memset (has_values, 0, max_values * sizeof *has_values);
351
352 cnt = 0;
353 insert_chance = 5;
354
355 spar = sparse_array_create (sizeof *values);
356 for (i = 0; i < num_actions; i++)
357 {
358 enum { INSERT, DELETE } action;
359 unsigned long *p;
360 int j;
361
362 if (cnt == 0)
363 {
364 action = INSERT;
365 if (insert_chance < 9)
366 insert_chance++;
367 }
368 else if (cnt == max_values)
369 {
370 action = DELETE;
371 if (insert_chance > 0)
372 insert_chance--;
373 }
374 else
375 action = rand () % 10 < insert_chance ? INSERT : DELETE;
376
377 if (action == INSERT)
378 {
379 int ins_index;
380
381 ins_index = scan_bools (false, has_values,
382 rand () % (max_values - cnt));
383 assert (has_values[ins_index] == false);
384 has_values[ins_index] = true;
385
386 p = sparse_array_insert (spar, values[ins_index]);
387 check (p != NULL);
388 *p = values[ins_index];
389
390 cnt++;
391 }
392 else if (action == DELETE)
393 {
394 int del_index;
395
396 del_index = scan_bools (true, has_values, rand () % cnt);
397 assert (has_values[del_index] == true);
398 has_values[del_index] = false;
399
400 check (sparse_array_remove (spar, values[del_index]));
401 cnt--;
402 }
403 else
404 abort ();
405
406 check (sparse_array_count (spar) == cnt);
407 for (j = 0; j < max_values; j++)
408 {
409 p = sparse_array_get (spar, values[j]);
410 if (has_values[j])
411 {
412 check (p != NULL);
413 check (*p == values[j]);
414 }
415 else
416 {
417 check (p == NULL);
418 if (rand () % 10 == 0)
419 sparse_array_remove (spar, values[j]);
420 }
421 }
422 }
423 sparse_array_destroy (spar);
424 free (has_values);
425 }
426
427 /* Main program. */
428
429 struct test
430 {
431 const char *name;
432 const char *description;
433 void (*function) (void);
434 };
435
436 static const struct test tests[] =
437 {
438 {
439 "random-insert-delete",
440 "random insertions and deletions",
441 test_random_insert_delete
442 },
443 {
444 "insert-delete-strides",
445 "insert in ascending order with strides and offset",
446 test_insert_delete_strides
447 },
448 };
449
450 enum { N_TESTS = sizeof tests / sizeof *tests };
451
452 int
main(int argc,char * argv[])453 main (int argc, char *argv[])
454 {
455 int i;
456
457 if (argc != 2)
458 {
459 fprintf (stderr, "exactly one argument required; use --help for help\n");
460 return EXIT_FAILURE;
461 }
462 else if (!strcmp (argv[1], "--help"))
463 {
464 printf ("%s: test sparse array library\n"
465 "usage: %s TEST-NAME\n"
466 "where TEST-NAME is one of the following:\n",
467 argv[0], argv[0]);
468 for (i = 0; i < N_TESTS; i++)
469 printf (" %s\n %s\n", tests[i].name, tests[i].description);
470 return 0;
471 }
472 else
473 {
474 for (i = 0; i < N_TESTS; i++)
475 if (!strcmp (argv[1], tests[i].name))
476 {
477 tests[i].function ();
478 return 0;
479 }
480
481 fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
482 return EXIT_FAILURE;
483 }
484 }
485