splay regression test

4 files changed, 93 insertions, 2 deletions

diff --git a/regress/sys/Makefile b/regress/sys/Makefile
index 586e1aefcf1..621f8f83288 100644
--- a/regress/sys/Makefile
+++ b/regress/sys/Makefile
@@ -1,7 +1,7 @@
-#	$OpenBSD: Makefile,v 1.9 2002/03/25 10:56:58 fgsch Exp $
+#	$OpenBSD: Makefile,v 1.10 2002/06/11 21:55:57 provos Exp $
 #	$NetBSD: Makefile,v 1.4 1995/04/20 22:41:08 cgd Exp $
 
-SUBDIR+= kern fdescfs uvm crypto
+SUBDIR+= kern fdescfs uvm crypto sys
 .if exists(arch/${MACHINE})
 SUBDIR+= arch/${MACHINE}
 .endif
diff --git a/regress/sys/sys/Makefile b/regress/sys/sys/Makefile
new file mode 100644
index 00000000000..41c50d85ce7
--- /dev/null
+++ b/regress/sys/sys/Makefile
@@ -0,0 +1,7 @@
+#	$OpenBSD: Makefile,v 1.1 2002/06/11 21:55:57 provos Exp $
+
+SUBDIR= tree
+
+install:
+
+.include <bsd.subdir.mk>
diff --git a/regress/sys/sys/tree/Makefile b/regress/sys/sys/tree/Makefile
new file mode 100644
index 00000000000..549809d88ca
--- /dev/null
+++ b/regress/sys/sys/tree/Makefile
@@ -0,0 +1,5 @@
+#	$OpenBSD: Makefile,v 1.1 2002/06/11 21:55:57 provos Exp $
+
+PROG=	splay-test
+
+.include <bsd.regress.mk>
diff --git a/regress/sys/sys/tree/splay-test.c b/regress/sys/sys/tree/splay-test.c
new file mode 100644
index 00000000000..cd8c1d6e311
--- /dev/null
+++ b/regress/sys/sys/tree/splay-test.c
@@ -0,0 +1,79 @@
+#include <sys/types.h>
+#include <sys/tree.h>
+#include <unistd.h>
+#include <stdio.h>
+#include <err.h>
+#include <stdlib.h>
+
+struct node {
+	SPLAY_ENTRY(node) node;
+	int key;
+};
+
+SPLAY_HEAD(tree, node) root;
+
+int
+compare(struct node *a, struct node *b)
+{
+	if (a->key < b->key) return (-1);
+	else if (a->key > b->key) return (1);
+	return (0);
+}
+
+SPLAY_PROTOTYPE(tree, node, node, compare);
+
+SPLAY_GENERATE(tree, node, node, compare);
+
+#define ITER 150
+#define MIN 5
+#define MAX 5000
+
+int
+main(int argc, char **argv)
+{
+	struct node *tmp, *ins;
+	int i, max, min;
+
+	SPLAY_INIT(&root);
+
+	for (i = 0; i < ITER; i++) {
+		tmp = malloc(sizeof(struct node));
+		if (tmp == NULL) err(1, "malloc");
+		do {
+			tmp->key = arc4random() % (MAX-MIN);
+			tmp->key += MIN;
+		} while (SPLAY_FIND(tree, &root, tmp) != NULL);
+		if (i == 0)
+			max = min = tmp->key;
+		else {
+			if (tmp->key > max)
+				max = tmp->key;
+			if (tmp->key < min)
+				min = tmp->key;
+		}
+		if (SPLAY_INSERT(tree, &root, tmp) != NULL)
+			errx(1, "SPLAY_INSERT failed");
+	}
+
+	ins = SPLAY_MIN(tree, &root);
+	if (ins->key != min)
+		errx(1, "min does not match");
+	tmp = ins;
+	ins = SPLAY_MAX(tree, &root);
+	if (ins->key != max)
+		errx(1, "max does not match");
+
+	if (SPLAY_REMOVE(tree, &root, tmp) != tmp)
+		errx(1, "SPLAY_REMOVE failed");
+
+	for (i = 0; i < ITER - 1; i++) {
+		tmp = SPLAY_ROOT(&root);
+		if (tmp == NULL)
+			errx(1, "SPLAY_ROOT error");
+		if (SPLAY_REMOVE(tree, &root, tmp) != tmp)
+			errx(1, "SPLAY_REMOVE error");
+		free(tmp);
+	}
+
+	exit(0);
+}