Source Code 1992 March/Source_Code_CD-ROM_Walnut_Creek_March_1992.iso/usenet/altsrcs/1/1868/sptree.3

Text File | 1990-12-28 | 7.5 KB | 373 lines

TH SPTREE 3  "10 February 1988"
.UC 4
.SH NAME
spdelete, spdeq, spempty, spenq, spenqafter, spenqbefore, spenqprior,
spfhead, spfnext, spfprev, spftail, sphead, spinit, spinstall, splay,
splookup, spnext, spprev, sprscan, spscan, spstats \- splay tree operations
.SH SYNOPSIS
.nf
.B #include "sptree.h"
.PP
.B void spdelete(n, q)
.B SPBLK *n;
.B SPTREE *q;
.PP
.B SPBLK *spdeq(np)
.B SPBLK **np;
.PP
.B int spempty(q)
.B SPTREE *q;
.PP
.B SPBLK *spenq(n, q)
.B SPBLK *n;
.B SPTREE *q;
.PP
.B SPBLK *spenqafter(n, n1, q)
.B SPBLK *n, *n1;
.B SPTREE *q;
.PP
.B SPBLK *spenqbefore(n, n1, q)
.B SPBLK *n, *n1;
.B SPTREE *q;
.PP
.B SPBLK *spenqprior(n, q)
.B SPBLK *n;
.B SPTREE *q;
.PP
.B SPBLK *spfhead(q)
.B SPTREE *q;
.PP
.B SPBLK *spfnext(n)
.B SPBLK *n;
.PP
.B SPBLK *spfprev(n)
.B SPBLK *n;
.PP
.B SPBLK *spftail(q)
.B SPTREE *q;
.PP
.B SPBLK *sphead(q)
.B SPTREE *q;
.PP
.B SPTREE *spinit();
.PP
.B SPBLK *spinstall(key, data, datb, q)
.B char *key, *data, *datb;
.B SPTREE *q;
.PP
.B void splay(n, q)
.B SPBLK *n;
.B SPTREE *q;
.PP
.B SPBLK *splookup(key, q)
.B char *key;
.B SPTREE *q;
.PP
.B SPBLK *spnext(n, q)
.B SPBLK *n;
.B SPTREE *q;
.PP
.B SPBLK *spprev(n, q)
.B SPBLK *n;
.B SPTREE *q;
.PP
.B void sprscan(f, n, q)
.B int (*f)();
.B SPBLK *n;
.B SPTREE *q;
.PP
.B void spscan(f, n, q)
.B int (*f)();
.B SPBLK *n;
.B SPTREE *q;
.PP
.B char *spstats(q)
.B SPTREE *q;
.PP
.fi
.SH DESCRIPTION
These functions operate on an event\-set or priority\-queue implemented
using splay trees.  These are similar to avl\-trees, but are not
concerned with keeping the tree strictly balanced.  Instead, the tree is
dynamically reorganized in a simple way that yields a good amortized
bound at the expense of worst case performance.
.PP
The SPTREE structure declared in sptree.h should only be handled
indirectly.  A pointer to an SPTREE is returned by
.I spinit
and should be handed blindly to other access functions.
.PP
The nodes in a splay tree are defined by the following structure,
declared in sptree.h.
.PP
.nf
typedef struct _spblk SPBLK;
typedef struct _spblk
{
    .
    .
    .

    char    *key;
    char    *data;
    char    *datb;
};
.fi
.PP
You should only refer to the
.I key,
.I data
and
.I datb
members.
.PP
The
.I key
is interpreted as a pointer to a null terminated string, and ordering is
determined by calls to the usual
.I strcmp
routine.
.PP
No meaning is associated with the auxiliary members
.I data
or
.I datb,
and you are free to stuff them with whatever good conscience and a legal
cast will allow.
.PP
.I Spdelete
deletes the node
.I n
from the tree
.I q.
The resulting tree is splayed around a new root, which is the successor
to
.I n.
.PP
.I Spdeq
removes and returns the head node from the sub\-tree rooted at node
.I n.
.PP
.I Spempty
returns non\-zero if the tree
.I q
has no members.
.PP
.I Spenq
inserts node
.I n
into tree
.I q
after all other nodes with the same key.  When this is done,
.I n
will be the root of the tree.
.PP
.I Spenqafter
inserts node
.I n
as the immediate sucessor of node
.I n1
in tree
.I q.
In so doing,
.I n1
becomes the root of the tree with
.I n
as its right son.
.PP
.I Spenqbefore
inserts node
.I n
as the immediate predecessor of node
.I n1
in tree
.I q.
In doing so,
.I n1
becomes the root of the tree with
.I n
as its left son.
.PP
.I Spenqprior
inserts node
.I n
into the tree
.I q
before all other nodes with the same key; after this is done,
.I n
will be the root of the tree.
.PP
.I Spfhead
returns a pointer to the head element in the tree
.I q,
but does not splay it to the root.
.PP
.I Spfnext
returns a pointer to the immediate successor of node
.I n
without doing any reorganization.
.PP
.I Spfprev
returns a pointer to the immediate predecessor of node
.I n
without doing any reoganization.
.PP
.I Spftail
returns a reference to the last node in the tree
.I q
without doing any reorganization.
.PP
.I Sphead
returns a pointer to the head event in the tree
.I q.
The returned node is made the root of the tree, as if
.I q
had been splayed around
.I n.
.PP
.I Spinit
creates a new splay tree using a \fImalloc\fP\-like routine named
.I emalloc
that must be supplied by the user.
.PP
.I Spinstall
inserts an entry with the key value pointed to by
.I key
with the auxiliary values
.I data
and
.I datb
into the tree
.I q.
If a node with the key value already exists, its auxiliarly values are
replaced.  If the node does not already exist, a new one is allocated
with \fImalloc\fP\-like function named
.I emalloc
that must be supplied by the user.
.PP
.I Splay
reorganizes the tree so that node
.I n
becomes the root of the tree in
.I q.
Results are unpredicatable if
.I n
is not in
.I q
to start with.
.I Q
is split from
.I n
up to the old root, with all nodes to the left of
.I n
ending up in the left sub\-tree, and all nodes to the right of
.I n
ending up in the right sub\-tree.  The left branch of the right
sub\-tree and the right branch of the left sub\-tree are shortened in
the process.
.PP
.I Splookup
searches for a node containing the key value pointed to by
.I key
in the tree
.I q.
A found node is splayed to the root and returned.  If the key is not
found, the function returns NULL and no reorganization is done.
.PP
.I
Spnext returns a pointer to the successor of
.I n
in
.I q.
The successor becomes the root of the tree.
.PP
.I Spprev
returns the predecessor of
.I n
in
.I q.
The predecessor becomes the root.
.PP
.I Sprscan
applies the function
.I f
starting at node
.I n
to the members of the tree
.I q
in reverse order.  If
.I n
is NULL, then the scan starts at the tail of the tree.  The tree is not
reorganized during the reverse scan.  The function is called with one
argument, a pointer to an SPBLK.  Its return value is ignored.
.PP
.I Spscan
applies the function
.I f
starting at node
.I n
in tree
.I q
and all successive nodes, in order.  If
.I n
is NULL, then the scan starts at the head of the tree.  The tree is not
reorganized during the scan.  The function is called with one argument,
a pointer to an SPBLK.  Its return value is ignored.
.PP
.I Spstats
returns a string of statistics on the activities in the tree
.I q.
It shows how many times
.I splookup
was called, and how many comparisons were needed per call,
the number of nodes that have been added with
.I spenq
and the number of comparisons needed per call, and finally, the number
of
.I splay
operations performed, and the number of loops done in each splay.  These
statistics give an indication of the average effective depth of the tree
for various operations.  The function returns a pointer to a static
buffer that is overwritten with each call.
.SH AUTHORS
The code was originally written in Pascal by Douglas W. Jones
([e-mail]) with assistance from Srinivas R. Sataluri.
It was translated to C with some new functions by Dave Brower
([e-mail]).  Bug fixes by Mark Moraes
([e-mail]) are gratefully appreciated.
.SH REFERENCES
The basic splay tree algorithms were originally presented in:
.PP
.nf
  Self Adjusting Binary Trees,
  by D. D. Sleator and R. E. Tarjan,
  Proc. ACM SIGACT Symposium on Theory
  of Computing (Boston, Apr 1983) 235-245.
.fi
.PP
More operations on priority queues were added to help support discrete
event simulation.  See, for example Chapter 14 of
.PP
.nf
  Introduction to Simula 67,
  by Gunther Lamprecht,
  Vieweg & Sohn, Braucschweig, Wiesbaden, 1981.
.fi
.PP
and Chapter 9 of
.PP
.nf
  Simula Begin,
  by Graham M. Birtwistle, et al,
  Studentlitteratur, Lund, 1979.
.fi
.PP
Splay trees are compared with other data structures in
.PP
.nf
  An Empirical Comparison of Priority-Queue and Event-Set Implementations,
  by Douglas W. Jones,
  Comm. ACM 29, 4 (Apr. 1986) 300-311.
.fi