daveb@ingres.com (When a problem comes along . . . you must whip it) (09/26/90)
In article <2430@ns-mx.uiowa.edu> jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) writes: > >Dave Brower of Sun Microsystems transliterated my Pascal version of splay >trees to C some time ago, and an early version of his transliteration is >in the Gnu C++ library. Unfortunately, that version has a bug (it won't >delete the last item from a tree!) but I gather it's been fairly widely >used with no complaints (because few people delete randomly in a tree, I >guess). > > Doug Jones > jones@herky.cs.uiowa.edu These bugs have been fixed in the version I've been sending out since 1988. No teasing, source enclosed below. It's amazing the way old versions refuse to die. Thanks to Doug and Mark Moraes. -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: # sptree.3 # spaux.c # spdaveb.c # sptree.c # sptree.h # testsp.c # This archive created: Wed Sep 26 09:02:14 1990 # By: When a problem comes along . . . you must whip it () export PATH; PATH=/bin:/usr/bin:$PATH if test -f 'sptree.3' then echo shar: "will not over-write existing file 'sptree.3'" else sed 's/^X//' << \SHAR_EOF > 'sptree.3' X XTH 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(np) X.B SPBLK **np; 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. XIt was translated to C with some new functions by Dave Brower X(daveb@rtech.uucp). Bug fixes by Mark Moraes X(moraes@csri.toronto.edu) are gratefully appreciated. 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 fi if test -f 'spaux.c' then echo shar: "will not over-write existing file 'spaux.c'" else 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 Thu Oct 6 12:11:33 PDT 1988 (daveb) Fixed spdeq, which was broken X handling one-node trees. I botched the pascal translation of X a VAR parameter. Changed interface, so callers must also be X corrected to pass the node by address rather than value. X Mon Apr 3 15:18:32 PDT 1989 (daveb) X Apply fix supplied by Mark Moraes <moraes@csri.toronto.edu> to X spdelete(), which dropped core when taking out the last element X in a subtree -- that is, when the right subtree was empty and X the leftlink was also null, it tried to take out the leftlink's X uplink anyway. 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 if (q->root) 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 fi if test -f 'spdaveb.c' then echo shar: "will not over-write existing file 'spdaveb.c'" else 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 n->cnt = 0; 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 fi if test -f 'sptree.c' then echo shar: "will not over-write existing file 'sptree.c'" else 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( np ) Return first key under *np, 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 * Thu Oct 6 12:11:33 PDT 1988 (daveb) Fixed spdeq, which was broken X * handling one-node trees. I botched the pascal translation of X * a VAR parameter. 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 n->cnt++; 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( np ) X XSPBLK **np; /* pointer to a node pointer */ 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( np == NULL || *np == NULL ) X { X deq = NULL; X } X else X { X next = *np; X left = next->leftlink; X if( left == NULL ) X { X deq = next; X *np = next->rightlink; X X if( *np != NULL ) X (*np)->uplink = NULL; X X } X else for(;;) /* left is not null */ 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 n->cnt++; /* bump reference count */ 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 fi if test -f 'sptree.h' then echo shar: "will not over-write existing file 'sptree.h'" else 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 int cnt; 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 * spfhead(); /* fast non-splaying head */ Xextern SPBLK * spfnext(); /* fast non-splaying next */ Xextern SPBLK * spfprev(); /* fast non-splaying prev */ X X# endif SHAR_EOF fi if test -f 'testsp.c' then echo shar: "will not over-write existing file 'testsp.c'" else sed 's/^X//' << \SHAR_EOF > 'testsp.c' X/* XFrom moraes@csri.toronto.edu Mon Apr 3 15:16:23 1989 XFrom: Mark Moraes <moraes@csri.toronto.edu> XTo: daveb@rtech.uucp XSubject: small fix for sptree XDate: Mon, 3 Apr 89 02:18:23 EDT X XHi. X XI enclose a diff to fix a problem in spaux.c, without which it dumps Xcode when deleting an item. X XI also enclose a little example program I used to test some of the Xtree functions. (not the queue ones though) Do you have a better test? X X[ nope. I'll use/hack the one he gave me -dB ] X*/ X X#include <stdio.h> X#define MAXSTR 512 X X#include "sptree.h" X Xchar * Xstrsave( s ) Xchar *s; X{ X char *emalloc(); X char *strcpy(); X return ( strcpy( emalloc( strlen(s) + 1 ), s ) ); X} X Xchar * Xemalloc(n) Xint n; X{ X char *malloc(); X char *p = malloc( n ); X if( p ) X return( p ); X X fprintf(stderr, "emalloc: can't allocate %d bytes\n", n ); X perror("possible cause"); X exit( 1 ); X /*NOTREACHED*/ X} X X X#define prompt() if(prompt_p) printf("testsp>"); else ; X Xmain() X{ X char buf[MAXSTR]; X char s1[8], s2[MAXSTR], s3[MAXSTR]; X SPBLK *result; X int prompt_p; X SPTREE *sp; X int prnode(); X X sp = spinit(); X prompt_p = isatty(fileno(stdin)); X prompt(); X while(fgets(buf, sizeof(buf), stdin) != NULL) { X sscanf(buf, " %s %s", s1, s2); X switch (*s1) { X case 'a': X sscanf(buf, " %*s %*s %s", s3); X spinstall(strsave(s2), strsave(s3), NULL, sp); X break; X case 's': X if ((result = splookup(s2, sp)) != NULL) X printf("found %s\n", result->data); X else X printf("no match\n"); X break; X case 'd': X if ((result = splookup(s2, sp)) != NULL) X spdelete(result, sp); X else X printf("no match\n"); X break; X case 'l': X spscan(prnode, NULL, sp); X break; X case 'p': X spshow(sp); X break; X case 'q': X exit( 0 ); X break; X default: X printf( X "'a string1 string2' inserts datum (string2) keyed by string1\n"); X printf( X "'d string1' deletes the datum associated with string1 if any\n"); X printf( X "'s string1' prints the datum associated with string1 if any\n"); X printf( X "'l' lists the elements of the tree in spscan() order\n"); X printf( X "'p' prints the shape and contents of the tree with spshow()\n"); X break; X } X prompt(); X } X printf("\n"); X#ifdef PRINT X printf("Stats = %s\n", spstats(sp)); X#endif X} X Xint Xprnode(spblk) XSPBLK *spblk; X{ X printf("Key = \"%s\", Data = \"%s\"\n", spblk->key, spblk->data); X} X SHAR_EOF fi exit 0 # End of shell archive -- "VMS is a text-only adventure game. If you win you can use unix." - w.davidson David Brower: {amdahl, cpsc6a, mtxinu, sun}!rtech!daveb daveb@ingres.com