X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=tests%2Flibpspp%2Fabt-test.c;h=f6def5a9fe67ff3c2945bac24c61f56b471783aa;hb=2c81ed67896a7d3522c4ccdaf09e832491efd589;hp=6a165929f7d2e46f10d20b3d632580ffec13ae68;hpb=9683d7528884fcb3c60705812de9f96889536388;p=pspp-builds.git diff --git a/tests/libpspp/abt-test.c b/tests/libpspp/abt-test.c index 6a165929..f6def5a9 100644 --- a/tests/libpspp/abt-test.c +++ b/tests/libpspp/abt-test.c @@ -1,20 +1,18 @@ -/* PSPP - computes sample statistics. +/* PSPP - a program for statistical analysis. Copyright (C) 2007 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 abt_* routines defined in abt.c. This test program aims to be as comprehensive as @@ -43,17 +41,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); @@ -77,9 +75,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) @@ -92,7 +90,7 @@ xmalloc (size_t n) } static void * -xmemdup (const void *p, size_t n) +xmemdup (const void *p, size_t n) { void *q = xmalloc (n); memcpy (q, p, n); @@ -101,7 +99,7 @@ xmemdup (const void *p, 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 (); @@ -132,7 +130,7 @@ abt_node_to_element (const struct abt_node *node) return value. Verifies that AUX points to aux_data. */ static int compare_elements (const struct abt_node *a_, const struct abt_node *b_, - const void *aux) + const void *aux) { const struct element *a = abt_node_to_element (a_); const struct element *b = abt_node_to_element (b_); @@ -147,7 +145,7 @@ static void reaugment_elements (struct abt_node *node_, const struct abt_node *left, const struct abt_node *right, - const void *aux) + const void *aux) { struct element *node = abt_node_to_element (node_); @@ -162,7 +160,7 @@ reaugment_elements (struct abt_node *node_, /* 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_; @@ -172,7 +170,7 @@ compare_ints_noaux (const void *a_, const void *b_) /* Swaps *A and *B. */ static void -swap (int *a, int *b) +swap (int *a, int *b) { int t = *a; *a = *b; @@ -203,7 +201,7 @@ next_permutation (int *values, size_t cnt) if (cnt > 0) { size_t i = cnt - 1; - while (i != 0) + while (i != 0) { i--; if (values[i] < values[i + 1]) @@ -214,18 +212,18 @@ next_permutation (int *values, size_t cnt) swap (values + i, values + j); reverse (values + (i + 1), cnt - (i + 1)); return true; - } + } } - + reverse (values, cnt); } - + return false; } /* Returns N!. */ static unsigned int -factorial (unsigned int n) +factorial (unsigned int n) { unsigned int value = 1; while (n > 1) @@ -242,10 +240,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); @@ -259,16 +257,16 @@ random_shuffle (void *array_, size_t cnt, size_t size) /* Finds and returns the element in ABT that is in the given 0-based POSITION in in-order. */ static struct element * -find_by_position (struct abt *abt, int position) +find_by_position (struct abt *abt, int position) { struct abt_node *p; - for (p = abt->root; p != NULL; ) + for (p = abt->root; p != NULL; ) { int p_pos = p->down[0] ? abt_node_to_element (p->down[0])->count : 0; if (position == p_pos) return abt_node_to_element (p); else if (position < p_pos) - p = p->down[0]; + p = p->down[0]; else { p = p->down[1]; @@ -281,11 +279,11 @@ find_by_position (struct abt *abt, int position) /* Checks that all the augmentations are correct in the subtree rooted at P. Returns the number of nodes in the subtree. */ static int -check_augmentations (struct abt_node *p_) +check_augmentations (struct abt_node *p_) { if (p_ == NULL) return 0; - else + else { struct element *p = abt_node_to_element (p_); int left_count = check_augmentations (p->node.down[0]); @@ -298,9 +296,9 @@ check_augmentations (struct abt_node *p_) /* Check that the levels are correct in the subtree rooted at P. */ static void -check_levels (struct abt_node *p) +check_levels (struct abt_node *p) { - if (p != NULL) + if (p != NULL) { int i, j; @@ -308,11 +306,11 @@ check_levels (struct abt_node *p) check_levels (p->down[1]); check (p->level >= 1); - if (p->level > 1) + if (p->level > 1) { struct abt_node *q = p->down[1]; check (q != NULL); - check (q->level == p->level || q->level == p->level - 1); + check (q->level == p->level || q->level == p->level - 1); } for (i = 0; i < 2; i++) @@ -327,7 +325,7 @@ check_levels (struct abt_node *p) 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 cnt) { struct element e; size_t i; @@ -336,39 +334,42 @@ check_abt (struct abt *abt, const int data[], size_t cnt) order = xmemdup (data, cnt * sizeof *data); qsort (order, cnt, sizeof *order, compare_ints_noaux); - for (i = 0; i < cnt; i++) + if (abt->compare != NULL) { - struct abt_node *p; - - e.data = data[i]; - if (rand () % 2) - p = abt_find (abt, &e.node); - else - p = abt_insert (abt, &e.node); - check (p != NULL); - check (p != &e.node); - check (abt_node_to_element (p)->data == data[i]); - } + for (i = 0; i < cnt; i++) + { + struct abt_node *p; + + e.data = data[i]; + if (rand () % 2) + p = abt_find (abt, &e.node); + else + p = abt_insert (abt, &e.node); + check (p != NULL); + check (p != &e.node); + check (abt_node_to_element (p)->data == data[i]); + } - e.data = -1; - check (abt_find (abt, &e.node) == NULL); + e.data = -1; + check (abt_find (abt, &e.node) == NULL); + } check_levels (abt->root); check_augmentations (abt->root); for (i = 0; i < cnt; i++) check (find_by_position (abt, i)->data == order[i]); - if (cnt == 0) + if (cnt == 0) { check (abt_first (abt) == NULL); check (abt_last (abt) == NULL); check (abt_next (abt, NULL) == NULL); check (abt_prev (abt, NULL) == NULL); } - else + else { struct abt_node *p; - + for (p = abt_first (abt), i = 0; i < cnt; p = abt_next (abt, p), i++) check (abt_node_to_element (p)->data == order[i]); check (p == NULL); @@ -381,28 +382,74 @@ check_abt (struct abt *abt, const int data[], size_t cnt) free (order); } +/* Ways that nodes can be inserted. */ +enum insertion_method + { + INSERT, /* With abt_insert. */ + INSERT_AFTER, /* With abt_insert_after. */ + INSERT_BEFORE /* With abt_insert_before. */ + }; + +/* Inserts INSERT into ABT with the given METHOD. */ +static void +insert_node (struct abt *abt, struct element *insert, + enum insertion_method method) +{ + if (method == INSERT) + check (abt_insert (abt, &insert->node) == NULL); + else + { + struct abt_node *p = abt->root; + int dir = 0; + if (p != NULL) + for (;;) + { + dir = insert->data > abt_node_to_element (p)->data; + if (p->down[dir] == NULL) + break; + p = p->down[dir]; + } + if (method == INSERT_AFTER) + { + if (p != NULL && (dir != 1 || p->down[1] != NULL)) + p = abt_prev (abt, p); + abt_insert_after (abt, p, &insert->node); + } + else + { + if (p != NULL && (dir != 0 || p->down[0] != NULL)) + p = abt_next (abt, p); + abt_insert_before (abt, p, &insert->node); + } + } +} + + /* Inserts the CNT values from 0 to CNT - 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. */ + 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 + operation. */ static void -test_insert_delete (const int insertions[], - const int deletions[], - size_t cnt) +do_test_insert_delete (enum insertion_method method, + const int insertions[], + const int deletions[], + size_t cnt) { struct element *elements; struct abt abt; size_t i; - + elements = xnmalloc (cnt, sizeof *elements); for (i = 0; i < cnt; i++) elements[i].data = i; - abt_init (&abt, compare_elements, reaugment_elements, &aux_data); + abt_init (&abt, method == INSERT ? compare_elements : NULL, + reaugment_elements, &aux_data); check_abt (&abt, NULL, 0); for (i = 0; i < cnt; i++) { - check (abt_insert (&abt, &elements[insertions[i]].node) == NULL); + insert_node (&abt, &elements[insertions[i]], method); check_abt (&abt, insertions, i + 1); } for (i = 0; i < cnt; i++) @@ -413,17 +460,31 @@ test_insert_delete (const int insertions[], free (elements); } + +/* Inserts the CNT values from 0 to CNT - 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) +{ + 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); +} /* Inserts values into an ABT in each possible order, then removes them in each possible order, up to a specified maximum size. */ static void -test_insert_any_remove_any (void) +test_insert_any_remove_any (void) { const int max_elems = 5; int cnt; - for (cnt = 0; cnt <= max_elems; cnt++) + for (cnt = 0; cnt <= max_elems; cnt++) { int *insertions, *deletions; unsigned int ins_perm_cnt; @@ -431,22 +492,22 @@ test_insert_any_remove_any (void) insertions = xnmalloc (cnt, sizeof *insertions); deletions = xnmalloc (cnt, sizeof *deletions); - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) insertions[i] = i; for (ins_perm_cnt = 0; ins_perm_cnt == 0 || next_permutation (insertions, cnt); - ins_perm_cnt++) + ins_perm_cnt++) { unsigned int del_perm_cnt; int i; - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) deletions[i] = i; for (del_perm_cnt = 0; del_perm_cnt == 0 || next_permutation (deletions, cnt); - del_perm_cnt++) + del_perm_cnt++) test_insert_delete (insertions, deletions, cnt); check (del_perm_cnt == factorial (cnt)); @@ -462,19 +523,19 @@ test_insert_any_remove_any (void) removes them in the same order, up to a specified maximum size. */ static void -test_insert_any_remove_same (void) +test_insert_any_remove_same (void) { const int max_elems = 7; int cnt; - for (cnt = 0; cnt <= max_elems; cnt++) + for (cnt = 0; cnt <= max_elems; cnt++) { int *values; unsigned int permutation_cnt; int i; values = xnmalloc (cnt, sizeof *values); - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) values[i] = i; for (permutation_cnt = 0; @@ -491,12 +552,12 @@ test_insert_any_remove_same (void) removes them in reverse order, up to a specified maximum size. */ static void -test_insert_any_remove_reverse (void) +test_insert_any_remove_reverse (void) { const int max_elems = 7; int cnt; - for (cnt = 0; cnt <= max_elems; cnt++) + for (cnt = 0; cnt <= max_elems; cnt++) { int *insertions, *deletions; unsigned int permutation_cnt; @@ -504,17 +565,17 @@ test_insert_any_remove_reverse (void) insertions = xnmalloc (cnt, sizeof *insertions); deletions = xnmalloc (cnt, sizeof *deletions); - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) insertions[i] = i; for (permutation_cnt = 0; permutation_cnt == 0 || next_permutation (insertions, cnt); - permutation_cnt++) + permutation_cnt++) { memcpy (deletions, insertions, sizeof *insertions * cnt); reverse (deletions, cnt); - - test_insert_delete (insertions, deletions, cnt); + + test_insert_delete (insertions, deletions, cnt); } check (permutation_cnt == factorial (cnt)); @@ -525,13 +586,13 @@ test_insert_any_remove_reverse (void) /* Inserts and removes values in an ABT in random orders. */ static void -test_random_sequence (void) +test_random_sequence (void) { const int max_elems = 128; const int max_trials = 8; int cnt; - for (cnt = 0; cnt <= max_elems; cnt += 2) + for (cnt = 0; cnt <= max_elems; cnt += 2) { int *insertions, *deletions; int trial; @@ -539,17 +600,17 @@ test_random_sequence (void) insertions = xnmalloc (cnt, sizeof *insertions); deletions = xnmalloc (cnt, sizeof *deletions); - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) insertions[i] = i; - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) deletions[i] = i; - for (trial = 0; trial < max_trials; trial++) + for (trial = 0; trial < max_trials; trial++) { random_shuffle (insertions, cnt, sizeof *insertions); random_shuffle (deletions, cnt, sizeof *deletions); - - test_insert_delete (insertions, deletions, cnt); + + test_insert_delete (insertions, deletions, cnt); } free (insertions); @@ -559,7 +620,7 @@ test_random_sequence (void) /* Inserts elements into an ABT in ascending order. */ static void -test_insert_ordered (void) +test_insert_ordered (void) { const int max_elems = 1024; struct element *elements; @@ -570,7 +631,7 @@ test_insert_ordered (void) abt_init (&abt, compare_elements, reaugment_elements, &aux_data); elements = xnmalloc (max_elems, sizeof *elements); values = xnmalloc (max_elems, sizeof *values); - for (i = 0; i < max_elems; i++) + for (i = 0; i < max_elems; i++) { values[i] = elements[i].data = i; check (abt_insert (&abt, &elements[i].node) == NULL); @@ -583,7 +644,7 @@ test_insert_ordered (void) /* Inserts elements into an ABT, then moves the nodes around in memory. */ static void -test_moved (void) +test_moved (void) { const int max_elems = 128; struct element *e[2]; @@ -597,13 +658,13 @@ test_moved (void) e[1] = xnmalloc (max_elems, sizeof *e[1]); values = xnmalloc (max_elems, sizeof *values); cur = 0; - for (i = 0; i < max_elems; i++) + for (i = 0; i < max_elems; i++) { values[i] = e[cur][i].data = i; check (abt_insert (&abt, &e[cur][i].node) == NULL); check_abt (&abt, values, i + 1); - for (j = 0; j <= i; j++) + for (j = 0; j <= i; j++) { e[!cur][j] = e[cur][j]; abt_moved (&abt, &e[!cur][j].node); @@ -623,7 +684,7 @@ test_changed (void) const int max_elems = 6; int cnt; - for (cnt = 0; cnt <= max_elems; cnt++) + for (cnt = 0; cnt <= max_elems; cnt++) { int *values, *changed_values; struct element *elements; @@ -633,17 +694,17 @@ test_changed (void) values = xnmalloc (cnt, sizeof *values); changed_values = xnmalloc (cnt, sizeof *changed_values); elements = xnmalloc (cnt, sizeof *elements); - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) values[i] = i; for (permutation_cnt = 0; permutation_cnt == 0 || next_permutation (values, cnt); - permutation_cnt++) + permutation_cnt++) { - for (i = 0; i < cnt; i++) + for (i = 0; i < cnt; i++) { int j, k; - for (j = 0; j <= cnt; j++) + for (j = 0; j <= cnt; j++) { struct abt abt; struct abt_node *changed_retval; @@ -652,11 +713,11 @@ test_changed (void) &aux_data); /* Add to ABT in order. */ - for (k = 0; k < cnt; k++) + for (k = 0; k < cnt; k++) { int n = values[k]; elements[n].data = n; - check (abt_insert (&abt, &elements[n].node) == NULL); + check (abt_insert (&abt, &elements[n].node) == NULL); } check_abt (&abt, values, cnt); @@ -680,7 +741,7 @@ test_changed (void) check_abt (&abt, changed_values, cnt); } } - } + } } check (permutation_cnt == factorial (cnt)); @@ -694,7 +755,7 @@ test_changed (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 ('.'); @@ -703,7 +764,7 @@ run_test (void (*test_function) (void), const char *name) } int -main (void) +main (void) { run_test (test_insert_any_remove_any, "insert any order, delete any order");