home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Usenet 1994 October
/
usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso
/
unix
/
volume14
/
splay-tree
/
spdaveb.c
< prev
next >
Wrap
C/C++ Source or Header
|
1988-05-08
|
6KB
|
333 lines
/*
* spdaveb.c -- daveb's new splay tree functions.
*
* The functions in this file provide an interface that is nearly
* the same as the hash library I swiped from mkmf, allowing
* replacement of one by the other. Hey, it worked for me!
*
* splookup() -- given a key, find a node in a tree.
* spinstall() -- install an item in the tree, overwriting existing value.
* spfhead() -- fast (non-splay) find the first node in a tree.
* spftail() -- fast (non-splay) find the last node in a tree.
* spscan() -- forward scan tree from the head.
* sprscan() -- reverse scan tree from the tail.
* spfnext() -- non-splaying next.
* spfprev() -- non-splaying prev.
* spstats() -- make char string of stats for a tree.
*
* Written by David Brower, daveb@rtech.uucp 1/88.
*/
# include "sptree.h"
/* USER SUPPLIED! */
extern char *emalloc();
/*----------------
*
* splookup() -- given key, find a node in a tree.
*
* Splays the found node to the root.
*/
SPBLK *
splookup( key, q )
register char * key;
register SPTREE * q;
{
register SPBLK * n;
register int Sct;
register int c;
/* find node in the tree */
n = q->root;
c = ++(q->lkpcmps);
q->lookups++;
while( n && (Sct = STRCMP( key, n->key ) ) )
{
c++;
n = ( Sct < 0 ) ? n->leftlink : n->rightlink;
}
q->lkpcmps = c;
/* reorganize tree around this node */
if( n != NULL )
splay( n, q );
return( n );
}
/*----------------
*
* spinstall() -- install an entry in a tree, overwriting any existing node.
*
* If the node already exists, replace its contents.
* If it does not exist, then allocate a new node and fill it in.
*/
SPBLK *
spinstall( key, data, datb, q )
register char * key;
register char * data;
register char * datb;
register SPTREE *q;
{
register SPBLK *n;
if( NULL == ( n = splookup( key, q ) ) )
{
n = (SPBLK *) emalloc( sizeof( *n ) );
n->key = key;
n->leftlink = NULL;
n->rightlink = NULL;
n->uplink = NULL;
spenq( n, q );
}
n->data = data;
n->datb = datb;
return( n );
}
/*----------------
*
* spfhead() -- return the "lowest" element in the tree.
*
* returns a reference to the head event in the event-set q.
* avoids splaying but just searches for and returns a pointer to
* the bottom of the left branch.
*/
SPBLK *
spfhead( q )
register SPTREE * q;
{
register SPBLK * x;
if( NULL != ( x = q->root ) )
while( x->leftlink != NULL )
x = x->leftlink;
return( x );
} /* spfhead */
/*----------------
*
* spftail() -- find the last node in a tree.
*
* Fast version does not splay result or intermediate steps.
*/
SPBLK *
spftail( q )
SPTREE * q;
{
register SPBLK * x;
if( NULL != ( x = q->root ) )
while( x->rightlink != NULL )
x = x->rightlink;
return( x );
} /* spftail */
/*----------------
*
* spscan() -- apply a function to nodes in ascending order.
*
* if n is given, start at that node, otherwise start from
* the head.
*/
void
spscan( f, n, q )
register int (*f)();
register SPBLK * n;
register SPTREE * q;
{
register SPBLK * x;
for( x = n != NULL ? n : spfhead( q ); x != NULL ; x = spfnext( x ) )
(*f)( x );
}
/*----------------
*
* sprscan() -- apply a function to nodes in descending order.
*
* if n is given, start at that node, otherwise start from
* the tail.
*/
void
sprscan( f, n, q )
register int (*f)();
register SPBLK * n;
register SPTREE * q;
{
register SPBLK *x;
for( x = n != NULL ? n : spftail( q ); x != NULL ; x = spfprev( x ) )
(*f)( x );
}
/*----------------
*
* spfnext() -- fast return next higer item in the tree, or NULL.
*
* return the successor of n in q, represented as a splay tree.
* This is a fast (on average) version that does not splay.
*/
SPBLK *
spfnext( n )
register SPBLK * n;
{
register SPBLK * next;
register SPBLK * x;
/* a long version, avoids splaying for fast average,
* poor amortized bound
*/
if( n == NULL )
return( n );
x = n->rightlink;
if( x != NULL )
{
while( x->leftlink != NULL )
x = x->leftlink;
next = x;
}
else /* x == NULL */
{
x = n->uplink;
next = NULL;
while( x != NULL )
{
if( x->leftlink == n )
{
next = x;
x = NULL;
}
else
{
n = x;
x = n->uplink;
}
}
}
return( next );
} /* spfnext */
/*----------------
*
* spfprev() -- return fast previous node in a tree, or NULL.
*
* return the predecessor of n in q, represented as a splay tree.
* This is a fast (on average) version that does not splay.
*/
SPBLK *
spfprev( n )
register SPBLK * n;
{
register SPBLK * prev;
register SPBLK * x;
/* a long version,
* avoids splaying for fast average, poor amortized bound
*/
if( n == NULL )
return( n );
x = n->leftlink;
if( x != NULL )
{
while( x->rightlink != NULL )
x = x->rightlink;
prev = x;
}
else
{
x = n->uplink;
prev = NULL;
while( x != NULL )
{
if( x->rightlink == n )
{
prev = x;
x = NULL;
}
else
{
n = x;
x = n->uplink;
}
}
}
return( prev );
} /* spfprev */
char *
spstats( q )
SPTREE *q;
{
static char buf[ 128 ];
float llen;
float elen;
float sloops;
if( q == NULL )
return("");
llen = q->lookups ? (float)q->lkpcmps / q->lookups : 0;
elen = q->enqs ? (float)q->enqcmps/q->enqs : 0;
sloops = q->splays ? (float)q->splayloops/q->splays : 0;
sprintf(buf, "f(%d %4.2f) i(%d %4.2f) s(%d %4.2f)",
q->lookups, llen, q->enqs, elen, q->splays, sloops );
return buf;
}