tally: implement tally_total()

Not as trivial as you might think, with overflow and underflow.

diff --git a/ccan/tally/tally.c b/ccan/tally/tally.c
index 1433a3aa2650e45cf2bfc44c3bce646400f8dfba..88407cf985ccfb30996383b51e7c291af00319fe 100644 (file)
--- a/ccan/tally/tally.c
+++ b/ccan/tally/tally.c
@@ -8,7 +8,7 @@
 #include <stdio.h>
 #include <assert.h>
 
 #include <stdio.h>
 #include <assert.h>
 

-#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 {
 
 /* 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. */
 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;
                return 0;

-       assert(step_bits < MAX_STEP_BITS);
+       assert(step_bits < SIZET_BITS);

        return (size_t)(val - min) >> step_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. */
 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;
                return min;

-       assert(step_bits < MAX_STEP_BITS);
+       assert(step_bits < SIZET_BITS);

        return min + ((ssize_t)b << step_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);
 }
 
        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;
 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 1f4b5d5f7576f89673a59ec78a45606ad9220691..b38cd70646f3b6205eb71e4ef07a01c2afec20cd 100644 (file)
--- 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);
 
  */
 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.
 /**
  * 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 (file)
index 0000000..1114a6e
--- /dev/null
+++ b/ccan/tally/test/run-total.c
@@ -0,0 +1,53 @@
+#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 == 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();
+}