X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=tests%2Flibpspp%2Fabt-test.c;fp=tests%2Flibpspp%2Fabt-test.c;h=177e8f9108c3027b9085445642ac3c0843518f63;hb=b525a9596e60d5ae4c6c464b4a426b77ade3dd72;hp=7ba395c6382c492b526b45c5cbc077e99d4cc588;hpb=89c05dfe33f9542e60e66dd383f7a514849b5947;p=pspp diff --git a/tests/libpspp/abt-test.c b/tests/libpspp/abt-test.c index 7ba395c638..177e8f9108 100644 --- a/tests/libpspp/abt-test.c +++ b/tests/libpspp/abt-test.c @@ -169,18 +169,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 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 @@ -188,26 +188,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; @@ -223,18 +223,18 @@ factorial (unsigned int n) 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); @@ -313,22 +313,22 @@ check_levels (struct abt_node *p) } } -/* 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; @@ -348,10 +348,10 @@ check_abt (struct abt *abt, const int data[], size_t cnt) 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); @@ -362,15 +362,15 @@ check_abt (struct abt *abt, const int data[], size_t cnt) { 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); } @@ -418,7 +418,7 @@ insert_node (struct abt *abt, struct element *insert, } -/* 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 @@ -427,45 +427,45 @@ static void 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); } /* Inserts values into an ABT in each possible order, then @@ -475,37 +475,37 @@ static void 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); @@ -519,23 +519,23 @@ static void 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); } @@ -548,29 +548,29 @@ static void 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); @@ -583,27 +583,27 @@ test_random_sequence (void) { 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); @@ -675,29 +675,29 @@ static void 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; @@ -706,37 +706,37 @@ test_changed (void) &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);