lib: import ccan modules for tdb2

Imported from git://git.ozlabs.org/~ccan/ccan init-1161-g661d41f

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

9 files changed, 430 insertions, 0 deletions

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 <ccan/tally/tally.c>
+#include <ccan/tap/tap.h>
+
+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 <ccan/tally/tally.c>
+#include <ccan/tap/tap.h>
+
+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 <ccan/tally/tally.c>
+#include <ccan/tap/tap.h>
+
+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 <ccan/tally/tally.c>
+#include <ccan/tap/tap.h>
+
+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 <ccan/tally/tally.c>
+#include <ccan/tap/tap.h>
+
+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 <ccan/tally/tally.c>
+#include <ccan/tap/tap.h>
+
+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 <ccan/tally/tally.c>
+#include <ccan/tap/tap.h>
+
+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 <ccan/tally/tally.c>
+#include <ccan/tap/tap.h>
+
+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 <ccan/tally/tally.c>
+#include <ccan/tap/tap.h>
+
+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();
+}