From e539f9ba0903c9f593167219f3aa2c0d51cd23df Mon Sep 17 00:00:00 2001 From: Matthew Fernandez Date: Thu, 10 Feb 2022 19:45:34 +1100 Subject: [PATCH] add unit tests for bitarray.h This demonstrates a current bug in bit clearing. --- lib/cgraph/test_bitarray.c | 190 +++++++++++++++++++++++++++++++++++++ rtest/test_regression.py | 18 ++++ 2 files changed, 208 insertions(+) create mode 100644 lib/cgraph/test_bitarray.c diff --git a/lib/cgraph/test_bitarray.c b/lib/cgraph/test_bitarray.c new file mode 100644 index 000000000..093b94913 --- /dev/null +++ b/lib/cgraph/test_bitarray.c @@ -0,0 +1,190 @@ +// basic unit tester for bitarray.h + +#ifdef NDEBUG +#error this is not intended to be compiled with assertions off +#endif + +#include +#include +#include +#include +#include +#include +#include + +// helper for basic construction and destruction, with nothing in-between +static void create_reset(size_t size) { + bitarray_t b; + memset(&b, 0, sizeof(b)); + int r = bitarray_new(&b, size); + assert(r == 0); + bitarray_reset(&b); +} + +// basic creation of a small array +static void test_create_reset_small(void) { create_reset(10); } + +// basic creation of a large array +static void test_create_reset_large(void) { create_reset(1023); } + +// setting and unsetting of all bits +static void set_unset(size_t size) { + + bitarray_t b; + memset(&b, 0, sizeof(b)); + int r = bitarray_new(&b, size); + assert(r == 0); + + // set and unset each bit + for (size_t i = 0; i < size; ++i) { + for (size_t j = 0; j < size; ++j) + assert(!bitarray_get(b, j)); + bitarray_set(&b, i, true); + for (size_t j = 0; j < size; ++j) + assert(bitarray_get(b, j) == (i == j)); + bitarray_set(&b, i, false); + for (size_t j = 0; j < size; ++j) + assert(!bitarray_get(b, j)); + } + + // try the same in reverse + for (size_t i = size - 1;; --i) { + for (size_t j = 0; j < size; ++j) + assert(!bitarray_get(b, j)); + bitarray_set(&b, i, true); + for (size_t j = 0; j < size; ++j) + assert(bitarray_get(b, j) == (i == j)); + bitarray_set(&b, i, false); + for (size_t j = 0; j < size; ++j) + assert(!bitarray_get(b, j)); + if (i == 0) + break; + } + + // a different, arbitrary order of a few bits + static const size_t INDEX[] = {3, 1, 4, 42, 6, 7, 123}; + for (size_t i = 0; i < sizeof(INDEX) / sizeof(INDEX[0]); ++i) { + if (INDEX[i] >= size) + continue; + for (size_t j = 0; j < size; ++j) + assert(!bitarray_get(b, j)); + bitarray_set(&b, INDEX[i], true); + for (size_t j = 0; j < size; ++j) + assert(bitarray_get(b, j) == (INDEX[i] == j)); + bitarray_set(&b, INDEX[i], false); + for (size_t j = 0; j < size; ++j) + assert(!bitarray_get(b, j)); + } + + bitarray_reset(&b); +} + +// set/unset for a small array +static void test_set_unset_small(void) { set_unset(10); } + +// set/unset for a large array +static void test_set_unset_large(void) { set_unset(1023); } + +// using an 8-bit aligned array +static void test_set_unset_aligned(void) { + set_unset(8); + set_unset(16); + set_unset(64); + set_unset(1024); + set_unset(4096); + set_unset(8192); +} + +// reusing an array +static void test_reuse(void) { + + size_t size = 10; + + bitarray_t b; + memset(&b, 0, sizeof(b)); + int r = bitarray_new(&b, size); + assert(r == 0); + + // set and unset each bit + for (size_t i = 0; i < size; ++i) { + for (size_t j = 0; j < size; ++j) + assert(!bitarray_get(b, j)); + bitarray_set(&b, i, true); + for (size_t j = 0; j < size; ++j) + assert(bitarray_get(b, j) == (i == j)); + bitarray_set(&b, i, false); + for (size_t j = 0; j < size; ++j) + assert(!bitarray_get(b, j)); + } + + bitarray_reset(&b); + + // reuse it with a different size + size = 1023; + r = bitarray_new(&b, size); + assert(r == 0); + + // set and unset each bit + for (size_t i = 0; i < size; ++i) { + for (size_t j = 0; j < size; ++j) + assert(!bitarray_get(b, j)); + bitarray_set(&b, i, true); + for (size_t j = 0; j < size; ++j) + assert(bitarray_get(b, j) == (i == j)); + bitarray_set(&b, i, false); + for (size_t j = 0; j < size; ++j) + assert(!bitarray_get(b, j)); + } + + bitarray_reset(&b); +} + +// redundant write to a bit +static void double_set(size_t size, bool value) { + + bitarray_t b; + memset(&b, 0, sizeof(b)); + int r = bitarray_new(&b, size); + assert(r == 0); + + static const size_t index = 7; + assert(!bitarray_get(b, index)); + bitarray_set(&b, index, value); + assert(bitarray_get(b, index) == value); + bitarray_set(&b, index, value); + assert(bitarray_get(b, index) == value); + + bitarray_reset(&b); +} + +// various versions of the above +static void test_double_set_small(void) { double_set(10, true); } +static void test_double_set_large(void) { double_set(1023, true); } +static void test_double_clear_small(void) { double_set(10, false); } +static void test_double_clear_large(void) { double_set(1023, false); } + +int main(void) { + +#define RUN(t) \ + do { \ + printf("running test_%s... ", #t); \ + fflush(stdout); \ + test_##t(); \ + printf("OK\n"); \ + } while (0) + + RUN(create_reset_small); + RUN(create_reset_large); + RUN(set_unset_small); + RUN(set_unset_large); + RUN(set_unset_aligned); + RUN(reuse); + RUN(double_set_small); + RUN(double_set_large); + RUN(double_clear_small); + RUN(double_clear_large); + +#undef RUN + + return EXIT_SUCCESS; +} diff --git a/rtest/test_regression.py b/rtest/test_regression.py index f0e856dd6..7f203084c 100644 --- a/rtest/test_regression.py +++ b/rtest/test_regression.py @@ -1515,3 +1515,21 @@ def test_gvmap_fclose(): # pass this through gvmap subprocess.run(["gvmap"], input=input.encode("utf-8"), check=True) + +@pytest.mark.xfail(strict=True) # FIXME +def test_bitarray(): + """run the bitarray unit tests""" + + # locate the bitarray unit tests + src = Path(__file__).parent.resolve() / "../lib/cgraph/test_bitarray.c" + assert src.exists() + + # locate lib directory that needs to be in the include path + lib = Path(__file__).parent.resolve() / "../lib" + + # extra C flags this compilation needs + cflags = ["-I", lib] + if platform.system() != "Windows": + cflags += ["-std=gnu99", "-Wall", "-Wextra", "-Werror"] + + _, _ = run_c(src, cflags=cflags) -- 2.40.0