--- splay-tree.c	2006-07-11 15:36:50.000000000 +0200
+++ splay-tree.nrn.c	2006-07-11 15:46:54.000000000 +0200
@@ -38,10 +38,6 @@ Boston, MA 02110-1301, USA.  */
 #include "splay-tree.h"
 
 static void splay_tree_delete_helper (splay_tree, splay_tree_node);
-static inline void rotate_left (splay_tree_node *,
-				splay_tree_node, splay_tree_node);
-static inline void rotate_right (splay_tree_node *,
-				splay_tree_node, splay_tree_node);
 static void splay_tree_splay (splay_tree, splay_tree_key);
 static int splay_tree_foreach_helper (splay_tree, splay_tree_node,
                                       splay_tree_foreach_fn, void*);
@@ -106,95 +102,103 @@ splay_tree_delete_helper (splay_tree sp,
 #undef VDEL
 }
 
-/* Rotate the edge joining the left child N with its parent P.  PP is the
-   grandparents pointer to P.  */
+/* Splay SP around KEY.
+   This works alot like spliting a BST except if you traverse
+   left left or right right you first rotate the root before splitting
+   then move down a node.  */
 
-static inline void
-rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
+static void
+splay_tree_splay (splay_tree sp, splay_tree_key key)
 {
-  splay_tree_node tmp;
-  tmp = n->right;
-  n->right = p;
-  p->left = tmp;
-  *pp = n;
-}
+  if (sp->root == 0)
+    return;
 
-/* Rotate the edge joining the right child N with its parent P.  PP is the
-   grandparents pointer to P.  */
+  /* temp_tree.left is all the nodes less than key while
+     temp_tree.right is all the nodes greater than key */
+  struct splay_tree_node_s temp_tree;
+
+  /* these are the points we will add new nodes to the respective trees */
+  splay_tree_node left_ptr;
+  splay_tree_node right_ptr;
 
-static inline void
-rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
-{
-  splay_tree_node tmp;
-  tmp = n->left;
-  n->left = p;
-  p->right = tmp;
-  *pp = n;
-}
+  /* current node we are splitting the tree at */
+  splay_tree_node current_node;
 
-/* Bottom up splay of key.  */
+  splay_tree_node tmp_node;
+  int comparison;
 
-static void
-splay_tree_splay (splay_tree sp, splay_tree_key key)
-{
-  if (sp->root == 0)
+  temp_tree.left = temp_tree.right = 0;
+  left_ptr = right_ptr = &temp_tree;
+
+  current_node = sp->root;
+  comparison = (*sp->comp) (key, current_node->key);
+
+  /* no splaying need */
+  if (comparison == 0)
     return;
 
-  do {
-    int cmp1, cmp2;
-    splay_tree_node n, c;
-
-    n = sp->root;
-    cmp1 = (*sp->comp) (key, n->key);
-
-    /* Found.  */
-    if (cmp1 == 0)
-      return;
-
-    /* Left or right?  If no child, then we're done.  */
-    if (cmp1 < 0)
-      c = n->left;
-    else
-      c = n->right;
-    if (!c)
-      return;
-
-    /* Next one left or right?  If found or no child, we're done
-       after one rotation.  */
-    cmp2 = (*sp->comp) (key, c->key);
-    if (cmp2 == 0
-        || (cmp2 < 0 && !c->left)
-        || (cmp2 > 0 && !c->right))
-      {
-	if (cmp1 < 0)
-	  rotate_left (&sp->root, n, c);
-	else
-	  rotate_right (&sp->root, n, c);
-        return;
-      }
-
-    /* Now we have the four cases of double-rotation.  */
-    if (cmp1 < 0 && cmp2 < 0)
-      {
-	rotate_left (&n->left, c, c->left);
-	rotate_left (&sp->root, n, n->left);
-      }
-    else if (cmp1 > 0 && cmp2 > 0)
-      {
-	rotate_right (&n->right, c, c->right);
-	rotate_right (&sp->root, n, n->right);
-      }
-    else if (cmp1 < 0 && cmp2 > 0)
-      {
-	rotate_right (&n->left, c, c->right);
-	rotate_left (&sp->root, n, n->left);
-      }
-    else if (cmp1 > 0 && cmp2 < 0)
-      {
-	rotate_left (&n->right, c, c->left);
-	rotate_right (&sp->root, n, n->right);
-      }
-  } while (1);
+  /* while we haven't found the node */
+  do
+    {
+      /* left */
+      if (comparison < 0)
+	{
+	  if (!current_node->left)
+	    break;
+	
+	  comparison = (*sp->comp) (key, current_node->left->key);
+	  /* left left */
+	  if (comparison < 0)
+	    {
+	      tmp_node = current_node->left;
+	      current_node->left = tmp_node->right;
+	      tmp_node->right = current_node;
+	      current_node = tmp_node;
+
+	      if (!current_node->left)
+		break;
+
+	      comparison = (*sp->comp) (key, current_node->left->key);
+	    }
+	  
+	  right_ptr->left = current_node;
+	  right_ptr = current_node;
+	  current_node = current_node->left;
+	}
+      /* right */
+      else
+	{
+	  if (!current_node->right)
+	    break;
+
+	  comparison = (*sp->comp) (key, current_node->right->key);
+	  /* right right */
+	  if (comparison > 0)
+	    {
+	      tmp_node = current_node->right;
+	      current_node->right = tmp_node->left;
+	      tmp_node->left = current_node;
+	      current_node = tmp_node;
+
+	      if (!current_node->right)
+		break;
+
+	      comparison = (*sp->comp) (key, current_node->right->key);
+	    }
+
+	  left_ptr->right = current_node;
+	  left_ptr = current_node;
+	  current_node = current_node->right;
+	}
+    }
+  while (comparison != 0);
+
+  left_ptr->right = current_node->left;
+  right_ptr->left = current_node->right;
+  current_node->left = temp_tree.right;
+  current_node->right = temp_tree.left;
+
+  sp->root = current_node;
 }
 
 /* Call FN, passing it the DATA, for every node below NODE, all of