X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=tests%2Flibpspp%2Ftower-test.c;h=f5c002652a4409af5f9ef834b2d3ca0dd2f3fe82;hb=a258da644fcf0667a93971adfc68e40badc756fa;hp=a59760c80a89bfd13c0e5e273f5282d6e54428e6;hpb=04bf0e1fed86a5dc9032f2fc8d89ed6217b566e1;p=pspp diff --git a/tests/libpspp/tower-test.c b/tests/libpspp/tower-test.c index a59760c80a..f5c002652a 100644 --- a/tests/libpspp/tower-test.c +++ b/tests/libpspp/tower-test.c @@ -1,20 +1,18 @@ -/* PSPP - computes sample statistics. - Copyright (C) 2007 Free Software Foundation, Inc. +/* PSPP - a program for statistical analysis. + Copyright (C) 2007, 2010 Free Software Foundation, Inc. - This program is free software; you can redistribute it and/or - modify it under the terms of the GNU General Public License as - published by the Free Software Foundation; either version 2 of the - License, or (at your option) any later version. + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. - This program is distributed in the hope that it will be useful, but - WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA - 02110-1301, USA. */ + along with this program. If not, see . */ /* This is a test program for the routines defined in tower.c. This test program aims to be as comprehensive as possible. @@ -41,26 +39,22 @@ #include "xalloc.h" -/* Currently running test. */ -static const char *test_name; - /* Exit with a failure code. (Place a breakpoint on this function while debugging.) */ static void -check_die (void) +check_die (void) { - exit (EXIT_FAILURE); + exit (EXIT_FAILURE); } /* If OK is not true, prints a message about failure on the current source file and the given LINE and terminates. */ static void -check_func (bool ok, int line) +check_func (bool ok, int line) { - if (!ok) + if (!ok) { - printf ("Check failed in %s test at %s, line %d\n", - test_name, __FILE__, line); + fprintf (stderr, "%s:%d: check failed\n", __FILE__, line); check_die (); } } @@ -88,7 +82,7 @@ tower_node_to_block (const struct tower_node *node) /* Swaps *A and *B. */ static void -swap (int *a, int *b) +swap (int *a, int *b) { int t = *a; *a = *b; @@ -119,7 +113,7 @@ next_permutation (int *values, size_t cnt) if (cnt > 0) { size_t i = cnt - 1; - while (i != 0) + while (i != 0) { i--; if (values[i] < values[i + 1]) @@ -130,18 +124,18 @@ next_permutation (int *values, size_t cnt) swap (values + i, values + j); reverse (values + (i + 1), cnt - (i + 1)); return true; - } + } } - + reverse (values, cnt); } - + return false; } /* Returns N!. */ static unsigned int -factorial (unsigned int n) +factorial (unsigned int n) { unsigned int value = 1; /* Disallow N values that overflow on 32-bit machines. */ @@ -154,7 +148,7 @@ factorial (unsigned int n) /* Returns C(n, k), the number of ways that K choices can be made from N items when order is unimportant. */ static unsigned int -binomial_cofficient (unsigned int n, unsigned int k) +binomial_cofficient (unsigned int n, unsigned int k) { assert (n >= k); return factorial (n) / factorial (k) / factorial (n - k); @@ -163,7 +157,7 @@ binomial_cofficient (unsigned int n, unsigned int k) /* Tests whether PARTS is a K-part integer composition of N. Returns true if so, false otherwise. */ static bool UNUSED -is_k_composition (int n, int k, const int parts[]) +is_k_composition (int n, int k, const int parts[]) { int sum; int i; @@ -184,7 +178,7 @@ is_k_composition (int n, int k, const int parts[]) already the greatest K-part composition of N (in which case PARTS is unaltered). */ static bool -next_k_composition (int n UNUSED, int k, int parts[]) +next_k_composition (int n UNUSED, int k, int parts[]) { int x, i; @@ -210,7 +204,7 @@ next_k_composition (int n UNUSED, int k, int parts[]) /* Sets the K integers in PARTS to the lexicographically first K-part composition of N. */ static void -first_k_composition (int n, int k, int parts[]) +first_k_composition (int n, int k, int parts[]) { int i; @@ -231,7 +225,7 @@ first_k_composition (int n, int k, int parts[]) Returns true if successful, false if the set of compositions has been exhausted. */ static bool -next_composition (int n, int *k, int parts[]) +next_composition (int n, int *k, int parts[]) { if (*k >= 1 && next_k_composition (n, *k, parts)) return true; @@ -245,9 +239,9 @@ next_composition (int n, int *k, int parts[]) } /* A block expected to be found in a tower. */ -struct expected_block +struct expected_block { - int height; /* Expected height of bottom of block. */ + int size; /* Expected thickness of block. */ int x; /* Expected value for `x' member. */ }; @@ -255,21 +249,22 @@ struct expected_block BLOCKS[]. */ static void check_tower (struct tower *t, - struct expected_block blocks[], size_t block_cnt) + struct expected_block blocks[], size_t block_cnt) { int total_height; struct tower_node *node; size_t i; - + + check (tower_count (t) == block_cnt); check (tower_is_empty (t) == (block_cnt == 0)); total_height = 0; - for (i = 0; i < block_cnt; i++) + for (i = 0; i < block_cnt; i++) { unsigned long int level; for (level = total_height; - level < total_height + blocks[i].height; - level++) + level < total_height + blocks[i].size; + level++) { struct tower_node *found; unsigned long int block_start; @@ -277,25 +272,28 @@ check_tower (struct tower *t, check (found != NULL); check (tower_node_to_block (found)->x == blocks[i].x); check (block_start == total_height); + check (tower_node_get_level (found) == total_height); + check (tower_node_get_index (found) == i); + check (tower_get (t, i) == found); } - total_height += blocks[i].height; + total_height += blocks[i].size; } check (tower_height (t) == total_height); for (node = tower_first (t), i = 0; node != NULL; - node = tower_next (t, node), i++) + node = tower_next (t, node), i++) { - check (tower_node_get_height (node) == blocks[i].height); + check (tower_node_get_size (node) == blocks[i].size); check (tower_node_to_block (node)->x == blocks[i].x); } check (i == block_cnt); for (node = tower_last (t), i = block_cnt - 1; node != NULL; - node = tower_prev (t, node), i--) + node = tower_prev (t, node), i--) { - check (tower_node_get_height (node) == blocks[i].height); + check (tower_node_get_size (node) == blocks[i].size); check (tower_node_to_block (node)->x == blocks[i].x); } check (i == SIZE_MAX); @@ -305,44 +303,44 @@ check_tower (struct tower *t, tower in all possible orders, up to a specified maximum tower height. */ static void -test_insert (void) +test_insert (void) { const int max_height = 7; int cnt; - for (cnt = 1; cnt <= max_height; cnt++) + for (cnt = 1; cnt <= max_height; cnt++) { unsigned int composition_cnt; struct expected_block *expected; - int *heights; + int *sizes; int block_cnt; int *order; struct block *blocks; - + expected = xnmalloc (cnt, sizeof *expected); - heights = xnmalloc (cnt, sizeof *heights); + sizes = xnmalloc (cnt, sizeof *sizes); order = xnmalloc (cnt, sizeof *order); blocks = xnmalloc (cnt, sizeof *blocks); block_cnt = 0; composition_cnt = 0; - while (next_composition (cnt, &block_cnt, heights)) + while (next_composition (cnt, &block_cnt, sizes)) { int i, j; unsigned int permutation_cnt; - for (i = 0; i < block_cnt; i++) + for (i = 0; i < block_cnt; i++) order[i] = i; permutation_cnt = 0; - while (permutation_cnt == 0 || next_permutation (order, block_cnt)) + while (permutation_cnt == 0 || next_permutation (order, block_cnt)) { struct tower t; /* Inserts the block_cnt blocks with the given - heights[] into T in the order given by order[]. */ + sizes[] into T in the order given by order[]. */ tower_init (&t); - for (i = 0; i < block_cnt; i++) + for (i = 0; i < block_cnt; i++) { struct block *under; int idx; @@ -356,14 +354,14 @@ test_insert (void) && (under == NULL || under->x > order[j])) under = &blocks[order[j]]; - tower_insert (&t, heights[idx], &blocks[idx].node, + tower_insert (&t, sizes[idx], &blocks[idx].node, under != NULL ? &under->node : NULL); } /* Check that the result is what we expect. */ for (i = 0; i < block_cnt; i++) { - expected[i].height = heights[i]; + expected[i].size = sizes[i]; expected[i].x = i; } check_tower (&t, expected, block_cnt); @@ -371,67 +369,67 @@ test_insert (void) permutation_cnt++; } check (permutation_cnt == factorial (block_cnt)); - + composition_cnt++; } check (composition_cnt == 1 << (cnt - 1)); free (expected); - free (heights); + free (sizes); free (order); free (blocks); } } /* Tests deleting blocks from towers that initially contain all - possible sets of block heights into a tower in all possible + possible sets of block sizes into a tower in all possible orders, up to a specified maximum tower height. */ static void -test_delete (void) +test_delete (void) { const int max_height = 7; int cnt; - for (cnt = 1; cnt <= max_height; cnt++) + for (cnt = 1; cnt <= max_height; cnt++) { unsigned int composition_cnt; struct expected_block *expected; - int *heights; + int *sizes; int block_cnt; int *order; struct block *blocks; - + expected = xnmalloc (cnt, sizeof *expected); - heights = xnmalloc (cnt, sizeof *heights); + sizes = xnmalloc (cnt, sizeof *sizes); order = xnmalloc (cnt, sizeof *order); blocks = xnmalloc (cnt, sizeof *blocks); block_cnt = 0; composition_cnt = 0; - while (next_composition (cnt, &block_cnt, heights)) + while (next_composition (cnt, &block_cnt, sizes)) { int i; unsigned int permutation_cnt; - for (i = 0; i < block_cnt; i++) + for (i = 0; i < block_cnt; i++) order[i] = i; permutation_cnt = 0; - while (permutation_cnt == 0 || next_permutation (order, block_cnt)) + while (permutation_cnt == 0 || next_permutation (order, block_cnt)) { struct tower t; /* Insert blocks into tower in ascending order. */ tower_init (&t); - for (i = 0; i < block_cnt; i++) + for (i = 0; i < block_cnt; i++) { blocks[i].x = i; - tower_insert (&t, heights[i], &blocks[i].node, NULL); + tower_insert (&t, sizes[i], &blocks[i].node, NULL); expected[i].x = i; - expected[i].height = heights[i]; + expected[i].size = sizes[i]; } check_tower (&t, expected, block_cnt); - + /* Delete blocks from tower in the order of order[]. */ for (i = 0; i < block_cnt; i++) @@ -439,7 +437,7 @@ test_delete (void) int idx = order[i]; int j; tower_delete (&t, &blocks[idx].node); - for (j = 0; ; j++) + for (j = 0; ; j++) { assert (j < block_cnt - i); if (expected[j].x == idx) @@ -455,85 +453,85 @@ test_delete (void) permutation_cnt++; } check (permutation_cnt == factorial (block_cnt)); - + composition_cnt++; } check (composition_cnt == 1 << (cnt - 1)); free (expected); - free (heights); + free (sizes); free (order); free (blocks); } } -/* Tests towers containing all possible block heights, resizing - the blocks to all possible heights that conserve the total +/* Tests towers containing all possible block sizes, resizing + the blocks to all possible sizes that conserve the total tower height, up to a maximum total tower height. */ static void -test_resize (void) +test_resize (void) { const int max_height = 9; int cnt; - for (cnt = 1; cnt <= max_height; cnt++) + for (cnt = 1; cnt <= max_height; cnt++) { unsigned int composition_cnt; struct expected_block *expected; - int *heights, *new_heights; + int *sizes, *new_sizes; int block_cnt; int *order; struct block *blocks; - + expected = xnmalloc (cnt, sizeof *expected); - heights = xnmalloc (cnt, sizeof *heights); - new_heights = xnmalloc (cnt, sizeof *new_heights); + sizes = xnmalloc (cnt, sizeof *sizes); + new_sizes = xnmalloc (cnt, sizeof *new_sizes); order = xnmalloc (cnt, sizeof *order); blocks = xnmalloc (cnt, sizeof *blocks); block_cnt = 0; composition_cnt = 0; - while (next_composition (cnt, &block_cnt, heights)) + while (next_composition (cnt, &block_cnt, sizes)) { int i; unsigned int resizes = 0; - for (resizes = 0, first_k_composition (cnt, block_cnt, new_heights); + for (resizes = 0, first_k_composition (cnt, block_cnt, new_sizes); (resizes == 0 - || next_k_composition (cnt, block_cnt, new_heights)); + || next_k_composition (cnt, block_cnt, new_sizes)); resizes++) { struct tower t; /* Insert blocks into tower in ascending order. */ tower_init (&t); - for (i = 0; i < block_cnt; i++) + for (i = 0; i < block_cnt; i++) { blocks[i].x = i; - tower_insert (&t, heights[i], &blocks[i].node, NULL); + tower_insert (&t, sizes[i], &blocks[i].node, NULL); expected[i].x = i; - expected[i].height = heights[i]; + expected[i].size = sizes[i]; } check_tower (&t, expected, block_cnt); /* Resize all the blocks. */ - for (i = 0; i < block_cnt; i++) + for (i = 0; i < block_cnt; i++) { - if (expected[i].height != new_heights[i] || rand () % 2) - tower_resize (&t, &blocks[i].node, new_heights[i]); - expected[i].height = new_heights[i]; + if (expected[i].size != new_sizes[i] || rand () % 2) + tower_resize (&t, &blocks[i].node, new_sizes[i]); + expected[i].size = new_sizes[i]; } check_tower (&t, expected, block_cnt); } check (resizes == binomial_cofficient (cnt - 1, block_cnt - 1)); - + composition_cnt++; } check (composition_cnt == 1 << (cnt - 1)); free (expected); - free (new_heights); - free (heights); + free (new_sizes); + free (sizes); free (order); free (blocks); } @@ -542,29 +540,29 @@ test_resize (void) /* Tests splicing all possible contiguous sets of blocks out of one tower into a second, initially empty tower. */ static void -test_splice_out (void) +test_splice_out (void) { const int max_height = 9; int cnt; - for (cnt = 1; cnt <= max_height; cnt++) + for (cnt = 1; cnt <= max_height; cnt++) { unsigned int composition_cnt; struct expected_block *expected; - int *heights, *new_heights; + int *sizes, *new_sizes; int block_cnt; int *order; struct block *blocks; - + expected = xnmalloc (cnt, sizeof *expected); - heights = xnmalloc (cnt, sizeof *heights); - new_heights = xnmalloc (cnt, sizeof *new_heights); + sizes = xnmalloc (cnt, sizeof *sizes); + new_sizes = xnmalloc (cnt, sizeof *new_sizes); order = xnmalloc (cnt, sizeof *order); blocks = xnmalloc (cnt, sizeof *blocks); block_cnt = 0; composition_cnt = 0; - while (next_composition (cnt, &block_cnt, heights)) + while (next_composition (cnt, &block_cnt, sizes)) { int i, j; @@ -578,12 +576,12 @@ test_splice_out (void) tower_init (&dst); /* Insert blocks into SRC and DST in ascending order. */ - for (k = 0; k < block_cnt; k++) + for (k = 0; k < block_cnt; k++) { blocks[k].x = k; - tower_insert (&src, heights[k], &blocks[k].node, NULL); + tower_insert (&src, sizes[k], &blocks[k].node, NULL); expected[k].x = k; - expected[k].height = heights[k]; + expected[k].size = sizes[k]; } check_tower (&src, expected, block_cnt); @@ -600,8 +598,8 @@ test_splice_out (void) check (composition_cnt == 1 << (cnt - 1)); free (expected); - free (new_heights); - free (heights); + free (new_sizes); + free (sizes); free (order); free (blocks); } @@ -610,29 +608,29 @@ test_splice_out (void) /* Tests splicing all of the contents of a tower into all possible positions in a second tower. */ static void -test_splice_in (void) +test_splice_in (void) { const int max_height = 9; int cnt; - for (cnt = 1; cnt <= max_height; cnt++) + for (cnt = 1; cnt <= max_height; cnt++) { unsigned int composition_cnt; struct expected_block *expected; - int *heights, *new_heights; + int *sizes, *new_sizes; int block_cnt; int *order; struct block *blocks; - + expected = xnmalloc (cnt, sizeof *expected); - heights = xnmalloc (cnt, sizeof *heights); - new_heights = xnmalloc (cnt, sizeof *new_heights); + sizes = xnmalloc (cnt, sizeof *sizes); + new_sizes = xnmalloc (cnt, sizeof *new_sizes); order = xnmalloc (cnt, sizeof *order); blocks = xnmalloc (cnt, sizeof *blocks); block_cnt = 0; composition_cnt = 0; - while (next_composition (cnt, &block_cnt, heights)) + while (next_composition (cnt, &block_cnt, sizes)) { int i, j; @@ -646,13 +644,13 @@ test_splice_in (void) tower_init (&dst); /* Insert blocks into SRC and DST in ascending order. */ - for (k = 0; k < block_cnt; k++) + for (k = 0; k < block_cnt; k++) { blocks[k].x = k; - tower_insert (k >= i && k < j ? &src : &dst, - heights[k], &blocks[k].node, NULL); + tower_insert (k >= i && k < j ? &src : &dst, + sizes[k], &blocks[k].node, NULL); expected[k].x = k; - expected[k].height = heights[k]; + expected[k].size = sizes[k]; } /* Splice SRC into DST. */ @@ -665,8 +663,8 @@ test_splice_in (void) check (composition_cnt == 1 << (cnt - 1)); free (expected); - free (new_heights); - free (heights); + free (new_sizes); + free (sizes); free (order); free (blocks); } @@ -675,25 +673,74 @@ test_splice_in (void) /* Main program. */ -/* Runs TEST_FUNCTION and prints a message about NAME. */ -static void -run_test (void (*test_function) (void), const char *name) -{ - test_name = name; - putchar ('.'); - fflush (stdout); - test_function (); -} +struct test + { + const char *name; + const char *description; + void (*function) (void); + }; + +static const struct test tests[] = + { + { + "insert", + "insert", + test_insert + }, + { + "delete", + "delete", + test_delete + }, + { + "resize", + "resize", + test_resize + }, + { + "splice-out", + "splice out", + test_splice_out + }, + { + "splice-in", + "splice in", + test_splice_in + }, + }; + +enum { N_TESTS = sizeof tests / sizeof *tests }; int -main (void) +main (int argc, char *argv[]) { - run_test (test_insert, "insert"); - run_test (test_delete, "delete"); - run_test (test_resize, "resize"); - run_test (test_splice_out, "splice out"); - run_test (test_splice_in, "splice in"); - putchar ('\n'); - - return 0; + int i; + + if (argc != 2) + { + fprintf (stderr, "exactly one argument required; use --help for help\n"); + return EXIT_FAILURE; + } + else if (!strcmp (argv[1], "--help")) + { + printf ("%s: test tower library\n" + "usage: %s TEST-NAME\n" + "where TEST-NAME is one of the following:\n", + argv[0], argv[0]); + for (i = 0; i < N_TESTS; i++) + printf (" %s\n %s\n", tests[i].name, tests[i].description); + return 0; + } + else + { + for (i = 0; i < N_TESTS; i++) + if (!strcmp (argv[1], tests[i].name)) + { + tests[i].function (); + return 0; + } + + fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]); + return EXIT_FAILURE; + } }