Just to splay a tree.

I was looking for something different from a RBTree for implementing a queue request indexed by an integer, with a lot of accesses. It's valueable to consider a simple O(n) queue, because the items are scarsely popped out.
A Splay Tree fits well in this case. Not so much code.

#ifndef SPLAY_TREE_H
#define SPLAY_TREE_H 1

#include <stdlib.h>

typedef struct tree_node Tree;

struct tree_node {
    Tree * left, * right;
    int item;
    void* data;
};

struct tree_node* searchSplay(int value, struct tree_node* n)
{
 if (n == NULL)
  return NULL;

 if (value > n->item)
  return search(value, n->left);
 else if (value < n->item)
  return search(value, n->right);
 else
  return n;

 return NULL;
}
Tree * splay (int i, Tree * t) {
/* Simple top down splay, not requiring i to be in the tree t.  */
/* What it does is described above.                             */
    Tree N, *l, *r, *y;
    if (t == NULL) return t;
    N.left = N.right = NULL;
    l = r = &N;

    for (;;) {
 if (i < t->item) {
     if (t->left == NULL) break;
     if (i < t->left->item) {
  y = t->left;                           /* rotate right */
  t->left = y->right;
  y->right = t;
  t = y;
  if (t->left == NULL) break;
     }
     r->left = t;                               /* link right */
     r = t;
     t = t->left;
 } else if (i > t->item) {
     if (t->right == NULL) break;
     if (i > t->right->item) {
  y = t->right;                          /* rotate left */
  t->right = y->left;
  y->left = t;
  t = y;
  if (t->right == NULL) break;
     }
     l->right = t;                              /* link left */
     l = t;
     t = t->right;
 } else {
     break;
 }
    }
    l->right = t->left;                                /* assemble */
    r->left = t->right;
    t->left = N.right;
    t->right = N.left;
    return t;
}

Tree * insertSplay(int i, void* data, Tree * t) {
/* Insert i into the tree t, unless it's already there.    */
/* Return a pointer to the resulting tree.                 */
    Tree * new;

    new = (Tree *) malloc (sizeof (Tree));
    if (new == NULL) {
     printf("Ran out of space\n");
     exit(1);
    }
    new->item = i;
    new->data = data;
    if (t == NULL) {
     new->left = new->right = NULL;
     size = 1;
     return new;
    }
    t = splay(i,t);
    if (i < t->item) {
 new->left = t->left;
 new->right = t;
 t->left = NULL;
 size ++;
 return new;
    } else if (i > t->item) {
 new->right = t->right;
 new->left = t;
 t->right = NULL;
 return new;
    } else { /* We get here if it's already in the tree */
             /* Don't add it again                      */
 free(new);
 return t;
    }
}

Tree * deleteSplay(int i, Tree * t) {
/* Deletes i from the tree if it's there.               */
/* Return a pointer to the resulting tree.              */
    Tree * x;
    if (t==NULL) return NULL;
    t = splay(i,t);
    if (i == t->item) {               /* found it */
 if (t->left == NULL) {
     x = t->right;
 } else {
     x = splay(i, t->left);
     x->right = t->right;
 }
 free(t);
 return x;
    }
    return t;                         /* It wasn't there */
}
#endif