asp@cs.cmu.edu (James Aspnes) (04/22/91)
Lest anybody be tempted to send $15 to Kenneth, even under his present
allegedly-friendlier terms, I'd like to point out that:
1. Hash tables and doubly-linked lists are both covered in the first
month of sophomore-level programming courses.
2. Kenneth's implementation isn't all that good.
3. You are better off using your $15 as a down-payment for a good
algorithms text (Sedgewick's _Algorithms in C_, which runs at
about $40 in hardcover, contains code for several varieties of
hash tables and linked lists, and much besides.)
4. If you just want to hack around with a generic data structure that
does just about everything, but don't want to know how it works,
the following free, public domain code from the comp.sources.unix
archives does everything a hash table or a linked list does, and
more.
--James Aspnes <asp@cs.cmu.edu>
Subject: v14i087: Splay tree library
Newsgroups: comp.sources.unix
Sender: sources
Approved: rsalz@uunet.UU.NET
Submitted-by: Dave Brower <rtech!llama!daveb>
Posting-number: Volume 14, Issue 87
Archive-name: splay-tree
[ Kinda like AVL or balanced tree stuff, but not really. --r$ ]
Here is a library for working with the splay trees Tarjan talked about
in his ACM Turing Lecture. I use it for symbol tables and the like.
Others might want to change the key type and the use of strcmp as the
ordering function.
It is a transliteration from Pascal code given me by Doug Jones at the U
of Iowa. Send thank you notes to him as jones@cs.uiowa.edu.
There is a man page and a Makefile for "libsptree.a." I would be
shocked, shocked indeed to find any critical system dependencies.
(Some of the statistics might want to be longs on 16 bit machines to
avoid overflow).
Users must supply their own emalloc() function. The cavalier might
do "-Demalloc=malloc" during the compilation.
-dB
#!/bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #!/bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
# Makefile
# spaux.c
# spdaveb.c
# sptree.3
# sptree.c
# sptree.h
# This archive created: Wed Feb 10 19:41:38 1988
export PATH; PATH=/bin:$PATH
if test -f 'Makefile'
then
echo shar: over-writing existing file "'Makefile'"
fi
sed 's/^X//' << \SHAR_EOF > 'Makefile'
X#
X# makefile for splay tree library
X
Xall: libsptree.a
X
Xlibsptree.a: sptree.o spaux.o spdaveb.o
X ar rvu libsptree.a sptree.o spaux.o spdaveb.o
X
SHAR_EOF
if test -f 'spaux.c'
then
echo shar: over-writing existing file "'spaux.c'"
fi
sed 's/^X//' << \SHAR_EOF > 'spaux.c'
X/*
X spaux.c: This code implements the following operations on an event-set
X or priority-queue implemented using splay trees:
X
X n = sphead( q ) n is the head item in q (not removed).
X spdelete( n, q ) n is removed from q.
X n = spnext( np, q ) n is the successor of np in q.
X n = spprev( np, q ) n is the predecessor of np in q.
X spenqbefore( n, np, q ) n becomes the predecessor of np in q.
X spenqafter( n, np, q ) n becomes the successor of np in q.
X
X In the above, n and np are pointers to single items (type
X SPBLK *); q is an event-set (type SPTREE *),
X The type definitions for these are taken
X from file sptree.h. All of these operations rest on basic
X splay tree operations from file sptree.c.
X
X The basic splay tree algorithms were originally presented in:
X
X Self Adjusting Binary Trees,
X by D. D. Sleator and R. E. Tarjan,
X Proc. ACM SIGACT Symposium on Theory
X of Computing (Boston, Apr 1983) 235-245.
X
X The operations in this package supplement the operations from
X file splay.h to provide support for operations typically needed
X on the pending event set in discrete event simulation. See, for
X example,
X
X Introduction to Simula 67,
X by Gunther Lamprecht, Vieweg & Sohn, Braucschweig, Wiesbaden, 1981.
X (Chapter 14 contains the relevant discussion.)
X
X Simula Begin,
X by Graham M. Birtwistle, et al, Studentlitteratur, Lund, 1979.
X (Chapter 9 contains the relevant discussion.)
X
X Many of the routines in this package use the splay procedure,
X for bottom-up splaying of the queue. Consequently, item n in
X delete and item np in all operations listed above must be in the
X event-set prior to the call or the results will be
X unpredictable (eg: chaos will ensue).
X
X Note that, in all cases, these operations can be replaced with
X the corresponding operations formulated for a conventional
X lexicographically ordered tree. The versions here all use the
X splay operation to ensure the amortized bounds; this usually
X leads to a very compact formulation of the operations
X themselves, but it may slow the average performance.
X
X Alternative versions based on simple binary tree operations are
X provided (commented out) for head, next, and prev, since these
X are frequently used to traverse the entire data structure, and
X the cost of traversal is independent of the shape of the
X structure, so the extra time taken by splay in this context is
X wasted.
X
X This code was written by:
X Douglas W. Jones with assistance from Srinivas R. Sataluri
X
X Translated to C by David Brower, daveb@rtech.uucp
X
X */
X
X# include "sptree.h"
X
X
X/*----------------
X *
X * sphead() -- return the "lowest" element in the tree.
X *
X * returns a reference to the head event in the event-set q,
X * represented as a splay tree; q->root ends up pointing to the head
X * event, and the old left branch of q is shortened, as if q had
X * been splayed about the head element; this is done by dequeueing
X * the head and then making the resulting queue the right son of
X * the head returned by spdeq; an alternative is provided which
X * avoids splaying but just searches for and returns a pointer to
X * the bottom of the left branch
X */
XSPBLK *
Xsphead( q )
X
Xregister SPTREE * q;
X
X{
X register SPBLK * x;
X
X /* splay version, good amortized bound */
X x = spdeq( q->root );
X if( x != NULL )
X {
X x->rightlink = q->root;
X x->leftlink = NULL;
X x->uplink = NULL;
X if( q->root != NULL )
X q->root->uplink = x;
X }
X q->root = x;
X
X /* alternative version, bad amortized bound,
X but faster on the average */
X
X# if 0
X x = q->root;
X while( x->leftlink != NULL )
X x = x->leftlink;
X# endif
X
X return( x );
X
X} /* sphead */
X
X
X
X/*----------------
X *
X * spdelete() -- Delete node from a tree.
X *
X * n is deleted from q; the resulting splay tree has been splayed
X * around its new root, which is the successor of n
X *
X */
Xvoid
Xspdelete( n, q )
X
Xregister SPBLK * n;
Xregister SPTREE * q;
X
X{
X register SPBLK * x;
X
X splay( n, q );
X x = spdeq( q->root->rightlink );
X if( x == NULL ) /* empty right subtree */
X {
X q->root = q->root->leftlink;
X q->root->uplink = NULL;
X }
X else /* non-empty right subtree */
X {
X x->uplink = NULL;
X x->leftlink = q->root->leftlink;
X x->rightlink = q->root->rightlink;
X if( x->leftlink != NULL )
X x->leftlink->uplink = x;
X if( x->rightlink != NULL )
X x->rightlink->uplink = x;
X q->root = x;
X }
X
X} /* spdelete */
X
X
X
X/*----------------
X *
X * spnext() -- return next higer item in the tree, or NULL.
X *
X * return the successor of n in q, represented as a splay tree; the
X * successor becomes the root; two alternate versions are provided,
X * one which is shorter, but slower, and one which is faster on the
X * average because it does not do any splaying
X *
X */
XSPBLK *
Xspnext( n, q )
X
Xregister SPBLK * n;
Xregister SPTREE * q;
X
X{
X register SPBLK * next;
X register SPBLK * x;
X
X /* splay version */
X splay( n, q );
X x = spdeq( n->rightlink );
X if( x != NULL )
X {
X x->leftlink = n;
X n->uplink = x;
X x->rightlink = n->rightlink;
X n->rightlink = NULL;
X if( x->rightlink != NULL )
X x->rightlink->uplink = x;
X q->root = x;
X x->uplink = NULL;
X }
X next = x;
X
X /* shorter slower version;
X deleting last "if" undoes the amortized bound */
X
X# if 0
X splay( n, q );
X x = n->rightlink;
X if( x != NULL )
X while( x->leftlink != NULL )
X x = x->leftlink;
X next = x;
X if( x != NULL )
X splay( x, q );
X# endif
X
X return( next );
X
X} /* spnext */
X
X
X
X/*----------------
X *
X * spprev() -- return previous node in a tree, or NULL.
X *
X * return the predecessor of n in q, represented as a splay tree;
X * the predecessor becomes the root; an alternate version is
X * provided which is faster on the average because it does not do
X * any splaying
X *
X */
XSPBLK *
Xspprev( n, q )
X
Xregister SPBLK * n;
Xregister SPTREE * q;
X
X{
X register SPBLK * prev;
X register SPBLK * x;
X
X /* splay version;
X note: deleting the last "if" undoes the amortized bound */
X
X splay( n, q );
X x = n->leftlink;
X if( x != NULL )
X while( x->rightlink != NULL )
X x = x->rightlink;
X prev = x;
X if( x != NULL )
X splay( x, q );
X
X return( prev );
X
X} /* spprev */
X
X
X
X/*----------------
X *
X * spenqbefore() -- insert node before another in a tree.
X *
X * returns pointer to n.
X *
X * event n is entered in the splay tree q as the immediate
X * predecessor of n1; in doing so, n1 becomes the root of the tree
X * with n as its left son
X *
X */
XSPBLK *
Xspenqbefore( n, n1, q )
X
Xregister SPBLK * n;
Xregister SPBLK * n1;
Xregister SPTREE * q;
X
X{
X splay( n1, q );
X n->key = n1->key;
X n->leftlink = n1->leftlink;
X if( n->leftlink != NULL )
X n->leftlink->uplink = n;
X n->rightlink = NULL;
X n->uplink = n1;
X n1->leftlink = n;
X
X return( n );
X
X} /* spenqbefore */
X
X
X
X/*----------------
X *
X * spenqafter() -- enter n after n1 in tree q.
X *
X * returns a pointer to n.
X *
X * event n is entered in the splay tree q as the immediate
X * successor of n1; in doing so, n1 becomes the root of the tree
X * with n as its right son
X */
XSPBLK *
Xspenqafter( n, n1, q )
X
Xregister SPBLK * n;
Xregister SPBLK * n1;
Xregister SPTREE * q;
X
X{
X splay( n1, q );
X n->key = n1->key;
X n->rightlink = n1->rightlink;
X if( n->rightlink != NULL )
X n->rightlink->uplink = n;
X n->leftlink = NULL;
X n->uplink = n1;
X n1->rightlink = n;
X
X return( n );
X
X} /* spenqafter */
X
X
SHAR_EOF
if test -f 'spdaveb.c'
then
echo shar: over-writing existing file "'spdaveb.c'"
fi
sed 's/^X//' << \SHAR_EOF > 'spdaveb.c'
X/*
X * spdaveb.c -- daveb's new splay tree functions.
X *
X * The functions in this file provide an interface that is nearly
X * the same as the hash library I swiped from mkmf, allowing
X * replacement of one by the other. Hey, it worked for me!
X *
X * splookup() -- given a key, find a node in a tree.
X * spinstall() -- install an item in the tree, overwriting existing value.
X * spfhead() -- fast (non-splay) find the first node in a tree.
X * spftail() -- fast (non-splay) find the last node in a tree.
X * spscan() -- forward scan tree from the head.
X * sprscan() -- reverse scan tree from the tail.
X * spfnext() -- non-splaying next.
X * spfprev() -- non-splaying prev.
X * spstats() -- make char string of stats for a tree.
X *
X * Written by David Brower, daveb@rtech.uucp 1/88.
X */
X
X
X# include "sptree.h"
X
X/* USER SUPPLIED! */
X
Xextern char *emalloc();
X
X
X/*----------------
X *
X * splookup() -- given key, find a node in a tree.
X *
X * Splays the found node to the root.
X */
XSPBLK *
Xsplookup( key, q )
X
Xregister char * key;
Xregister SPTREE * q;
X
X{
X register SPBLK * n;
X register int Sct;
X register int c;
X
X /* find node in the tree */
X n = q->root;
X c = ++(q->lkpcmps);
X q->lookups++;
X while( n && (Sct = STRCMP( key, n->key ) ) )
X {
X c++;
X n = ( Sct < 0 ) ? n->leftlink : n->rightlink;
X }
X q->lkpcmps = c;
X
X /* reorganize tree around this node */
X if( n != NULL )
X splay( n, q );
X
X return( n );
X}
X
X
X
X/*----------------
X *
X * spinstall() -- install an entry in a tree, overwriting any existing node.
X *
X * If the node already exists, replace its contents.
X * If it does not exist, then allocate a new node and fill it in.
X */
X
XSPBLK *
Xspinstall( key, data, datb, q )
X
Xregister char * key;
Xregister char * data;
Xregister char * datb;
Xregister SPTREE *q;
X
X{
X register SPBLK *n;
X
X if( NULL == ( n = splookup( key, q ) ) )
X {
X n = (SPBLK *) emalloc( sizeof( *n ) );
X n->key = key;
X n->leftlink = NULL;
X n->rightlink = NULL;
X n->uplink = NULL;
X spenq( n, q );
X }
X
X n->data = data;
X n->datb = datb;
X
X return( n );
X}
X
X
X
X
X/*----------------
X *
X * spfhead() -- return the "lowest" element in the tree.
X *
X * returns a reference to the head event in the event-set q.
X * avoids splaying but just searches for and returns a pointer to
X * the bottom of the left branch.
X */
XSPBLK *
Xspfhead( q )
X
Xregister SPTREE * q;
X
X{
X register SPBLK * x;
X
X if( NULL != ( x = q->root ) )
X while( x->leftlink != NULL )
X x = x->leftlink;
X
X return( x );
X
X} /* spfhead */
X
X
X
X
X/*----------------
X *
X * spftail() -- find the last node in a tree.
X *
X * Fast version does not splay result or intermediate steps.
X */
XSPBLK *
Xspftail( q )
X
XSPTREE * q;
X
X{
X register SPBLK * x;
X
X
X if( NULL != ( x = q->root ) )
X while( x->rightlink != NULL )
X x = x->rightlink;
X
X return( x );
X
X} /* spftail */
X
X
X/*----------------
X *
X * spscan() -- apply a function to nodes in ascending order.
X *
X * if n is given, start at that node, otherwise start from
X * the head.
X */
Xvoid
Xspscan( f, n, q )
X
Xregister int (*f)();
Xregister SPBLK * n;
Xregister SPTREE * q;
X
X{
X register SPBLK * x;
X
X for( x = n != NULL ? n : spfhead( q ); x != NULL ; x = spfnext( x ) )
X (*f)( x );
X}
X
X
X
X/*----------------
X *
X * sprscan() -- apply a function to nodes in descending order.
X *
X * if n is given, start at that node, otherwise start from
X * the tail.
X */
Xvoid
Xsprscan( f, n, q )
X
Xregister int (*f)();
Xregister SPBLK * n;
Xregister SPTREE * q;
X
X{
X register SPBLK *x;
X
X for( x = n != NULL ? n : spftail( q ); x != NULL ; x = spfprev( x ) )
X (*f)( x );
X}
X
X
X
X/*----------------
X *
X * spfnext() -- fast return next higer item in the tree, or NULL.
X *
X * return the successor of n in q, represented as a splay tree.
X * This is a fast (on average) version that does not splay.
X */
XSPBLK *
Xspfnext( n )
X
Xregister SPBLK * n;
X
X{
X register SPBLK * next;
X register SPBLK * x;
X
X /* a long version, avoids splaying for fast average,
X * poor amortized bound
X */
X
X if( n == NULL )
X return( n );
X
X x = n->rightlink;
X if( x != NULL )
X {
X while( x->leftlink != NULL )
X x = x->leftlink;
X next = x;
X }
X else /* x == NULL */
X {
X x = n->uplink;
X next = NULL;
X while( x != NULL )
X {
X if( x->leftlink == n )
X {
X next = x;
X x = NULL;
X }
X else
X {
X n = x;
X x = n->uplink;
X }
X }
X }
X
X return( next );
X
X} /* spfnext */
X
X
X
X/*----------------
X *
X * spfprev() -- return fast previous node in a tree, or NULL.
X *
X * return the predecessor of n in q, represented as a splay tree.
X * This is a fast (on average) version that does not splay.
X */
XSPBLK *
Xspfprev( n )
X
Xregister SPBLK * n;
X
X{
X register SPBLK * prev;
X register SPBLK * x;
X
X /* a long version,
X * avoids splaying for fast average, poor amortized bound
X */
X
X if( n == NULL )
X return( n );
X
X x = n->leftlink;
X if( x != NULL )
X {
X while( x->rightlink != NULL )
X x = x->rightlink;
X prev = x;
X }
X else
X {
X x = n->uplink;
X prev = NULL;
X while( x != NULL )
X {
X if( x->rightlink == n )
X {
X prev = x;
X x = NULL;
X }
X else
X {
X n = x;
X x = n->uplink;
X }
X }
X }
X
X return( prev );
X
X} /* spfprev */
X
X
X
Xchar *
Xspstats( q )
XSPTREE *q;
X{
X static char buf[ 128 ];
X float llen;
X float elen;
X float sloops;
X
X if( q == NULL )
X return("");
X
X llen = q->lookups ? (float)q->lkpcmps / q->lookups : 0;
X elen = q->enqs ? (float)q->enqcmps/q->enqs : 0;
X sloops = q->splays ? (float)q->splayloops/q->splays : 0;
X
X sprintf(buf, "f(%d %4.2f) i(%d %4.2f) s(%d %4.2f)",
X q->lookups, llen, q->enqs, elen, q->splays, sloops );
X
X return buf;
X}
X
SHAR_EOF
if test -f 'sptree.3'
then
echo shar: over-writing existing file "'sptree.3'"
fi
sed 's/^X//' << \SHAR_EOF > 'sptree.3'
X.TH SPTREE 3 "10 February 1988"
X.UC 4
X.SH NAME
Xspdelete, spdeq, spempty, spenq, spenqafter, spenqbefore, spenqprior,
Xspfhead, spfnext, spfprev, spftail, sphead, spinit, spinstall, splay,
Xsplookup, spnext, spprev, sprscan, spscan, spstats \- splay tree operations
X.SH SYNOPSIS
X.nf
X.B #include "sptree.h"
X.PP
X.B void spdelete(n, q)
X.B SPBLK *n;
X.B SPTREE *q;
X.PP
X.B SPBLK *spdeq(n)
X.B SPBLK *n;
X.PP
X.B int spempty(q)
X.B SPTREE *q;
X.PP
X.B SPBLK *spenq(n, q)
X.B SPBLK *n;
X.B SPTREE *q;
X.PP
X.B SPBLK *spenqafter(n, n1, q)
X.B SPBLK *n, *n1;
X.B SPTREE *q;
X.PP
X.B SPBLK *spenqbefore(n, n1, q)
X.B SPBLK *n, *n1;
X.B SPTREE *q;
X.PP
X.B SPBLK *spenqprior(n, q)
X.B SPBLK *n;
X.B SPTREE *q;
X.PP
X.B SPBLK *spfhead(q)
X.B SPTREE *q;
X.PP
X.B SPBLK *spfnext(n)
X.B SPBLK *n;
X.PP
X.B SPBLK *spfprev(n)
X.B SPBLK *n;
X.PP
X.B SPBLK *spftail(q)
X.B SPTREE *q;
X.PP
X.B SPBLK *sphead(q)
X.B SPTREE *q;
X.PP
X.B SPTREE *spinit();
X.PP
X.B SPBLK *spinstall(key, data, datb, q)
X.B char *key, *data, *datb;
X.B SPTREE *q;
X.PP
X.B void splay(n, q)
X.B SPBLK *n;
X.B SPTREE *q;
X.PP
X.B SPBLK *splookup(key, q)
X.B char *key;
X.B SPTREE *q;
X.PP
X.B SPBLK *spnext(n, q)
X.B SPBLK *n;
X.B SPTREE *q;
X.PP
X.B SPBLK *spprev(n, q)
X.B SPBLK *n;
X.B SPTREE *q;
X.PP
X.B void sprscan(f, n, q)
X.B int (*f)();
X.B SPBLK *n;
X.B SPTREE *q;
X.PP
X.B void spscan(f, n, q)
X.B int (*f)();
X.B SPBLK *n;
X.B SPTREE *q;
X.PP
X.B char *spstats(q)
X.B SPTREE *q;
X.PP
X.fi
X.SH DESCRIPTION
XThese functions operate on an event\-set or priority\-queue implemented
Xusing splay trees. These are similar to avl\-trees, but are not
Xconcerned with keeping the tree strictly balanced. Instead, the tree is
Xdynamically reorganized in a simple way that yields a good amortized
Xbound at the expense of worst case performance.
X.PP
XThe SPTREE structure declared in sptree.h should only be handled
Xindirectly. A pointer to an SPTREE is returned by
X.I spinit
Xand should be handed blindly to other access functions.
X.PP
XThe nodes in a splay tree are defined by the following structure,
Xdeclared in sptree.h.
X.PP
X.nf
Xtypedef struct _spblk SPBLK;
Xtypedef struct _spblk
X{
X .
X .
X .
X
X char *key;
X char *data;
X char *datb;
X};
X.fi
X.PP
XYou should only refer to the
X.I key,
X.I data
Xand
X.I datb
Xmembers.
X.PP
XThe
X.I key
Xis interpreted as a pointer to a null terminated string, and ordering is
Xdetermined by calls to the usual
X.I strcmp
Xroutine.
X.PP
XNo meaning is associated with the auxiliary members
X.I data
Xor
X.I datb,
Xand you are free to stuff them with whatever good conscience and a legal
Xcast will allow.
X.PP
X.I Spdelete
Xdeletes the node
X.I n
Xfrom the tree
X.I q.
XThe resulting tree is splayed around a new root, which is the successor
Xto
X.I n.
X.PP
X.I Spdeq
Xremoves and returns the head node from the sub\-tree rooted at node
X.I n.
X.PP
X.I Spempty
Xreturns non\-zero if the tree
X.I q
Xhas no members.
X.PP
X.I Spenq
Xinserts node
X.I n
Xinto tree
X.I q
Xafter all other nodes with the same key. When this is done,
X.I n
Xwill be the root of the tree.
X.PP
X.I Spenqafter
Xinserts node
X.I n
Xas the immediate sucessor of node
X.I n1
Xin tree
X.I q.
XIn so doing,
X.I n1
Xbecomes the root of the tree with
X.I n
Xas its right son.
X.PP
X.I Spenqbefore
Xinserts node
X.I n
Xas the immediate predecessor of node
X.I n1
Xin tree
X.I q.
XIn doing so,
X.I n1
Xbecomes the root of the tree with
X.I n
Xas its left son.
X.PP
X.I Spenqprior
Xinserts node
X.I n
Xinto the tree
X.I q
Xbefore all other nodes with the same key; after this is done,
X.I n
Xwill be the root of the tree.
X.PP
X.I Spfhead
Xreturns a pointer to the head element in the tree
X.I q,
Xbut does not splay it to the root.
X.PP
X.I Spfnext
Xreturns a pointer to the immediate successor of node
X.I n
Xwithout doing any reorganization.
X.PP
X.I Spfprev
Xreturns a pointer to the immediate predecessor of node
X.I n
Xwithout doing any reoganization.
X.PP
X.I Spftail
Xreturns a reference to the last node in the tree
X.I q
Xwithout doing any reorganization.
X.PP
X.I Sphead
Xreturns a pointer to the head event in the tree
X.I q.
XThe returned node is made the root of the tree, as if
X.I q
Xhad been splayed around
X.I n.
X.PP
X.I Spinit
Xcreates a new splay tree using a \fImalloc\fP\-like routine named
X.I emalloc
Xthat must be supplied by the user.
X.PP
X.I Spinstall
Xinserts an entry with the key value pointed to by
X.I key
Xwith the auxiliary values
X.I data
Xand
X.I datb
Xinto the tree
X.I q.
XIf a node with the key value already exists, its auxiliarly values are
Xreplaced. If the node does not already exist, a new one is allocated
Xwith \fImalloc\fP\-like function named
X.I emalloc
Xthat must be supplied by the user.
X.PP
X.I Splay
Xreorganizes the tree so that node
X.I n
Xbecomes the root of the tree in
X.I q.
XResults are unpredicatable if
X.I n
Xis not in
X.I q
Xto start with.
X.I Q
Xis split from
X.I n
Xup to the old root, with all nodes to the left of
X.I n
Xending up in the left sub\-tree, and all nodes to the right of
X.I n
Xending up in the right sub\-tree. The left branch of the right
Xsub\-tree and the right branch of the left sub\-tree are shortened in
Xthe process.
X.PP
X.I Splookup
Xsearches for a node containing the key value pointed to by
X.I key
Xin the tree
X.I q.
XA found node is splayed to the root and returned. If the key is not
Xfound, the function returns NULL and no reorganization is done.
X.PP
X.I
XSpnext returns a pointer to the successor of
X.I n
Xin
X.I q.
XThe successor becomes the root of the tree.
X.PP
X.I Spprev
Xreturns the predecessor of
X.I n
Xin
X.I q.
XThe predecessor becomes the root.
X.PP
X.I Sprscan
Xapplies the function
X.I f
Xstarting at node
X.I n
Xto the members of the tree
X.I q
Xin reverse order. If
X.I n
Xis NULL, then the scan starts at the tail of the tree. The tree is not
Xreorganized during the reverse scan. The function is called with one
Xargument, a pointer to an SPBLK. Its return value is ignored.
X.PP
X.I Spscan
Xapplies the function
X.I f
Xstarting at node
X.I n
Xin tree
X.I q
Xand all successive nodes, in order. If
X.I n
Xis NULL, then the scan starts at the head of the tree. The tree is not
Xreorganized during the scan. The function is called with one argument,
Xa pointer to an SPBLK. Its return value is ignored.
X.PP
X.I Spstats
Xreturns a string of statistics on the activities in the tree
X.I q.
XIt shows how many times
X.I splookup
Xwas called, and how many comparisons were needed per call,
Xthe number of nodes that have been added with
X.I spenq
Xand the number of comparisons needed per call, and finally, the number
Xof
X.I splay
Xoperations performed, and the number of loops done in each splay. These
Xstatistics give an indication of the average effective depth of the tree
Xfor various operations. The function returns a pointer to a static
Xbuffer that is overwritten with each call.
X.SH AUTHORS
XThe code was originally written in Pascal by Douglas W. Jones
X(jones@cs.uiowa.edu) with assistance from Srinivas R. Sataluri. It was
Xtranslated to C with some new functions by Dave Brower
X(daveb@rtech.uucp).
X.SH REFERENCES
XThe basic splay tree algorithms were originally presented in:
X.PP
X.nf
X Self Adjusting Binary Trees,
X by D. D. Sleator and R. E. Tarjan,
X Proc. ACM SIGACT Symposium on Theory
X of Computing (Boston, Apr 1983) 235-245.
X.fi
X.PP
XMore operations on priority queues were added to help support discrete
Xevent simulation. See, for example Chapter 14 of
X.PP
X.nf
X Introduction to Simula 67,
X by Gunther Lamprecht,
X Vieweg & Sohn, Braucschweig, Wiesbaden, 1981.
X.fi
X.PP
Xand Chapter 9 of
X.PP
X.nf
X Simula Begin,
X by Graham M. Birtwistle, et al,
X Studentlitteratur, Lund, 1979.
X.fi
X.PP
XSplay trees are compared with other data structures in
X.PP
X.nf
X An Empirical Comparison of Priority-Queue and Event-Set Implementations,
X by Douglas W. Jones,
X Comm. ACM 29, 4 (Apr. 1986) 300-311.
X.fi
SHAR_EOF
if test -f 'sptree.c'
then
echo shar: over-writing existing file "'sptree.c'"
fi
sed 's/^X//' << \SHAR_EOF > 'sptree.c'
X/*
X *
X * sptree.c: The following code implements the basic operations on
X * an event-set or priority-queue implemented using splay trees:
X *
X * SPTREE *spinit( compare ) Make a new tree
X * int spempty(); Is tree empty?
X * SPBLK *spenq( n, q ) Insert n in q after all equal keys.
X * SPBLK *spdeq( q ) Return first key in q, removing it.
X * SPBLK *spenqprior( n, q ) Insert n in q before all equal keys.
X * void splay( n, q ) n (already in q) becomes the root.
X *
X * In the above, n points to an SPBLK type, while q points to an
X * SPTREE.
X *
X * The implementation used here is based on the implementation
X * which was used in the tests of splay trees reported in:
X *
X * An Empirical Comparison of Priority-Queue and Event-Set Implementations,
X * by Douglas W. Jones, Comm. ACM 29, 4 (Apr. 1986) 300-311.
X *
X * The changes made include the addition of the enqprior
X * operation and the addition of up-links to allow for the splay
X * operation. The basic splay tree algorithms were originally
X * presented in:
X *
X * Self Adjusting Binary Trees,
X * by D. D. Sleator and R. E. Tarjan,
X * Proc. ACM SIGACT Symposium on Theory
X * of Computing (Boston, Apr 1983) 235-245.
X *
X * The enq and enqprior routines use variations on the
X * top-down splay operation, while the splay routine is bottom-up.
X * All are coded for speed.
X *
X * Written by:
X * Douglas W. Jones
X *
X * Translated to C by:
X * David Brower, daveb@rtech.uucp
X *
X */
X
X# include "sptree.h"
X
X/* USER SUPPLIED! */
X
Xextern char *emalloc();
X
X
X/*----------------
X *
X * spinit() -- initialize an empty splay tree
X *
X */
XSPTREE *
Xspinit()
X{
X register SPTREE * q;
X
X q = (SPTREE *) emalloc( sizeof( *q ) );
X
X q->lookups = 0;
X q->lkpcmps = 0;
X q->enqs = 0;
X q->enqcmps = 0;
X q->splays = 0;
X q->splayloops = 0;
X q->root = NULL;
X return( q );
X}
X
X/*----------------
X *
X * spempty() -- is an event-set represented as a splay tree empty?
X */
Xint
Xspempty( q )
X
XSPTREE *q;
X
X{
X return( q == NULL || q->root == NULL );
X}
X
X
X/*----------------
X *
X * spenq() -- insert item in a tree.
X *
X * put n in q after all other nodes with the same key; when this is
X * done, n will be the root of the splay tree representing q, all nodes
X * in q with keys less than or equal to that of n will be in the
X * left subtree, all with greater keys will be in the right subtree;
X * the tree is split into these subtrees from the top down, with rotations
X * performed along the way to shorten the left branch of the right subtree
X * and the right branch of the left subtree
X */
XSPBLK *
Xspenq( n, q )
X
Xregister SPBLK * n;
Xregister SPTREE * q;
X
X{
X register SPBLK * left; /* the rightmost node in the left tree */
X register SPBLK * right; /* the leftmost node in the right tree */
X register SPBLK * next; /* the root of the unsplit part */
X register SPBLK * temp;
X
X register char * key;
X register int Sct; /* Strcmp value */
X
X q->enqs++;
X n->uplink = NULL;
X next = q->root;
X q->root = n;
X if( next == NULL ) /* trivial enq */
X {
X n->leftlink = NULL;
X n->rightlink = NULL;
X }
X else /* difficult enq */
X {
X key = n->key;
X left = n;
X right = n;
X
X /* n's left and right children will hold the right and left
X splayed trees resulting from splitting on n->key;
X note that the children will be reversed! */
X
X q->enqcmps++;
X if ( STRCMP( next->key, key ) > 0 )
X goto two;
X
X one: /* assert next->key <= key */
X
X do /* walk to the right in the left tree */
X {
X temp = next->rightlink;
X if( temp == NULL )
X {
X left->rightlink = next;
X next->uplink = left;
X right->leftlink = NULL;
X goto done; /* job done, entire tree split */
X }
X
X q->enqcmps++;
X if( STRCMP( temp->key, key ) > 0 )
X {
X left->rightlink = next;
X next->uplink = left;
X left = next;
X next = temp;
X goto two; /* change sides */
X }
X
X next->rightlink = temp->leftlink;
X if( temp->leftlink != NULL )
X temp->leftlink->uplink = next;
X left->rightlink = temp;
X temp->uplink = left;
X temp->leftlink = next;
X next->uplink = temp;
X left = temp;
X next = temp->rightlink;
X if( next == NULL )
X {
X right->leftlink = NULL;
X goto done; /* job done, entire tree split */
X }
X
X q->enqcmps++;
X
X } while( STRCMP( next->key, key ) <= 0 ); /* change sides */
X
X two: /* assert next->key > key */
X
X do /* walk to the left in the right tree */
X {
X temp = next->leftlink;
X if( temp == NULL )
X {
X right->leftlink = next;
X next->uplink = right;
X left->rightlink = NULL;
X goto done; /* job done, entire tree split */
X }
X
X q->enqcmps++;
X if( STRCMP( temp->key, key ) <= 0 )
X {
X right->leftlink = next;
X next->uplink = right;
X right = next;
X next = temp;
X goto one; /* change sides */
X }
X next->leftlink = temp->rightlink;
X if( temp->rightlink != NULL )
X temp->rightlink->uplink = next;
X right->leftlink = temp;
X temp->uplink = right;
X temp->rightlink = next;
X next->uplink = temp;
X right = temp;
X next = temp->leftlink;
X if( next == NULL )
X {
X left->rightlink = NULL;
X goto done; /* job done, entire tree split */
X }
X
X q->enqcmps++;
X
X } while( STRCMP( next->key, key ) > 0 ); /* change sides */
X
X goto one;
X
X done: /* split is done, branches of n need reversal */
X
X temp = n->leftlink;
X n->leftlink = n->rightlink;
X n->rightlink = temp;
X }
X
X return( n );
X
X} /* spenq */
X
X
X/*----------------
X *
X * spdeq() -- return and remove head node from a subtree.
X *
X * remove and return the head node from the node set; this deletes
X * (and returns) the leftmost node from q, replacing it with its right
X * subtree (if there is one); on the way to the leftmost node, rotations
X * are performed to shorten the left branch of the tree
X */
XSPBLK *
Xspdeq( n )
X
Xregister SPBLK * n;
X
X{
X register SPBLK * deq; /* one to return */
X register SPBLK * next; /* the next thing to deal with */
X register SPBLK * left; /* the left child of next */
X register SPBLK * farleft; /* the left child of left */
X register SPBLK * farfarleft; /* the left child of farleft */
X
X if( n == NULL )
X {
X deq = NULL;
X }
X else
X {
X next = n;
X left = next->leftlink;
X if( left == NULL )
X {
X deq = next;
X n = next->rightlink;
X if( n != NULL )
X n->uplink = NULL;
X }
X else for(;;)
X {
X /* next is not it, left is not NULL, might be it */
X farleft = left->leftlink;
X if( farleft == NULL )
X {
X deq = left;
X next->leftlink = left->rightlink;
X if( left->rightlink != NULL )
X left->rightlink->uplink = next;
X break;
X }
X
X /* next, left are not it, farleft is not NULL, might be it */
X farfarleft = farleft->leftlink;
X if( farfarleft == NULL )
X {
X deq = farleft;
X left->leftlink = farleft->rightlink;
X if( farleft->rightlink != NULL )
X farleft->rightlink->uplink = left;
X break;
X }
X
X /* next, left, farleft are not it, rotate */
X next->leftlink = farleft;
X farleft->uplink = next;
X left->leftlink = farleft->rightlink;
X if( farleft->rightlink != NULL )
X farleft->rightlink->uplink = left;
X farleft->rightlink = left;
X left->uplink = farleft;
X next = farleft;
X left = farfarleft;
X }
X }
X
X return( deq );
X
X} /* spdeq */
X
X
X/*----------------
X *
X * spenqprior() -- insert into tree before other equal keys.
X *
X * put n in q before all other nodes with the same key; after this is
X * done, n will be the root of the splay tree representing q, all nodes in
X * q with keys less than that of n will be in the left subtree, all with
X * greater or equal keys will be in the right subtree; the tree is split
X * into these subtrees from the top down, with rotations performed along
X * the way to shorten the left branch of the right subtree and the right
X * branch of the left subtree; the logic of spenqprior is exactly the
X * same as that of spenq except for a substitution of comparison
X * operators
X */
XSPBLK *
Xspenqprior( n, q )
X
Xregister SPBLK * n;
XSPTREE * q;
X
X{
X
X register SPBLK * left; /* the rightmost node in the left tree */
X register SPBLK * right; /* the leftmost node in the right tree */
X register SPBLK * next; /* the root of unsplit part of tree */
X register SPBLK * temp;
X register int Sct; /* Strcmp value */
X register char *key;
X
X n->uplink = NULL;
X next = q->root;
X q->root = n;
X if( next == NULL ) /* trivial enq */
X {
X n->leftlink = NULL;
X n->rightlink = NULL;
X }
X else /* difficult enq */
X {
X key = n->key;
X left = n;
X right = n;
X
X /* n's left and right children will hold the right and left
X splayed trees resulting from splitting on n->key;
X note that the children will be reversed! */
X
X if( STRCMP( next->key, key ) >= 0 )
X goto two;
X
X one: /* assert next->key < key */
X
X do /* walk to the right in the left tree */
X {
X temp = next->rightlink;
X if( temp == NULL )
X {
X left->rightlink = next;
X next->uplink = left;
X right->leftlink = NULL;
X goto done; /* job done, entire tree split */
X }
X if( STRCMP( temp->key, key ) >= 0 )
X {
X left->rightlink = next;
X next->uplink = left;
X left = next;
X next = temp;
X goto two; /* change sides */
X }
X next->rightlink = temp->leftlink;
X if( temp->leftlink != NULL )
X temp->leftlink->uplink = next;
X left->rightlink = temp;
X temp->uplink = left;
X temp->leftlink = next;
X next->uplink = temp;
X left = temp;
X next = temp->rightlink;
X if( next == NULL )
X {
X right->leftlink = NULL;
X goto done; /* job done, entire tree split */
X }
X
X } while( STRCMP( next->key, key ) < 0 ); /* change sides */
X
X two: /* assert next->key >= key */
X
X do /* walk to the left in the right tree */
X {
X temp = next->leftlink;
X if( temp == NULL )
X {
X right->leftlink = next;
X next->uplink = right;
X left->rightlink = NULL;
X goto done; /* job done, entire tree split */
X }
X if( STRCMP( temp->key, key ) < 0 )
X {
X right->leftlink = next;
X next->uplink = right;
X right = next;
X next = temp;
X goto one; /* change sides */
X }
X next->leftlink = temp->rightlink;
X if( temp->rightlink != NULL )
X temp->rightlink->uplink = next;
X right->leftlink = temp;
X temp->uplink = right;
X temp->rightlink = next;
X next->uplink = temp;
X right = temp;
X next = temp->leftlink;
X if( next == NULL )
X {
X left->rightlink = NULL;
X goto done; /* job done, entire tree split */
X }
X
X } while( STRCMP( next->key, key ) >= 0 ); /* change sides */
X
X goto one;
X
X done: /* split is done, branches of n need reversal */
X
X temp = n->leftlink;
X n->leftlink = n->rightlink;
X n->rightlink = temp;
X }
X
X return( n );
X
X} /* spenqprior */
X
X/*----------------
X *
X * splay() -- reorganize the tree.
X *
X * the tree is reorganized so that n is the root of the
X * splay tree representing q; results are unpredictable if n is not
X * in q to start with; q is split from n up to the old root, with all
X * nodes to the left of n ending up in the left subtree, and all nodes
X * to the right of n ending up in the right subtree; the left branch of
X * the right subtree and the right branch of the left subtree are
X * shortened in the process
X *
X * this code assumes that n is not NULL and is in q; it can sometimes
X * detect n not in q and complain
X */
X
Xvoid
Xsplay( n, q )
X
Xregister SPBLK * n;
XSPTREE * q;
X
X{
X register SPBLK * up; /* points to the node being dealt with */
X register SPBLK * prev; /* a descendent of up, already dealt with */
X register SPBLK * upup; /* the parent of up */
X register SPBLK * upupup; /* the grandparent of up */
X register SPBLK * left; /* the top of left subtree being built */
X register SPBLK * right; /* the top of right subtree being built */
X
X left = n->leftlink;
X right = n->rightlink;
X prev = n;
X up = prev->uplink;
X
X q->splays++;
X
X while( up != NULL )
X {
X q->splayloops++;
X
X /* walk up the tree towards the root, splaying all to the left of
X n into the left subtree, all to right into the right subtree */
X
X upup = up->uplink;
X if( up->leftlink == prev ) /* up is to the right of n */
X {
X if( upup != NULL && upup->leftlink == up ) /* rotate */
X {
X upupup = upup->uplink;
X upup->leftlink = up->rightlink;
X if( upup->leftlink != NULL )
X upup->leftlink->uplink = upup;
X up->rightlink = upup;
X upup->uplink = up;
X if( upupup == NULL )
X q->root = up;
X else if( upupup->leftlink == upup )
X upupup->leftlink = up;
X else
X upupup->rightlink = up;
X up->uplink = upupup;
X upup = upupup;
X }
X up->leftlink = right;
X if( right != NULL )
X right->uplink = up;
X right = up;
X
X }
X else /* up is to the left of n */
X {
X if( upup != NULL && upup->rightlink == up ) /* rotate */
X {
X upupup = upup->uplink;
X upup->rightlink = up->leftlink;
X if( upup->rightlink != NULL )
X upup->rightlink->uplink = upup;
X up->leftlink = upup;
X upup->uplink = up;
X if( upupup == NULL )
X q->root = up;
X else if( upupup->rightlink == upup )
X upupup->rightlink = up;
X else
X upupup->leftlink = up;
X up->uplink = upupup;
X upup = upupup;
X }
X up->rightlink = left;
X if( left != NULL )
X left->uplink = up;
X left = up;
X }
X prev = up;
X up = upup;
X }
X
X# ifdef DEBUG
X if( q->root != prev )
X {
X/* fprintf(stderr, " *** bug in splay: n not in q *** " ); */
X abort();
X }
X# endif
X
X n->leftlink = left;
X n->rightlink = right;
X if( left != NULL )
X left->uplink = n;
X if( right != NULL )
X right->uplink = n;
X q->root = n;
X n->uplink = NULL;
X
X} /* splay */
X
SHAR_EOF
if test -f 'sptree.h'
then
echo shar: over-writing existing file "'sptree.h'"
fi
sed 's/^X//' << \SHAR_EOF > 'sptree.h'
X/*
X** sptree.h: The following type declarations provide the binary tree
X** representation of event-sets or priority queues needed by splay trees
X**
X** assumes that data and datb will be provided by the application
X** to hold all application specific information
X**
X** assumes that key will be provided by the application, comparable
X** with the compare function applied to the addresses of two keys.
X*/
X
X# ifndef SPTREE_H
X# define SPTREE_H
X
X# ifndef NULL
X# define NULL 0
X# endif
X
X# define STRCMP( a, b ) ( (Sct = *(a) - *(b)) ? Sct : strcmp( (a), (b) ) )
X
Xtypedef struct _spblk SPBLK;
X
Xtypedef struct _spblk
X{
X SPBLK * leftlink;
X SPBLK * rightlink;
X SPBLK * uplink;
X
X char * key; /* formerly time/timetyp */
X char * data; /* formerly aux/auxtype */
X char * datb;
X};
X
Xtypedef struct
X{
X SPBLK * root; /* root node */
X
X /* Statistics, not strictly necessary, but handy for tuning */
X
X int lookups; /* number of splookup()s */
X int lkpcmps; /* number of lookup comparisons */
X
X int enqs; /* number of spenq()s */
X int enqcmps; /* compares in spenq */
X
X int splays;
X int splayloops;
X
X} SPTREE;
X
X
X/* sptree.c */
Xextern SPTREE * spinit(); /* init tree */
Xextern int spempty(); /* is tree empty? */
Xextern SPBLK * spenq(); /* insert item into the tree */
Xextern SPBLK * spdeq(); /* return and remove lowest item in subtree */
Xextern SPBLK * spenqprior(); /* insert before items with same key */
Xextern void splay(); /* reorganize tree */
X
X/* spaux.c */
Xextern SPBLK * sphead(); /* return first node in tree */
Xextern void spdelete(); /* delete node from tree */
Xextern SPBLK * spnext(); /* return next node in tree */
Xextern SPBLK * spprev(); /* return previous node in tree */
Xextern SPBLK * spenqbefore(); /* enqueue before existing node */
Xextern SPBLK * spenqafter(); /* enqueue after existing node */
X
X/* spdaveb.c */
Xextern SPBLK * splookup(); /* find key in a tree */
Xextern SPBLK * spinstall(); /* enter an item, allocating or replacing */
Xextern SPBLK * sptail(); /* find end of a tree */
Xextern void spscan(); /* scan forward through tree */
Xextern void sprscan(); /* reverse scan through tree */
Xextern SPBLK * spfnext(); /* fast non-splaying next */
Xextern SPBLK * spfprev(); /* fast non-splaying prev */
X
X# endif
SHAR_EOF
# End of shell archive
exit 0