1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2009 Free Software Foundation, Inc.
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.
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.
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/>. */
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. */
29 #include <libpspp/sparse-array.h>
36 /* Support preliminaries. */
37 #if __GNUC__ >= 2 && !defined UNUSED
38 #define UNUSED __attribute__ ((unused))
43 /* Currently running test. */
44 static const char *test_name;
46 /* Exit with a failure code.
47 (Place a breakpoint on this function while debugging.) */
54 /* If OK is not true, prints a message about failure on the
55 current source file and the given LINE and terminates. */
57 check_func (bool ok, int line)
61 printf ("%s:%d: Check failed in %s test\n",
62 __FILE__, line, test_name);
67 /* Verifies that EXPR evaluates to true.
68 If not, prints a message citing the calling line number and
70 #define check(EXPR) check_func ((EXPR), __LINE__)
72 /* Prints a message about memory exhaustion and exits with a
77 printf ("virtual memory exhausted\n");
81 /* Allocates and returns N bytes of memory. */
97 /* Returns a malloc()'d duplicate of the N bytes starting at
100 xmemdup (const void *p, size_t n)
102 void *q = xmalloc (n);
107 /* Allocates and returns N * M bytes of memory. */
109 xnmalloc (size_t n, size_t m)
111 if ((size_t) -1 / m <= n)
113 return xmalloc (n * m);
116 /* Compares A and B and returns a strcmp-type return value. */
118 compare_unsigned_longs_noaux (const void *a_, const void *b_)
120 const unsigned long *a = a_;
121 const unsigned long *b = b_;
123 return *a < *b ? -1 : *a > *b;
126 /* Checks that SPAR contains the CNT ints in DATA, that its
127 structure is correct, and that certain operations on SPAR
128 produce the expected results. */
130 check_sparse_array (struct sparse_array *spar,
131 const unsigned long data[], size_t cnt)
134 unsigned long *order;
138 check (sparse_array_count (spar) == cnt);
140 for (i = 0; i < cnt; i++)
142 p = sparse_array_get (spar, data[i]);
144 check (*p == data[i]);
147 order = xmemdup (data, cnt * sizeof *data);
148 qsort (order, cnt, sizeof *order, compare_unsigned_longs_noaux);
150 for (i = 0; i < cnt; i++)
152 p = sparse_array_get (spar, order[i]);
154 check (*p == order[i]);
157 if (cnt > 0 && order[0] - 1 != order[cnt - 1])
159 check (sparse_array_get (spar, order[0] - 1) == NULL);
160 check (!sparse_array_remove (spar, order[0] - 1));
162 if (cnt > 0 && order[0] != order[cnt - 1] + 1)
164 check (sparse_array_get (spar, order[cnt - 1] + 1) == NULL);
165 check (!sparse_array_remove (spar, order[cnt - 1] + 1));
168 for (i = 0, p = sparse_array_first (spar, &idx); i < cnt;
169 i++, p = sparse_array_next (spar, idx, &idx))
172 check (idx == order[i]);
173 check (*p == order[i]);
177 for (i = 0, p = sparse_array_last (spar, &idx); i < cnt;
178 i++, p = sparse_array_prev (spar, idx, &idx))
181 check (idx == order[cnt - i - 1]);
182 check (*p == order[cnt - i - 1]);
189 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into a
190 sparse array in the order specified by INSERTIONS, then
191 deletes them in the order specified by DELETIONS, checking the
192 array's contents for correctness after each operation. */
194 test_insert_delete (const unsigned long insertions[],
195 const unsigned long deletions[],
198 struct sparse_array *spar;
201 spar = sparse_array_create (sizeof *insertions);
202 for (i = 0; i < cnt; i++)
204 unsigned long *p = sparse_array_insert (spar, insertions[i]);
206 check_sparse_array (spar, insertions, i + 1);
208 for (i = 0; i < cnt; i++)
210 bool deleted = sparse_array_remove (spar, deletions[i]);
212 check_sparse_array (spar, deletions + i + 1, cnt - (i + 1));
214 check_sparse_array (spar, NULL, 0);
215 sparse_array_destroy (spar);
218 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into a
219 sparse array in the order specified by INSERTIONS, then
220 destroys the sparse array, to check that sparse_cases_destroy
221 properly frees all the nodes. */
223 test_destroy (const unsigned long insertions[], size_t cnt)
225 struct sparse_array *spar;
228 spar = sparse_array_create (sizeof *insertions);
229 for (i = 0; i < cnt; i++)
231 unsigned long *p = sparse_array_insert (spar, insertions[i]);
233 check_sparse_array (spar, insertions, i + 1);
235 sparse_array_destroy (spar);
238 /* Randomly shuffles the CNT elements in ARRAY, each of which is
239 SIZE bytes in size. */
241 random_shuffle (void *array_, size_t cnt, size_t size)
243 char *array = array_;
244 char *tmp = xmalloc (size);
247 for (i = 0; i < cnt; i++)
249 size_t j = rand () % (cnt - i) + i;
252 memcpy (tmp, array + j * size, size);
253 memcpy (array + j * size, array + i * size, size);
254 memcpy (array + i * size, tmp, size);
261 /* Tests inserting and deleting elements whose values are
262 determined by starting from various offsets and skipping
263 across various strides, and doing so in various orders. */
265 test_insert_delete_strides (void)
267 static const unsigned long strides[] =
269 1, 2, 4, 16, 64, 4096, 262144, 16777216,
270 3, 5, 17, 67, 4099, 262147, 16777259,
272 const size_t stride_cnt = sizeof strides / sizeof *strides;
274 static const unsigned long offsets[] =
278 1024ul * 1024 * 512 + 23,
281 const size_t offset_cnt = sizeof offsets / sizeof *offsets;
284 unsigned long *insertions, *deletions;
285 const unsigned long *stride, *offset;
287 insertions = xnmalloc (cnt, sizeof *insertions);
288 deletions = xnmalloc (cnt, sizeof *deletions);
289 for (stride = strides; stride < strides + stride_cnt; stride++)
291 for (offset = offsets; offset < offsets + offset_cnt; offset++)
295 for (k = 0; k < cnt; k++)
296 insertions[k] = *stride * k + *offset;
298 test_insert_delete (insertions, insertions, cnt);
299 test_destroy (insertions, cnt);
301 for (k = 0; k < cnt; k++)
302 deletions[k] = insertions[cnt - k - 1];
303 test_insert_delete (insertions, deletions, cnt);
305 random_shuffle (insertions, cnt, sizeof *insertions);
306 test_insert_delete (insertions, insertions, cnt);
307 test_insert_delete (insertions, deletions, cnt);
316 /* Returns the index in ARRAY of the (CNT+1)th element that has
319 scan_bools (bool target, bool array[], size_t cnt)
324 if (array[i] == target && cnt-- == 0)
328 /* Performs a random sequence of insertions and deletions in a
331 test_random_insert_delete (void)
333 unsigned long int values[] =
335 0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096,
336 8192, 16384, 32768, 65536, 131072, 262144, 4194304, 8388608,
337 16777216, 33554432, 67108864, 134217728, 268435456, 536870912,
338 1073741824, 2147483648,
340 3, 7, 15, 31, 63, 127, 257, 511, 1023, 2047, 4095,
341 8191, 16383, 32767, 65535, 131071, 262143, 4194303, 8388607,
342 16777215, 33554431, 67108863, 134217727, 268435455, 536870911,
343 1073741823, 2147483647, 4294967295,
345 const int max_values = sizeof values / sizeof *values;
347 const int num_actions = 250000;
348 struct sparse_array *spar;
354 has_values = xnmalloc (max_values, sizeof *has_values);
355 memset (has_values, 0, max_values * sizeof *has_values);
360 spar = sparse_array_create (sizeof *values);
361 for (i = 0; i < num_actions; i++)
363 enum { INSERT, DELETE } action;
370 if (insert_chance < 9)
373 else if (cnt == max_values)
376 if (insert_chance > 0)
380 action = rand () % 10 < insert_chance ? INSERT : DELETE;
382 if (action == INSERT)
386 ins_index = scan_bools (false, has_values,
387 rand () % (max_values - cnt));
388 assert (has_values[ins_index] == false);
389 has_values[ins_index] = true;
391 p = sparse_array_insert (spar, values[ins_index]);
393 *p = values[ins_index];
397 else if (action == DELETE)
401 del_index = scan_bools (true, has_values, rand () % cnt);
402 assert (has_values[del_index] == true);
403 has_values[del_index] = false;
405 check (sparse_array_remove (spar, values[del_index]));
411 check (sparse_array_count (spar) == cnt);
412 for (j = 0; j < max_values; j++)
414 p = sparse_array_get (spar, values[j]);
418 check (*p == values[j]);
423 if (rand () % 10 == 0)
424 sparse_array_remove (spar, values[j]);
428 sparse_array_destroy (spar);
434 /* Runs TEST_FUNCTION and prints a message about NAME. */
436 run_test (void (*test_function) (void), const char *name)
447 run_test (test_random_insert_delete,
448 "random insertions and deletions");
449 run_test (test_insert_delete_strides,
450 "insert in ascending order with strides and offset");