Back to index

plt-scheme  4.2.1
Classes | Defines | Typedefs | Functions
splay.c File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  tree_node

Defines

#define Splay_Item(t)   t->item
#define Set_Splay_Item(t, v)   t->item = v

Typedefs

typedef struct tree_node

Functions

static Treesplay (unsigned long i, Tree *t)
static Treesplay_insert (unsigned long i, Tree *new, Tree *t)
static Treesplay_delete (unsigned long i, Tree *t)

Class Documentation

struct tree_node

Definition at line 57 of file splay.c.

Collaboration diagram for tree_node:
Class Members
void * data
unsigned long item
Tree * left
Tree * right

Define Documentation

#define Set_Splay_Item (   t,
 
)    t->item = v

Definition at line 63 of file splay.c.

#define Splay_Item (   t)    t->item

Definition at line 62 of file splay.c.


Typedef Documentation

typedef struct tree_node

Definition at line 56 of file splay.c.


Function Documentation

static Tree* splay ( unsigned long  i,
Tree t 
) [static]

Definition at line 66 of file splay.c.

                                                {
/* 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 < Splay_Item(t)) {
           if (t->left == NULL) break;
           if (i < Splay_Item(t->left)) {
              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 > Splay_Item(t)) {
           if (t->right == NULL) break;
           if (i > Splay_Item(t->right)) {
              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;
}

Here is the caller graph for this function:

static Tree* splay_delete ( unsigned long  i,
Tree t 
) [static]

Definition at line 137 of file splay.c.

                                                      {
/* 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 == Splay_Item(t)) {               /* found it */
       if (t->left == NULL) {
           x = t->right;
       } else {
           x = splay(i, t->left);
           x->right = t->right;
       }
       return x;
    }
    return t;                         /* It wasn't there */
}

Here is the call graph for this function:

static Tree* splay_insert ( unsigned long  i,
Tree new,
Tree t 
) [static]

Definition at line 110 of file splay.c.

                                                                  {
/* Insert i into the tree t, unless it's already there.    */
/* Return a pointer to the resulting tree.                 */
    Set_Splay_Item(new, i);
    if (t == NULL) {
       new->left = new->right = NULL;
       return new;
    }
    t = splay(i,t);
    if (i < Splay_Item(t)) {
       new->left = t->left;
       new->right = t;
       t->left = NULL;
       return new;
    } else if (i > Splay_Item(t)) {
       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                      */
       return t;
    }
}

Here is the call graph for this function: