home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1868 / spdaveb.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-12-28  |  5.8 KB  |  334 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.     n->cnt = 0;
  93.     spenq( n, q );
  94.     }
  95.  
  96.     n->data = data;
  97.     n->datb = datb;
  98.  
  99.     return( n );
  100. }
  101.  
  102.  
  103.  
  104.  
  105. /*----------------
  106.  *
  107.  * spfhead() --    return the "lowest" element in the tree.
  108.  *
  109.  *    returns a reference to the head event in the event-set q.
  110.  *    avoids splaying but just searches for and returns a pointer to
  111.  *    the bottom of the left branch.
  112.  */
  113. SPBLK *
  114. spfhead( q )
  115.  
  116. register SPTREE * q;
  117.  
  118. {
  119.     register SPBLK * x;
  120.  
  121.     if( NULL != ( x = q->root ) )
  122.     while( x->leftlink != NULL )
  123.         x = x->leftlink;
  124.  
  125.     return( x );
  126.  
  127. } /* spfhead */
  128.  
  129.  
  130.  
  131.  
  132. /*----------------
  133.  *
  134.  * spftail() -- find the last node in a tree.
  135.  *
  136.  *    Fast version does not splay result or intermediate steps.
  137.  */
  138. SPBLK *
  139. spftail( q )
  140.  
  141. SPTREE * q;
  142.  
  143. {
  144.     register SPBLK * x;
  145.  
  146.  
  147.     if( NULL != ( x = q->root ) )
  148.     while( x->rightlink != NULL )
  149.         x = x->rightlink;
  150.  
  151.     return( x );
  152.  
  153. } /* spftail */
  154.  
  155.  
  156. /*----------------
  157.  *
  158.  * spscan() -- apply a function to nodes in ascending order.
  159.  *
  160.  *    if n is given, start at that node, otherwise start from
  161.  *    the head.
  162.  */
  163. void
  164. spscan( f, n, q )
  165.  
  166. register int (*f)();
  167. register SPBLK * n;
  168. register SPTREE * q;
  169.  
  170. {
  171.     register SPBLK * x;
  172.  
  173.     for( x = n != NULL ? n : spfhead( q ); x != NULL ; x = spfnext( x ) )
  174.         (*f)( x );
  175. }
  176.  
  177.  
  178.  
  179. /*----------------
  180.  *
  181.  * sprscan() -- apply a function to nodes in descending order.
  182.  *
  183.  *    if n is given, start at that node, otherwise start from
  184.  *    the tail.
  185.  */
  186. void
  187. sprscan( f, n, q )
  188.  
  189. register int (*f)();
  190. register SPBLK * n;
  191. register SPTREE * q;
  192.  
  193. {
  194.     register SPBLK *x;
  195.  
  196.     for( x = n != NULL ? n : spftail( q ); x != NULL ; x = spfprev( x ) )
  197.         (*f)( x );
  198. }
  199.  
  200.  
  201.  
  202. /*----------------
  203.  *
  204.  * spfnext() -- fast return next higer item in the tree, or NULL.
  205.  *
  206.  *    return the successor of n in q, represented as a splay tree.
  207.  *    This is a fast (on average) version that does not splay.
  208.  */
  209. SPBLK *
  210. spfnext( n )
  211.  
  212. register SPBLK * n;
  213.  
  214. {
  215.     register SPBLK * next;
  216.     register SPBLK * x;
  217.  
  218.     /* a long version, avoids splaying for fast average,
  219.      * poor amortized bound
  220.      */
  221.  
  222.     if( n == NULL )
  223.         return( n );
  224.  
  225.     x = n->rightlink;
  226.     if( x != NULL )
  227.     {
  228.         while( x->leftlink != NULL )
  229.         x = x->leftlink;
  230.         next = x;
  231.     }
  232.     else    /* x == NULL */
  233.     {
  234.         x = n->uplink;
  235.         next = NULL;
  236.         while( x != NULL )
  237.     {
  238.             if( x->leftlink == n )
  239.         {
  240.                 next = x;
  241.                 x = NULL;
  242.             }
  243.         else
  244.         {
  245.                 n = x;
  246.                 x = n->uplink;
  247.             }
  248.         }
  249.     }
  250.  
  251.     return( next );
  252.  
  253. } /* spfnext */
  254.  
  255.  
  256.  
  257. /*----------------
  258.  *
  259.  * spfprev() -- return fast previous node in a tree, or NULL.
  260.  *
  261.  *    return the predecessor of n in q, represented as a splay tree.
  262.  *    This is a fast (on average) version that does not splay.
  263.  */
  264. SPBLK *
  265. spfprev( n )
  266.  
  267. register SPBLK * n;
  268.  
  269. {
  270.     register SPBLK * prev;
  271.     register SPBLK * x;
  272.  
  273.     /* a long version,
  274.      * avoids splaying for fast average, poor amortized bound
  275.      */
  276.  
  277.     if( n == NULL )
  278.         return( n );
  279.  
  280.     x = n->leftlink;
  281.     if( x != NULL )
  282.     {
  283.         while( x->rightlink != NULL )
  284.         x = x->rightlink;
  285.         prev = x;
  286.     }
  287.     else
  288.     {
  289.         x = n->uplink;
  290.         prev = NULL;
  291.         while( x != NULL )
  292.     {
  293.             if( x->rightlink == n )
  294.         {
  295.                 prev = x;
  296.                 x = NULL;
  297.             }
  298.         else
  299.         {
  300.                 n = x;
  301.                 x = n->uplink;
  302.             }
  303.         }
  304.     }
  305.  
  306.     return( prev );
  307.  
  308. } /* spfprev */
  309.  
  310.  
  311.  
  312. char *
  313. spstats( q )
  314. SPTREE *q;
  315. {
  316.     static char buf[ 128 ];
  317.     float llen;
  318.     float elen;
  319.     float sloops;
  320.  
  321.     if( q == NULL )
  322.     return("");
  323.  
  324.     llen = q->lookups ? (float)q->lkpcmps / q->lookups : 0;
  325.     elen = q->enqs ? (float)q->enqcmps/q->enqs : 0;
  326.     sloops = q->splays ? (float)q->splayloops/q->splays : 0;
  327.  
  328.     sprintf(buf, "f(%d %4.2f) i(%d %4.2f) s(%d %4.2f)",
  329.     q->lookups, llen, q->enqs, elen, q->splays, sloops );
  330.  
  331.     return buf;
  332. }
  333.  
  334.