X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=tests%2Flibpspp%2Fllx-test.c;h=2befd51a4451c899f18fac5a23146444ba9d35a2;hb=ee46f6404b033f4d1312c6b52a207ec2da99d94b;hp=12dc0f52214d8a9a287a76210ff726552f333c5c;hpb=9683d7528884fcb3c60705812de9f96889536388;p=pspp-builds.git
diff --git a/tests/libpspp/llx-test.c b/tests/libpspp/llx-test.c
index 12dc0f52..2befd51a 100644
--- a/tests/libpspp/llx-test.c
+++ b/tests/libpspp/llx-test.c
@@ -1,32 +1,34 @@
-/* PSPP - computes sample statistics.
+/* PSPP - a program for statistical analysis.
Copyright (C) 2006 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 llx_* routines defined in
ll.c. This test program aims to be as comprehensive as
possible. "gcov -b" should report 100% coverage of lines and
branches in llx.c and llx.h. "valgrind --leak-check=yes
--show-reachable=yes" should give a clean report.
-
+
This test program depends only on ll.c, llx.c, and the
standard C library.
See ll-test.c for a similar program for the ll_* routines. */
+#ifdef HAVE_CONFIG_H
+#include
+#endif
+
#include
#include
#include
@@ -46,17 +48,17 @@ 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);
@@ -80,9 +82,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)
@@ -96,7 +98,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 ();
@@ -112,13 +114,13 @@ null_allocate_node (void *aux UNUSED)
/* Does nothing. */
static void
-null_release_node (struct llx *llx UNUSED, void *aux UNUSED)
+null_release_node (struct llx *llx UNUSED, void *aux UNUSED)
{
}
/* Memory manager that fails all allocations and does nothing on
free. */
-static const struct llx_manager llx_null_mgr =
+static const struct llx_manager llx_null_mgr =
{
null_allocate_node,
null_release_node,
@@ -134,7 +136,7 @@ struct element
int y; /* Secondary value. */
};
-int aux_data;
+static int aux_data;
/* Prints the elements in LIST. */
static void UNUSED
@@ -143,7 +145,7 @@ print_list (struct llx_list *list)
struct llx *x;
printf ("list:");
- for (x = llx_head (list); x != llx_null (list); x = llx_next (x))
+ for (x = llx_head (list); x != llx_null (list); x = llx_next (x))
{
const struct element *e = llx_data (x);
printf (" %d", e->x);
@@ -155,19 +157,19 @@ print_list (struct llx_list *list)
AUX for each element in LIST. */
static void UNUSED
print_pred (struct llx_list *list,
- llx_predicate_func *predicate, void *aux UNUSED)
+ llx_predicate_func *predicate, void *aux UNUSED)
{
struct llx *x;
printf ("pred:");
- for (x = llx_head (list); x != llx_null (list); x = llx_next (x))
+ for (x = llx_head (list); x != llx_null (list); x = llx_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;
@@ -180,7 +182,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 void *a_, const void *b_, void *aux)
+compare_elements (const void *a_, const void *b_, void *aux)
{
const struct element *a = a_;
const struct element *b = b_;
@@ -193,7 +195,7 @@ compare_elements (const void *a_, const void *b_, void *aux)
strcmp-type return value. Verifies that AUX points to
aux_data. */
static int
-compare_elements_x_y (const void *a_, const void *b_, void *aux)
+compare_elements_x_y (const void *a_, const void *b_, void *aux)
{
const struct element *a = a_;
const struct element *b = b_;
@@ -222,7 +224,7 @@ compare_elements_y (const void *a_, const void *b_, void *aux)
/* Returns true if the bit in *PATTERN indicated by `x in
*ELEMENT is set, false otherwise. */
static bool
-pattern_pred (const void *element_, void *pattern_)
+pattern_pred (const void *element_, void *pattern_)
{
const struct element *element = element_;
unsigned int *pattern = pattern_;
@@ -242,7 +244,7 @@ allocate_elements (size_t n,
struct llx_list *list,
struct element ***elems,
struct llx ***elemp,
- int **values)
+ int **values)
{
size_t i;
@@ -250,35 +252,35 @@ allocate_elements (size_t n,
llx_init (list);
*elems = xnmalloc (n, sizeof **elems);
- if (elemp != NULL)
+ if (elemp != NULL)
{
*elemp = xnmalloc (n + 1, sizeof *elemp);
(*elemp)[n] = llx_null (list);
}
-
- for (i = 0; i < n; i++)
+
+ for (i = 0; i < n; i++)
{
(*elems)[i] = xmalloc (sizeof ***elems);
- if (list != NULL)
+ if (list != NULL)
{
struct llx *llx = llx_push_tail (list, (*elems)[i], &llx_malloc_mgr);
if (elemp != NULL)
- (*elemp)[i] = llx;
+ (*elemp)[i] = llx;
}
}
-
+
if (values != NULL)
*values = xnmalloc (n, sizeof *values);
}
/* Copies the CNT values of `x' from LIST into VALUES[]. */
static void
-extract_values (struct llx_list *list, int values[], size_t cnt)
+extract_values (struct llx_list *list, int values[], size_t cnt)
{
struct llx *x;
-
+
check (llx_count (list) == cnt);
- for (x = llx_head (list); x != llx_null (list); x = llx_next (x))
+ for (x = llx_head (list); x != llx_null (list); x = llx_next (x))
{
struct element *e = llx_data (x);
*values++ = e->x;
@@ -293,16 +295,16 @@ allocate_ascending (size_t n,
struct llx_list *list,
struct element ***elems,
struct llx ***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
@@ -314,16 +316,16 @@ allocate_pattern (size_t n,
struct llx_list *list,
struct element ***elems,
struct llx ***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
@@ -335,10 +337,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);
@@ -355,17 +357,17 @@ allocate_random (size_t n,
struct llx_list *list,
struct element ***elems,
struct llx ***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 LIST, the N elements of ELEMS, ELEMP, and VALUES. */
@@ -374,7 +376,7 @@ free_elements (size_t n,
struct llx_list *list,
struct element **elems,
struct llx **elemp,
- int *values)
+ int *values)
{
size_t i;
@@ -382,14 +384,14 @@ free_elements (size_t n,
llx_destroy (list, NULL, NULL, &llx_malloc_mgr);
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_;
@@ -399,7 +401,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_;
@@ -409,7 +411,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 llx_list *list, int elements[], size_t cnt)
+check_list_contents (struct llx_list *list, int elements[], size_t cnt)
{
struct llx *llx;
size_t i;
@@ -417,7 +419,7 @@ check_list_contents (struct llx_list *list, int elements[], size_t cnt)
check ((cnt == 0) == llx_is_empty (list));
/* Iterate in forward order. */
- for (llx = llx_head (list), i = 0; i < cnt; llx = llx_next (llx), i++)
+ for (llx = llx_head (list), i = 0; i < cnt; llx = llx_next (llx), i++)
{
struct element *e = llx_data (llx);
check (elements[i] == e->x);
@@ -448,7 +450,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;
@@ -487,7 +489,7 @@ test_push_pop (void)
/* Push on tail. */
llx_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;
llx_push_tail (&list, elems[i], &llx_malloc_mgr);
@@ -495,7 +497,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 = llx_pop_tail (&list, &llx_malloc_mgr);
check (e->x == max_elems - i - 1);
@@ -512,7 +514,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 = llx_pop_head (&list, &llx_malloc_mgr);
check (e->x == (int) i);
@@ -524,12 +526,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 llx **elemp;
@@ -542,7 +544,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;
@@ -567,12 +569,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 llx_list list;
struct element **elems;
@@ -584,9 +586,9 @@ test_swap (void)
allocate_ascending (cnt, &list, &elems, &elemp, &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;
@@ -595,7 +597,7 @@ test_swap (void)
values[i] = values[j];
values[j] = t;
check_list_contents (&list, values, cnt);
- }
+ }
free_elements (cnt, &list, elems, elemp, values);
}
@@ -603,15 +605,15 @@ test_swap (void)
/* 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++)
{
@@ -650,14 +652,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 llx_list list;
@@ -685,7 +687,7 @@ test_remove_range (void)
/* Tests llx_remove_equal. */
static void
-test_remove_equal (void)
+test_remove_equal (void)
{
const int max_elems = 8;
@@ -694,7 +696,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 llx_list list;
struct element **elems;
@@ -708,13 +710,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;
@@ -730,7 +732,7 @@ test_remove_equal (void)
/* Tests llx_remove_if. */
static void
-test_remove_if (void)
+test_remove_if (void)
{
const int max_elems = 8;
@@ -739,7 +741,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 llx_list list;
struct element **elems;
@@ -752,14 +754,14 @@ test_remove_if (void)
allocate_ascending (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;
if (!delete)
- values[remaining++] = i;
+ values[remaining++] = i;
}
- check ((int) llx_remove_if (elemp[r0], elemp[r1],
+ check ((int) llx_remove_if (elemp[r0], elemp[r1],
pattern_pred, &pattern,
&llx_malloc_mgr)
== cnt - remaining);
@@ -781,7 +783,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 llx_list list;
struct element **elems;
@@ -820,7 +822,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 llx_list list;
struct element **elems;
@@ -853,12 +855,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 llx_find_equal. */
static void
-test_find_equal (void)
+test_find_equal (void)
{
test_examine_equal_range (test_find_equal_helper);
}
@@ -875,26 +877,26 @@ test_find_if_helper (int r0, int r1, int eq_pat, struct llx **elemp)
if (eq_pat & (1 << i))
break;
- check (match == elemp[i]);
+ check (match == elemp[i]);
}
/* Tests llx_find_if. */
static void
-test_find_if (void)
+test_find_if (void)
{
test_examine_if_range (test_find_if_helper);
}
/* Tests llx_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 llx_list list;
struct element **elems;
@@ -907,10 +909,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;
@@ -918,7 +920,7 @@ test_find_adjacent_equal (void)
else
match--;
}
-
+
for (i = 0; i <= cnt; i++)
{
struct llx *llx1 = llx_find_adjacent_equal (elemp[i], llx_null (&list),
@@ -929,7 +931,7 @@ test_find_adjacent_equal (void)
llx2 = llx_null (&list);
for (j = i; j < cnt - 1; j++)
- if (eq_pat & (1 << j))
+ if (eq_pat & (1 << j))
{
llx2 = elemp[j];
break;
@@ -951,7 +953,7 @@ test_count_range_helper (int r0, int r1, int eq_pat UNUSED, struct llx **elemp)
/* Tests llx_count_range. */
static void
-test_count_range (void)
+test_count_range (void)
{
test_examine_if_range (test_count_range_helper);
}
@@ -970,20 +972,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 llx_count_equal. */
static void
-test_count_equal (void)
+test_count_equal (void)
{
test_examine_equal_range (test_count_equal_helper);
}
/* Helper function for testing llx_count_if. */
static void
-test_count_if_helper (int r0, int r1, int eq_pat, struct llx **elemp)
+test_count_if_helper (int r0, int r1, int eq_pat, struct llx **elemp)
{
int count1;
int count2;
@@ -996,19 +998,19 @@ test_count_if_helper (int r0, int r1, int eq_pat, struct llx **elemp)
if (eq_pat & (1 << i))
count2++;
- check (count1 == count2);
+ check (count1 == count2);
}
/* Tests llx_count_if. */
static void
-test_count_if (void)
+test_count_if (void)
{
test_examine_if_range (test_count_if_helper);
}
/* Returns N!. */
static unsigned int
-factorial (unsigned int n)
+factorial (unsigned int n)
{
unsigned int value = 1;
while (n > 1)
@@ -1020,13 +1022,13 @@ factorial (unsigned int n)
VALUES. If VALUES contains duplicates, they must be
adjacent. */
static unsigned int
-expected_perms (int *values, size_t cnt)
+expected_perms (int *values, size_t cnt)
{
size_t i, j;
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])
@@ -1038,12 +1040,12 @@ expected_perms (int *values, size_t cnt)
/* Tests llx_min and llx_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 llx_list list;
struct element **elems;
@@ -1057,32 +1059,32 @@ test_min_max (void)
perm_cnt = 1;
while (llx_next_permutation (llx_head (&list), llx_null (&list),
- compare_elements, &aux_data))
+ compare_elements, &aux_data))
{
int r0, r1;
struct llx *x;
int i;
-
+
for (i = 0, x = llx_head (&list); x != llx_null (&list);
- x = llx_next (x), i++)
+ x = llx_next (x), i++)
{
struct element *e = llx_data (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 llx *min = llx_min (elemp[r0], elemp[r1],
compare_elements, &aux_data);
struct llx *max = llx_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
{
struct element *min_elem = llx_data (min);
struct element *max_elem = llx_data (max);
@@ -1099,7 +1101,7 @@ test_min_max (void)
max_int = value;
}
check (min != elemp[r1] && min_elem->x == min_int);
- check (max != elemp[r1] && max_elem->x == max_int);
+ check (max != elemp[r1] && max_elem->x == max_int);
}
}
perm_cnt++;
@@ -1114,7 +1116,7 @@ test_min_max (void)
/* Tests llx_lexicographical_compare_3way. */
static void
-test_lexicographical_compare_3way (void)
+test_lexicographical_compare_3way (void)
{
const int max_elems = 4;
@@ -1123,7 +1125,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 llx_list list_a, list_b;
struct element **elems_a, **elems_b;
@@ -1154,7 +1156,7 @@ test_lexicographical_compare_3way (void)
compare_elements, &aux_data);
check (a_ordering == b_ordering);
- }
+ }
free_elements (cnt_a, &list_a, elems_a, elemp_a, values_a);
free_elements (cnt_b, &list_b, elems_b, elemp_b, values_b);
@@ -1164,24 +1166,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 (void *e_, void *next_output_)
+apply_func (void *e_, void *next_output_)
{
struct element *e = e_;
int **next_output = next_output_;
-
+
*(*next_output)++ = e->x;
}
/* Tests llx_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 llx_list list;
@@ -1200,7 +1202,7 @@ test_apply (void)
llx_apply (elemp[r0], elemp[r1], apply_func, &next_output);
check_list_contents (&list, values, cnt);
llx_destroy (&list, NULL, NULL, &llx_malloc_mgr);
-
+
check (r1 - r0 == next_output - output);
for (j = 0; j < r1 - r0; j++)
check (output[j] == r0 + j);
@@ -1212,7 +1214,7 @@ test_apply (void)
/* Tests llx_destroy. */
static void
-test_destroy (void)
+test_destroy (void)
{
const int max_elems = 8;
@@ -1234,7 +1236,7 @@ test_destroy (void)
output = next_output = xnmalloc (cnt, sizeof *output);
llx_destroy (&list, apply_func, &next_output, &llx_malloc_mgr);
-
+
check (cnt == next_output - output);
for (j = 0; j < cnt; j++)
check (output[j] == j);
@@ -1246,14 +1248,14 @@ test_destroy (void)
/* Tests llx_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 llx_list list;
@@ -1284,12 +1286,12 @@ test_reverse (void)
/* Tests llx_next_permutation and llx_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 llx_list list;
struct element **elems;
@@ -1304,7 +1306,7 @@ test_permutations_no_dups (void)
perm_cnt = 1;
extract_values (&list, old_values, cnt);
while (llx_next_permutation (llx_head (&list), llx_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 +1323,7 @@ test_permutations_no_dups (void)
llx_reverse (llx_head (&list), llx_null (&list));
extract_values (&list, old_values, cnt);
while (llx_prev_permutation (llx_head (&list), llx_null (&list),
- compare_elements, &aux_data))
+ compare_elements, &aux_data))
{
extract_values (&list, new_values, cnt);
check (lexicographical_compare_3way (new_values, cnt,
@@ -1344,7 +1346,7 @@ test_permutations_no_dups (void)
/* Tests llx_next_permutation and llx_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;
@@ -1353,7 +1355,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 llx_list list;
struct element **elems;
@@ -1365,7 +1367,7 @@ test_permutations_with_dups (void)
unsigned int permutation_cnt;
int left = cnt;
int value = 0;
-
+
allocate_elements (cnt, &list, &elems, &elemp, &values);
value = 0;
@@ -1384,7 +1386,7 @@ test_permutations_with_dups (void)
permutation_cnt = 1;
extract_values (&list, old_values, cnt);
while (llx_next_permutation (llx_head (&list), llx_null (&list),
- compare_elements, &aux_data))
+ compare_elements, &aux_data))
{
extract_values (&list, new_values, cnt);
check (lexicographical_compare_3way (new_values, cnt,
@@ -1401,7 +1403,7 @@ test_permutations_with_dups (void)
llx_reverse (llx_head (&list), llx_null (&list));
extract_values (&list, old_values, cnt);
while (llx_prev_permutation (llx_head (&list), llx_null (&list),
- compare_elements, &aux_data))
+ compare_elements, &aux_data))
{
extract_values (&list, new_values, cnt);
check (lexicographical_compare_3way (new_values, cnt,
@@ -1422,13 +1424,13 @@ test_permutations_with_dups (void)
/* Tests llx_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_fillxer = 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_fillxer; pfx++)
@@ -1497,12 +1499,12 @@ test_merge_no_dups (void)
/* Tests llx_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++)
@@ -1519,9 +1521,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++;
@@ -1529,19 +1531,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;
@@ -1550,11 +1552,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);
@@ -1576,12 +1578,12 @@ test_merge_with_dups (void)
/* Tests llx_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 llx_list list;
struct element **elems;
@@ -1597,7 +1599,7 @@ test_sort_exhaustive (void)
perm_cnt = 1;
while (llx_next_permutation (llx_head (&list), llx_null (&list),
- compare_elements, &aux_data))
+ compare_elements, &aux_data))
{
struct llx_list perm_list;
int j;
@@ -1605,7 +1607,7 @@ test_sort_exhaustive (void)
extract_values (&list, perm_values, cnt);
llx_init (&perm_list);
for (j = 0; j < cnt; j++)
- {
+ {
perm_elems[j]->x = perm_values[j];
llx_push_tail (&perm_list, perm_elems[j], &llx_malloc_mgr);
}
@@ -1615,7 +1617,7 @@ test_sort_exhaustive (void)
check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
compare_elements, &aux_data));
llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
- perm_cnt++;
+ perm_cnt++;
}
check (perm_cnt == factorial (cnt));
@@ -1627,7 +1629,7 @@ test_sort_exhaustive (void)
/* Tests that llx_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;
@@ -1649,7 +1651,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))
@@ -1659,14 +1661,14 @@ test_sort_stable (void)
perm_cnt = 1;
while (llx_next_permutation (llx_head (&list), llx_null (&list),
- compare_elements_y, &aux_data))
+ compare_elements_y, &aux_data))
{
struct llx_list perm_list;
extract_values (&list, perm_values, cnt);
llx_init (&perm_list);
for (i = 0; i < cnt; i++)
- {
+ {
perm_elems[i]->x = perm_values[i];
perm_elems[i]->y = i;
llx_push_tail (&perm_list, perm_elems[i], &llx_malloc_mgr);
@@ -1677,7 +1679,7 @@ test_sort_stable (void)
check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
compare_elements_x_y, &aux_data));
llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
- perm_cnt++;
+ perm_cnt++;
}
check (perm_cnt == factorial (cnt));
@@ -1697,7 +1699,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 llx_list list;
@@ -1741,7 +1743,7 @@ test_sort_big (void)
/* Tests llx_unique. */
static void
-test_unique (void)
+test_unique (void)
{
const int max_elems = 10;
@@ -1762,7 +1764,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;
@@ -1792,7 +1794,7 @@ test_unique (void)
/* Tests llx_sort_unique. */
static void
-test_sort_unique (void)
+test_sort_unique (void)
{
const int max_elems = 7;
int cnt, inc_pat;
@@ -1817,7 +1819,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;
@@ -1831,14 +1833,14 @@ test_sort_unique (void)
perm_cnt = 1;
while (llx_next_permutation (llx_head (&list), llx_null (&list),
- compare_elements, &aux_data))
+ compare_elements, &aux_data))
{
struct llx_list perm_list;
extract_values (&list, perm_values, cnt);
llx_init (&perm_list);
for (i = 0; i < cnt; i++)
- {
+ {
perm_elems[i]->x = perm_values[i];
perm_elems[i]->y = i;
llx_push_tail (&perm_list, perm_elems[i], &llx_malloc_mgr);
@@ -1853,7 +1855,7 @@ test_sort_unique (void)
perm_cnt++;
}
check (perm_cnt == expected_perms (values, cnt));
-
+
free_elements (cnt, &list, elems, NULL, values);
free_elements (cnt, NULL, perm_elems, NULL, perm_values);
free (unique_values);
@@ -1862,7 +1864,7 @@ test_sort_unique (void)
/* Tests llx_insert_ordered. */
static void
-test_insert_ordered (void)
+test_insert_ordered (void)
{
const int max_elems = 6;
int cnt, inc_pat;
@@ -1884,7 +1886,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))
@@ -1894,14 +1896,14 @@ test_insert_ordered (void)
perm_cnt = 1;
while (llx_next_permutation (llx_head (&list), llx_null (&list),
- compare_elements_y, &aux_data))
+ compare_elements_y, &aux_data))
{
struct llx_list perm_list;
extract_values (&list, perm_values, cnt);
llx_init (&perm_list);
for (i = 0; i < cnt; i++)
- {
+ {
perm_elems[i]->x = perm_values[i];
perm_elems[i]->y = i;
llx_insert_ordered (llx_head (&perm_list),
@@ -1913,7 +1915,7 @@ test_insert_ordered (void)
check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
compare_elements_x_y, &aux_data));
llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
- perm_cnt++;
+ perm_cnt++;
}
check (perm_cnt == factorial (cnt));
@@ -1927,7 +1929,7 @@ static void
test_partition (void)
{
const int max_elems = 10;
-
+
int cnt;
unsigned int pbase;
int r0, r1;
@@ -1946,7 +1948,7 @@ test_partition (void)
int i, j;
int first_false;
struct llx *part_llx;
-
+
allocate_ascending (cnt, &list, &elems, &elemp, &values);
/* Check that llx_find_partition works okay in every
@@ -1957,12 +1959,12 @@ test_partition (void)
break;
j = i;
for (; i < r1; i++)
- if (pattern & (1u << i))
+ if (pattern & (1u << i))
break;
part_llx = llx_find_partition (elemp[r0], elemp[r1],
pattern_pred,
&pattern);
- if (i == r1)
+ if (i == r1)
check (part_llx == elemp[j]);
else
check (part_llx == NULL);
@@ -1980,7 +1982,7 @@ test_partition (void)
{
if (first_false == -1)
first_false = i;
- values[j++] = i;
+ values[j++] = i;
}
if (first_false == -1)
first_false = r1;
@@ -2004,14 +2006,14 @@ test_partition (void)
/* Tests that allocation failure is gracefully handled. */
static void
-test_allocation_failure (void)
+test_allocation_failure (void)
{
struct llx_list list;
llx_init (&list);
- check (llx_push_head (&list, NULL, &llx_null_mgr) == NULL);
- check (llx_push_tail (&list, NULL, &llx_null_mgr) == NULL);
- check (llx_insert (llx_null (&list), NULL, &llx_null_mgr) == NULL);
+ check (llx_push_head (&list, NULL, &llx_null_mgr) == NULL);
+ check (llx_push_tail (&list, NULL, &llx_null_mgr) == NULL);
+ check (llx_insert (llx_null (&list), NULL, &llx_null_mgr) == NULL);
check_list_contents (&list, NULL, 0);
}
@@ -2019,7 +2021,7 @@ test_allocation_failure (void)
/* Runs TEST_FUNCTION and prints a message about NAME. */
static void
-run_test (void (*test_function) (void), const char *name)
+run_test (void (*test_function) (void), const char *name)
{
test_name = name;
putchar ('.');
@@ -2028,7 +2030,7 @@ run_test (void (*test_function) (void), const char *name)
}
int
-main (void)
+main (void)
{
run_test (test_push_pop, "push/pop");
run_test (test_insert_remove, "insert/remove");