likely: use htable_type
authorRusty Russell <rusty@rustcorp.com.au>
Tue, 27 Sep 2011 06:28:43 +0000 (15:58 +0930)
committerRusty Russell <rusty@rustcorp.com.au>
Tue, 27 Sep 2011 06:28:43 +0000 (15:58 +0930)
Also general cleanups:
(1) Don't assume that strings are folded by the compiler.
(2) Implement likely_stats_reset().
(3) Return non-const string from likely_stats(), as caller must free it.
(4) Don't use struct info indirection (that was from when we used callbacks?)
(5) Close memory leak in run-debug.c

ccan/likely/likely.c
ccan/likely/likely.h
ccan/likely/test/run-debug.c

index faa2bd8eb8fe22e3c8d85df77883b6550008368c..1114efc2077f81895b1cf535cc828fc2aac4c33f 100644 (file)
@@ -2,11 +2,9 @@
 #ifdef CCAN_LIKELY_DEBUG
 #include <ccan/likely/likely.h>
 #include <ccan/hash/hash.h>
 #ifdef CCAN_LIKELY_DEBUG
 #include <ccan/likely/likely.h>
 #include <ccan/hash/hash.h>
-#include <ccan/htable/htable.h>
+#include <ccan/htable/htable_type.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <stdio.h>
-static struct htable *htable;
-
 struct trace {
        const char *condstr;
        const char *file;
 struct trace {
        const char *condstr;
        const char *file;
@@ -15,27 +13,27 @@ struct trace {
        unsigned long count, right;
 };
 
        unsigned long count, right;
 };
 
-/* We hash the pointers, which will be identical for same call. */
-static unsigned long hash_trace(const struct trace *trace)
+static size_t hash_trace(const struct trace *trace)
 {
 {
-       return hash_pointer(trace->condstr,
-                           hash_pointer(trace->file,
-                                        trace->line + trace->expect));
+       return hash(trace->condstr, strlen(trace->condstr),
+                   hash(trace->file, strlen(trace->file),
+                        trace->line + trace->expect));
 }
 
 }
 
-static bool hash_cmp(const void *htelem, void *cmpdata)
+static bool trace_eq(const struct trace *t1, const struct trace *t2)
 {
 {
-       const struct trace *t1 = htelem, *t2 = cmpdata;
        return t1->condstr == t2->condstr
                && t1->file == t2->file
                && t1->line == t2->line
                && t1->expect == t2->expect;
 }
 
        return t1->condstr == t2->condstr
                && t1->file == t2->file
                && t1->line == t2->line
                && t1->expect == t2->expect;
 }
 
-static size_t rehash(const void *elem, void *priv)
-{
-       return hash_trace(elem);
-}
+/* struct thash */
+HTABLE_DEFINE_TYPE(struct trace, (const struct trace *), hash_trace, trace_eq,
+                  thash);
+
+static struct thash htable
+= { HTABLE_INITIALIZER(htable.raw, thash_hash, NULL) };
 
 static void init_trace(struct trace *trace,
                       const char *condstr, const char *file, unsigned int line,
 
 static void init_trace(struct trace *trace,
                       const char *condstr, const char *file, unsigned int line,
@@ -48,12 +46,11 @@ static void init_trace(struct trace *trace,
        trace->count = trace->right = 0;
 }
 
        trace->count = trace->right = 0;
 }
 
-static struct trace *add_trace(const char *condstr,
-                              const char *file, unsigned int line, bool expect)
+static struct trace *add_trace(const struct trace *t)
 {
        struct trace *trace = malloc(sizeof(*trace));
 {
        struct trace *trace = malloc(sizeof(*trace));
-       init_trace(trace, condstr, file, line, expect);
-       htable_add(htable, hash_trace(trace), trace);
+       *trace = *t;
+       thash_add(&htable, trace);
        return trace;
 }
 
        return trace;
 }
 
@@ -63,13 +60,10 @@ long _likely_trace(bool cond, bool expect,
 {
        struct trace *p, trace;
 
 {
        struct trace *p, trace;
 
-       if (!htable)
-               htable = htable_new(rehash, NULL);
-
        init_trace(&trace, condstr, file, line, expect);
        init_trace(&trace, condstr, file, line, expect);
-       p = htable_get(htable, hash_trace(&trace), hash_cmp, &trace);
+       p = thash_get(&htable, &trace);
        if (!p)
        if (!p)
-               p = add_trace(condstr, file, line, expect);
+               p = add_trace(&trace);
 
        p->count++;
        if (cond == expect)
 
        p->count++;
        if (cond == expect)
@@ -78,65 +72,65 @@ long _likely_trace(bool cond, bool expect,
        return cond;
 }
 
        return cond;
 }
 
-struct get_stats_info {
-       struct trace *worst;
-       unsigned int min_hits;
-       double worst_ratio;
-};
-
 static double right_ratio(const struct trace *t)
 {
        return (double)t->right / t->count;
 }
 
 static double right_ratio(const struct trace *t)
 {
        return (double)t->right / t->count;
 }
 
-static void get_stats(struct trace *trace, struct get_stats_info *info)
+char *likely_stats(unsigned int min_hits, unsigned int percent)
 {
 {
-       if (trace->count < info->min_hits)
-               return;
-
-       if (right_ratio(trace) < info->worst_ratio) {
-               info->worst = trace;
-               info->worst_ratio = right_ratio(trace);
-       }
-}
-
-const char *likely_stats(unsigned int min_hits, unsigned int percent)
-{
-       struct get_stats_info info;
-       struct htable_iter i;
+       struct trace *worst;
+       double worst_ratio;
+       struct thash_iter i;
        char *ret;
        char *ret;
-       struct trace *trace;
-
-       if (!htable)
-               return NULL;
+       struct trace *t;
 
 
-       info.min_hits = min_hits;
-       info.worst = NULL;
-       info.worst_ratio = 2;
+       worst = NULL;
+       worst_ratio = 2;
 
        /* This is O(n), but it's not likely called that often. */
 
        /* This is O(n), but it's not likely called that often. */
-       for (trace = htable_first(htable, &i);
-            trace;
-            trace = htable_next(htable,&i)) {
-               get_stats(trace, &info);
+       for (t = thash_first(&htable, &i); t; t = thash_next(&htable, &i)) {
+               if (t->count >= min_hits) {
+                       if (right_ratio(t) < worst_ratio) {
+                               worst = t;
+                               worst_ratio = right_ratio(t);
+                       }
+               }
        }
 
        }
 
-       if (info.worst_ratio * 100 > percent)
+       if (worst_ratio * 100 > percent)
                return NULL;
 
                return NULL;
 
-       ret = malloc(strlen(info.worst->condstr) +
-                    strlen(info.worst->file) +
+       ret = malloc(strlen(worst->condstr) +
+                    strlen(worst->file) +
                     sizeof(long int) * 8 +
                     sizeof("%s:%u:%slikely(%s) correct %u%% (%lu/%lu)"));
        sprintf(ret, "%s:%u:%slikely(%s) correct %u%% (%lu/%lu)",
                     sizeof(long int) * 8 +
                     sizeof("%s:%u:%slikely(%s) correct %u%% (%lu/%lu)"));
        sprintf(ret, "%s:%u:%slikely(%s) correct %u%% (%lu/%lu)",
-               info.worst->file, info.worst->line,
-               info.worst->expect ? "" : "un", info.worst->condstr,
-               (unsigned)(info.worst_ratio * 100),
-               info.worst->right, info.worst->count);
+               worst->file, worst->line,
+               worst->expect ? "" : "un", worst->condstr,
+               (unsigned)(worst_ratio * 100),
+               worst->right, worst->count);
 
 
-       htable_del(htable, hash_trace(info.worst), info.worst);
-       free(info.worst);
+       thash_del(&htable, worst);
+       free(worst);
 
        return ret;
 }
 
        return ret;
 }
+
+void likely_stats_reset(void)
+{
+       struct thash_iter i;
+       struct trace *t;
+
+       /* This is a bit better than O(n^2), but we have to loop since
+        * first/next during delete is unreliable. */
+       while ((t = thash_first(&htable, &i)) != NULL) {
+               for (; t; t = thash_next(&htable, &i)) {
+                       thash_del(&htable, t);
+                       free(t);
+               }
+       }
+
+       thash_clear(&htable);
+}
 #endif /*CCAN_LIKELY_DEBUG*/
 #endif /*CCAN_LIKELY_DEBUG*/
index 5e4fc831c960dbe09d480fbc20182c596e3703f6..410772dbde78a37ec99c64261758961ae2f2821b 100644 (file)
@@ -74,7 +74,7 @@ long _likely_trace(bool cond, bool expect,
  * @percent: maximum percentage correct
  *
  * When CCAN_LIKELY_DEBUG is defined, likely() and unlikely() trace their
  * @percent: maximum percentage correct
  *
  * When CCAN_LIKELY_DEBUG is defined, likely() and unlikely() trace their
- * results: this causes a significant slowdown, but allows analysis of 
+ * results: this causes a significant slowdown, but allows analysis of
  * whether the branches are labelled correctly.
  *
  * This function returns a malloc'ed description of the least-correct
  * whether the branches are labelled correctly.
  *
  * This function returns a malloc'ed description of the least-correct
@@ -101,6 +101,13 @@ long _likely_trace(bool cond, bool expect,
  *     #endif
  *     }
  */
  *     #endif
  *     }
  */
-const char *likely_stats(unsigned int min_hits, unsigned int percent);
+char *likely_stats(unsigned int min_hits, unsigned int percent);
+
+/**
+ * likely_stats_reset - free up memory of likely()/unlikely() branches.
+ *
+ * This can also plug memory leaks.
+ */
+void likely_stats_reset(void);
 #endif /* CCAN_LIKELY_DEBUG */
 #endif /* CCAN_LIKELY_H */
 #endif /* CCAN_LIKELY_DEBUG */
 #endif /* CCAN_LIKELY_H */
index df78619271fc705eb9f0ded4c2868b84e48419dd..afb21e2be2fd1fd966df24d6e0cf80228cafc38b 100644 (file)
@@ -28,9 +28,9 @@ static bool likely_one_unlikely_two(unsigned int val1, unsigned int val2)
 
 int main(int argc, char *argv[])
 {
 
 int main(int argc, char *argv[])
 {
-       const char *bad;
+       char *bad;
 
 
-       plan_tests(13);
+       plan_tests(14);
 
        /* Correct guesses. */
        one_seems_likely(1);
 
        /* Correct guesses. */
        one_seems_likely(1);
@@ -46,6 +46,7 @@ int main(int argc, char *argv[])
        bad = likely_stats(3, 90);
        ok(strends(bad, "run-debug.c:9:likely(val == 1) correct 33% (1/3)"),
           "likely_stats returned %s", bad);
        bad = likely_stats(3, 90);
        ok(strends(bad, "run-debug.c:9:likely(val == 1) correct 33% (1/3)"),
           "likely_stats returned %s", bad);
+       free(bad);
 
        /* Nothing else above 90% */
        ok1(!likely_stats(0, 90));
 
        /* Nothing else above 90% */
        ok1(!likely_stats(0, 90));
@@ -54,6 +55,7 @@ int main(int argc, char *argv[])
        bad = likely_stats(0, 100);
        ok(strends(bad, "run-debug.c:16:unlikely(val == 1) correct 100% (1/1)"),
           "likely_stats returned %s", bad);
        bad = likely_stats(0, 100);
        ok(strends(bad, "run-debug.c:16:unlikely(val == 1) correct 100% (1/1)"),
           "likely_stats returned %s", bad);
+       free(bad);
 
        /* Nothing left (table is actually cleared) */
        ok1(!likely_stats(0, 100));
 
        /* Nothing left (table is actually cleared) */
        ok1(!likely_stats(0, 100));
@@ -66,6 +68,7 @@ int main(int argc, char *argv[])
        bad = likely_stats(0, 90);
        ok(strends(bad, "run-debug.c:16:unlikely(val == 1) correct 66% (2/3)"),
           "likely_stats returned %s", bad);
        bad = likely_stats(0, 90);
        ok(strends(bad, "run-debug.c:16:unlikely(val == 1) correct 66% (2/3)"),
           "likely_stats returned %s", bad);
+       free(bad);
        ok1(!likely_stats(0, 100));
 
        likely_one_unlikely_two(1, 1);
        ok1(!likely_stats(0, 100));
 
        likely_one_unlikely_two(1, 1);
@@ -77,9 +80,19 @@ int main(int argc, char *argv[])
        bad = likely_stats(0, 90);
        ok(strends(bad, "run-debug.c:24:unlikely(val2 == 2) correct 75% (3/4)"),
           "likely_stats returned %s", bad);
        bad = likely_stats(0, 90);
        ok(strends(bad, "run-debug.c:24:unlikely(val2 == 2) correct 75% (3/4)"),
           "likely_stats returned %s", bad);
+       free(bad);
        bad = likely_stats(0, 100);
        ok(strends(bad, "run-debug.c:24:likely(val1 == 1) correct 100% (4/4)"),
           "likely_stats returned %s", bad);
        bad = likely_stats(0, 100);
        ok(strends(bad, "run-debug.c:24:likely(val1 == 1) correct 100% (4/4)"),
           "likely_stats returned %s", bad);
+       free(bad);
+
+       ok1(!likely_stats(0, 100));
+
+       /* Check that reset works! */
+       one_seems_unlikely(0);
+       one_seems_unlikely(2);
+       one_seems_unlikely(1);
+       likely_stats_reset();
 
        ok1(!likely_stats(0, 100));
 
 
        ok1(!likely_stats(0, 100));