X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=tests%2Flibpspp%2Frange-set-test.c;h=9f444ad7e62eade3d692153f3fd62f8440a08c42;hb=a091aa55567a4f2a9ecc08f126a959497be43f22;hp=b1c7451ecc5b5010cc8ef4b0d34eeead23cab509;hpb=93b4335785430ab6de290b7978e2d506106a8ba5;p=pspp-builds.git diff --git a/tests/libpspp/range-set-test.c b/tests/libpspp/range-set-test.c index b1c7451e..9f444ad7 100644 --- a/tests/libpspp/range-set-test.c +++ b/tests/libpspp/range-set-test.c @@ -1,20 +1,18 @@ -/* PSPP - computes sample statistics. - Copyright (C) 2007 Free Software Foundation, Inc. +/* PSPP - a program for statistical analysis. + Copyright (C) 2007, 2009 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 routines defined in range-set.c. This test program aims to be as comprehensive as @@ -48,17 +46,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); @@ -72,7 +70,7 @@ check_func (bool ok, int line) #define check(EXPR) check_func ((EXPR), __LINE__) /* A contiguous region. */ -struct region +struct region { unsigned long int start; /* Start of region. */ unsigned long int end; /* One past the end. */ @@ -86,10 +84,10 @@ struct region This implementation is designed to be obviously correct, not to be efficient. */ static int -count_one_bits (unsigned long int x) +count_one_bits (unsigned long int x) { int count = 0; - while (x & 1) + while (x & 1) { count++; x >>= 1; @@ -106,13 +104,13 @@ count_one_bits (unsigned long int x) to be efficient. */ static bool next_region (unsigned int pattern, unsigned int offset, - unsigned long int *start, unsigned long int *width) + unsigned long int *start, unsigned long int *width) { unsigned int i; assert (offset <= UINT_BIT); for (i = offset; i < UINT_BIT; i++) - if (pattern & (1u << i)) + if (pattern & (1u << i)) { *start = i; *width = count_one_bits (pattern >> i); @@ -129,7 +127,7 @@ print_regions (const struct range_set *rs) printf ("result:"); for (node = range_set_first (rs); node != NULL; - node = range_set_next (rs, node)) + node = range_set_next (rs, node)) printf (" (%lu,%lu)", range_set_node_get_start (node), range_set_node_get_end (node)); printf ("\n"); @@ -137,16 +135,16 @@ print_regions (const struct range_set *rs) /* Checks that the regions in RS match the bits in PATTERN. */ static void -check_pattern (const struct range_set *rs, unsigned int pattern) +check_pattern (const struct range_set *rs, unsigned int pattern) { const struct range_set_node *node; unsigned long int start, width; int i; - + for (node = rand () % 2 ? range_set_first (rs) : range_set_next (rs, NULL), start = width = 0; next_region (pattern, start + width, &start, &width); - node = range_set_next (rs, node)) + node = range_set_next (rs, node)) { check (node != NULL); check (range_set_node_get_start (node) == start); @@ -166,7 +164,7 @@ check_pattern (const struct range_set *rs, unsigned int pattern) /* Creates and returns a range set that contains regions for the bits set in PATTERN. */ static struct range_set * -make_pattern (unsigned int pattern) +make_pattern (unsigned int pattern) { unsigned long int start = 0; unsigned long int width = 0; @@ -180,7 +178,7 @@ make_pattern (unsigned int pattern) /* Returns an unsigned int with bits OFS...OFS+CNT (exclusive) set to 1, other bits set to 0. */ static unsigned int -bit_range (unsigned int ofs, unsigned int cnt) +bit_range (unsigned int ofs, unsigned int cnt) { assert (ofs < UINT_BIT); assert (cnt <= UINT_BIT); @@ -192,37 +190,40 @@ bit_range (unsigned int ofs, unsigned int cnt) /* Tests inserting all possible patterns into all possible range sets (up to a small maximum number of bits). */ static void -test_insert (void) +test_insert (void) { const int positions = 9; unsigned int init_pat; int i, j; - - for (init_pat = 0; init_pat < (1u << positions); init_pat++) + + for (init_pat = 0; init_pat < (1u << positions); init_pat++) for (i = 0; i < positions + 1; i++) for (j = i; j <= positions + 1; j++) { - struct range_set *rs; + struct range_set *rs, *rs2; unsigned int final_pat; rs = make_pattern (init_pat); range_set_insert (rs, i, j - i); final_pat = init_pat | bit_range (i, j - i); check_pattern (rs, final_pat); + rs2 = range_set_clone (rs, NULL); + check_pattern (rs2, final_pat); range_set_destroy (rs); + range_set_destroy (rs2); } } /* Tests deleting all possible patterns from all possible range sets (up to a small maximum number of bits). */ static void -test_delete (void) +test_delete (void) { const int positions = 9; unsigned int init_pat; int i, j; - - for (init_pat = 0; init_pat < (1u << positions); init_pat++) + + for (init_pat = 0; init_pat < (1u << positions); init_pat++) for (i = 0; i < positions + 1; i++) for (j = i; j <= positions + 1; j++) { @@ -245,8 +246,8 @@ test_allocate (void) const int positions = 9; unsigned int init_pat; int request; - - for (init_pat = 0; init_pat < (1u << positions); init_pat++) + + for (init_pat = 0; init_pat < (1u << positions); init_pat++) for (request = 1; request <= positions + 1; request++) { struct range_set *rs; @@ -279,7 +280,7 @@ test_allocate (void) /* Check results. */ check (success == expect_success); - if (expect_success) + if (expect_success) { check (start == expect_start); check (width == expect_width); @@ -287,9 +288,63 @@ test_allocate (void) } } +/* Tests all possible full allocations in all possible range sets + (up to a small maximum number of bits). */ +static void +test_allocate_fully (void) +{ + const int positions = 9; + unsigned int init_pat; + int request; + + for (init_pat = 0; init_pat < (1u << positions); init_pat++) + for (request = 1; request <= positions + 1; request++) + { + struct range_set *rs; + unsigned long int start, expect_start; + bool success, expect_success; + unsigned int final_pat; + int i; + + /* Figure out expected results. */ + expect_success = false; + expect_start = 0; + final_pat = init_pat; + for (i = 0; i < positions - request + 1; i++) + { + int j; + + final_pat = init_pat; + for (j = i; j < i + request; j++) + { + if (!(init_pat & (1u << j))) + goto next; + final_pat &= ~(1u << j); + } + + expect_success = true; + expect_start = i; + break; + next: + final_pat = init_pat; + } + + /* Test. */ + rs = make_pattern (init_pat); + success = range_set_allocate_fully (rs, request, &start); + check_pattern (rs, final_pat); + range_set_destroy (rs); + + /* Check results. */ + check (success == expect_success); + if (expect_success) + check (start == expect_start); + } +} + /* Tests freeing a range set through a pool. */ static void -test_pool (void) +test_pool (void) { struct pool *pool; struct range_set *rs; @@ -301,7 +356,7 @@ test_pool (void) range_set_insert (rs, 1, 10); range_set_destroy (rs); pool_destroy (pool); - + /* Just destroy the pool. Makes sure that this doesn't cause a leak. */ pool = pool_create (); @@ -309,12 +364,19 @@ test_pool (void) range_set_insert (rs, 1, 10); pool_destroy (pool); } + +/* Tests range_set_destroy(NULL). */ +static void +test_destroy_null (void) +{ + range_set_destroy (NULL); +} /* Main program. */ /* 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 ('.'); @@ -323,12 +385,14 @@ run_test (void (*test_function) (void), const char *name) } int -main (void) +main (void) { run_test (test_insert, "insert"); run_test (test_delete, "delete"); run_test (test_allocate, "allocate"); + run_test (test_allocate_fully, "allocate_fully"); run_test (test_pool, "pool"); + run_test (test_destroy_null, "destroy null"); putchar ('\n'); return 0;