Module Name: src
Committed By: drochner
Date: Thu Apr 2 12:49:59 UTC 2009
Modified Files:
src/regress/lib/libc/gen: Makefile
Added Files:
src/regress/lib/libc/gen/rbtree: Makefile rbstress.c
Log Message:
add a test which stresses the rbtree code with random numbers
To generate a diff of this commit:
cvs rdiff -u -r1.5 -r1.6 src/regress/lib/libc/gen/Makefile
cvs rdiff -u -r0 -r1.1 src/regress/lib/libc/gen/rbtree/Makefile \
src/regress/lib/libc/gen/rbtree/rbstress.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/regress/lib/libc/gen/Makefile
diff -u src/regress/lib/libc/gen/Makefile:1.5 src/regress/lib/libc/gen/Makefile:1.6
--- src/regress/lib/libc/gen/Makefile:1.5 Wed May 17 21:12:23 2006
+++ src/regress/lib/libc/gen/Makefile Thu Apr 2 12:49:59 2009
@@ -1,5 +1,6 @@
-# $NetBSD: Makefile,v 1.5 2006/05/17 21:12:23 christos Exp $
+# $NetBSD: Makefile,v 1.6 2009/04/02 12:49:59 drochner Exp $
SUBDIR+= humanize_number vis tfmtcheck seekdir-twice telldir-memuse
+SUBDIR+= rbtree
.include <bsd.subdir.mk>
Added files:
Index: src/regress/lib/libc/gen/rbtree/Makefile
diff -u /dev/null src/regress/lib/libc/gen/rbtree/Makefile:1.1
--- /dev/null Thu Apr 2 12:49:59 2009
+++ src/regress/lib/libc/gen/rbtree/Makefile Thu Apr 2 12:49:59 2009
@@ -0,0 +1,13 @@
+# $NetBSD: Makefile,v 1.1 2009/04/02 12:49:59 drochner Exp $
+
+WARNS=4
+
+PROG= rbstress
+LDADD= -lpthread
+
+NOMAN=
+
+regress:
+ ./rbstress
+
+.include <bsd.prog.mk>
Index: src/regress/lib/libc/gen/rbtree/rbstress.c
diff -u /dev/null src/regress/lib/libc/gen/rbtree/rbstress.c:1.1
--- /dev/null Thu Apr 2 12:49:59 2009
+++ src/regress/lib/libc/gen/rbtree/rbstress.c Thu Apr 2 12:49:59 2009
@@ -0,0 +1,83 @@
+/* $NetBSD: rbstress.c,v 1.1 2009/04/02 12:49:59 drochner Exp $ */
+
+#include <sys/cdefs.h>
+#include <sys/tree.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+struct mist {
+ RB_ENTRY(mist) rbentry;
+ int key;
+};
+RB_HEAD(head, mist) tt;
+
+static int
+mistcmp(struct mist *a, struct mist *b)
+{
+#if 0
+ return (b->key - a->key); /* wrong, can overflow */
+#else
+ if (b->key > a->key)
+ return 1;
+ else if (b->key < a->key)
+ return (-1);
+ else
+ return 0;
+#endif
+}
+
+RB_PROTOTYPE(head, mist, rbentry, mistcmp)
+RB_GENERATE(head, mist, rbentry, mistcmp)
+
+static struct mist *
+addmist(int key)
+{
+ struct mist *m;
+
+ m = malloc(sizeof(struct mist));
+ m->key = key;
+ RB_INSERT(head, &tt, m);
+ return m;
+}
+
+static int
+findmist(struct mist *m)
+{
+
+ return (!!RB_FIND(head, &tt, m));
+}
+
+#define N 1000
+static int
+test(void)
+{
+ struct mist *m[N];
+ int fail, i, j;
+
+ RB_INIT(&tt);
+ fail = 0;
+ for (i = 0; i < N; i++) {
+ m[i] = addmist(random() << 1); /* use all 32 bits */
+ for (j = 0; j <= i; j++)
+ if (!findmist(m[j]))
+ fail++;
+ }
+ return fail;
+}
+
+int
+main(int argc, char **argv)
+{
+ int i, fail, f;
+
+ srandom(4711);
+ fail = 0;
+ for (i = 0; i < 10; i++) {
+ f = test();
+ if (f) {
+ printf("loop %d: %d errors\n", i, f);
+ fail += f;
+ }
+ }
+ exit(!!fail);
+}
