Module Name: src
Committed By: joerg
Date: Wed Mar 3 01:55:04 UTC 2010
Modified Files:
src/usr.bin/nbperf: graph2.c graph3.c nbperf.1 nbperf.c nbperf.h
Log Message:
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.
To generate a diff of this commit:
cvs rdiff -u -r1.2 -r1.3 src/usr.bin/nbperf/graph2.c \
src/usr.bin/nbperf/graph3.c src/usr.bin/nbperf/nbperf.c \
src/usr.bin/nbperf/nbperf.h
cvs rdiff -u -r1.1 -r1.2 src/usr.bin/nbperf/nbperf.1
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/usr.bin/nbperf/graph2.c
diff -u src/usr.bin/nbperf/graph2.c:1.2 src/usr.bin/nbperf/graph2.c:1.3
--- src/usr.bin/nbperf/graph2.c:1.2 Sat Aug 22 17:52:17 2009
+++ src/usr.bin/nbperf/graph2.c Wed Mar 3 01:55:04 2010
@@ -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;
}
Index: src/usr.bin/nbperf/graph3.c
diff -u src/usr.bin/nbperf/graph3.c:1.2 src/usr.bin/nbperf/graph3.c:1.3
--- src/usr.bin/nbperf/graph3.c:1.2 Sat Aug 22 17:52:17 2009
+++ src/usr.bin/nbperf/graph3.c Wed Mar 3 01:55:04 2010
@@ -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;
}
Index: src/usr.bin/nbperf/nbperf.c
diff -u src/usr.bin/nbperf/nbperf.c:1.2 src/usr.bin/nbperf/nbperf.c:1.3
--- src/usr.bin/nbperf/nbperf.c:1.2 Sat Aug 22 17:52:17 2009
+++ src/usr.bin/nbperf/nbperf.c Wed Mar 3 01:55:04 2010
@@ -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)
Index: src/usr.bin/nbperf/nbperf.h
diff -u src/usr.bin/nbperf/nbperf.h:1.2 src/usr.bin/nbperf/nbperf.h:1.3
--- src/usr.bin/nbperf/nbperf.h:1.2 Sat Aug 22 17:52:17 2009
+++ src/usr.bin/nbperf/nbperf.h Wed Mar 3 01:55:04 2010
@@ -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;
Index: src/usr.bin/nbperf/nbperf.1
diff -u src/usr.bin/nbperf/nbperf.1:1.1 src/usr.bin/nbperf/nbperf.1:1.2
--- src/usr.bin/nbperf/nbperf.1:1.1 Sat Aug 15 16:21:05 2009
+++ src/usr.bin/nbperf/nbperf.1 Wed Mar 3 01:55:04 2010
@@ -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
