X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=tests%2Flibpspp%2Fll-test.c;h=7bf01248c1b7a4cf2fe695431590e61fbaa7a574;hb=7891023bc75024553f2564017b685cdb13eeec33;hp=03fc0fd7d8be953061a7b7ed3ad4a6dd860426b8;hpb=480a0746507ce73d26f528b56dc3ed80195096e0;p=pspp diff --git a/tests/libpspp/ll-test.c b/tests/libpspp/ll-test.c index 03fc0fd7d8..7bf01248c1 100644 --- a/tests/libpspp/ll-test.c +++ b/tests/libpspp/ll-test.c @@ -1,20 +1,18 @@ -/* PSPP - computes sample statistics. - Copyright (C) 2006 Free Software Foundation, Inc. +/* PSPP - a program for statistical analysis. + Copyright (C) 2006, 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 ll_* routines defined in ll.c. This test program aims to be as comprehensive as @@ -28,6 +26,10 @@ See llx-test.c for a similar program for the llx_* routines. */ +#ifdef HAVE_CONFIG_H +#include +#endif + #include #include #include @@ -41,26 +43,22 @@ #define UNUSED #endif -/* 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 (); } } @@ -81,9 +79,9 @@ xalloc_die (void) /* Allocates and returns N bytes of memory. */ static void * -xmalloc (size_t n) +xmalloc (size_t n) { - if (n != 0) + if (n != 0) { void *p = malloc (n); if (p == NULL) @@ -97,7 +95,7 @@ xmalloc (size_t n) /* Allocates and returns N * M bytes of memory. */ static void * -xnmalloc (size_t n, size_t m) +xnmalloc (size_t n, size_t m) { if ((size_t) -1 / m <= n) xalloc_die (); @@ -114,7 +112,7 @@ struct element int y; /* Secondary value. */ }; -int aux_data; +static int aux_data; /* Returns the `struct element' that LL is embedded within. */ static struct element * @@ -130,7 +128,7 @@ print_list (struct ll_list *list) struct ll *x; printf ("list:"); - for (x = ll_head (list); x != ll_null (list); x = ll_next (x)) + for (x = ll_head (list); x != ll_null (list); x = ll_next (x)) { struct element *e = ll_to_element (x); printf (" %d", e->x); @@ -142,19 +140,19 @@ print_list (struct ll_list *list) AUX for each element in LIST. */ static void UNUSED print_pred (struct ll_list *list, - ll_predicate_func *predicate, void *aux UNUSED) + ll_predicate_func *predicate, void *aux UNUSED) { struct ll *x; printf ("pred:"); - for (x = ll_head (list); x != ll_null (list); x = ll_next (x)) + for (x = ll_head (list); x != ll_null (list); x = ll_next (x)) printf (" %d", predicate (x, aux)); printf ("\n"); } /* Prints the CNT numbers in VALUES. */ static void UNUSED -print_array (int values[], size_t cnt) +print_array (int values[], size_t cnt) { size_t i; @@ -167,7 +165,7 @@ print_array (int values[], size_t cnt) /* Compares the `x' values in A and B and returns a strcmp-type return value. Verifies that AUX points to aux_data. */ static int -compare_elements (const struct ll *a_, const struct ll *b_, void *aux) +compare_elements (const struct ll *a_, const struct ll *b_, void *aux) { const struct element *a = ll_to_element (a_); const struct element *b = ll_to_element (b_); @@ -180,7 +178,7 @@ compare_elements (const struct ll *a_, const struct ll *b_, void *aux) strcmp-type return value. Verifies that AUX points to aux_data. */ static int -compare_elements_x_y (const struct ll *a_, const struct ll *b_, void *aux) +compare_elements_x_y (const struct ll *a_, const struct ll *b_, void *aux) { const struct element *a = ll_to_element (a_); const struct element *b = ll_to_element (b_); @@ -209,10 +207,10 @@ compare_elements_y (const struct ll *a_, const struct ll *b_, void *aux) /* Returns true if the bit in *PATTERN indicated by `x in *ELEMENT is set, false otherwise. */ static bool -pattern_pred (const struct ll *element_, void *pattern_) +pattern_pred (const struct ll *element_, void *pattern_) { const struct element *element = ll_to_element (element_); - unsigned *pattern = pattern_; + unsigned int *pattern = pattern_; return (*pattern & (1u << element->x)) != 0; } @@ -229,7 +227,7 @@ allocate_elements (size_t n, struct ll_list *list, struct element ***elems, struct ll ***elemp, - int **values) + int **values) { size_t i; @@ -237,33 +235,33 @@ allocate_elements (size_t n, ll_init (list); *elems = xnmalloc (n, sizeof **elems); - for (i = 0; i < n; i++) + for (i = 0; i < n; i++) { (*elems)[i] = xmalloc (sizeof ***elems); if (list != NULL) ll_push_tail (list, &(*elems)[i]->ll); } - - if (elemp != NULL) + + if (elemp != NULL) { *elemp = xnmalloc (n + 1, sizeof *elemp); for (i = 0; i < n; i++) (*elemp)[i] = &(*elems)[i]->ll; (*elemp)[n] = ll_null (list); } - + if (values != NULL) *values = xnmalloc (n, sizeof *values); } /* Copies the CNT values of `x' from LIST into VALUES[]. */ static void -extract_values (struct ll_list *list, int values[], size_t cnt) +extract_values (struct ll_list *list, int values[], size_t cnt) { struct ll *x; - + check (ll_count (list) == cnt); - for (x = ll_head (list); x != ll_null (list); x = ll_next (x)) + for (x = ll_head (list); x != ll_null (list); x = ll_next (x)) { struct element *e = ll_to_element (x); *values++ = e->x; @@ -278,16 +276,16 @@ allocate_ascending (size_t n, struct ll_list *list, struct element ***elems, struct ll ***elemp, - int **values) + int **values) { size_t i; allocate_elements (n, list, elems, elemp, values); - for (i = 0; i < n; i++) + for (i = 0; i < n; i++) (*elems)[i]->x = i; if (values != NULL) - extract_values (list, *values, n); + extract_values (list, *values, n); } /* As allocate_elements, but sets binary values extracted from @@ -299,16 +297,16 @@ allocate_pattern (size_t n, struct ll_list *list, struct element ***elems, struct ll ***elemp, - int **values) + int **values) { size_t i; allocate_elements (n, list, elems, elemp, values); - - for (i = 0; i < n; i++) + + for (i = 0; i < n; i++) (*elems)[i]->x = (pattern & (1 << i)) != 0; if (values != NULL) - extract_values (list, *values, n); + extract_values (list, *values, n); } /* Randomly shuffles the CNT elements in ARRAY, each of which is @@ -320,10 +318,10 @@ random_shuffle (void *array_, size_t cnt, size_t size) char *tmp = xmalloc (size); size_t i; - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) { size_t j = rand () % (cnt - i) + i; - if (i != j) + if (i != j) { memcpy (tmp, array + j * size, size); memcpy (array + j * size, array + i * size, size); @@ -340,17 +338,17 @@ allocate_random (size_t n, struct ll_list *list, struct element ***elems, struct ll ***elemp, - int **values) + int **values) { size_t i; allocate_elements (n, list, elems, elemp, values); - - for (i = 0; i < n; i++) + + for (i = 0; i < n; i++) (*elems)[i]->x = i; random_shuffle (*elems, n, sizeof **elems); if (values != NULL) - extract_values (list, *values, n); + extract_values (list, *values, n); } /* Frees the N elements of ELEMS, ELEMP, and VALUES. */ @@ -358,20 +356,20 @@ static void free_elements (size_t n, struct element **elems, struct ll **elemp, - int *values) + int *values) { size_t i; for (i = 0; i < n; i++) free (elems[i]); - free (elems); + free (elems); free (elemp); free (values); } /* Compares A and B and returns a strcmp-type return value. */ static int -compare_ints (const void *a_, const void *b_, void *aux UNUSED) +compare_ints (const void *a_, const void *b_, void *aux UNUSED) { const int *a = a_; const int *b = b_; @@ -381,7 +379,7 @@ compare_ints (const void *a_, const void *b_, void *aux UNUSED) /* Compares A and B and returns a strcmp-type return value. */ static int -compare_ints_noaux (const void *a_, const void *b_) +compare_ints_noaux (const void *a_, const void *b_) { const int *a = a_; const int *b = b_; @@ -391,7 +389,7 @@ compare_ints_noaux (const void *a_, const void *b_) /* Checks that LIST contains the CNT values in ELEMENTS. */ static void -check_list_contents (struct ll_list *list, int elements[], size_t cnt) +check_list_contents (struct ll_list *list, int elements[], size_t cnt) { struct ll *ll; size_t i; @@ -399,7 +397,7 @@ check_list_contents (struct ll_list *list, int elements[], size_t cnt) check ((cnt == 0) == ll_is_empty (list)); /* Iterate in forward order. */ - for (ll = ll_head (list), i = 0; i < cnt; ll = ll_next (ll), i++) + for (ll = ll_head (list), i = 0; i < cnt; ll = ll_next (ll), i++) { struct element *e = ll_to_element (ll); check (elements[i] == e->x); @@ -430,7 +428,7 @@ lexicographical_compare_3way (const void *array1, size_t count1, size_t size, int (*compare) (const void *, const void *, void *aux), - void *aux) + void *aux) { const char *first1 = array1; const char *first2 = array2; @@ -469,7 +467,7 @@ test_push_pop (void) /* Push on tail. */ ll_init (&list); check_list_contents (&list, NULL, 0); - for (i = 0; i < max_elems; i++) + for (i = 0; i < max_elems; i++) { values[i] = elems[i]->x = i; ll_push_tail (&list, &elems[i]->ll); @@ -477,7 +475,7 @@ test_push_pop (void) } /* Remove from tail. */ - for (i = 0; i < max_elems; i++) + for (i = 0; i < max_elems; i++) { struct element *e = ll_to_element (ll_pop_tail (&list)); check (e->x == max_elems - i - 1); @@ -494,7 +492,7 @@ test_push_pop (void) } /* Remove from start. */ - for (i = 0; i < max_elems; i++) + for (i = 0; i < max_elems; i++) { struct element *e = ll_to_element (ll_pop_head (&list)); check (e->x == (int) i); @@ -506,12 +504,12 @@ test_push_pop (void) /* Tests insertion and removal at arbitrary positions. */ static void -test_insert_remove (void) +test_insert_remove (void) { const int max_elems = 16; int cnt; - for (cnt = 0; cnt < max_elems; cnt++) + for (cnt = 0; cnt < max_elems; cnt++) { struct element **elems; struct ll **elemp; @@ -523,7 +521,7 @@ test_insert_remove (void) allocate_ascending (cnt, &list, &elems, &elemp, NULL); extra.x = -1; - for (pos = 0; pos <= cnt; pos++) + for (pos = 0; pos <= cnt; pos++) { int i, j; @@ -547,12 +545,12 @@ test_insert_remove (void) /* Tests swapping individual elements. */ static void -test_swap (void) +test_swap (void) { const int max_elems = 8; int cnt; - for (cnt = 0; cnt <= max_elems; cnt++) + for (cnt = 0; cnt <= max_elems; cnt++) { struct ll_list list; struct element **elems; @@ -563,9 +561,9 @@ test_swap (void) allocate_ascending (cnt, &list, &elems, NULL, &values); check_list_contents (&list, values, cnt); - for (i = 0; i < cnt; i++) - for (j = 0; j < cnt; j++) - for (k = 0; k < 2; k++) + for (i = 0; i < cnt; i++) + for (j = 0; j < cnt; j++) + for (k = 0; k < 2; k++) { int t; @@ -574,23 +572,23 @@ test_swap (void) values[i] = values[j]; values[j] = t; check_list_contents (&list, values, cnt); - } - + } + free_elements (cnt, elems, NULL, values); } } /* Tests swapping ranges of list elements. */ static void -test_swap_range (void) +test_swap_range (void) { const int max_elems = 8; int cnt, a0, a1, b0, b1, r; - for (cnt = 0; cnt <= max_elems; cnt++) - for (a0 = 0; a0 <= cnt; a0++) + for (cnt = 0; cnt <= max_elems; cnt++) + for (a0 = 0; a0 <= cnt; a0++) for (a1 = a0; a1 <= cnt; a1++) - for (b0 = a1; b0 <= cnt; b0++) + for (b0 = a1; b0 <= cnt; b0++) for (b1 = b0; b1 <= cnt; b1++) for (r = 0; r < 2; r++) { @@ -629,14 +627,14 @@ test_swap_range (void) /* Tests removing ranges of list elements. */ static void -test_remove_range (void) +test_remove_range (void) { const int max_elems = 8; int cnt, r0, r1; for (cnt = 0; cnt <= max_elems; cnt++) - for (r0 = 0; r0 <= cnt; r0++) + for (r0 = 0; r0 <= cnt; r0++) for (r1 = r0; r1 <= cnt; r1++) { struct ll_list list; @@ -664,7 +662,7 @@ test_remove_range (void) /* Tests ll_remove_equal. */ static void -test_remove_equal (void) +test_remove_equal (void) { const int max_elems = 8; @@ -673,7 +671,7 @@ test_remove_equal (void) for (cnt = 0; cnt <= max_elems; cnt++) for (r0 = 0; r0 <= cnt; r0++) for (r1 = r0; r1 <= cnt; r1++) - for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) + for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) { struct ll_list list; struct element **elems; @@ -687,13 +685,13 @@ test_remove_equal (void) allocate_elements (cnt, &list, &elems, &elemp, &values); remaining = 0; - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) { int x = eq_pat & (1 << i) ? -1 : i; bool delete = x == -1 && r0 <= i && i < r1; elems[i]->x = x; if (!delete) - values[remaining++] = x; + values[remaining++] = x; } to_remove.x = -1; @@ -708,7 +706,7 @@ test_remove_equal (void) /* Tests ll_remove_if. */ static void -test_remove_if (void) +test_remove_if (void) { const int max_elems = 8; @@ -717,7 +715,7 @@ test_remove_if (void) for (cnt = 0; cnt <= max_elems; cnt++) for (r0 = 0; r0 <= cnt; r0++) for (r1 = r0; r1 <= cnt; r1++) - for (pattern = 0; pattern <= 1 << cnt; pattern++) + for (pattern = 0; pattern <= 1 << cnt; pattern++) { struct ll_list list; struct element **elems; @@ -730,15 +728,15 @@ test_remove_if (void) allocate_elements (cnt, &list, &elems, &elemp, &values); remaining = 0; - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) { bool delete = (pattern & (1 << i)) && r0 <= i && i < r1; elems[i]->x = i; if (!delete) - values[remaining++] = i; + values[remaining++] = i; } - check ((int) ll_remove_if (elemp[r0], elemp[r1], + check ((int) ll_remove_if (elemp[r0], elemp[r1], pattern_pred, &pattern) == cnt - remaining); check_list_contents (&list, values, remaining); @@ -749,7 +747,7 @@ test_remove_if (void) /* Tests ll_moved. */ static void -test_moved (void) +test_moved (void) { const int max_elems = 8; @@ -768,7 +766,7 @@ test_moved (void) allocate_elements (cnt, NULL, &new_elems, NULL, NULL); check_list_contents (&list, values, cnt); - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) { *new_elems[i] = *elems[i]; ll_moved (&new_elems[i]->ll); @@ -792,7 +790,7 @@ test_examine_equal_range (void (*helper) (int r0, int r1, int eq_pat, int cnt, r0, r1, eq_pat; for (cnt = 0; cnt <= max_elems; cnt++) - for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) + for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) { struct ll_list list; struct element **elems; @@ -831,7 +829,7 @@ test_examine_if_range (void (*helper) (int r0, int r1, int eq_pat, int cnt, r0, r1, eq_pat; for (cnt = 0; cnt <= max_elems; cnt++) - for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) + for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) { struct ll_list list; struct element **elems; @@ -864,12 +862,12 @@ test_find_equal_helper (int r0, int r1, int eq_pat, if (eq_pat & (1 << i)) break; - check (match == elemp[i]); + check (match == elemp[i]); } /* Tests ll_find_equal. */ static void -test_find_equal (void) +test_find_equal (void) { test_examine_equal_range (test_find_equal_helper); } @@ -886,26 +884,26 @@ test_find_if_helper (int r0, int r1, int eq_pat, struct ll **elemp) if (eq_pat & (1 << i)) break; - check (match == elemp[i]); + check (match == elemp[i]); } /* Tests ll_find_if. */ static void -test_find_if (void) +test_find_if (void) { test_examine_if_range (test_find_if_helper); } /* Tests ll_find_adjacent_equal. */ static void -test_find_adjacent_equal (void) +test_find_adjacent_equal (void) { const int max_elems = 8; int cnt, eq_pat; for (cnt = 0; cnt <= max_elems; cnt++) - for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) + for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) { struct ll_list list; struct element **elems; @@ -918,10 +916,10 @@ test_find_adjacent_equal (void) allocate_ascending (cnt, &list, &elems, &elemp, &values); match = -1; - for (i = 0; i < cnt - 1; i++) + for (i = 0; i < cnt - 1; i++) { elems[i]->y = i; - if (eq_pat & (1 << i)) + if (eq_pat & (1 << i)) { values[i] = elems[i]->x = match; values[i + 1] = elems[i + 1]->x = match; @@ -929,7 +927,7 @@ test_find_adjacent_equal (void) else match--; } - + for (i = 0; i <= cnt; i++) { struct ll *ll1 = ll_find_adjacent_equal (elemp[i], ll_null (&list), @@ -940,7 +938,7 @@ test_find_adjacent_equal (void) ll2 = ll_null (&list); for (j = i; j < cnt - 1; j++) - if (eq_pat & (1 << j)) + if (eq_pat & (1 << j)) { ll2 = elemp[j]; break; @@ -962,7 +960,7 @@ test_count_range_helper (int r0, int r1, int eq_pat UNUSED, struct ll **elemp) /* Tests ll_count_range. */ static void -test_count_range (void) +test_count_range (void) { test_examine_if_range (test_count_range_helper); } @@ -981,20 +979,20 @@ test_count_equal_helper (int r0, int r1, int eq_pat, for (i = r0; i < r1; i++) if (eq_pat & (1 << i)) count2++; - - check (count1 == count2); + + check (count1 == count2); } /* Tests ll_count_equal. */ static void -test_count_equal (void) +test_count_equal (void) { test_examine_equal_range (test_count_equal_helper); } /* Helper function for testing ll_count_if. */ static void -test_count_if_helper (int r0, int r1, int eq_pat, struct ll **elemp) +test_count_if_helper (int r0, int r1, int eq_pat, struct ll **elemp) { int count1; int count2; @@ -1007,21 +1005,21 @@ test_count_if_helper (int r0, int r1, int eq_pat, struct ll **elemp) if (eq_pat & (1 << i)) count2++; - check (count1 == count2); + check (count1 == count2); } /* Tests ll_count_if. */ static void -test_count_if (void) +test_count_if (void) { test_examine_if_range (test_count_if_helper); } /* Returns N!. */ -static unsigned -factorial (unsigned n) +static unsigned int +factorial (unsigned int n) { - unsigned value = 1; + unsigned int value = 1; while (n > 1) value *= n--; return value; @@ -1030,14 +1028,14 @@ factorial (unsigned n) /* Returns the number of permutations of the CNT values in VALUES. If VALUES contains duplicates, they must be adjacent. */ -static unsigned -expected_perms (int *values, size_t cnt) +static unsigned int +expected_perms (int *values, size_t cnt) { size_t i, j; - unsigned perm_cnt; - + unsigned int perm_cnt; + perm_cnt = factorial (cnt); - for (i = 0; i < cnt; i = j) + for (i = 0; i < cnt; i = j) { for (j = i + 1; j < cnt; j++) if (values[i] != values[j]) @@ -1049,12 +1047,12 @@ expected_perms (int *values, size_t cnt) /* Tests ll_min and ll_max. */ static void -test_min_max (void) +test_min_max (void) { const int max_elems = 6; int cnt; - for (cnt = 0; cnt <= max_elems; cnt++) + for (cnt = 0; cnt <= max_elems; cnt++) { struct ll_list list; struct element **elems; @@ -1068,32 +1066,32 @@ test_min_max (void) perm_cnt = 1; while (ll_next_permutation (ll_head (&list), ll_null (&list), - compare_elements, &aux_data)) + compare_elements, &aux_data)) { int r0, r1; struct ll *x; int i; - + for (i = 0, x = ll_head (&list); x != ll_null (&list); - x = ll_next (x), i++) + x = ll_next (x), i++) { struct element *e = ll_to_element (x); elemp[i] = x; new_values[i] = e->x; } for (r0 = 0; r0 <= cnt; r0++) - for (r1 = r0; r1 <= cnt; r1++) + for (r1 = r0; r1 <= cnt; r1++) { struct ll *min = ll_min (elemp[r0], elemp[r1], compare_elements, &aux_data); struct ll *max = ll_max (elemp[r0], elemp[r1], compare_elements, &aux_data); - if (r0 == r1) + if (r0 == r1) { check (min == elemp[r1]); - check (max == elemp[r1]); + check (max == elemp[r1]); } - else + else { int min_int, max_int; int i; @@ -1110,7 +1108,7 @@ test_min_max (void) check (min != elemp[r1] && ll_to_element (min)->x == min_int); check (max != elemp[r1] - && ll_to_element (max)->x == max_int); + && ll_to_element (max)->x == max_int); } } perm_cnt++; @@ -1125,7 +1123,7 @@ test_min_max (void) /* Tests ll_lexicographical_compare_3way. */ static void -test_lexicographical_compare_3way (void) +test_lexicographical_compare_3way (void) { const int max_elems = 4; @@ -1134,7 +1132,7 @@ test_lexicographical_compare_3way (void) for (cnt_a = 0; cnt_a <= max_elems; cnt_a++) for (pat_a = 0; pat_a <= 1 << cnt_a; pat_a++) for (cnt_b = 0; cnt_b <= max_elems; cnt_b++) - for (pat_b = 0; pat_b <= 1 << cnt_b; pat_b++) + for (pat_b = 0; pat_b <= 1 << cnt_b; pat_b++) { struct ll_list list_a, list_b; struct element **elems_a, **elems_b; @@ -1165,7 +1163,7 @@ test_lexicographical_compare_3way (void) compare_elements, &aux_data); check (a_ordering == b_ordering); - } + } free_elements (cnt_a, elems_a, elemp_a, values_a); free_elements (cnt_b, elems_b, elemp_b, values_b); @@ -1175,24 +1173,24 @@ test_lexicographical_compare_3way (void) /* Appends the `x' value in element E to the array pointed to by NEXT_OUTPUT, and advances NEXT_OUTPUT to the next position. */ static void -apply_func (struct ll *e_, void *next_output_) +apply_func (struct ll *e_, void *next_output_) { struct element *e = ll_to_element (e_); int **next_output = next_output_; - + *(*next_output)++ = e->x; } /* Tests ll_apply. */ static void -test_apply (void) +test_apply (void) { const int max_elems = 8; int cnt, r0, r1; for (cnt = 0; cnt <= max_elems; cnt++) - for (r0 = 0; r0 <= cnt; r0++) + for (r0 = 0; r0 <= cnt; r0++) for (r1 = r0; r1 <= cnt; r1++) { struct ll_list list; @@ -1223,14 +1221,14 @@ test_apply (void) /* Tests ll_reverse. */ static void -test_reverse (void) +test_reverse (void) { const int max_elems = 8; int cnt, r0, r1; for (cnt = 0; cnt <= max_elems; cnt++) - for (r0 = 0; r0 <= cnt; r0++) + for (r0 = 0; r0 <= cnt; r0++) for (r1 = r0; r1 <= cnt; r1++) { struct ll_list list; @@ -1261,12 +1259,12 @@ test_reverse (void) /* Tests ll_next_permutation and ll_prev_permutation when the permuted values have no duplicates. */ static void -test_permutations_no_dups (void) +test_permutations_no_dups (void) { const int max_elems = 8; int cnt; - for (cnt = 0; cnt <= max_elems; cnt++) + for (cnt = 0; cnt <= max_elems; cnt++) { struct ll_list list; struct element **elems; @@ -1281,7 +1279,7 @@ test_permutations_no_dups (void) perm_cnt = 1; extract_values (&list, old_values, cnt); while (ll_next_permutation (ll_head (&list), ll_null (&list), - compare_elements, &aux_data)) + compare_elements, &aux_data)) { extract_values (&list, new_values, cnt); check (lexicographical_compare_3way (new_values, cnt, @@ -1298,7 +1296,7 @@ test_permutations_no_dups (void) ll_reverse (ll_head (&list), ll_null (&list)); extract_values (&list, old_values, cnt); while (ll_prev_permutation (ll_head (&list), ll_null (&list), - compare_elements, &aux_data)) + compare_elements, &aux_data)) { extract_values (&list, new_values, cnt); check (lexicographical_compare_3way (new_values, cnt, @@ -1321,7 +1319,7 @@ test_permutations_no_dups (void) /* Tests ll_next_permutation and ll_prev_permutation when the permuted values contain duplicates. */ static void -test_permutations_with_dups (void) +test_permutations_with_dups (void) { const int max_elems = 8; const int max_dup = 3; @@ -1330,7 +1328,7 @@ test_permutations_with_dups (void) int cnt, repeat; for (repeat = 0; repeat < repetitions; repeat++) - for (cnt = 0; cnt < max_elems; cnt++) + for (cnt = 0; cnt < max_elems; cnt++) { struct ll_list list; struct element **elems; @@ -1338,10 +1336,10 @@ test_permutations_with_dups (void) int *old_values = xnmalloc (max_elems, sizeof *values); int *new_values = xnmalloc (max_elems, sizeof *values); - unsigned permutation_cnt; + unsigned int permutation_cnt; int left = cnt; int value = 0; - + allocate_elements (cnt, &list, &elems, NULL, &values); value = 0; @@ -1360,7 +1358,7 @@ test_permutations_with_dups (void) permutation_cnt = 1; extract_values (&list, old_values, cnt); while (ll_next_permutation (ll_head (&list), ll_null (&list), - compare_elements, &aux_data)) + compare_elements, &aux_data)) { extract_values (&list, new_values, cnt); check (lexicographical_compare_3way (new_values, cnt, @@ -1377,7 +1375,7 @@ test_permutations_with_dups (void) ll_reverse (ll_head (&list), ll_null (&list)); extract_values (&list, old_values, cnt); while (ll_prev_permutation (ll_head (&list), ll_null (&list), - compare_elements, &aux_data)) + compare_elements, &aux_data)) { extract_values (&list, new_values, cnt); check (lexicographical_compare_3way (new_values, cnt, @@ -1398,13 +1396,13 @@ test_permutations_with_dups (void) /* Tests ll_merge when no equal values are to be merged. */ static void -test_merge_no_dups (void) +test_merge_no_dups (void) { const int max_elems = 8; const int max_filler = 3; int merge_cnt, pattern, pfx, gap, sfx, order; - + for (merge_cnt = 0; merge_cnt < max_elems; merge_cnt++) for (pattern = 0; pattern <= (1 << merge_cnt); pattern++) for (pfx = 0; pfx < max_filler; pfx++) @@ -1473,12 +1471,12 @@ test_merge_no_dups (void) /* Tests ll_merge when equal values are to be merged. */ static void -test_merge_with_dups (void) +test_merge_with_dups (void) { const int max_elems = 8; int cnt, merge_pat, inc_pat, order; - + for (cnt = 0; cnt <= max_elems; cnt++) for (merge_pat = 0; merge_pat <= (1 << cnt); merge_pat++) for (inc_pat = 0; inc_pat <= (1 << cnt); inc_pat++) @@ -1495,9 +1493,9 @@ test_merge_with_dups (void) allocate_elements (cnt, &list, &elems, &elemp, &values); j = 0; - for (i = k = 0; i < cnt; i++) + for (i = k = 0; i < cnt; i++) { - if (merge_pat & (1u << i)) + if (merge_pat & (1u << i)) elems[j++]->x = k; if (inc_pat & (1u << i)) k++; @@ -1505,19 +1503,19 @@ test_merge_with_dups (void) mid = j; for (i = k = 0; i < cnt; i++) { - if (!(merge_pat & (1u << i))) + if (!(merge_pat & (1u << i))) elems[j++]->x = k; if (inc_pat & (1u << i)) k++; } check (cnt == j); - if (order == 0) + if (order == 0) { for (i = 0; i < cnt; i++) - elems[i]->y = i; + elems[i]->y = i; } - else + else { for (i = 0; i < mid; i++) elems[i]->y = 100 + i; @@ -1526,11 +1524,11 @@ test_merge_with_dups (void) } j = 0; - for (i = k = 0; i < cnt; i++) + for (i = k = 0; i < cnt; i++) { values[j++] = k; if (inc_pat & (1u << i)) - k++; + k++; } check (cnt == j); @@ -1552,12 +1550,12 @@ test_merge_with_dups (void) /* Tests ll_sort on all permutations up to a maximum number of elements. */ static void -test_sort_exhaustive (void) +test_sort_exhaustive (void) { const int max_elems = 8; int cnt; - for (cnt = 0; cnt <= max_elems; cnt++) + for (cnt = 0; cnt <= max_elems; cnt++) { struct ll_list list; struct element **elems; @@ -1573,7 +1571,7 @@ test_sort_exhaustive (void) perm_cnt = 1; while (ll_next_permutation (ll_head (&list), ll_null (&list), - compare_elements, &aux_data)) + compare_elements, &aux_data)) { struct ll_list perm_list; int j; @@ -1581,7 +1579,7 @@ test_sort_exhaustive (void) extract_values (&list, perm_values, cnt); ll_init (&perm_list); for (j = 0; j < cnt; j++) - { + { perm_elems[j]->x = perm_values[j]; ll_push_tail (&perm_list, &perm_elems[j]->ll); } @@ -1590,7 +1588,7 @@ test_sort_exhaustive (void) check_list_contents (&perm_list, values, cnt); check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list), compare_elements, &aux_data)); - perm_cnt++; + perm_cnt++; } check (perm_cnt == factorial (cnt)); @@ -1602,7 +1600,7 @@ test_sort_exhaustive (void) /* Tests that ll_sort is stable in the presence of equal values. */ static void -test_sort_stable (void) +test_sort_stable (void) { const int max_elems = 6; int cnt, inc_pat; @@ -1624,7 +1622,7 @@ test_sort_stable (void) allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values); j = 0; - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) { elems[i]->x = values[i] = j; if (inc_pat & (1 << i)) @@ -1634,14 +1632,14 @@ test_sort_stable (void) perm_cnt = 1; while (ll_next_permutation (ll_head (&list), ll_null (&list), - compare_elements_y, &aux_data)) + compare_elements_y, &aux_data)) { struct ll_list perm_list; extract_values (&list, perm_values, cnt); ll_init (&perm_list); for (i = 0; i < cnt; i++) - { + { perm_elems[i]->x = perm_values[i]; perm_elems[i]->y = i; ll_push_tail (&perm_list, &perm_elems[i]->ll); @@ -1651,7 +1649,7 @@ test_sort_stable (void) check_list_contents (&perm_list, values, cnt); check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list), compare_elements_x_y, &aux_data)); - perm_cnt++; + perm_cnt++; } check (perm_cnt == factorial (cnt)); @@ -1671,7 +1669,7 @@ test_sort_subset (void) for (cnt = 0; cnt <= max_elems; cnt++) for (repeat = 0; repeat < 100; repeat++) - for (r0 = 0; r0 <= cnt; r0++) + for (r0 = 0; r0 <= cnt; r0++) for (r1 = r0; r1 <= cnt; r1++) { struct ll_list list; @@ -1715,7 +1713,7 @@ test_sort_big (void) /* Tests ll_unique. */ static void -test_unique (void) +test_unique (void) { const int max_elems = 10; @@ -1736,7 +1734,7 @@ test_unique (void) allocate_elements (cnt, &list, &elems, NULL, &values); j = unique_values = 0; - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) { unique_values = j + 1; elems[i]->x = values[i] = j; @@ -1763,7 +1761,7 @@ test_unique (void) /* Tests ll_sort_unique. */ static void -test_sort_unique (void) +test_sort_unique (void) { const int max_elems = 7; int cnt, inc_pat; @@ -1788,7 +1786,7 @@ test_sort_unique (void) allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values); j = unique_cnt = 0; - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) { elems[i]->x = values[i] = j; unique_cnt = j + 1; @@ -1802,14 +1800,14 @@ test_sort_unique (void) perm_cnt = 1; while (ll_next_permutation (ll_head (&list), ll_null (&list), - compare_elements, &aux_data)) + compare_elements, &aux_data)) { struct ll_list perm_list; extract_values (&list, perm_values, cnt); ll_init (&perm_list); for (i = 0; i < cnt; i++) - { + { perm_elems[i]->x = perm_values[i]; perm_elems[i]->y = i; ll_push_tail (&perm_list, &perm_elems[i]->ll); @@ -1819,7 +1817,7 @@ test_sort_unique (void) check_list_contents (&perm_list, unique_values, unique_cnt); check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list), compare_elements_x_y, &aux_data)); - perm_cnt++; + perm_cnt++; } check (perm_cnt == expected_perms (values, cnt)); @@ -1831,7 +1829,7 @@ test_sort_unique (void) /* Tests ll_insert_ordered. */ static void -test_insert_ordered (void) +test_insert_ordered (void) { const int max_elems = 6; int cnt, inc_pat; @@ -1853,7 +1851,7 @@ test_insert_ordered (void) allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values); j = 0; - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) { elems[i]->x = values[i] = j; if (inc_pat & (1 << i)) @@ -1863,14 +1861,14 @@ test_insert_ordered (void) perm_cnt = 1; while (ll_next_permutation (ll_head (&list), ll_null (&list), - compare_elements_y, &aux_data)) + compare_elements_y, &aux_data)) { struct ll_list perm_list; extract_values (&list, perm_values, cnt); ll_init (&perm_list); for (i = 0; i < cnt; i++) - { + { perm_elems[i]->x = perm_values[i]; perm_elems[i]->y = i; ll_insert_ordered (ll_head (&perm_list), ll_null (&perm_list), @@ -1879,7 +1877,7 @@ test_insert_ordered (void) } check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list), compare_elements_x_y, &aux_data)); - perm_cnt++; + perm_cnt++; } check (perm_cnt == factorial (cnt)); @@ -1893,9 +1891,9 @@ static void test_partition (void) { const int max_elems = 10; - + int cnt; - unsigned pbase; + unsigned int pbase; int r0, r1; for (cnt = 0; cnt < max_elems; cnt++) @@ -1908,11 +1906,11 @@ test_partition (void) struct ll **elemp; int *values; - unsigned pattern = pbase << r0; + unsigned int pattern = pbase << r0; int i, j; int first_false; struct ll *part_ll; - + allocate_ascending (cnt, &list, &elems, &elemp, &values); /* Check that ll_find_partition works okay in every @@ -1923,12 +1921,12 @@ test_partition (void) break; j = i; for (; i < r1; i++) - if (pattern & (1u << i)) + if (pattern & (1u << i)) break; part_ll = ll_find_partition (elemp[r0], elemp[r1], pattern_pred, &pattern); - if (i == r1) + if (i == r1) check (part_ll == elemp[j]); else check (part_ll == NULL); @@ -1946,7 +1944,7 @@ test_partition (void) { if (first_false == -1) first_false = i; - values[j++] = i; + values[j++] = i; } if (first_false == -1) first_false = r1; @@ -1970,56 +1968,199 @@ test_partition (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[] = + { + { + "push-pop", + "push/pop", + test_push_pop + }, + { + "insert-remove", + "insert/remove", + test_insert_remove + }, + { + "swap", + "swap", + test_swap + }, + { + "swap-range", + "swap_range", + test_swap_range + }, + { + "remove-range", + "remove_range", + test_remove_range + }, + { + "remove-equal", + "remove_equal", + test_remove_equal + }, + { + "remove-if", + "remove_if", + test_remove_if + }, + { + "moved", + "moved", + test_moved + }, + { + "find-equal", + "find_equal", + test_find_equal + }, + { + "find-if", + "find_if", + test_find_if + }, + { + "find-adjacent-equal", + "find_adjacent_equal", + test_find_adjacent_equal + }, + { + "count-range", + "count_range", + test_count_range + }, + { + "count-equal", + "count_equal", + test_count_equal + }, + { + "count-if", + "count_if", + test_count_if + }, + { + "min-max", + "min/max", + test_min_max + }, + { + "lexicographical-compare-3way", + "lexicographical_compare_3way", + test_lexicographical_compare_3way + }, + { + "apply", + "apply", + test_apply + }, + { + "reverse", + "reverse", + test_reverse + }, + { + "permutations-no-dups", + "permutations (no dups)", + test_permutations_no_dups + }, + { + "permutations-with-dups", + "permutations (with dups)", + test_permutations_with_dups + }, + { + "merge-no-dups", + "merge (no dups)", + test_merge_no_dups + }, + { + "merge-with-dups", + "merge (with dups)", + test_merge_with_dups + }, + { + "sort-exhaustive", + "sort (exhaustive)", + test_sort_exhaustive + }, + { + "sort-stable", + "sort (stability)", + test_sort_stable + }, + { + "sort-subset", + "sort (subset)", + test_sort_subset + }, + { + "sort-big", + "sort (big)", + test_sort_big + }, + { + "unique", + "unique", + test_unique + }, + { + "sort-unique", + "sort_unique", + test_sort_unique + }, + { + "insert-ordered", + "insert_ordered", + test_insert_ordered + }, + { + "partition", + "partition", + test_partition + }, + }; + +enum { N_TESTS = sizeof tests / sizeof *tests }; int -main (void) -{ - run_test (test_push_pop, "push/pop"); - run_test (test_insert_remove, "insert/remove"); - run_test (test_swap, "swap"); - run_test (test_swap_range, "swap_range"); - run_test (test_remove_range, "remove_range"); - run_test (test_remove_equal, "remove_equal"); - run_test (test_remove_if, "remove_if"); - run_test (test_moved, "moved"); - run_test (test_find_equal, "find_equal"); - run_test (test_find_if, "find_if"); - run_test (test_find_adjacent_equal, "find_adjacent_equal"); - run_test (test_count_range, "count_range"); - run_test (test_count_equal, "count_equal"); - run_test (test_count_if, "count_if"); - run_test (test_min_max, "min/max"); - run_test (test_lexicographical_compare_3way, "lexicographical_compare_3way"); - run_test (test_apply, "apply"); - run_test (test_reverse, "reverse"); - run_test (test_permutations_no_dups, "permutations (no dups)"); - run_test (test_permutations_with_dups, "permutations (with dups)"); - run_test (test_merge_no_dups, "merge (no dups)"); - run_test (test_merge_with_dups, "merge (with dups)"); - run_test (test_sort_exhaustive, "sort (exhaustive)"); - run_test (test_sort_stable, "sort (stability)"); - run_test (test_sort_subset, "sort (subset)"); - run_test (test_sort_big, "sort (big)"); - run_test (test_unique, "unique"); - run_test (test_sort_unique, "sort_unique"); - run_test (test_insert_ordered, "insert_ordered"); - run_test (test_partition, "partition"); - putchar ('\n'); - - return 0; -} - -/* - Local Variables: - compile-command: "gcc -Wall -Wstrict-prototypes -Wmissing-prototypes ll.c ll-test.c -o ll-test -g" - End: - */ +main (int argc, char *argv[]) +{ + 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 doubly linked list (ll) 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; + } +}