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-xarray.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-xarray.c when
21 compiled with -DNDEBUG. "valgrind --leak-check=yes
22 --show-reachable=yes" should give a clean report. */
36 #include <libpspp/argv-parser.h>
37 #include <libpspp/assertion.h>
38 #include <libpspp/hash-functions.h>
39 #include <libpspp/model-checker.h>
40 #include <libpspp/sparse-xarray.h>
41 #include <libpspp/str.h>
48 /* Maximum size of sparse_xarray supported for model checking
53 /* Test parameters. */
56 /* Controlling the test state space. */
57 int n_columns; /* Number of columns in each row. */
58 int max_rows; /* Maximum number of rows. */
59 int max_memory_rows; /* Max rows before writing to disk. */
60 unsigned char n_values; /* Number of unique cell values. */
61 int n_xarrays; /* Number of sparse_xarrays in state. */
63 /* Types of operations to perform. */
64 bool write_cells; /* Write to individual cells. */
65 bool write_rows; /* Write whole rows. */
66 bool write_columns; /* Write whole columns. */
67 bool copy_within_xarray; /* Copy column ranges in a single xarray. */
72 struct sparse_xarray *xarrays[2];
76 test_state_destroy (const struct test_params *params, struct test_state *ts)
80 for (i = 0; i < params->n_xarrays; i++)
81 sparse_xarray_destroy (ts->xarrays[i]);
84 static struct test_state *
85 test_state_clone (const struct test_params *params,
86 const struct test_state *ots)
88 struct test_state *ts;
91 ts = xmalloc (sizeof *ts);
92 for (i = 0; i < params->n_xarrays; i++)
94 ts->xarrays[i] = sparse_xarray_clone (ots->xarrays[i]);
95 if (ts->xarrays[i] == NULL)
103 uint8_t data[MAX_ROWS][MAX_COLS];
104 bool contains_row[MAX_ROWS];
109 struct xarray_model models[2];
112 /* Extracts the contents of TS into TM. */
114 test_model_extract (const struct test_params *params,
115 const struct test_state *ts, struct test_model *tm)
119 for (i = 0; i < params->n_xarrays; i++)
121 const struct sparse_xarray *sx = ts->xarrays[i];
122 struct xarray_model *model = &tm->models[i];
123 size_t n_columns = sparse_xarray_get_n_columns (sx);
124 size_t n_rows = sparse_xarray_get_n_rows (sx);
127 assert (n_rows < MAX_ROWS);
128 assert (n_columns < MAX_COLS);
129 for (row = 0; row < params->max_rows; row++)
131 model->contains_row[row] = sparse_xarray_contains_row (sx, row);
132 if (!sparse_xarray_read (sx, row, 0, n_columns, model->data[row]))
138 /* Checks that test state TS matches the test model TM and
139 reports any mismatches via mc_error. Then, adds SX to MC as a
142 check_state (struct mc *mc, struct test_state *ts, const struct test_model *tm)
144 const struct test_params *params = mc_get_aux (mc);
145 int n_columns = params->n_columns;
149 for (i = 0; i < params->n_xarrays; i++)
151 const struct xarray_model *model = &tm->models[i];
152 const struct sparse_xarray *sx = ts->xarrays[i];
157 assert (n_columns < MAX_COLS);
159 /* Check row count. */
161 for (row = 0; row < params->max_rows; row++)
162 if (model->contains_row[row])
164 if (n_rows != sparse_xarray_get_n_rows (sx))
165 mc_error (mc, "xarray %d: row count (%zu) does not match expected "
166 "(%d)", i, sparse_xarray_get_n_rows (sx), n_rows);
168 /* Check row containment. */
169 for (row = 0; row < params->max_rows; row++)
171 bool contains = sparse_xarray_contains_row (sx, row);
172 if (contains && !model->contains_row[row])
173 mc_error (mc, "xarray %d: row %d is contained by sparse_xarray "
174 "but should not be", i, row);
175 else if (!contains && model->contains_row[row])
176 mc_error (mc, "xarray %d: row %d is not contained by "
177 "sparse_xarray but should be", i, row);
180 /* Check contents. */
182 for (row = 0; row < params->max_rows; row++)
184 unsigned char data[MAX_COLS];
186 if (!sparse_xarray_read (sx, row, 0, n_columns, data))
188 for (col = 0; col < params->n_columns; col++)
189 if (data[col] != model->data[row][col])
191 mc_error (mc, "xarray %d: element %zu,%zu (of %zu,%zu) "
192 "differs: %d should be %d",
193 i, row, col, n_rows, n_columns, data[col],
194 model->data[row][col]);
203 mc_error (mc, "xarray %d: expected:", i);
205 for (row = 0; row < params->max_rows; row++)
208 for (col = 0; col < n_columns; col++)
209 ds_put_format (&ds, " %d", model->data[row][col]);
210 mc_error (mc, "xarray %d: row %zu:%s", i, row, ds_cstr (&ds));
213 mc_error (mc, "xarray %d: actual:", i);
215 for (row = 0; row < params->max_rows; row++)
217 unsigned char data[MAX_COLS];
219 if (!sparse_xarray_read (sx, row, 0, n_columns, data))
223 for (col = 0; col < n_columns; col++)
224 ds_put_format (&ds, " %d", data[col]);
225 mc_error (mc, "xarray %d: row %zu:%s", i, row, ds_cstr (&ds));
233 for (i = 0; i < params->n_xarrays; i++)
234 hash = sparse_xarray_model_checker_hash (ts->xarrays[i], hash);
235 if (mc_discard_dup_state (mc, hash))
236 test_state_destroy (params, ts);
238 mc_add_state (mc, ts);
242 next_data (unsigned char *data, int n, int n_values)
245 for (i = n - 1; i >= 0; i--)
248 if (data[i] < n_values)
255 struct copy_columns_params
257 int n; /* Number of columns to copy. */
258 int src; /* Offset of first source column. */
259 int dst; /* Offset of first destination column. */
263 copy_columns (const void *src_, void *dst_, void *copy_)
265 const struct copy_columns_params *copy = copy_;
266 const uint8_t *src = src_;
269 memmove (dst + copy->dst, src + copy->src, copy->n);
273 /* "init" function for struct mc_class. */
275 sparse_xarray_mc_init (struct mc *mc)
277 struct test_params *params = mc_get_aux (mc);
278 struct test_state *ts;
279 struct test_model tm;
282 mc_name_operation (mc, "empty sparse_xarray with n_columns=%zu, "
283 "max_memory_rows=%zu",
284 params->n_columns, params->max_memory_rows);
285 ts = xmalloc (sizeof *ts);
286 for (i = 0; i < params->n_xarrays; i++)
287 ts->xarrays[i] = sparse_xarray_create (params->n_columns,
288 params->max_memory_rows);
289 memset (&tm, 0, sizeof tm);
290 check_state (mc, ts, &tm);
293 /* "mutate" function for struct mc_class. */
295 sparse_xarray_mc_mutate (struct mc *mc, const void *ots_)
297 struct test_params *params = mc_get_aux (mc);
298 size_t n_columns = params->n_columns;
299 const struct test_state *ots = ots_;
300 struct test_model otm;
303 test_model_extract (params, ots, &otm);
304 for (i = 0; i < params->n_xarrays; i++)
307 int row, col, n, src, dst;
309 /* Write all possible values to each possible single cell. */
310 if (params->write_cells)
311 for (row = 0; row < params->max_rows; row++)
312 for (col = 0; col < n_columns; col++)
313 for (value = 0; value < params->n_values; value++)
314 if (mc_include_state (mc))
316 struct test_state *ts = test_state_clone (params, ots);
317 struct sparse_xarray *sx = ts->xarrays[i];
318 struct test_model tm = otm;
319 struct xarray_model *model = &tm.models[i];
321 mc_name_operation (mc, "xarray %d: set (%d,%d) to %d",
323 if (!sparse_xarray_write (sx, row, col, 1, &value))
325 model->data[row][col] = value;
326 model->contains_row[row] = true;
327 check_state (mc, ts, &tm);
330 /* Write all possible row contents to each row. */
331 if (params->write_rows)
332 for (row = 0; row < params->max_rows; row++)
334 struct test_model tm = otm;
335 struct xarray_model *model = &tm.models[i];
337 memset (model->data[row], 0, n_columns);
338 model->contains_row[row] = true;
341 if (mc_include_state (mc))
343 struct test_state *ts = test_state_clone (params, ots);
344 struct sparse_xarray *sx = ts->xarrays[i];
345 char row_string[MAX_COLS + 1];
347 mc_name_operation (mc, "xarray %d: set row %d to %s",
349 for (col = 0; col < n_columns; col++)
351 value = model->data[row][col];
352 row_string[col] = value < 10 ? '0' + value : '*';
354 row_string[n_columns] = '\0';
355 if (!sparse_xarray_write (sx, row, 0, n_columns,
358 check_state (mc, ts, &tm);
361 while (next_data (model->data[row], n_columns, params->n_values));
364 /* Write all possible values to each possible column. */
365 if (params->write_columns)
366 for (col = 0; col < n_columns; col++)
367 for (value = 0; value < params->n_values; value++)
368 if (mc_include_state (mc))
370 struct test_state *ts = test_state_clone (params, ots);
371 struct sparse_xarray *sx = ts->xarrays[i];
372 struct test_model tm = otm;
373 struct xarray_model *model = &tm.models[i];
375 mc_name_operation (mc, "xarray %d: write value %d to "
376 "column %d", i, value, col);
377 if (!sparse_xarray_write_columns (sx, col, 1, &value))
379 for (row = 0; row < params->max_rows; row++)
380 model->data[row][col] = value;
381 check_state (mc, ts, &tm);
384 /* Copy all possible column ranges within a single sparse_xarray. */
385 if (params->copy_within_xarray)
386 for (n = 1; n <= n_columns; n++)
387 for (src = 0; src <= n_columns - n; src++)
388 for (dst = 0; dst <= n_columns - n; dst++)
389 if (mc_include_state (mc))
391 struct copy_columns_params copy_aux;
392 struct test_state *ts = test_state_clone (params, ots);
393 struct sparse_xarray *sx = ts->xarrays[i];
394 struct test_model tm = otm;
395 struct xarray_model *model = &tm.models[i];
397 mc_name_operation (mc, "xarray %d: copy %d columns from "
398 "offset %d to offset %d", i, n, src, dst);
403 if (!sparse_xarray_copy (sx, sx, copy_columns, ©_aux))
406 for (row = 0; row < params->max_rows; row++)
407 memmove (&model->data[row][dst],
408 &model->data[row][src], n);
410 check_state (mc, ts, &tm);
414 if (params->n_xarrays == 2)
416 int row, n, src, dst;
418 /* Copy all possible column ranges from xarrays[0] to xarrays[1]. */
419 for (n = 1; n <= n_columns; n++)
420 for (src = 0; src <= n_columns - n; src++)
421 for (dst = 0; dst <= n_columns - n; dst++)
422 if (mc_include_state (mc))
424 struct copy_columns_params copy_aux;
425 struct test_state *ts = test_state_clone (params, ots);
426 struct test_model tm = otm;
428 mc_name_operation (mc, "copy %d columns from offset %d in "
429 "xarray 0 to offset %d in xarray 1",
435 if (!sparse_xarray_copy (ts->xarrays[0], ts->xarrays[1],
436 copy_columns, ©_aux))
439 for (row = 0; row < params->max_rows; row++)
441 if (tm.models[0].contains_row[row])
442 tm.models[1].contains_row[row] = true;
443 memmove (&tm.models[1].data[row][dst],
444 &tm.models[0].data[row][src], n);
447 check_state (mc, ts, &tm);
452 /* "destroy" function for struct mc_class. */
454 sparse_xarray_mc_destroy (const struct mc *mc UNUSED, void *ts_)
456 struct test_params *params = mc_get_aux (mc);
457 struct test_state *ts = ts_;
459 test_state_destroy (params, ts);
465 printf ("%s, for testing the sparse_xarray implementation.\n"
466 "Usage: %s [OPTION]...\n"
467 "\nTest state space parameters (min...max, default):\n"
468 " --columns=N Number of columns per row (0...5, 3)\n"
469 " --max-rows=N Maximum number of rows (0...5, 3)\n"
470 " --max-memory-rows=N Max rows before paging to disk (0...5, 3)\n"
471 " --values=N Number of unique cell values (1...254, 3)\n"
472 " --xarrays=N Number of xarrays at a time (1...2, 1)\n"
473 "\nTest operation parameters:\n"
474 " --no-write-cells Do not write individual cells\n"
475 " --no-write-rows Do not write whole rows\n"
476 " --no-write-columns Do not write whole columns\n"
477 " --no-copy-columns Do not copy column ranges in an xarray\n",
478 program_name, program_name);
480 fputs ("\nOther options:\n"
481 " --help Display this help message\n"
482 "\nReport bugs to <bug-gnu-pspp@gnu.org>\n",
496 OPT_NO_WRITE_COLUMNS,
501 static struct argv_option sparse_xarray_argv_options[] =
503 {"columns", 0, required_argument, OPT_COLUMNS},
504 {"max-rows", 0, required_argument, OPT_MAX_ROWS},
505 {"max-memory-rows", 0, required_argument, OPT_MAX_MEMORY_ROWS},
506 {"values", 0, required_argument, OPT_VALUES},
507 {"xarrays", 0, required_argument, OPT_XARRAYS},
508 {"no-write-cells", 0, no_argument, OPT_NO_WRITE_CELLS},
509 {"no-write-rows", 0, no_argument, OPT_NO_WRITE_ROWS},
510 {"no-write-columns", 0, no_argument, OPT_NO_WRITE_COLUMNS},
511 {"no-copy-columns", 0, no_argument, OPT_NO_COPY_COLUMNS},
512 {"help", 'h', no_argument, OPT_HELP},
514 enum { N_SPARSE_XARRAY_ARGV_OPTIONS = (sizeof sparse_xarray_argv_options
515 / sizeof *sparse_xarray_argv_options) };
518 sparse_xarray_option_callback (int id, void *params_)
520 struct test_params *params = params_;
524 params->n_columns = atoi (optarg);
528 params->max_rows = atoi (optarg);
531 case OPT_MAX_MEMORY_ROWS:
532 params->max_memory_rows = atoi (optarg);
536 params->n_values = atoi (optarg);
540 params->n_xarrays = atoi (optarg);
543 case OPT_NO_WRITE_CELLS:
544 params->write_cells = false;
547 case OPT_NO_WRITE_ROWS:
548 params->write_rows = false;
551 case OPT_NO_WRITE_COLUMNS:
552 params->write_columns = false;
555 case OPT_NO_COPY_COLUMNS:
556 params->copy_within_xarray = false;
569 main (int argc, char *argv[])
571 static const struct mc_class sparse_xarray_mc_class =
573 sparse_xarray_mc_init,
574 sparse_xarray_mc_mutate,
575 sparse_xarray_mc_destroy,
578 struct test_params params;
579 struct mc_options *options;
580 struct mc_results *results;
581 struct argv_parser *parser;
585 set_program_name (argv[0]);
587 /* Default parameters. */
588 params.n_columns = 3;
590 params.max_memory_rows = 3;
592 params.n_xarrays = 1;
593 params.write_cells = true;
594 params.write_rows = true;
595 params.write_columns = true;
596 params.copy_within_xarray = true;
598 /* Parse command line. */
599 parser = argv_parser_create ();
600 options = mc_options_create ();
601 mc_options_register_argv_parser (options, parser);
602 argv_parser_add_options (parser, sparse_xarray_argv_options,
603 N_SPARSE_XARRAY_ARGV_OPTIONS,
604 sparse_xarray_option_callback, ¶ms);
605 if (!argv_parser_run (parser, argc, argv))
607 argv_parser_destroy (parser);
608 verbosity = mc_options_get_verbosity (options);
610 /* Force parameters into allowed ranges. */
611 params.n_columns = MAX (0, MIN (params.n_columns, MAX_COLS));
612 params.max_rows = MAX (0, MIN (params.max_rows, MAX_ROWS));
613 params.max_memory_rows = MAX (0, MIN (params.max_memory_rows,
615 params.n_values = MIN (254, MAX (1, params.n_values));
616 params.n_xarrays = MAX (1, MIN (2, params.n_xarrays));
617 mc_options_set_aux (options, ¶ms);
618 results = mc_run (&sparse_xarray_mc_class, options);
620 /* Output results. */
621 success = (mc_results_get_stop_reason (results) != MC_MAX_ERROR_COUNT
622 && mc_results_get_stop_reason (results) != MC_INTERRUPTED);
623 if (verbosity > 0 || !success)
625 printf ("Parameters: "
626 "--columns=%d --max-rows=%d --max-memory-rows=%d --values=%d "
628 params.n_columns, params.max_rows, params.max_memory_rows,
629 params.n_values, params.n_xarrays);
630 if (!params.write_cells)
631 printf (" --no-write-cells");
632 if (!params.write_rows)
633 printf (" --no-write-rows");
634 if (!params.write_columns)
635 printf (" --no-write-columns");
636 if (!params.copy_within_xarray)
637 printf (" --no-copy-columns");
639 mc_results_print (results, stdout);
641 mc_results_destroy (results);
643 return success ? 0 : EXIT_FAILURE;