From e0fd4d1173f6d761dd6e09f820e1901e9400d8ba Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Fri, 24 Sep 2010 17:12:07 +0930 Subject: [PATCH] tally: implement tally_total() Not as trivial as you might think, with overflow and underflow. --- ccan/tally/tally.c | 37 ++++++++++++++++++++++---- ccan/tally/tally.h | 11 ++++++++ ccan/tally/test/run-total.c | 53 +++++++++++++++++++++++++++++++++++++ 3 files changed, 96 insertions(+), 5 deletions(-) create mode 100644 ccan/tally/test/run-total.c diff --git a/ccan/tally/tally.c b/ccan/tally/tally.c index 1433a3aa..88407cf9 100644 --- a/ccan/tally/tally.c +++ b/ccan/tally/tally.c @@ -8,7 +8,7 @@ #include #include -#define MAX_STEP_BITS (sizeof(size_t)*CHAR_BIT) +#define SIZET_BITS (sizeof(size_t)*CHAR_BIT) /* We use power of 2 steps. I tried being tricky, but it got buggy. */ struct tally { @@ -55,9 +55,9 @@ struct tally *tally_new(size_t buckets) static unsigned bucket_of(ssize_t min, unsigned step_bits, ssize_t val) { /* Don't over-shift. */ - if (step_bits == MAX_STEP_BITS) + if (step_bits == SIZET_BITS) return 0; - assert(step_bits < MAX_STEP_BITS); + assert(step_bits < SIZET_BITS); return (size_t)(val - min) >> step_bits; } @@ -65,9 +65,9 @@ static unsigned bucket_of(ssize_t min, unsigned step_bits, ssize_t val) static ssize_t bucket_min(ssize_t min, unsigned step_bits, unsigned b) { /* Don't over-shift. */ - if (step_bits == MAX_STEP_BITS) + if (step_bits == SIZET_BITS) return min; - assert(step_bits < MAX_STEP_BITS); + assert(step_bits < SIZET_BITS); return min + ((ssize_t)b << step_bits); } @@ -324,6 +324,33 @@ ssize_t tally_mean(const struct tally *tally) return divls64(tally->total[1], tally->total[0], count); } +ssize_t tally_total(const struct tally *tally, ssize_t *overflow) +{ + if (overflow) { + *overflow = tally->total[1]; + return tally->total[0]; + } + + /* If result is negative, make sure we can represent it. */ + if (tally->total[1] & (1 << (SIZET_BITS-1))) { + /* Must have only underflowed once, and must be able to + * represent result at ssize_t. */ + if ((~tally->total[1])+1 != 0 + || (ssize_t)tally->total[0] >= 0) { + /* Underflow, return minimum. */ + return (ssize_t)((size_t)1 << (SIZET_BITS - 1)); + } + } else { + /* Result is positive, must not have overflowed, and must be + * able to represent as ssize_t. */ + if (tally->total[1] || (ssize_t)tally->total[0] < 0) { + /* Overflow. Return maximum. */ + return (ssize_t)~((size_t)1 << (SIZET_BITS - 1)); + } + } + return tally->total[0]; +} + static ssize_t bucket_range(const struct tally *tally, unsigned b, size_t *err) { ssize_t min, max; diff --git a/ccan/tally/tally.h b/ccan/tally/tally.h index 1f4b5d5f..b38cd706 100644 --- a/ccan/tally/tally.h +++ b/ccan/tally/tally.h @@ -51,6 +51,17 @@ ssize_t tally_max(const struct tally *tally); */ ssize_t tally_mean(const struct tally *tally); +/** + * tally_total - the total value passed to tally_add. + * @tally: the tally structure. + * @overflow: the overflow value (or NULL). + * + * If your total can't overflow a ssize_t, you don't need @overflow. + * Otherwise, @overflow is the upper ssize_t, and the return value should + * be treated as the lower size_t (ie. the sign bit is in @overflow). + */ +ssize_t tally_total(const struct tally *tally, ssize_t *overflow); + /** * tally_approx_median - the approximate median value passed to tally_add. * @tally: the tally structure. diff --git a/ccan/tally/test/run-total.c b/ccan/tally/test/run-total.c new file mode 100644 index 00000000..1114a6ee --- /dev/null +++ b/ccan/tally/test/run-total.c @@ -0,0 +1,53 @@ +#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 == 0xFFFFFFFE); + ok1(tally_total(tally, NULL) == max); + + /* Overflow into upper size_t. */ + tally_add(tally, max); + total = tally_total(tally, &overflow); + ok1(overflow == 1); + ok1((size_t)total == 0x7FFFFFFD); + ok1(tally_total(tally, NULL) == max); + free(tally); + + return exit_status(); +} -- 2.39.2