home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume14 / splay-tree / spdaveb.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-05-08  |  5.8 KB  |  333 lines
  1. /*
  2.  * spdaveb.c -- daveb's new splay tree functions.
  3.  *
  4.  * The functions in this file provide an interface that is nearly
  5.  * the same as the hash library I swiped from mkmf, allowing
  6.  * replacement of one by the other.  Hey, it worked for me!
  7.  *
  8.  * splookup() -- given a key, find a node in a tree.
  9.  * spinstall() -- install an item in the tree, overwriting existing value.
  10.  * spfhead() -- fast (non-splay) find the first node in a tree.
  11.  * spftail() -- fast (non-splay) find the last node in a tree.
  12.  * spscan() -- forward scan tree from the head.
  13.  * sprscan() -- reverse scan tree from the tail.
  14.  * spfnext() -- non-splaying next.
  15.  * spfprev() -- non-splaying prev.
  16.  * spstats() -- make char string of stats for a tree.
  17.  *
  18.  * Written by David Brower, daveb@rtech.uucp 1/88.
  19.  */
  20.  
  21.  
  22. # include "sptree.h"
  23.  
  24. /* USER SUPPLIED! */
  25.  
  26. extern char *emalloc();
  27.  
  28.  
  29. /*----------------
  30.  *
  31.  * splookup() -- given key, find a node in a tree.
  32.  *
  33.  *    Splays the found node to the root.
  34.  */
  35. SPBLK *
  36. splookup( key, q )
  37.  
  38. register char * key;
  39. register SPTREE * q;
  40.  
  41. {
  42.     register SPBLK * n;
  43.     register int Sct;
  44.     register int c;
  45.  
  46.     /* find node in the tree */
  47.     n = q->root;
  48.     c = ++(q->lkpcmps);
  49.     q->lookups++;
  50.     while( n && (Sct = STRCMP( key, n->key ) ) )
  51.     {
  52.     c++;
  53.     n = ( Sct < 0 ) ? n->leftlink : n->rightlink;
  54.     }
  55.     q->lkpcmps = c;
  56.  
  57.     /* reorganize tree around this node */
  58.     if( n != NULL )
  59.     splay( n, q );
  60.  
  61.     return( n );
  62. }
  63.  
  64.  
  65.  
  66. /*----------------
  67.  *
  68.  * spinstall() -- install an entry in a tree, overwriting any existing node.
  69.  *
  70.  *    If the node already exists, replace its contents.
  71.  *    If it does not exist, then allocate a new node and fill it in.
  72.  */
  73.  
  74. SPBLK *
  75. spinstall( key, data, datb, q )
  76.  
  77. register char * key;
  78. register char * data;
  79. register char * datb;
  80. register SPTREE *q;
  81.  
  82. {
  83.     register SPBLK *n;
  84.  
  85.     if( NULL == ( n = splookup( key, q ) ) )
  86.     {
  87.     n = (SPBLK *) emalloc( sizeof( *n ) );
  88.     n->key = key;
  89.     n->leftlink = NULL;
  90.     n->rightlink = NULL;
  91.     n->uplink = NULL;
  92.     spenq( n, q );
  93.     }
  94.  
  95.     n->data = data;
  96.     n->datb = datb;
  97.  
  98.     return( n );
  99. }
  100.  
  101.  
  102.  
  103.  
  104. /*----------------
  105.  *
  106.  * spfhead() --    return the "lowest" element in the tree.
  107.  *
  108.  *    returns a reference to the head event in the event-set q.
  109.  *    avoids splaying but just searches for and returns a pointer to
  110.  *    the bottom of the left branch.
  111.  */
  112. SPBLK *
  113. spfhead( q )
  114.  
  115. register SPTREE * q;
  116.  
  117. {
  118.     register SPBLK * x;
  119.  
  120.     if( NULL != ( x = q->root ) )
  121.     while( x->leftlink != NULL )
  122.         x = x->leftlink;
  123.  
  124.     return( x );
  125.  
  126. } /* spfhead */
  127.  
  128.  
  129.  
  130.  
  131. /*----------------
  132.  *
  133.  * spftail() -- find the last node in a tree.
  134.  *
  135.  *    Fast version does not splay result or intermediate steps.
  136.  */
  137. SPBLK *
  138. spftail( q )
  139.  
  140. SPTREE * q;
  141.  
  142. {
  143.     register SPBLK * x;
  144.  
  145.  
  146.     if( NULL != ( x = q->root ) )
  147.     while( x->rightlink != NULL )
  148.         x = x->rightlink;
  149.  
  150.     return( x );
  151.  
  152. } /* spftail */
  153.  
  154.  
  155. /*----------------
  156.  *
  157.  * spscan() -- apply a function to nodes in ascending order.
  158.  *
  159.  *    if n is given, start at that node, otherwise start from
  160.  *    the head.
  161.  */
  162. void
  163. spscan( f, n, q )
  164.  
  165. register int (*f)();
  166. register SPBLK * n;
  167. register SPTREE * q;
  168.  
  169. {
  170.     register SPBLK * x;
  171.  
  172.     for( x = n != NULL ? n : spfhead( q ); x != NULL ; x = spfnext( x ) )
  173.         (*f)( x );
  174. }
  175.  
  176.  
  177.  
  178. /*----------------
  179.  *
  180.  * sprscan() -- apply a function to nodes in descending order.
  181.  *
  182.  *    if n is given, start at that node, otherwise start from
  183.  *    the tail.
  184.  */
  185. void
  186. sprscan( f, n, q )
  187.  
  188. register int (*f)();
  189. register SPBLK * n;
  190. register SPTREE * q;
  191.  
  192. {
  193.     register SPBLK *x;
  194.  
  195.     for( x = n != NULL ? n : spftail( q ); x != NULL ; x = spfprev( x ) )
  196.         (*f)( x );
  197. }
  198.  
  199.  
  200.  
  201. /*----------------
  202.  *
  203.  * spfnext() -- fast return next higer item in the tree, or NULL.
  204.  *
  205.  *    return the successor of n in q, represented as a splay tree.
  206.  *    This is a fast (on average) version that does not splay.
  207.  */
  208. SPBLK *
  209. spfnext( n )
  210.  
  211. register SPBLK * n;
  212.  
  213. {
  214.     register SPBLK * next;
  215.     register SPBLK * x;
  216.  
  217.     /* a long version, avoids splaying for fast average,
  218.      * poor amortized bound
  219.      */
  220.  
  221.     if( n == NULL )
  222.         return( n );
  223.  
  224.     x = n->rightlink;
  225.     if( x != NULL )
  226.     {
  227.         while( x->leftlink != NULL )
  228.         x = x->leftlink;
  229.         next = x;
  230.     }
  231.     else    /* x == NULL */
  232.     {
  233.         x = n->uplink;
  234.         next = NULL;
  235.         while( x != NULL )
  236.     {
  237.             if( x->leftlink == n )
  238.         {
  239.                 next = x;
  240.                 x = NULL;
  241.             }
  242.         else
  243.         {
  244.                 n = x;
  245.                 x = n->uplink;
  246.             }
  247.         }
  248.     }
  249.  
  250.     return( next );
  251.  
  252. } /* spfnext */
  253.  
  254.  
  255.  
  256. /*----------------
  257.  *
  258.  * spfprev() -- return fast previous node in a tree, or NULL.
  259.  *
  260.  *    return the predecessor of n in q, represented as a splay tree.
  261.  *    This is a fast (on average) version that does not splay.
  262.  */
  263. SPBLK *
  264. spfprev( n )
  265.  
  266. register SPBLK * n;
  267.  
  268. {
  269.     register SPBLK * prev;
  270.     register SPBLK * x;
  271.  
  272.     /* a long version,
  273.      * avoids splaying for fast average, poor amortized bound
  274.      */
  275.  
  276.     if( n == NULL )
  277.         return( n );
  278.  
  279.     x = n->leftlink;
  280.     if( x != NULL )
  281.     {
  282.         while( x->rightlink != NULL )
  283.         x = x->rightlink;
  284.         prev = x;
  285.     }
  286.     else
  287.     {
  288.         x = n->uplink;
  289.         prev = NULL;
  290.         while( x != NULL )
  291.     {
  292.             if( x->rightlink == n )
  293.         {
  294.                 prev = x;
  295.                 x = NULL;
  296.             }
  297.         else
  298.         {
  299.                 n = x;
  300.                 x = n->uplink;
  301.             }
  302.         }
  303.     }
  304.  
  305.     return( prev );
  306.  
  307. } /* spfprev */
  308.  
  309.  
  310.  
  311. char *
  312. spstats( q )
  313. SPTREE *q;
  314. {
  315.     static char buf[ 128 ];
  316.     float llen;
  317.     float elen;
  318.     float sloops;
  319.  
  320.     if( q == NULL )
  321.     return("");
  322.  
  323.     llen = q->lookups ? (float)q->lkpcmps / q->lookups : 0;
  324.     elen = q->enqs ? (float)q->enqcmps/q->enqs : 0;
  325.     sloops = q->splays ? (float)q->splayloops/q->splays : 0;
  326.  
  327.     sprintf(buf, "f(%d %4.2f) i(%d %4.2f) s(%d %4.2f)",
  328.     q->lookups, llen, q->enqs, elen, q->splays, sloops );
  329.  
  330.     return buf;
  331. }
  332.  
  333.