[src/trunk]: src/usr.bin/nbperf Add a check for duplicate keys. The check is ...

[joerg <joerg%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/d6abc9db2fd0
branches:  trunk
changeset: 752668:d6abc9db2fd0
user:      joerg <joerg%NetBSD.org@localhost>
date:      Wed Mar 03 01:55:04 2010 +0000

description:
Add a check for duplicate keys. The check is run once and quadratic in
the hash collision chain length, which is expected to be fairly low.

diffstat:

 usr.bin/nbperf/graph2.c |  39 +++++++++++++++++++++++++++++++++++++--
 usr.bin/nbperf/graph3.c |  40 ++++++++++++++++++++++++++++++++++++++--
 usr.bin/nbperf/nbperf.1 |   9 +++++++--
 usr.bin/nbperf/nbperf.c |   8 ++++++--
 usr.bin/nbperf/nbperf.h |   3 ++-
 5 files changed, 90 insertions(+), 9 deletions(-)

diffs (228 lines):

diff -r 2846cdab5447 -r d6abc9db2fd0 usr.bin/nbperf/graph2.c
--- a/usr.bin/nbperf/graph2.c   Wed Mar 03 01:26:01 2010 +0000
+++ b/usr.bin/nbperf/graph2.c   Wed Mar 03 01:55:04 2010 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: graph2.c,v 1.2 2009/08/22 17:52:17 joerg Exp $ */
+/*     $NetBSD: graph2.c,v 1.3 2010/03/03 01:55:04 joerg Exp $ */
 /*-
  * Copyright (c) 2009 The NetBSD Foundation, Inc.
  * All rights reserved.
@@ -32,12 +32,13 @@
  */
 
 #include <sys/cdefs.h>
-__RCSID("$NetBSD: graph2.c,v 1.2 2009/08/22 17:52:17 joerg Exp $");
+__RCSID("$NetBSD: graph2.c,v 1.3 2010/03/03 01:55:04 joerg Exp $");
 
 #include <err.h>
 #include <inttypes.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 
 #include "nbperf.h"
 #include "graph2.h"
@@ -71,6 +72,35 @@
        graph->output_order = NULL;
 }
 
+static int
+graph2_check_duplicates(struct nbperf *nbperf, struct graph2 *graph)
+{
+       struct vertex2 *v;
+       struct edge2 *e, *e2;
+       uint32_t i, j;
+
+       for (i = 0; i < graph->e; ++i) {
+               e = &graph->edges[i];
+               v = &graph->verts[e->left];
+               j = v->l_edge;
+               e2 = &graph->edges[j];
+               for (;;) {
+                       if (i < j && e->right == e2->right &&
+                           nbperf->keylens[i] == nbperf->keylens[j] &&
+                           memcmp(nbperf->keys[i], nbperf->keys[j],
+                           nbperf->keylens[i]) == 0) {
+                               nbperf->has_duplicates = 1;
+                               return -1;
+                       }
+                       if (e2->l_next == unused)
+                               break;
+                       j = e2->l_next;
+                       e2 = &graph->edges[j];
+               }               
+       }
+       return 0;
+}
+
 int
 graph2_hash(struct nbperf *nbperf, struct graph2 *graph)
 {
@@ -108,6 +138,11 @@
                v->r_edge = i;
        }
 
+       if (nbperf->first_round) {
+               nbperf->first_round = 0;
+               return graph2_check_duplicates(nbperf, graph);
+       }
+
        return 0;
 }
 
diff -r 2846cdab5447 -r d6abc9db2fd0 usr.bin/nbperf/graph3.c
--- a/usr.bin/nbperf/graph3.c   Wed Mar 03 01:26:01 2010 +0000
+++ b/usr.bin/nbperf/graph3.c   Wed Mar 03 01:55:04 2010 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: graph3.c,v 1.2 2009/08/22 17:52:17 joerg Exp $ */
+/*     $NetBSD: graph3.c,v 1.3 2010/03/03 01:55:04 joerg Exp $ */
 /*-
  * Copyright (c) 2009 The NetBSD Foundation, Inc.
  * All rights reserved.
@@ -32,12 +32,13 @@
  */
 
 #include <sys/cdefs.h>
-__RCSID("$NetBSD: graph3.c,v 1.2 2009/08/22 17:52:17 joerg Exp $");
+__RCSID("$NetBSD: graph3.c,v 1.3 2010/03/03 01:55:04 joerg Exp $");
 
 #include <err.h>
 #include <inttypes.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 
 #include "nbperf.h"
 #include "graph3.h"
@@ -71,6 +72,36 @@
        graph->output_order = NULL;
 }
 
+static int
+graph3_check_duplicates(struct nbperf *nbperf, struct graph3 *graph)
+{
+       struct vertex3 *v;
+       struct edge3 *e, *e2;
+       uint32_t i, j;
+
+       for (i = 0; i < graph->e; ++i) {
+               e = &graph->edges[i];
+               v = &graph->verts[e->left];
+               j = v->l_edge;
+               e2 = &graph->edges[j];
+               for (;;) {
+                       if (i < j && e->middle == e2->middle &&
+                           e->right == e2->right &&
+                           nbperf->keylens[i] == nbperf->keylens[j] &&
+                           memcmp(nbperf->keys[i], nbperf->keys[j],
+                           nbperf->keylens[i]) == 0) {
+                               nbperf->has_duplicates = 1;
+                               return -1;
+                       }
+                       if (e2->l_next == unused)
+                               break;
+                       j = e2->l_next;
+                       e2 = &graph->edges[j];
+               }               
+       }
+       return 0;
+}
+
 int
 graph3_hash(struct nbperf *nbperf, struct graph3 *graph)
 {
@@ -121,6 +152,11 @@
                v->r_edge = i;
        }
 
+       if (nbperf->first_round) {
+               nbperf->first_round = 0;
+               return graph3_check_duplicates(nbperf, graph);
+       }
+
        return 0;
 }
 
diff -r 2846cdab5447 -r d6abc9db2fd0 usr.bin/nbperf/nbperf.1
--- a/usr.bin/nbperf/nbperf.1   Wed Mar 03 01:26:01 2010 +0000
+++ b/usr.bin/nbperf/nbperf.1   Wed Mar 03 01:55:04 2010 +0000
@@ -1,4 +1,4 @@
-.\"    $NetBSD: nbperf.1,v 1.1 2009/08/15 16:21:05 joerg Exp $
+.\"    $NetBSD: nbperf.1,v 1.2 2010/03/03 01:55:04 joerg Exp $
 .\"
 .\" Copyright (c) 2009 The NetBSD Foundation, Inc.
 .\" All rights reserved.
@@ -27,7 +27,7 @@
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 .\" POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd July 13, 2009
+.Dd March 3, 2010
 .Dt NBPERF 1
 .Os
 .Sh NAME
@@ -122,6 +122,11 @@
 flag is specified, it will be static.
 .Pp
 After each failing iteration, a dot is written to stderr.
+.Pp
+.Nm
+checks for duplicate keys on the first iteration that passed basic hash distribution
+tests.
+In that case, an error message is printed and the program terminates.
 .Sh EXIT STATUS
 .Ex -std
 .Sh SEE ALSO
diff -r 2846cdab5447 -r d6abc9db2fd0 usr.bin/nbperf/nbperf.c
--- a/usr.bin/nbperf/nbperf.c   Wed Mar 03 01:26:01 2010 +0000
+++ b/usr.bin/nbperf/nbperf.c   Wed Mar 03 01:55:04 2010 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: nbperf.c,v 1.2 2009/08/22 17:52:17 joerg Exp $ */
+/*     $NetBSD: nbperf.c,v 1.3 2010/03/03 01:55:04 joerg Exp $ */
 /*-
  * Copyright (c) 2009 The NetBSD Foundation, Inc.
  * All rights reserved.
@@ -32,7 +32,7 @@
  */
 
 #include <sys/cdefs.h>
-__RCSID("$NetBSD: nbperf.c,v 1.2 2009/08/22 17:52:17 joerg Exp $");
+__RCSID("$NetBSD: nbperf.c,v 1.3 2010/03/03 01:55:04 joerg Exp $");
 
 #include <sys/endian.h>
 #include <err.h>
@@ -101,6 +101,8 @@
            .map_output = NULL,
            .output = NULL,
            .static_hash = 0,
+           .first_round = 1,
+           .has_duplicates = 0,
        };
        FILE *input;
        size_t curlen = 0, curalloc = 0;
@@ -217,6 +219,8 @@
 
        looped = 0;
        while ((*build_hash)(&nbperf)) {
+               if (nbperf.has_duplicates)
+                       errx(1, "Duplicate keys detected");
                fputc('.', stderr);
                looped = 1;
                if (max_iterations == 0xffffffffU)
diff -r 2846cdab5447 -r d6abc9db2fd0 usr.bin/nbperf/nbperf.h
--- a/usr.bin/nbperf/nbperf.h   Wed Mar 03 01:26:01 2010 +0000
+++ b/usr.bin/nbperf/nbperf.h   Wed Mar 03 01:55:04 2010 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: nbperf.h,v 1.2 2009/08/22 17:52:17 joerg Exp $ */
+/*     $NetBSD: nbperf.h,v 1.3 2010/03/03 01:55:04 joerg Exp $ */
 /*-
  * Copyright (c) 2009 The NetBSD Foundation, Inc.
  * All rights reserved.
@@ -41,6 +41,7 @@
        size_t n;
        const void * __restrict * keys;
        const size_t *keylens;
+       int first_round, has_duplicates;
 
        double c;