From 754c677b0bbf3ea6c7d2a73c93848f1b0d68c91e Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 20 Jun 2011 16:54:15 +0930 Subject: lib: import ccan modules for tdb2 Imported from git://git.ozlabs.org/~ccan/ccan init-1161-g661d41f Signed-off-by: Rusty Russell --- lib/ccan/tally/test/run-bucket_of.c | 71 ++++++++++++++++++++++ lib/ccan/tally/test/run-divlu64.c | 31 ++++++++++ lib/ccan/tally/test/run-histogram.c | 108 ++++++++++++++++++++++++++++++++++ lib/ccan/tally/test/run-mean.c | 29 +++++++++ lib/ccan/tally/test/run-median.c | 45 ++++++++++++++ lib/ccan/tally/test/run-min-max.c | 20 +++++++ lib/ccan/tally/test/run-mode.c | 45 ++++++++++++++ lib/ccan/tally/test/run-renormalize.c | 25 ++++++++ lib/ccan/tally/test/run-total.c | 56 ++++++++++++++++++ 9 files changed, 430 insertions(+) create mode 100644 lib/ccan/tally/test/run-bucket_of.c create mode 100644 lib/ccan/tally/test/run-divlu64.c create mode 100644 lib/ccan/tally/test/run-histogram.c create mode 100644 lib/ccan/tally/test/run-mean.c create mode 100644 lib/ccan/tally/test/run-median.c create mode 100644 lib/ccan/tally/test/run-min-max.c create mode 100644 lib/ccan/tally/test/run-mode.c create mode 100644 lib/ccan/tally/test/run-renormalize.c create mode 100644 lib/ccan/tally/test/run-total.c (limited to 'lib/ccan/tally/test') diff --git a/lib/ccan/tally/test/run-bucket_of.c b/lib/ccan/tally/test/run-bucket_of.c new file mode 100644 index 0000000000..5e12725757 --- /dev/null +++ b/lib/ccan/tally/test/run-bucket_of.c @@ -0,0 +1,71 @@ +#include +#include + +int main(void) +{ + unsigned int i, max_step; + ssize_t min, max; + + max = (ssize_t)~(1ULL << (sizeof(max)*CHAR_BIT - 1)); + min = (ssize_t)(1ULL << (sizeof(max)*CHAR_BIT - 1)); + max_step = sizeof(max)*CHAR_BIT; + + plan_tests(2 + 100 + 10 + 5 + + 2 + 100 + 5 + 4 + + (1 << 7) * (max_step - 7)); + + /* Single step, single bucket == easy. */ + ok1(bucket_of(0, 0, 0) == 0); + + /* Double step, still in first bucket. */ + ok1(bucket_of(0, 1, 0) == 0); + + /* Step 8. */ + for (i = 0; i < 100; i++) + ok1(bucket_of(0, 3, i) == i >> 3); + + /* 10 values in 5 buckets, step 2. */ + for (i = 0; i < 10; i++) + ok1(bucket_of(0, 1, i) == i >> 1); + + /* Extreme cases. */ + ok1(bucket_of(min, 0, min) == 0); + ok1(bucket_of(min, max_step-1, min) == 0); + ok1(bucket_of(min, max_step-1, max) == 1); + ok1(bucket_of(min, max_step, min) == 0); + ok1(bucket_of(min, max_step, max) == 0); + + /* Now, bucket_min() should match: */ + ok1(bucket_min(0, 0, 0) == 0); + + /* Double step, val in first bucket still 0. */ + ok1(bucket_min(0, 1, 0) == 0); + + /* Step 8. */ + for (i = 0; i < 100; i++) + ok1(bucket_min(0, 3, i) == i << 3); + + /* 10 values in 5 buckets, step 2. */ + for (i = 0; i < 5; i++) + ok1(bucket_min(0, 1, i) == i << 1); + + /* Extreme cases. */ + ok1(bucket_min(min, 0, 0) == min); + ok1(bucket_min(min, max_step-1, 0) == min); + ok1(bucket_min(min, max_step-1, 1) == 0); + ok1(bucket_min(min, max_step, 0) == min); + + /* Now, vary step and number of buckets, but bucket_min and bucket_of + * must agree. */ + for (i = 0; i < (1 << 7); i++) { + unsigned int j; + for (j = 0; j < max_step - 7; j++) { + ssize_t val; + + val = bucket_min(-(ssize_t)i, j, i); + ok1(bucket_of(-(ssize_t)i, j, val) == i); + } + } + + return exit_status(); +} diff --git a/lib/ccan/tally/test/run-divlu64.c b/lib/ccan/tally/test/run-divlu64.c new file mode 100644 index 0000000000..057e47432c --- /dev/null +++ b/lib/ccan/tally/test/run-divlu64.c @@ -0,0 +1,31 @@ +#include +#include + +int main(void) +{ + unsigned int i, j; + + plan_tests(5985); + /* Simple tests. */ + for (i = 0; i < 127; i++) { + uint64_t u1, u0; + if (i < 64) { + u1 = 0; + u0 = 1ULL << i; + j = 0; + } else { + u1 = 1ULL << (i - 64); + u0 = 0; + j = i - 63; + } + for (; j < 63; j++) { + uint64_t answer; + if (j > i) + answer = 0; + else + answer = 1ULL << (i - j); + ok1(divlu64(u1, u0, 1ULL << j) == answer); + } + } + return exit_status(); +} diff --git a/lib/ccan/tally/test/run-histogram.c b/lib/ccan/tally/test/run-histogram.c new file mode 100644 index 0000000000..a9894ecd85 --- /dev/null +++ b/lib/ccan/tally/test/run-histogram.c @@ -0,0 +1,108 @@ +#include +#include + +int main(void) +{ + int i; + struct tally *tally; + char *graph, *p; + + plan_tests(100 + 1 + 10 + 1 + 100 + 1 + 10 + 1 + 10 * 2 + 1); + + /* Uniform distribution, easy. */ + tally = tally_new(100); + for (i = 0; i < 100; i++) + tally_add(tally, i); + + /* 1:1 height. */ + graph = p = tally_histogram(tally, 20, 100); + for (i = 0; i < 100; i++) { + char *eol = strchr(p, '\n'); + + /* We expect it filled all way to the end. */ + ok1(eol - p == 20); + p = eol + 1; + } + ok1(!*p); + free(graph); + + /* Reduced height. */ + graph = p = tally_histogram(tally, 20, 10); + for (i = 0; i < 10; i++) { + char *eol = strchr(p, '\n'); + + /* First once can be truncated (bucket aliasing) */ + if (eol) { + ok1(eol - p == 20 || (eol - p < 20 && i == 0)); + } else + /* We should, at worst, half-fill graph */ + ok1(i > 5); + + if (eol) + p = eol + 1; + } + ok1(!*p); + free(graph); + + /* Enlarged height (gets capped). */ + graph = p = tally_histogram(tally, 20, 1000); + for (i = 0; i < 100; i++) { + char *eol = strchr(p, '\n'); + /* We expect it filled all way to the end. */ + ok1(eol - p == 20); + p = eol + 1; + } + ok1(!*p); + free(graph); + free(tally); + + /* Distinctive increasing pattern. */ + tally = tally_new(10); + for (i = 0; i < 10; i++) { + unsigned int j; + for (j = 0; j <= i; j++) + tally_add(tally, i); + } + + graph = p = tally_histogram(tally, 10, 10); + for (i = 0; i < 10; i++) { + char *eol = strchr(p, '\n'); + ok1(eol - p == 10 - i); + p = eol + 1; + } + ok1(!*p); + diag("Here's the pretty: %s", graph); + free(graph); + free(tally); + + /* With negative values. */ + tally = tally_new(10); + for (i = 0; i < 10; i++) { + tally_add(tally, i - 5); + } + + graph = p = tally_histogram(tally, 10, 10); + for (i = 0; i < 10; i++) { + char *eol = strchr(p, '\n'); + + /* We expect it filled all way to the end. */ + ok1(eol - p == 10); + + /* Check min/max labels. */ + if (i == 0) + ok1(strncmp(p, "4*", 2) == 0); + else if (i == 9) + ok1(strncmp(p, "-5*", 3) == 0); + else if (i == 4) + ok1(p[0] == '+'); /* 0 marker */ + else + ok1(p[0] == '|'); + p = eol + 1; + } + ok1(!*p); + diag("Here's the pretty: %s", graph); + free(graph); + free(tally); + + return exit_status(); +} diff --git a/lib/ccan/tally/test/run-mean.c b/lib/ccan/tally/test/run-mean.c new file mode 100644 index 0000000000..a4a67cf9c8 --- /dev/null +++ b/lib/ccan/tally/test/run-mean.c @@ -0,0 +1,29 @@ +#include +#include + +int main(void) +{ + int i; + struct tally *tally = tally_new(0); + ssize_t min, max; + + max = (ssize_t)~(1ULL << (sizeof(max)*CHAR_BIT - 1)); + min = (ssize_t)(1ULL << (sizeof(max)*CHAR_BIT - 1)); + + plan_tests(100 + 100); + /* Simple mean test: should always be 0. */ + for (i = 0; i < 100; i++) { + tally_add(tally, i); + tally_add(tally, -i); + ok1(tally_mean(tally) == 0); + } + + /* Works for big values too... */ + for (i = 0; i < 100; i++) { + tally_add(tally, max - i); + tally_add(tally, min + 1 + i); + ok1(tally_mean(tally) == 0); + } + + return exit_status(); +} diff --git a/lib/ccan/tally/test/run-median.c b/lib/ccan/tally/test/run-median.c new file mode 100644 index 0000000000..f461c2ec8f --- /dev/null +++ b/lib/ccan/tally/test/run-median.c @@ -0,0 +1,45 @@ +#include +#include + +int main(void) +{ + int i; + struct tally *tally = tally_new(100); + ssize_t min, max, median; + size_t err; + + max = (ssize_t)~(1ULL << (sizeof(max)*CHAR_BIT - 1)); + min = (ssize_t)(1ULL << (sizeof(max)*CHAR_BIT - 1)); + + plan_tests(100*2 + 100*2 + 100*2); + /* Simple median test: should always be around 0. */ + for (i = 0; i < 100; i++) { + tally_add(tally, i); + tally_add(tally, -i); + median = tally_approx_median(tally, &err); + ok1(err <= 4); + ok1(median - (ssize_t)err <= 0 && median + (ssize_t)err >= 0); + } + + /* Works for big values too... */ + for (i = 0; i < 100; i++) { + tally_add(tally, max - i); + tally_add(tally, min + 1 + i); + median = tally_approx_median(tally, &err); + /* Error should be < 100th of max - min. */ + ok1(err <= max / 100 * 2); + ok1(median - (ssize_t)err <= 0 && median + (ssize_t)err >= 0); + } + free(tally); + + tally = tally_new(10); + for (i = 0; i < 100; i++) { + tally_add(tally, i); + median = tally_approx_median(tally, &err); + ok1(err <= i / 10 + 1); + ok1(median - (ssize_t)err <= i/2 + && median + (ssize_t)err >= i/2); + } + + return exit_status(); +} diff --git a/lib/ccan/tally/test/run-min-max.c b/lib/ccan/tally/test/run-min-max.c new file mode 100644 index 0000000000..ffb0f2eff4 --- /dev/null +++ b/lib/ccan/tally/test/run-min-max.c @@ -0,0 +1,20 @@ +#include +#include + +int main(void) +{ + int i; + struct tally *tally = tally_new(0); + + plan_tests(100 * 4); + /* Test max, min and num. */ + for (i = 0; i < 100; i++) { + tally_add(tally, i); + ok1(tally_num(tally) == i*2 + 1); + tally_add(tally, -i); + ok1(tally_num(tally) == i*2 + 2); + ok1(tally_max(tally) == i); + ok1(tally_min(tally) == -i); + } + return exit_status(); +} diff --git a/lib/ccan/tally/test/run-mode.c b/lib/ccan/tally/test/run-mode.c new file mode 100644 index 0000000000..7216738bfb --- /dev/null +++ b/lib/ccan/tally/test/run-mode.c @@ -0,0 +1,45 @@ +#include +#include + +int main(void) +{ + int i; + struct tally *tally = tally_new(100); + ssize_t min, max, mode; + size_t err; + + max = (ssize_t)~(1ULL << (sizeof(max)*CHAR_BIT - 1)); + min = (ssize_t)(1ULL << (sizeof(max)*CHAR_BIT - 1)); + + plan_tests(100 + 50 + 100 + 100 + 10); + /* Simple mode test: should always be around 0 (we add that twice). */ + for (i = 0; i < 100; i++) { + tally_add(tally, i); + tally_add(tally, -i); + mode = tally_approx_mode(tally, &err); + if (i < 50) + ok1(err == 0); + ok1(mode - (ssize_t)err <= 0 && mode + (ssize_t)err >= 0); + } + + /* Works for big values too... */ + for (i = 0; i < 100; i++) { + tally_add(tally, max - i); + tally_add(tally, min + 1 + i); + mode = tally_approx_mode(tally, &err); + ok1(mode - (ssize_t)err <= 0 && mode + (ssize_t)err >= 0); + } + free(tally); + + tally = tally_new(10); + tally_add(tally, 0); + for (i = 0; i < 100; i++) { + tally_add(tally, i); + mode = tally_approx_mode(tally, &err); + if (i < 10) + ok1(err == 0); + ok1(mode - (ssize_t)err <= 0 && mode + (ssize_t)err >= 0); + } + + return exit_status(); +} diff --git a/lib/ccan/tally/test/run-renormalize.c b/lib/ccan/tally/test/run-renormalize.c new file mode 100644 index 0000000000..7c141528d2 --- /dev/null +++ b/lib/ccan/tally/test/run-renormalize.c @@ -0,0 +1,25 @@ +#include +#include + +int main(void) +{ + struct tally *tally = tally_new(2); + + plan_tests(4); + tally->min = 0; + tally->max = 0; + tally->counts[0] = 1; + + /* This renormalize should do nothing. */ + renormalize(tally, 0, 1); + ok1(tally->counts[0] == 1); + ok1(tally->counts[1] == 0); + tally->counts[1]++; + + /* This renormalize should collapse both into bucket 0. */ + renormalize(tally, 0, 3); + ok1(tally->counts[0] == 2); + ok1(tally->counts[1] == 0); + + return exit_status(); +} diff --git a/lib/ccan/tally/test/run-total.c b/lib/ccan/tally/test/run-total.c new file mode 100644 index 0000000000..d7d73e58a5 --- /dev/null +++ b/lib/ccan/tally/test/run-total.c @@ -0,0 +1,56 @@ +#include +#include + +int main(void) +{ + struct tally *tally; + ssize_t total, overflow; + ssize_t min, max; + + max = (ssize_t)~(1ULL << (sizeof(max)*CHAR_BIT - 1)); + min = (ssize_t)(1ULL << (sizeof(max)*CHAR_BIT - 1)); + + plan_tests(15); + + /* Simple case. */ + tally = tally_new(0); + tally_add(tally, min); + ok1(tally_total(tally, NULL) == min); + ok1(tally_total(tally, &overflow) == min); + ok1(overflow == -1); + + /* Underflow. */ + tally_add(tally, min); + total = tally_total(tally, &overflow); + ok1(overflow == -1); + ok1((size_t)total == 0); + ok1(tally_total(tally, NULL) == min); + free(tally); + + /* Simple case. */ + tally = tally_new(0); + tally_add(tally, max); + ok1(tally_total(tally, NULL) == max); + ok1(tally_total(tally, &overflow) == max); + ok1(overflow == 0); + + /* Overflow into sign bit... */ + tally_add(tally, max); + total = tally_total(tally, &overflow); + ok1(overflow == 0); + ok1((size_t)total == (size_t)-2); + ok1(tally_total(tally, NULL) == max); + + /* Overflow into upper size_t. */ + tally_add(tally, max); + total = tally_total(tally, &overflow); + ok1(overflow == 1); + if (sizeof(size_t) == 4) + ok1((size_t)total == 0x7FFFFFFD); + else if (sizeof(size_t) == 8) + ok1((size_t)total == 0x7FFFFFFFFFFFFFFDULL); + ok1(tally_total(tally, NULL) == max); + free(tally); + + return exit_status(); +} -- cgit