1 /* PSPP - computes sample statistics.
2 Copyright (C) 2007 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 /* This is a test program for the sparse array routines defined
20 in sparse-array.c. This test program aims to be as
21 comprehensive as possible. "gcov -b" should report 100%
22 coverage of lines and branches in sparse-array.c when compiled
23 with -DNDEBUG. "valgrind --leak-check=yes
24 --show-reachable=yes" should give a clean report. */
30 #include <libpspp/sparse-array.h>
37 /* Support preliminaries. */
38 #if __GNUC__ >= 2 && !defined UNUSED
39 #define UNUSED __attribute__ ((unused))
44 /* Currently running test. */
45 static const char *test_name;
47 /* Exit with a failure code.
48 (Place a breakpoint on this function while debugging.) */
55 /* If OK is not true, prints a message about failure on the
56 current source file and the given LINE and terminates. */
58 check_func (bool ok, int line)
62 printf ("%s:%d: Check failed in %s test\n",
63 __FILE__, line, test_name);
68 /* Verifies that EXPR evaluates to true.
69 If not, prints a message citing the calling line number and
71 #define check(EXPR) check_func ((EXPR), __LINE__)
73 /* Prints a message about memory exhaustion and exits with a
78 printf ("virtual memory exhausted\n");
82 /* Allocates and returns N bytes of memory. */
98 /* Returns a malloc()'d duplicate of the N bytes starting at
101 xmemdup (const void *p, size_t n)
103 void *q = xmalloc (n);
108 /* Allocates and returns N * M bytes of memory. */
110 xnmalloc (size_t n, size_t m)
112 if ((size_t) -1 / m <= n)
114 return xmalloc (n * m);
117 /* Compares A and B and returns a strcmp-type return value. */
119 compare_unsigned_longs_noaux (const void *a_, const void *b_)
121 const unsigned long *a = a_;
122 const unsigned long *b = b_;
124 return *a < *b ? -1 : *a > *b;
127 /* Checks that SPAR contains the CNT ints in DATA, that its
128 structure is correct, and that certain operations on SPAR
129 produce the expected results. */
131 check_sparse_array (struct sparse_array *spar,
132 const unsigned long data[], size_t cnt)
135 unsigned long *order;
139 check (sparse_array_count (spar) == cnt);
141 for (i = 0; i < cnt; i++)
143 p = sparse_array_get (spar, data[i]);
145 check (*p == data[i]);
148 order = xmemdup (data, cnt * sizeof *data);
149 qsort (order, cnt, sizeof *order, compare_unsigned_longs_noaux);
151 for (i = 0; i < cnt; i++)
153 p = sparse_array_get (spar, order[i]);
155 check (*p == order[i]);
158 if (cnt > 0 && order[0] - 1 != order[cnt - 1])
160 check (sparse_array_get (spar, order[0] - 1) == NULL);
161 check (!sparse_array_remove (spar, order[0] - 1));
163 if (cnt > 0 && order[0] != order[cnt - 1] + 1)
165 check (sparse_array_get (spar, order[cnt - 1] + 1) == NULL);
166 check (!sparse_array_remove (spar, order[cnt - 1] + 1));
169 for (i = 0, p = sparse_array_scan (spar, NULL, &idx); i < cnt;
170 i++, p = sparse_array_scan (spar, &idx, &idx))
173 check (idx == order[i]);
174 check (*p == order[i]);
181 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into a
182 sparse array in the order specified by INSERTIONS, then
183 deletes them in the order specified by DELETIONS, checking the
184 array's contents for correctness after each operation. */
186 test_insert_delete (const unsigned long insertions[],
187 const unsigned long deletions[],
190 struct sparse_array *spar;
193 spar = sparse_array_create (sizeof *insertions);
194 for (i = 0; i < cnt; i++)
196 unsigned long *p = sparse_array_insert (spar, insertions[i]);
198 check_sparse_array (spar, insertions, i + 1);
200 for (i = 0; i < cnt; i++)
202 bool deleted = sparse_array_remove (spar, deletions[i]);
204 check_sparse_array (spar, deletions + i + 1, cnt - (i + 1));
206 check_sparse_array (spar, NULL, 0);
207 sparse_array_destroy (spar);
210 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into a
211 sparse array in the order specified by INSERTIONS, then
212 destroys the sparse array, to check that sparse_cases_destroy
213 properly frees all the nodes. */
215 test_destroy (const unsigned long insertions[], size_t cnt)
217 struct sparse_array *spar;
220 spar = sparse_array_create (sizeof *insertions);
221 for (i = 0; i < cnt; i++)
223 unsigned long *p = sparse_array_insert (spar, insertions[i]);
225 check_sparse_array (spar, insertions, i + 1);
227 sparse_array_destroy (spar);
230 /* Randomly shuffles the CNT elements in ARRAY, each of which is
231 SIZE bytes in size. */
233 random_shuffle (void *array_, size_t cnt, size_t size)
235 char *array = array_;
236 char *tmp = xmalloc (size);
239 for (i = 0; i < cnt; i++)
241 size_t j = rand () % (cnt - i) + i;
244 memcpy (tmp, array + j * size, size);
245 memcpy (array + j * size, array + i * size, size);
246 memcpy (array + i * size, tmp, size);
253 /* Tests inserting and deleting elements whose values are
254 determined by starting from various offsets and skipping
255 across various strides, and doing so in various orders. */
257 test_insert_delete_strides (void)
259 static const unsigned long strides[] =
261 1, 2, 4, 16, 64, 4096, 262144, 16777216,
262 3, 5, 17, 67, 4099, 262147, 16777259,
264 const size_t stride_cnt = sizeof strides / sizeof *strides;
266 static const unsigned long offsets[] =
270 1024ul * 1024 * 512 + 23,
273 const size_t offset_cnt = sizeof offsets / sizeof *offsets;
276 unsigned long *insertions, *deletions;
277 const unsigned long *stride, *offset;
279 insertions = xnmalloc (cnt, sizeof *insertions);
280 deletions = xnmalloc (cnt, sizeof *deletions);
281 for (stride = strides; stride < strides + stride_cnt; stride++)
283 for (offset = offsets; offset < offsets + offset_cnt; offset++)
287 for (k = 0; k < cnt; k++)
288 insertions[k] = *stride * k + *offset;
290 test_insert_delete (insertions, insertions, cnt);
291 test_destroy (insertions, cnt);
293 for (k = 0; k < cnt; k++)
294 deletions[k] = insertions[cnt - k - 1];
295 test_insert_delete (insertions, deletions, cnt);
297 random_shuffle (insertions, cnt, sizeof *insertions);
298 test_insert_delete (insertions, insertions, cnt);
299 test_insert_delete (insertions, deletions, cnt);
308 /* Returns the index in ARRAY of the (CNT+1)th element that has
311 scan_bools (bool target, bool array[], size_t cnt)
316 if (array[i] == target && cnt-- == 0)
320 /* Performs a random sequence of insertions and deletions in a
323 test_random_insert_delete (void)
325 unsigned long int values[] =
327 0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096,
328 8192, 16384, 32768, 65536, 131072, 262144, 4194304, 8388608,
329 16777216, 33554432, 67108864, 134217728, 268435456, 536870912,
330 1073741824, 2147483648,
332 3, 7, 15, 31, 63, 127, 257, 511, 1023, 2047, 4095,
333 8191, 16383, 32767, 65535, 131071, 262143, 4194303, 8388607,
334 16777215, 33554431, 67108863, 134217727, 268435455, 536870911,
335 1073741823, 2147483647, 4294967295,
337 const int max_values = sizeof values / sizeof *values;
339 const int num_actions = 250000;
340 struct sparse_array *spar;
346 has_values = xnmalloc (max_values, sizeof *has_values);
347 memset (has_values, 0, max_values * sizeof *has_values);
352 spar = sparse_array_create (sizeof *values);
353 for (i = 0; i < num_actions; i++)
355 enum { INSERT, DELETE } action;
362 if (insert_chance < 9)
365 else if (cnt == max_values)
368 if (insert_chance > 0)
372 action = rand () % 10 < insert_chance ? INSERT : DELETE;
374 if (action == INSERT)
378 ins_index = scan_bools (false, has_values,
379 rand () % (max_values - cnt));
380 assert (has_values[ins_index] == false);
381 has_values[ins_index] = true;
383 p = sparse_array_insert (spar, values[ins_index]);
385 *p = values[ins_index];
389 else if (action == DELETE)
393 del_index = scan_bools (true, has_values, rand () % cnt);
394 assert (has_values[del_index] == true);
395 has_values[del_index] = false;
397 check (sparse_array_remove (spar, values[del_index]));
403 check (sparse_array_count (spar) == cnt);
404 for (j = 0; j < max_values; j++)
406 p = sparse_array_get (spar, values[j]);
410 check (*p == values[j]);
415 if (rand () % 10 == 0)
416 sparse_array_remove (spar, values[j]);
420 sparse_array_destroy (spar);
426 /* Runs TEST_FUNCTION and prints a message about NAME. */
428 run_test (void (*test_function) (void), const char *name)
439 run_test (test_random_insert_delete,
440 "random insertions and deletions");
441 run_test (test_insert_delete_strides,
442 "insert in ascending order with strides and offset");