X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=tests%2Flibpspp%2Frange-set-test.c;h=e8cbffa5e6334408bbd69dc4c7c2a7e9dbb72829;hb=bd17d2af982332ee1791998361b1ac6731fe14fa;hp=894c679726b3f946baac3922448905becff92634;hpb=43b1296aafe7582e7dbe6c2b6a8b478d7d9b0fcf;p=pspp-builds.git diff --git a/tests/libpspp/range-set-test.c b/tests/libpspp/range-set-test.c index 894c6797..e8cbffa5 100644 --- a/tests/libpspp/range-set-test.c +++ b/tests/libpspp/range-set-test.c @@ -1,5 +1,5 @@ /* PSPP - a program for statistical analysis. - Copyright (C) 2007 Free Software Foundation, Inc. + 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 @@ -119,6 +119,47 @@ next_region (unsigned int pattern, unsigned int offset, return false; } +/* Searches the bits in PATTERN from left to right starting from + just beyond bit OFFSET for one or more 1-bits. If any are + found, sets *START to the bit index of the first and *WIDTH to + the number of contiguous 1-bits and returns true. Otherwise, + returns false. + This implementation is designed to be obviously correct, not + to be efficient. */ +static bool +prev_region (unsigned int pattern, unsigned int offset, + unsigned long int *start, unsigned long int *width) +{ + unsigned int i; + + assert (offset <= UINT_BIT); + for (i = offset; i-- > 0; ) + if (pattern & (1u << i)) + { + *start = i; + *width = 1; + while (i-- > 0 && pattern & (1u << i)) + { + ++*width; + --*start; + } + return true; + } + return false; +} + +/* Searches the bits in PATTERN from right to left starting from + bit OFFSET. Returns the bit index of the first 1-bit found, + or ULONG_MAX if none is found. */ +static unsigned long int +next_1bit (unsigned int pattern, unsigned int offset) +{ + for (; offset < UINT_BIT; offset++) + if (pattern & (1u << offset)) + return offset; + return ULONG_MAX; +} + /* Prints the regions in RS to stdout. */ static void UNUSED print_regions (const struct range_set *rs) @@ -139,6 +180,7 @@ check_pattern (const struct range_set *rs, unsigned int pattern) { const struct range_set_node *node; unsigned long int start, width; + unsigned long int s1, s2; int i; for (node = rand () % 2 ? range_set_first (rs) : range_set_next (rs, NULL), @@ -153,6 +195,52 @@ check_pattern (const struct range_set *rs, unsigned int pattern) } check (node == NULL); + for (node = rand () % 2 ? range_set_last (rs) : range_set_prev (rs, NULL), + start = UINT_BIT; + prev_region (pattern, start, &start, &width); + node = range_set_prev (rs, node)) + { + check (node != NULL); + check (range_set_node_get_start (node) == start); + check (range_set_node_get_end (node) == start + width); + check (range_set_node_get_width (node) == width); + } + check (node == NULL); + + /* Scan from all possible positions, resetting the cache each + time, to ensure that we get the correct answers without + caching. */ + for (start = 0; start <= 32; start++) + { + struct range_set *nonconst_rs = (struct range_set *) rs; + nonconst_rs->cache_end = 0; + s1 = range_set_scan (rs, start); + s2 = next_1bit (pattern, start); + check (s1 == s2); + } + + /* Scan in forward order to exercise expected cache behavior. */ + for (s1 = range_set_scan (rs, 0), s2 = next_1bit (pattern, 0); ; + s1 = range_set_scan (rs, s1 + 1), s2 = next_1bit (pattern, s2 + 1)) + { + check (s1 == s2); + if (s1 == ULONG_MAX) + break; + } + + /* Scan in random order to frustrate cache. */ + for (i = 0; i < 32; i++) + { + start = rand () % 32; + s1 = range_set_scan (rs, start); + s2 = next_1bit (pattern, start); + check (s1 == s2); + } + + /* Test range_set_scan() with negative cache. */ + check (!range_set_contains (rs, 999)); + check (range_set_scan (rs, 1111) == ULONG_MAX); + for (i = 0; i < UINT_BIT; i++) check (range_set_contains (rs, i) == ((pattern & (1u << i)) != 0)); check (!range_set_contains (rs, @@ -288,6 +376,60 @@ 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) @@ -310,6 +452,13 @@ 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. */ @@ -329,7 +478,9 @@ 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;