X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=tests%2Flibpspp%2Ftower-test.c;h=33393ae1b0b1d61fb608e908b5d4fd9d22c15390;hb=d98583b9425b8a053dc21b539203406bac74adc5;hp=504e19f409aa05bb8a4df7b6969d6197d91f739b;hpb=43b1296aafe7582e7dbe6c2b6a8b478d7d9b0fcf;p=pspp diff --git a/tests/libpspp/tower-test.c b/tests/libpspp/tower-test.c index 504e19f409..33393ae1b0 100644 --- a/tests/libpspp/tower-test.c +++ b/tests/libpspp/tower-test.c @@ -1,5 +1,5 @@ /* PSPP - a program for statistical analysis. - Copyright (C) 2007 Free Software Foundation, Inc. + Copyright (C) 2007, 2010, 2013 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 @@ -39,9 +39,6 @@ #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 @@ -57,8 +54,7 @@ check_func (bool ok, int line) { 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 (); } } @@ -93,18 +89,18 @@ swap (int *a, int *b) *b = t; } -/* Reverses the order of the CNT integers starting at VALUES. */ +/* Reverses the order of the N integers starting at VALUES. */ static void -reverse (int *values, size_t cnt) +reverse (int *values, size_t n) { size_t i = 0; - size_t j = cnt; + size_t j = n; while (j > i) swap (&values[i++], &values[--j]); } -/* Arranges the CNT blocks in VALUES into the lexicographically +/* Arranges the N blocks in VALUES into the lexicographically next greater permutation. Returns true if successful. If VALUES is already the lexicographically greatest permutation of its blocks (i.e. ordered from greatest to @@ -112,26 +108,26 @@ reverse (int *values, size_t cnt) permutation (i.e. ordered from smallest to largest) and returns false. */ static bool -next_permutation (int *values, size_t cnt) +next_permutation (int *values, size_t n) { - if (cnt > 0) + if (n > 0) { - size_t i = cnt - 1; + size_t i = n - 1; while (i != 0) { i--; if (values[i] < values[i + 1]) { size_t j; - for (j = cnt - 1; values[i] >= values[j]; j--) + for (j = n - 1; values[i] >= values[j]; j--) continue; swap (values + i, values + j); - reverse (values + (i + 1), cnt - (i + 1)); + reverse (values + (i + 1), n - (i + 1)); return true; } } - reverse (values, cnt); + reverse (values, n); } return false; @@ -144,7 +140,7 @@ factorial (unsigned int n) unsigned int value = 1; /* Disallow N values that overflow on 32-bit machines. */ assert (n <= 12); - for (; n > 1; ) + for (; n > 1;) value *= n--; return value; } @@ -245,28 +241,29 @@ next_composition (int n, int *k, int parts[]) /* A block expected to be found in a tower. */ struct expected_block { - int height; /* Expected height of bottom of block. */ + int size; /* Expected thickness of block. */ int x; /* Expected value for `x' member. */ }; -/* Checks that tower T contains the BLOCK_CNT blocks described by +/* Checks that tower T contains the BLOCK_N blocks described by BLOCKS[]. */ static void check_tower (struct tower *t, - struct expected_block blocks[], size_t block_cnt) + struct expected_block blocks[], size_t n_blocks) { int total_height; struct tower_node *node; size_t i; - check (tower_is_empty (t) == (block_cnt == 0)); + check (tower_count (t) == n_blocks); + check (tower_is_empty (t) == (n_blocks == 0)); total_height = 0; - for (i = 0; i < block_cnt; i++) + for (i = 0; i < n_blocks; i++) { unsigned long int level; for (level = total_height; - level < total_height + blocks[i].height; + level < total_height + blocks[i].size; level++) { struct tower_node *found; @@ -275,8 +272,11 @@ 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); @@ -284,16 +284,16 @@ check_tower (struct tower *t, node != NULL; 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); + check (i == n_blocks); - for (node = tower_last (t), i = block_cnt - 1; + for (node = tower_last (t), i = n_blocks - 1; node != NULL; 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); @@ -306,41 +306,41 @@ static void test_insert (void) { const int max_height = 7; - int cnt; + int n; - for (cnt = 1; cnt <= max_height; cnt++) + for (n = 1; n <= max_height; n++) { - unsigned int composition_cnt; + unsigned int n_compositions; struct expected_block *expected; - int *heights; - int block_cnt; + int *sizes; + int n_blocks; int *order; struct block *blocks; - expected = xnmalloc (cnt, sizeof *expected); - heights = xnmalloc (cnt, sizeof *heights); - order = xnmalloc (cnt, sizeof *order); - blocks = xnmalloc (cnt, sizeof *blocks); + expected = xnmalloc (n, sizeof *expected); + sizes = xnmalloc (n, sizeof *sizes); + order = xnmalloc (n, sizeof *order); + blocks = xnmalloc (n, sizeof *blocks); - block_cnt = 0; - composition_cnt = 0; - while (next_composition (cnt, &block_cnt, heights)) + n_blocks = 0; + n_compositions = 0; + while (next_composition (n, &n_blocks, sizes)) { int i, j; - unsigned int permutation_cnt; + unsigned int n_permutations; - for (i = 0; i < block_cnt; i++) + for (i = 0; i < n_blocks; i++) order[i] = i; - permutation_cnt = 0; - while (permutation_cnt == 0 || next_permutation (order, block_cnt)) + n_permutations = 0; + while (n_permutations == 0 || next_permutation (order, n_blocks)) { struct tower t; - /* Inserts the block_cnt blocks with the given - heights[] into T in the order given by order[]. */ + /* Inserts the n_blocks blocks with the given + sizes[] into T in the order given by order[]. */ tower_init (&t); - for (i = 0; i < block_cnt; i++) + for (i = 0; i < n_blocks; i++) { struct block *under; int idx; @@ -354,184 +354,184 @@ 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++) + for (i = 0; i < n_blocks; i++) { - expected[i].height = heights[i]; + expected[i].size = sizes[i]; expected[i].x = i; } - check_tower (&t, expected, block_cnt); + check_tower (&t, expected, n_blocks); - permutation_cnt++; + n_permutations++; } - check (permutation_cnt == factorial (block_cnt)); + check (n_permutations == factorial (n_blocks)); - composition_cnt++; + n_compositions++; } - check (composition_cnt == 1 << (cnt - 1)); + check (n_compositions == 1 << (n - 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) { const int max_height = 7; - int cnt; + int n; - for (cnt = 1; cnt <= max_height; cnt++) + for (n = 1; n <= max_height; n++) { - unsigned int composition_cnt; + unsigned int n_compositions; struct expected_block *expected; - int *heights; - int block_cnt; + int *sizes; + int n_blocks; int *order; struct block *blocks; - expected = xnmalloc (cnt, sizeof *expected); - heights = xnmalloc (cnt, sizeof *heights); - order = xnmalloc (cnt, sizeof *order); - blocks = xnmalloc (cnt, sizeof *blocks); + expected = xnmalloc (n, sizeof *expected); + sizes = xnmalloc (n, sizeof *sizes); + order = xnmalloc (n, sizeof *order); + blocks = xnmalloc (n, sizeof *blocks); - block_cnt = 0; - composition_cnt = 0; - while (next_composition (cnt, &block_cnt, heights)) + n_blocks = 0; + n_compositions = 0; + while (next_composition (n, &n_blocks, sizes)) { int i; - unsigned int permutation_cnt; + unsigned int n_permutations; - for (i = 0; i < block_cnt; i++) + for (i = 0; i < n_blocks; i++) order[i] = i; - permutation_cnt = 0; - while (permutation_cnt == 0 || next_permutation (order, block_cnt)) + n_permutations = 0; + while (n_permutations == 0 || next_permutation (order, n_blocks)) { struct tower t; /* Insert blocks into tower in ascending order. */ tower_init (&t); - for (i = 0; i < block_cnt; i++) + for (i = 0; i < n_blocks; 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); + check_tower (&t, expected, n_blocks); /* Delete blocks from tower in the order of order[]. */ - for (i = 0; i < block_cnt; i++) + for (i = 0; i < n_blocks; i++) { int idx = order[i]; int j; tower_delete (&t, &blocks[idx].node); for (j = 0; ; j++) { - assert (j < block_cnt - i); + assert (j < n_blocks - i); if (expected[j].x == idx) { - memcpy (&expected[j], &expected[j + 1], - sizeof *expected * (block_cnt - i - j - 1)); + memmove (&expected[j], &expected[j + 1], + sizeof *expected * (n_blocks - i - j - 1)); break; } } - check_tower (&t, expected, block_cnt - i - 1); + check_tower (&t, expected, n_blocks - i - 1); } - permutation_cnt++; + n_permutations++; } - check (permutation_cnt == factorial (block_cnt)); + check (n_permutations == factorial (n_blocks)); - composition_cnt++; + n_compositions++; } - check (composition_cnt == 1 << (cnt - 1)); + check (n_compositions == 1 << (n - 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) { const int max_height = 9; - int cnt; + int n; - for (cnt = 1; cnt <= max_height; cnt++) + for (n = 1; n <= max_height; n++) { - unsigned int composition_cnt; + unsigned int n_compositions; struct expected_block *expected; - int *heights, *new_heights; - int block_cnt; + int *sizes, *new_sizes; + int n_blocks; int *order; struct block *blocks; - expected = xnmalloc (cnt, sizeof *expected); - heights = xnmalloc (cnt, sizeof *heights); - new_heights = xnmalloc (cnt, sizeof *new_heights); - order = xnmalloc (cnt, sizeof *order); - blocks = xnmalloc (cnt, sizeof *blocks); + expected = xnmalloc (n, sizeof *expected); + sizes = xnmalloc (n, sizeof *sizes); + new_sizes = xnmalloc (n, sizeof *new_sizes); + order = xnmalloc (n, sizeof *order); + blocks = xnmalloc (n, sizeof *blocks); - block_cnt = 0; - composition_cnt = 0; - while (next_composition (cnt, &block_cnt, heights)) + n_blocks = 0; + n_compositions = 0; + while (next_composition (n, &n_blocks, sizes)) { int i; unsigned int resizes = 0; - for (resizes = 0, first_k_composition (cnt, block_cnt, new_heights); + for (resizes = 0, first_k_composition (n, n_blocks, new_sizes); (resizes == 0 - || next_k_composition (cnt, block_cnt, new_heights)); + || next_k_composition (n, n_blocks, 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 < n_blocks; 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); + check_tower (&t, expected, n_blocks); /* Resize all the blocks. */ - for (i = 0; i < block_cnt; i++) + for (i = 0; i < n_blocks; 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_tower (&t, expected, n_blocks); } - check (resizes == binomial_cofficient (cnt - 1, block_cnt - 1)); + check (resizes == binomial_cofficient (n - 1, n_blocks - 1)); - composition_cnt++; + n_compositions++; } - check (composition_cnt == 1 << (cnt - 1)); + check (n_compositions == 1 << (n - 1)); free (expected); - free (new_heights); - free (heights); + free (new_sizes); + free (sizes); free (order); free (blocks); } @@ -543,31 +543,31 @@ static void test_splice_out (void) { const int max_height = 9; - int cnt; + int n; - for (cnt = 1; cnt <= max_height; cnt++) + for (n = 1; n <= max_height; n++) { - unsigned int composition_cnt; + unsigned int n_compositions; struct expected_block *expected; - int *heights, *new_heights; - int block_cnt; + int *sizes, *new_sizes; + int n_blocks; int *order; struct block *blocks; - expected = xnmalloc (cnt, sizeof *expected); - heights = xnmalloc (cnt, sizeof *heights); - new_heights = xnmalloc (cnt, sizeof *new_heights); - order = xnmalloc (cnt, sizeof *order); - blocks = xnmalloc (cnt, sizeof *blocks); + expected = xnmalloc (n, sizeof *expected); + sizes = xnmalloc (n, sizeof *sizes); + new_sizes = xnmalloc (n, sizeof *new_sizes); + order = xnmalloc (n, sizeof *order); + blocks = xnmalloc (n, sizeof *blocks); - block_cnt = 0; - composition_cnt = 0; - while (next_composition (cnt, &block_cnt, heights)) + n_blocks = 0; + n_compositions = 0; + while (next_composition (n, &n_blocks, sizes)) { int i, j; - for (i = 0; i < block_cnt; i++) - for (j = i; j <= block_cnt; j++) + for (i = 0; i < n_blocks; i++) + for (j = i; j <= n_blocks; j++) { struct tower src, dst; int k; @@ -576,30 +576,30 @@ 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 < n_blocks; 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); + check_tower (&src, expected, n_blocks); /* Splice blocks I...J into DST. */ tower_splice (&dst, NULL, &src, &blocks[i].node, - j < block_cnt ? &blocks[j].node : NULL); + j < n_blocks ? &blocks[j].node : NULL); check_tower (&dst, &expected[i], j - i); memmove (&expected[i], &expected[j], - sizeof *expected * (block_cnt - j)); - check_tower (&src, expected, block_cnt - (j - i)); + sizeof *expected * (n_blocks - j)); + check_tower (&src, expected, n_blocks - (j - i)); } - composition_cnt++; + n_compositions++; } - check (composition_cnt == 1 << (cnt - 1)); + check (n_compositions == 1 << (n - 1)); free (expected); - free (new_heights); - free (heights); + free (new_sizes); + free (sizes); free (order); free (blocks); } @@ -611,31 +611,31 @@ static void test_splice_in (void) { const int max_height = 9; - int cnt; + int n; - for (cnt = 1; cnt <= max_height; cnt++) + for (n = 1; n <= max_height; n++) { - unsigned int composition_cnt; + unsigned int n_compositions; struct expected_block *expected; - int *heights, *new_heights; - int block_cnt; + int *sizes, *new_sizes; + int n_blocks; int *order; struct block *blocks; - expected = xnmalloc (cnt, sizeof *expected); - heights = xnmalloc (cnt, sizeof *heights); - new_heights = xnmalloc (cnt, sizeof *new_heights); - order = xnmalloc (cnt, sizeof *order); - blocks = xnmalloc (cnt, sizeof *blocks); + expected = xnmalloc (n, sizeof *expected); + sizes = xnmalloc (n, sizeof *sizes); + new_sizes = xnmalloc (n, sizeof *new_sizes); + order = xnmalloc (n, sizeof *order); + blocks = xnmalloc (n, sizeof *blocks); - block_cnt = 0; - composition_cnt = 0; - while (next_composition (cnt, &block_cnt, heights)) + n_blocks = 0; + n_compositions = 0; + while (next_composition (n, &n_blocks, sizes)) { int i, j; - for (i = 0; i < block_cnt; i++) - for (j = i; j <= block_cnt; j++) + for (i = 0; i < n_blocks; i++) + for (j = i; j <= n_blocks; j++) { struct tower src, dst; int k; @@ -644,27 +644,27 @@ 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 < n_blocks; k++) { blocks[k].x = k; tower_insert (k >= i && k < j ? &src : &dst, - heights[k], &blocks[k].node, NULL); + sizes[k], &blocks[k].node, NULL); expected[k].x = k; - expected[k].height = heights[k]; + expected[k].size = sizes[k]; } /* Splice SRC into DST. */ - tower_splice (&dst, j < block_cnt ? &blocks[j].node : NULL, + tower_splice (&dst, j < n_blocks ? &blocks[j].node : NULL, &src, i != j ? &blocks[i].node : NULL, NULL); - check_tower (&dst, expected, block_cnt); + check_tower (&dst, expected, n_blocks); } - composition_cnt++; + n_compositions++; } - check (composition_cnt == 1 << (cnt - 1)); + check (n_compositions == 1 << (n - 1)); free (expected); - free (new_heights); - free (heights); + free (new_sizes); + free (sizes); free (order); free (blocks); } @@ -673,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; + } }