Splay tree test; incomplate; leaky; should work under OS3

4 files changed, 307 insertions, 35 deletions

diff --git a/amiga/Makefile.target b/amiga/Makefile.target
index f42214021..e6ba70d24 100644
--- a/amiga/Makefile.target
+++ b/amiga/Makefile.target
@@ -76,7 +76,7 @@ S_AMIGA := gui.c tree.c history.c hotlist.c schedule.c file.c		\
 	datatypes.c dt_picture.c dt_anim.c dt_sound.c plugin_hack.c	\
 	stringview/stringview.c stringview/urlhistory.c rtg.c		\
 	agclass/amigaguide_class.c os3support.c font_bitmap.c		\
-	selectmenu.c hash/xxhash.c
+	selectmenu.c hash/xxhash.c splaytree.c splaytree.h
 S_AMIGA := $(addprefix amiga/,$(S_AMIGA))
 
 # This is the final source build list
diff --git a/amiga/font.c b/amiga/font.c
index 8848021b3..fb40f9727 100644
--- a/amiga/font.c
+++ b/amiga/font.c
@@ -75,7 +75,7 @@
 struct ami_font_node
 {
 #ifdef __amigaos4__
-	struct SkipNode skip_node;
+	struct SplayNode splay_node;
 #endif
 	struct OutlineFont *font;
 	char *bold;
@@ -151,11 +151,8 @@ const uint16 sc_table[] = {
 #endif
 		0, 0};
 
-#ifdef __amigaos4__
-struct SkipList *ami_font_list = NULL;
-#else
-struct MinList *ami_font_list = NULL;
-#endif
+struct SplayTree *ami_font_list = NULL;
+//TODO struct MinList *ami_font_lru = NULL
 struct List ami_diskfontlib_list;
 lwc_string *glypharray[0xffff + 1];
 ULONG ami_devicedpi;
@@ -376,13 +373,8 @@ static struct ami_font_node *ami_font_open(const char *font, bool critical)
 	struct ami_font_node *nodedata = NULL;
 	uint32 hash = 0;
 
-#ifdef __amigaos4__
 	hash = XXH32(font, strlen(font), 0);
-	nodedata = (struct ami_font_node *)FindSkipNode(ami_font_list, (APTR)hash);		
-#else
-	struct nsObject *node = (struct nsObject *)FindIName((struct List *)ami_font_list, font);
-	if(node) nodedata = node->objstruct;
-#endif
+	nodedata = (struct ami_font_node *)FindSplayNode(ami_font_list, (APTR)hash);		
 
 	if(nodedata) {
 		GetSysTime(&nodedata->lastused);
@@ -391,11 +383,8 @@ static struct ami_font_node *ami_font_open(const char *font, bool critical)
 
 	LOG("Font cache miss: %s (%lx)", font, hash);
 
-#ifdef __amigaos4__
-	nodedata = (struct ami_font_node *)InsertSkipNode(ami_font_list, (APTR)hash, sizeof(struct ami_font_node));
-#else
-	nodedata = AllocVecTagList(sizeof(struct ami_font_node), NULL);
-#endif
+	nodedata = (struct ami_font_node *)InsertSplayNode(ami_font_list, (APTR)hash, sizeof(struct ami_font_node));
+	/* TODO: add hash to LRU list */
 
 	if(nodedata == NULL) {
 		warn_user("NoMemory", "");
@@ -432,14 +421,6 @@ static struct ami_font_node *ami_font_open(const char *font, bool critical)
 
 	GetSysTime(&nodedata->lastused);
 
-#ifndef __amigaos4__
-	node = AddObject(ami_font_list, AMINS_FONT);
-	if(node) {
-		node->objstruct = nodedata;
-		node->dtz_Node.ln_Name = strdup(font);
-	}
-#endif
-
 	return nodedata;
 }
 
@@ -927,6 +908,8 @@ static LONG ami_font_cache_sort(struct Hook *hook, APTR key1, APTR key2)
 }
 #endif
 
+#if 0
+// TODO: Rewrite to page through the LRU list as splay trees don't let us do this */
 #ifdef __amigaos4__
 static void ami_font_cleanup(struct SkipList *skiplist)
 {
@@ -981,6 +964,7 @@ static void ami_font_cleanup(struct MinList *ami_font_list)
 	ami_schedule(300000, (void *)ami_font_cleanup, ami_font_list);
 }
 #endif
+#endif //0
 
 void ami_init_fonts(void)
 {
@@ -988,18 +972,17 @@ void ami_init_fonts(void)
 	ami_font_initscanner(false, true);
 
 	/* Initialise font caching etc lists */
-#ifdef __amigaos4__
 	ami_font_cache_hook.h_Entry = (HOOKFUNC)ami_font_cache_sort;
 	ami_font_cache_hook.h_Data = 0;
-	ami_font_list = CreateSkipList(&ami_font_cache_hook, 8);
-#else
-	ami_font_list = NewObjList();
-#endif
+	ami_font_list = CreateSplayTree(&ami_font_cache_hook);
 
 	NewList(&ami_diskfontlib_list);
 
 	/* run first cleanup in ten minutes */
+#if 0
+// TODO: Needs rewriting */
 	ami_schedule(600000, (void *)ami_font_cleanup, ami_font_list);
+#endif
 }
 
 #ifdef __amigaos4__
@@ -1024,11 +1007,10 @@ static void ami_font_del_skiplist(struct SkipList *skiplist)
 void ami_close_fonts(void)
 {
 	LOG("Cleaning up font cache");
+#if 0
+//TODO: rewrite this
 	ami_schedule(-1, (void *)ami_font_cleanup, ami_font_list);
-#ifdef __amigaos4__
-	ami_font_del_skiplist(ami_font_list);
-#else
-	FreeObjList(ami_font_list);
+ 	ami_font_del_splaytree(ami_font_list);
 #endif
 	ami_font_list = NULL;
 	ami_font_finiscanner();
diff --git a/amiga/splaytree.c b/amiga/splaytree.c
new file mode 100644
index 000000000..5f610f732
--- /dev/null
+++ b/amiga/splaytree.c
@@ -0,0 +1,250 @@
+/**
+ * Copyright (c) 2015 Fredrik Wikstrom <fredrik@a500.org>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#ifndef __amigaos4__
+#include "amiga/splaytree.h"
+#include <proto/exec.h>
+#include <proto/utility.h>
+
+struct SplayNode {
+	struct SplayNode *parent;
+	struct SplayNode *left;
+	struct SplayNode *right;
+	APTR key;
+	APTR data;
+};
+
+struct SplayTree {
+	APTR mempool;
+	struct Hook *hook;
+	struct SplayNode *root;
+};
+
+struct SplayTree *CreateSplayTree(struct Hook *hook) {
+	struct SplayTree *tree;
+
+	tree = AllocMem(sizeof(*tree), MEMF_PUBLIC);
+	if (tree == NULL)
+		return NULL;
+
+	tree->mempool = CreatePool(MEMF_PUBLIC, 4096, 1024);
+	if (tree->mempool == NULL) {
+		FreeMem(tree, sizeof(*tree));
+	}
+
+	tree->hook = hook;
+	tree->root = NULL;
+
+	return tree;
+}
+
+void DeleteSplayTree(struct SplayTree *tree) {
+	if (tree != NULL) {
+		DeletePool(tree->mempool);
+		FreeMem(tree, sizeof(*tree));
+	}
+}
+
+static void left_rotate(struct SplayTree *tree, struct SplayNode *sn) {
+	struct SplayNode *s2 = sn->right;
+
+	if (s2 != NULL) {
+		sn->right = s2->left;
+		if (s2->left != NULL)
+			s2->left->parent = sn;
+		s2->parent = sn->parent;
+	}
+
+	if (sn->parent == NULL)
+		tree->root = s2;
+	else if (sn == sn->parent->left)
+		sn->parent->left = s2;
+	else
+		sn->parent->right = s2;
+
+	if (s2 != NULL)
+		s2->left = sn;
+
+	sn->parent = s2;
+}
+
+static void right_rotate(struct SplayTree *tree, struct SplayNode *sn) {
+	struct SplayNode *s2 = sn->left;
+
+	if (s2 != NULL) {
+		sn->left = s2->right;
+		if (s2->right != NULL)
+			s2->right->parent = sn;
+		s2->parent = sn->parent;
+	}
+
+	if (sn->parent == NULL)
+		tree->root = s2;
+	else if (sn == sn->parent->left)
+		sn->parent->left = s2;
+	else
+		sn->parent->right = s2;
+
+	if (s2 != NULL)
+		s2->right = sn;
+
+	sn->parent = s2;
+}
+
+static void splay(struct SplayTree *tree, struct SplayNode *sn) {
+	while (sn->parent != NULL) {
+		if (sn->parent->parent == NULL) {
+			if (sn == sn->parent->left)
+				right_rotate(tree, sn->parent);
+			else
+				left_rotate(tree, sn->parent);
+		} else if (sn->parent == sn->parent->parent->left) {
+			if (sn == sn->parent->left)
+				right_rotate(tree, sn->parent->parent);
+			else
+				left_rotate(tree, sn->parent);
+			right_rotate(tree, sn->parent);
+		} else {
+			if (sn == sn->parent->left)
+				right_rotate(tree, sn->parent);
+			else
+				left_rotate(tree, sn->parent->parent);
+			left_rotate(tree, sn->parent);
+		}
+	}
+}
+
+static struct SplayNode *find(struct SplayTree *tree, APTR key) {
+	struct SplayNode *sn = tree->root;
+	int res;
+
+	while (sn != NULL) {
+		res = CallHookPkt(tree->hook, key, sn->key);
+		if (res > 0)
+			sn = sn->right;
+		else if (res < 0)
+			sn = sn->left;
+		else
+			break;
+	}
+
+	return sn;
+}
+
+static void replace(struct SplayTree *tree, struct SplayNode *sn, struct SplayNode *s2) {
+	if (sn->parent == NULL)
+		tree->root = s2;
+	else if (sn == sn->parent->left)
+		sn->parent->left = s2;
+	else
+		sn->parent->right = s2;
+
+	if (s2 != NULL)
+		s2->parent = sn->parent;
+}
+
+BOOL InsertSplayNode(struct SplayTree *tree, APTR key, APTR data) {
+	struct SplayNode *sn = tree->root;
+	struct SplayNode *parent = NULL;
+	int res;
+
+	if (data == NULL)
+		return FALSE;
+
+	while (sn != NULL) {
+		parent = sn;
+		res = CallHookPkt(tree->hook, key, sn->key);
+		if (res > 0)
+			sn = sn->right;
+		else
+			sn = sn->left;
+	}
+
+	sn = AllocPooled(tree->mempool, sizeof(*sn));
+	if (sn == NULL)
+		return FALSE;
+
+	sn->parent = parent;
+	sn->left = NULL;
+	sn->right = NULL;
+	sn->key = key;
+	sn->data = data;
+
+	if (parent == NULL)
+		tree->root = sn;
+	else {
+		res = CallHookPkt(tree->hook, sn->key, parent->key);
+		if (res > 0)
+			parent->right = sn;
+		else
+			parent->left = sn;
+	}
+
+	splay(tree, sn);
+
+	return TRUE;
+}
+
+APTR FindSplayNode(struct SplayTree *tree, APTR key) {
+	struct SplayNode *sn;
+
+	sn = find(tree, key);
+	if (sn == NULL)
+		return NULL;
+
+	splay(tree, sn);
+
+	return sn->data;
+}
+
+BOOL RemoveSplayNode(struct SplayTree *tree, APTR key) {
+	struct SplayNode *sn;
+
+	sn = find(tree, key);
+	if (sn == NULL)
+		return FALSE;
+
+	splay(tree, sn);
+
+	if (sn->left == NULL)
+		replace(tree, sn, sn->right);
+	else if (sn->right == NULL)
+		replace(tree, sn, sn->left);
+	else {
+		struct SplayNode *s2 = sn->right;
+
+		while (s2->left != NULL)
+			s2 = s2->left;
+
+		if (sn != s2->parent) {
+			replace(tree, s2, s2->right);
+			s2->right = sn->right;
+			s2->right->parent = s2;
+		}
+
+		replace(tree, sn, s2);
+		s2->left = sn->left;
+		s2->left->parent = s2;
+	}
+
+	FreePooled(tree->mempool, sn, sizeof(*sn));
+
+	return TRUE;
+}
+#endif //__amigaos4__
+
diff --git a/amiga/splaytree.h b/amiga/splaytree.h
new file mode 100644
index 000000000..c81633622
--- /dev/null
+++ b/amiga/splaytree.h
@@ -0,0 +1,40 @@
+/**
+ * Copyright (c) 2015 Fredrik Wikstrom <fredrik@a500.org>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#ifndef __amigaos4__
+#ifndef SPLAYTREE_H
+#define SPLAYTREE_H
+
+#ifndef EXEC_TYPES_H
+#include <exec/types.h>
+#endif
+#ifndef UTILITY_HOOKS_H
+#include <utility/hooks.h>
+#endif
+
+struct SplayTree;
+
+struct SplayTree *CreateSplayTree(struct Hook *hook);
+void DeleteSplayTree(struct SplayTree *tree);
+BOOL InsertSplayNode(struct SplayTree *tree, APTR key, APTR data);
+APTR FindSplayNode(struct SplayTree *tree, APTR key);
+BOOL RemoveSplayNode(struct SplayTree *tree, APTR key);
+
+#endif
+#endif // __amigaos4__
+