From 3c01c39227b53e54143e3db8c9edb67ba92a5dd4 Mon Sep 17 00:00:00 2001
From: wessels <>
Date: Fri, 21 Feb 1997 04:04:07 +0000
Subject: [PATCH] Adding splay and binary tree code

---
 include/splay.h |  15 +++++
 lib/Makefile.in |   4 +-
 lib/splay.c     | 157 ++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 175 insertions(+), 1 deletion(-)
 create mode 100644 include/splay.h
 create mode 100644 lib/splay.c

diff --git a/include/splay.h b/include/splay.h
new file mode 100644
index 0000000000..00ad46035b
--- /dev/null
+++ b/include/splay.h
@@ -0,0 +1,15 @@
+
+typedef struct _splay_node {
+	void *data;
+	struct _splay_node *left;
+	struct _splay_node *right;
+} splayNode;
+
+typedef int (*SPCMP) _PARAMS((const void *, splayNode *));
+
+extern int splayLastResult;
+
+splayNode *splay_insert _PARAMS((void *, splayNode *, SPCMP));
+splayNode *splay_splay _PARAMS((const void *, splayNode *, SPCMP));
+void splay_destroy _PARAMS((splayNode *, void (*) _PARAMS((void *))));
+
diff --git a/lib/Makefile.in b/lib/Makefile.in
index 820ce4aa70..d16f070c63 100644
--- a/lib/Makefile.in
+++ b/lib/Makefile.in
@@ -3,7 +3,7 @@
 #
 #  Darren Hardy, hardy@cs.colorado.edu, April 1994
 #
-#  $Id: Makefile.in,v 1.20 1996/11/25 02:38:20 wessels Exp $
+#  $Id: Makefile.in,v 1.21 1997/02/20 21:04:07 wessels Exp $
 #
 prefix		= @prefix@
 srcdir		= @srcdir@
@@ -29,6 +29,8 @@ UTILOBJS	= rfc1123.o \
 		  getfullhostname.o \
 		  base64.o \
 		  uudecode.o \
+		  tree.o \
+		  splay.o \
 		  $(LIBOBJS)
 REGEXOBJS	= GNUregex.o
 LIBS		= libmiscutil.a @LIBREGEX@
diff --git a/lib/splay.c b/lib/splay.c
new file mode 100644
index 0000000000..167e065526
--- /dev/null
+++ b/lib/splay.c
@@ -0,0 +1,157 @@
+
+#include "config.h"
+
+#if HAVE_STDIO_H
+#include <stdio.h>
+#endif
+#if HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
+#if HAVE_UNISTD_H
+#include <unistd.h>
+#endif
+
+#include "ansiproto.h"
+#include "splay.h"
+#include "util.h"
+
+int splayLastResult = 0;
+
+splayNode *
+splay_insert (void *data, splayNode *top, SPCMP compare)
+{
+    splayNode *new = xcalloc(sizeof(splayNode), 1);
+    new->data = data;
+    if (top == NULL) {
+        new->left = new->right = NULL;
+        return new;
+    }
+    top = splay_splay(data, top, compare);
+    if (splayLastResult < 0) {
+        new->left = top->left;
+        new->right = top;
+        top->left = NULL;
+        return new;
+    } else if (splayLastResult > 0) {
+        new->right = top->right;
+        new->left = top;
+        top->right = NULL;
+        return new;
+    } else {
+	/* duplicate entry */
+        free(new);
+        return top;
+    }
+}
+
+splayNode *
+splay_splay (const void *data, splayNode *top, SPCMP compare)
+{
+    splayNode N;
+    splayNode *l;
+    splayNode *r;
+    splayNode *y;
+    if (top == NULL)
+        return top;
+    N.left = N.right = NULL;
+    l = r = &N;
+
+    for (;;) {
+        splayLastResult = compare(data, top);
+        if (splayLastResult < 0) {
+            if (top->left == NULL)
+                break;
+            if ((splayLastResult = compare(data, top->left)) < 0) {
+                y = top->left;    /* rotate right */
+                top->left = y->right;
+                y->right = top;
+                top = y;
+                if (top->left == NULL)
+                    break;
+            }
+            r->left = top;        /* link right */
+            r = top;
+            top = top->left;
+        } else if (splayLastResult > 0) {
+            if (top->right == NULL)
+                break;
+            if ((splayLastResult = compare(data, top->right)) > 0) {
+                y = top->right;   /* rotate left */
+                top->right = y->left;
+                y->left = top;
+                top = y;
+                if (top->right == NULL)
+                    break;
+            }
+            l->right = top;       /* link left */
+            l = top;
+            top = top->right;
+        } else {
+            break;
+        }
+    }
+    l->right = top->left;         /* assemble */
+    r->left = top->right;
+    top->left = N.right;
+    top->right = N.left;
+    return top;
+}
+
+void
+splay_destroy(splayNode *top, void (*free_func) _PARAMS((void *)))
+{
+	if (top->left)
+		splay_destroy(top->left, free_func);
+	if (top->right)
+		splay_destroy(top->right, free_func);
+	free_func(top->data);
+	xfree(top);
+}
+
+
+#ifdef DRIVER
+
+void
+splay_print(splayNode *top, void (*printfunc)())
+{
+	if (top == NULL)
+		return;
+	splay_print(top->left, printfunc);
+	printfunc(top->data);
+	splay_print(top->right, printfunc);
+}
+
+typedef struct {
+	int i;
+} intnode;
+
+int
+compareint (void *a, splayNode *n)
+{
+	intnode *A = a;
+	intnode *B = n->data;
+	return A->i - B->i;
+}
+
+void
+printint (void *a)
+{
+	intnode *A = a;
+	printf ("%d\n", A->i);
+}
+
+main(int argc, char *argv[])
+{
+	int i;
+	intnode *I;
+	splayNode *top = NULL;
+	srandom(time(NULL));
+	for (i=0; i< 100; i++) {
+		I = xcalloc (sizeof(intnode), 1);
+		I->i = random();
+		top = splay_insert(I, top, compareint);
+	}
+	splay_print (top, printint);
+	return 0;
+}
+#endif
-- 
2.47.3