*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 elements in VALUES into the lexicographically
+/* Arranges the N elements in VALUES into the lexicographically
next greater permutation. Returns true if successful.
If VALUES is already the lexicographically greatest
permutation of its elements (i.e. ordered from greatest to
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;
return value;
}
-/* Randomly shuffles the CNT elements in ARRAY, each of which is
+/* Randomly shuffles the N elements in ARRAY, each of which is
SIZE bytes in size. */
static void
-random_shuffle (void *array_, size_t cnt, size_t size)
+random_shuffle (void *array_, size_t n, size_t size)
{
char *array = array_;
char *tmp = xmalloc (size);
size_t i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- size_t j = rand () % (cnt - i) + i;
+ size_t j = rand () % (n - i) + i;
if (i != j)
{
memcpy (tmp, array + j * size, size);
}
}
-/* Checks that ABT contains the CNT ints in DATA, that its
+/* Checks that ABT contains the N ints in DATA, that its
structure is correct, and that certain operations on ABT
produce the expected results. */
static void
-check_abt (struct abt *abt, const int data[], size_t cnt)
+check_abt (struct abt *abt, const int data[], size_t n)
{
struct element e;
size_t i;
int *order;
- order = xmemdup (data, cnt * sizeof *data);
- qsort (order, cnt, sizeof *order, compare_ints_noaux);
+ order = xmemdup (data, n * sizeof *data);
+ qsort (order, n, sizeof *order, compare_ints_noaux);
if (abt->compare != NULL)
{
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
struct abt_node *p;
check_levels (abt->root);
check_augmentations (abt->root);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
check (find_by_position (abt, i)->data == order[i]);
- if (cnt == 0)
+ if (n == 0)
{
check (abt_first (abt) == NULL);
check (abt_last (abt) == NULL);
{
struct abt_node *p;
- for (p = abt_first (abt), i = 0; i < cnt; p = abt_next (abt, p), i++)
+ for (p = abt_first (abt), i = 0; i < n; p = abt_next (abt, p), i++)
check (abt_node_to_element (p)->data == order[i]);
check (p == NULL);
- for (p = abt_last (abt), i = 0; i < cnt; p = abt_prev (abt, p), i++)
- check (abt_node_to_element (p)->data == order[cnt - i - 1]);
+ for (p = abt_last (abt), i = 0; i < n; p = abt_prev (abt, p), i++)
+ check (abt_node_to_element (p)->data == order[n - i - 1]);
check (p == NULL);
}
- check (abt_is_empty (abt) == (cnt == 0));
+ check (abt_is_empty (abt) == (n == 0));
free (order);
}
}
-/* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
+/* Inserts the N values from 0 to N - 1 (inclusive) into an
ABT in the order specified by INSERTIONS using the given
METHOD, then deletes them in the order specified by DELETIONS,
checking the ABT's contents for correctness after each
do_test_insert_delete (enum insertion_method method,
const int insertions[],
const int deletions[],
- size_t cnt)
+ size_t n)
{
struct element *elements;
struct abt abt;
size_t i;
- elements = xnmalloc (cnt, sizeof *elements);
- for (i = 0; i < cnt; i++)
+ elements = xnmalloc (n, sizeof *elements);
+ for (i = 0; i < n; i++)
elements[i].data = i;
abt_init (&abt, method == INSERT ? compare_elements : NULL,
reaugment_elements, &aux_data);
check_abt (&abt, NULL, 0);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
insert_node (&abt, &elements[insertions[i]], method);
check_abt (&abt, insertions, i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
abt_delete (&abt, &elements[deletions[i]].node);
- check_abt (&abt, deletions + i + 1, cnt - i - 1);
+ check_abt (&abt, deletions + i + 1, n - i - 1);
}
free (elements);
}
-/* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
+/* Inserts the N values from 0 to N - 1 (inclusive) into an
ABT in the order specified by INSERTIONS, then deletes them in
the order specified by DELETIONS, checking the ABT's contents
for correctness after each operation. */
static void
test_insert_delete (const int insertions[],
const int deletions[],
- size_t cnt)
+ size_t n)
{
- do_test_insert_delete (INSERT, insertions, deletions, cnt);
- do_test_insert_delete (INSERT_AFTER, insertions, deletions, cnt);
- do_test_insert_delete (INSERT_BEFORE, insertions, deletions, cnt);
+ do_test_insert_delete (INSERT, insertions, deletions, n);
+ do_test_insert_delete (INSERT_AFTER, insertions, deletions, n);
+ do_test_insert_delete (INSERT_BEFORE, insertions, deletions, n);
}
\f
/* Inserts values into an ABT in each possible order, then
test_insert_any_remove_any (void)
{
const int max_elems = 5;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int ins_n_perms;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
for (ins_n_perms = 0;
- ins_n_perms == 0 || next_permutation (insertions, cnt);
+ ins_n_perms == 0 || next_permutation (insertions, n);
ins_n_perms++)
{
unsigned int del_n_perms;
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i;
for (del_n_perms = 0;
- del_n_perms == 0 || next_permutation (deletions, cnt);
+ del_n_perms == 0 || next_permutation (deletions, n);
del_n_perms++)
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
- check (del_n_perms == factorial (cnt));
+ check (del_n_perms == factorial (n));
}
- check (ins_n_perms == factorial (cnt));
+ check (ins_n_perms == factorial (n));
free (insertions);
free (deletions);
test_insert_any_remove_same (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ for (i = 0; i < n; i++)
values[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
- test_insert_delete (values, values, cnt);
- check (n_permutations == factorial (cnt));
+ test_insert_delete (values, values, n);
+ check (n_permutations == factorial (n));
free (values);
}
test_insert_any_remove_reverse (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
unsigned int n_permutations;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (insertions, cnt);
+ n_permutations == 0 || next_permutation (insertions, n);
n_permutations++)
{
- memcpy (deletions, insertions, sizeof *insertions * cnt);
- reverse (deletions, cnt);
+ memcpy (deletions, insertions, sizeof *insertions * n);
+ reverse (deletions, n);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (insertions);
free (deletions);
{
const int max_elems = 128;
const int max_trials = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt += 2)
+ for (n = 0; n <= max_elems; n += 2)
{
int *insertions, *deletions;
int trial;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i;
for (trial = 0; trial < max_trials; trial++)
{
- random_shuffle (insertions, cnt, sizeof *insertions);
- random_shuffle (deletions, cnt, sizeof *deletions);
+ random_shuffle (insertions, n, sizeof *insertions);
+ random_shuffle (deletions, n, sizeof *deletions);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
free (insertions);
test_changed (void)
{
const int max_elems = 6;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values, *changed_values;
struct element *elements;
unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- changed_values = xnmalloc (cnt, sizeof *changed_values);
- elements = xnmalloc (cnt, sizeof *elements);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ changed_values = xnmalloc (n, sizeof *changed_values);
+ elements = xnmalloc (n, sizeof *elements);
+ for (i = 0; i < n; i++)
values[i] = i;
for (n_permutations = 0;
- n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations == 0 || next_permutation (values, n);
n_permutations++)
{
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
int j, k;
- for (j = 0; j <= cnt; j++)
+ for (j = 0; j <= n; j++)
{
struct abt abt;
struct abt_node *changed_retval;
&aux_data);
/* Add to ABT in order. */
- for (k = 0; k < cnt; k++)
+ for (k = 0; k < n; k++)
{
int n = values[k];
elements[n].data = n;
check (abt_insert (&abt, &elements[n].node) == NULL);
}
- check_abt (&abt, values, cnt);
+ check_abt (&abt, values, n);
/* Change value i to j. */
elements[i].data = j;
- for (k = 0; k < cnt; k++)
+ for (k = 0; k < n; k++)
changed_values[k] = k;
changed_retval = abt_changed (&abt, &elements[i].node);
- if (i != j && j < cnt)
+ if (i != j && j < n)
{
/* Will cause duplicate. */
check (changed_retval == &elements[j].node);
- changed_values[i] = changed_values[cnt - 1];
- check_abt (&abt, changed_values, cnt - 1);
+ changed_values[i] = changed_values[n - 1];
+ check_abt (&abt, changed_values, n - 1);
}
else
{
/* Succeeds. */
check (changed_retval == NULL);
changed_values[i] = j;
- check_abt (&abt, changed_values, cnt);
+ check_abt (&abt, changed_values, n);
}
}
}
}
- check (n_permutations == factorial (cnt));
+ check (n_permutations == factorial (n));
free (values);
free (changed_values);
projects / pspp / blobdiff