home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1868 / sptree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-12-28  |  15.3 KB  |  574 lines
  1. /*
  2.  *
  3.  *  sptree.c:  The following code implements the basic operations on
  4.  *  an event-set or priority-queue implemented using splay trees:
  5.  *
  6.  *  SPTREE *spinit( compare )    Make a new tree
  7.  *  int spempty();        Is tree empty?
  8.  *  SPBLK *spenq( n, q )    Insert n in q after all equal keys.
  9.  *  SPBLK *spdeq( np )        Return first key under *np, removing it.
  10.  *  SPBLK *spenqprior( n, q )    Insert n in q before all equal keys.
  11.  *  void splay( n, q )        n (already in q) becomes the root.
  12.  *
  13.  *  In the above, n points to an SPBLK type, while q points to an
  14.  *  SPTREE.
  15.  *
  16.  *  The implementation used here is based on the implementation
  17.  *  which was used in the tests of splay trees reported in:
  18.  *
  19.  *    An Empirical Comparison of Priority-Queue and Event-Set Implementations,
  20.  *    by Douglas W. Jones, Comm. ACM 29, 4 (Apr. 1986) 300-311.
  21.  *
  22.  *  The changes made include the addition of the enqprior
  23.  *  operation and the addition of up-links to allow for the splay
  24.  *  operation.  The basic splay tree algorithms were originally
  25.  *  presented in:
  26.  *
  27.  *    Self Adjusting Binary Trees,
  28.  *        by D. D. Sleator and R. E. Tarjan,
  29.  *            Proc. ACM SIGACT Symposium on Theory
  30.  *            of Computing (Boston, Apr 1983) 235-245.
  31.  *
  32.  *  The enq and enqprior routines use variations on the
  33.  *  top-down splay operation, while the splay routine is bottom-up.
  34.  *  All are coded for speed.
  35.  *
  36.  *  Written by:
  37.  *    Douglas W. Jones
  38.  *
  39.  *  Translated to C by:
  40.  *    David Brower, daveb@rtech.uucp
  41.  *
  42.  * Thu Oct  6 12:11:33 PDT 1988 (daveb) Fixed spdeq, which was broken
  43.  *    handling one-node trees.  I botched the pascal translation of
  44.  *    a VAR parameter.
  45.  */
  46.  
  47. # include "sptree.h"
  48.  
  49. /* USER SUPPLIED! */
  50.  
  51. extern char *emalloc();
  52.  
  53.  
  54. /*----------------
  55.  *
  56.  * spinit() -- initialize an empty splay tree
  57.  *
  58.  */
  59. SPTREE *
  60. spinit()
  61. {
  62.     register SPTREE * q;
  63.  
  64.     q = (SPTREE *) emalloc( sizeof( *q ) );
  65.  
  66.     q->lookups = 0;
  67.     q->lkpcmps = 0;
  68.     q->enqs = 0;
  69.     q->enqcmps = 0;
  70.     q->splays = 0;
  71.     q->splayloops = 0;
  72.     q->root = NULL;
  73.     return( q );
  74. }
  75.  
  76. /*----------------
  77.  *
  78.  * spempty() -- is an event-set represented as a splay tree empty?
  79.  */
  80. int
  81. spempty( q )
  82.  
  83. SPTREE *q;
  84.  
  85. {
  86.     return( q == NULL || q->root == NULL );
  87. }
  88.  
  89.  
  90. /*----------------
  91.  *
  92.  *  spenq() -- insert item in a tree.
  93.  *
  94.  *  put n in q after all other nodes with the same key; when this is
  95.  *  done, n will be the root of the splay tree representing q, all nodes
  96.  *  in q with keys less than or equal to that of n will be in the
  97.  *  left subtree, all with greater keys will be in the right subtree;
  98.  *  the tree is split into these subtrees from the top down, with rotations
  99.  *  performed along the way to shorten the left branch of the right subtree
  100.  *  and the right branch of the left subtree
  101.  */
  102. SPBLK *
  103. spenq( n, q )
  104.  
  105. register SPBLK * n;
  106. register SPTREE * q;
  107.  
  108. {
  109.     register SPBLK * left;    /* the rightmost node in the left tree */
  110.     register SPBLK * right;    /* the leftmost node in the right tree */
  111.     register SPBLK * next;    /* the root of the unsplit part */
  112.     register SPBLK * temp;
  113.  
  114.     register char * key;
  115.     register int Sct;        /* Strcmp value */
  116.  
  117.     q->enqs++;
  118.     n->uplink = NULL;
  119.     next = q->root;
  120.     q->root = n;
  121.     if( next == NULL )    /* trivial enq */
  122.     {
  123.         n->leftlink = NULL;
  124.         n->rightlink = NULL;
  125.     }
  126.     else        /* difficult enq */
  127.     {
  128.         key = n->key;
  129.         left = n;
  130.         right = n;
  131.  
  132.         /* n's left and right children will hold the right and left
  133.        splayed trees resulting from splitting on n->key;
  134.        note that the children will be reversed! */
  135.  
  136.     q->enqcmps++;
  137.         if ( STRCMP( next->key, key ) > 0 )
  138.         goto two;
  139.  
  140.     one:    /* assert next->key <= key */
  141.  
  142.     do    /* walk to the right in the left tree */
  143.     {
  144.             temp = next->rightlink;
  145.             if( temp == NULL )
  146.         {
  147.                 left->rightlink = next;
  148.                 next->uplink = left;
  149.                 right->leftlink = NULL;
  150.                 goto done;    /* job done, entire tree split */
  151.             }
  152.  
  153.         q->enqcmps++;
  154.             if( STRCMP( temp->key, key ) > 0 )
  155.         {
  156.                 left->rightlink = next;
  157.                 next->uplink = left;
  158.                 left = next;
  159.                 next = temp;
  160.                 goto two;    /* change sides */
  161.             }
  162.  
  163.             next->rightlink = temp->leftlink;
  164.             if( temp->leftlink != NULL )
  165.             temp->leftlink->uplink = next;
  166.             left->rightlink = temp;
  167.             temp->uplink = left;
  168.             temp->leftlink = next;
  169.             next->uplink = temp;
  170.             left = temp;
  171.             next = temp->rightlink;
  172.             if( next == NULL )
  173.         {
  174.                 right->leftlink = NULL;
  175.                 goto done;    /* job done, entire tree split */
  176.             }
  177.  
  178.         q->enqcmps++;
  179.  
  180.     } while( STRCMP( next->key, key ) <= 0 );    /* change sides */
  181.  
  182.     two:    /* assert next->key > key */
  183.  
  184.     do    /* walk to the left in the right tree */
  185.     {
  186.             temp = next->leftlink;
  187.             if( temp == NULL )
  188.         {
  189.                 right->leftlink = next;
  190.                 next->uplink = right;
  191.                 left->rightlink = NULL;
  192.                 goto done;    /* job done, entire tree split */
  193.             }
  194.  
  195.         q->enqcmps++;
  196.             if( STRCMP( temp->key, key ) <= 0 )
  197.         {
  198.                 right->leftlink = next;
  199.                 next->uplink = right;
  200.                 right = next;
  201.                 next = temp;
  202.                 goto one;    /* change sides */
  203.             }
  204.             next->leftlink = temp->rightlink;
  205.             if( temp->rightlink != NULL )
  206.             temp->rightlink->uplink = next;
  207.             right->leftlink = temp;
  208.             temp->uplink = right;
  209.             temp->rightlink = next;
  210.             next->uplink = temp;
  211.             right = temp;
  212.             next = temp->leftlink;
  213.             if( next == NULL )
  214.         {
  215.                 left->rightlink = NULL;
  216.                 goto done;    /* job done, entire tree split */
  217.             }
  218.  
  219.         q->enqcmps++;
  220.  
  221.     } while( STRCMP( next->key, key ) > 0 );    /* change sides */
  222.  
  223.         goto one;
  224.  
  225.     done:    /* split is done, branches of n need reversal */
  226.  
  227.         temp = n->leftlink;
  228.         n->leftlink = n->rightlink;
  229.         n->rightlink = temp;
  230.     }
  231.  
  232.     n->cnt++;
  233.     return( n );
  234.  
  235. } /* spenq */
  236.  
  237.  
  238. /*----------------
  239.  *
  240.  *  spdeq() -- return and remove head node from a subtree.
  241.  *
  242.  *  remove and return the head node from the node set; this deletes
  243.  *  (and returns) the leftmost node from q, replacing it with its right
  244.  *  subtree (if there is one); on the way to the leftmost node, rotations
  245.  *  are performed to shorten the left branch of the tree
  246.  */
  247. SPBLK *
  248. spdeq( np )
  249.  
  250. SPBLK **np;        /* pointer to a node pointer */
  251.  
  252. {
  253.     register SPBLK * deq;        /* one to return */
  254.     register SPBLK * next;           /* the next thing to deal with */
  255.     register SPBLK * left;          /* the left child of next */
  256.     register SPBLK * farleft;        /* the left child of left */
  257.     register SPBLK * farfarleft;    /* the left child of farleft */
  258.  
  259.     if( np == NULL || *np == NULL )
  260.     {
  261.         deq = NULL;
  262.     }
  263.     else
  264.     {
  265.         next = *np;
  266.         left = next->leftlink;
  267.         if( left == NULL )
  268.     {
  269.             deq = next;
  270.             *np = next->rightlink;
  271.  
  272.             if( *np != NULL )
  273.         (*np)->uplink = NULL;
  274.  
  275.         }
  276.     else for(;;)    /* left is not null */
  277.     {
  278.             /* next is not it, left is not NULL, might be it */
  279.             farleft = left->leftlink;
  280.             if( farleft == NULL )
  281.         {
  282.                 deq = left;
  283.                 next->leftlink = left->rightlink;
  284.                 if( left->rightlink != NULL )
  285.             left->rightlink->uplink = next;
  286.         break;
  287.             }
  288.  
  289.             /* next, left are not it, farleft is not NULL, might be it */
  290.             farfarleft = farleft->leftlink;
  291.             if( farfarleft == NULL )
  292.         {
  293.                 deq = farleft;
  294.                 left->leftlink = farleft->rightlink;
  295.                 if( farleft->rightlink != NULL )
  296.             farleft->rightlink->uplink = left;
  297.         break;
  298.             }
  299.  
  300.             /* next, left, farleft are not it, rotate */
  301.             next->leftlink = farleft;
  302.             farleft->uplink = next;
  303.             left->leftlink = farleft->rightlink;
  304.             if( farleft->rightlink != NULL )
  305.         farleft->rightlink->uplink = left;
  306.             farleft->rightlink = left;
  307.             left->uplink = farleft;
  308.             next = farleft;
  309.             left = farfarleft;
  310.     }
  311.     }
  312.  
  313.     return( deq );
  314.  
  315. } /* spdeq */
  316.  
  317.  
  318. /*----------------
  319.  *
  320.  *  spenqprior() -- insert into tree before other equal keys.
  321.  *
  322.  *  put n in q before all other nodes with the same key; after this is
  323.  *  done, n will be the root of the splay tree representing q, all nodes in
  324.  *  q with keys less than that of n will be in the left subtree, all with
  325.  *  greater or equal keys will be in the right subtree; the tree is split
  326.  *  into these subtrees from the top down, with rotations performed along
  327.  *  the way to shorten the left branch of the right subtree and the right
  328.  *  branch of the left subtree; the logic of spenqprior is exactly the
  329.  *  same as that of spenq except for a substitution of comparison
  330.  *  operators
  331.  */
  332. SPBLK *
  333. spenqprior( n, q )
  334.  
  335. register SPBLK * n;
  336. SPTREE * q;
  337.  
  338. {
  339.  
  340.     register SPBLK * left;    /* the rightmost node in the left tree */
  341.     register SPBLK * right;    /* the leftmost node in the right tree */
  342.     register SPBLK * next;    /* the root of unsplit part of tree */
  343.     register SPBLK * temp;
  344.     register int Sct;        /* Strcmp value */
  345.     register char *key;
  346.  
  347.     n->uplink = NULL;
  348.     next = q->root;
  349.     q->root = n;
  350.     if( next == NULL )    /* trivial enq */
  351.     {
  352.         n->leftlink = NULL;
  353.         n->rightlink = NULL;
  354.     }
  355.     else        /* difficult enq */
  356.     {
  357.         key = n->key;
  358.         left = n;
  359.         right = n;
  360.  
  361.         /* n's left and right children will hold the right and left
  362.        splayed trees resulting from splitting on n->key;
  363.        note that the children will be reversed! */
  364.  
  365.         if( STRCMP( next->key, key ) >= 0 )
  366.         goto two;
  367.  
  368.     one:    /* assert next->key < key */
  369.  
  370.     do    /* walk to the right in the left tree */
  371.     {
  372.             temp = next->rightlink;
  373.             if( temp == NULL )
  374.         {
  375.                 left->rightlink = next;
  376.                 next->uplink = left;
  377.                 right->leftlink = NULL;
  378.                 goto done;    /* job done, entire tree split */
  379.             }
  380.             if( STRCMP( temp->key, key ) >= 0 )
  381.         {
  382.                 left->rightlink = next;
  383.                 next->uplink = left;
  384.                 left = next;
  385.                 next = temp;
  386.                 goto two;    /* change sides */
  387.             }
  388.             next->rightlink = temp->leftlink;
  389.             if( temp->leftlink != NULL )
  390.         temp->leftlink->uplink = next;
  391.             left->rightlink = temp;
  392.             temp->uplink = left;
  393.             temp->leftlink = next;
  394.             next->uplink = temp;
  395.             left = temp;
  396.             next = temp->rightlink;
  397.             if( next == NULL )
  398.         {
  399.                 right->leftlink = NULL;
  400.                 goto done;    /* job done, entire tree split */
  401.             }
  402.  
  403.     } while( STRCMP( next->key, key ) < 0 );    /* change sides */
  404.  
  405.     two:    /* assert next->key >= key */
  406.  
  407.     do     /* walk to the left in the right tree */
  408.     {
  409.             temp = next->leftlink;
  410.             if( temp == NULL )
  411.         {
  412.                 right->leftlink = next;
  413.                 next->uplink = right;
  414.                 left->rightlink = NULL;
  415.                 goto done;    /* job done, entire tree split */
  416.             }
  417.             if( STRCMP( temp->key, key ) < 0 )
  418.         {
  419.                 right->leftlink = next;
  420.                 next->uplink = right;
  421.                 right = next;
  422.                 next = temp;
  423.                 goto one;    /* change sides */
  424.             }
  425.             next->leftlink = temp->rightlink;
  426.             if( temp->rightlink != NULL )
  427.         temp->rightlink->uplink = next;
  428.             right->leftlink = temp;
  429.             temp->uplink = right;
  430.             temp->rightlink = next;
  431.             next->uplink = temp;
  432.             right = temp;
  433.             next = temp->leftlink;
  434.             if( next == NULL )
  435.         {
  436.                 left->rightlink = NULL;
  437.                 goto done;    /* job done, entire tree split */
  438.             }
  439.  
  440.     } while( STRCMP( next->key, key ) >= 0 );    /* change sides */
  441.  
  442.         goto one;
  443.  
  444.     done:    /* split is done, branches of n need reversal */
  445.  
  446.         temp = n->leftlink;
  447.         n->leftlink = n->rightlink;
  448.         n->rightlink = temp;
  449.     }
  450.  
  451.     return( n );
  452.  
  453. } /* spenqprior */
  454.  
  455. /*----------------
  456.  *
  457.  *  splay() -- reorganize the tree.
  458.  *
  459.  *  the tree is reorganized so that n is the root of the
  460.  *  splay tree representing q; results are unpredictable if n is not
  461.  *  in q to start with; q is split from n up to the old root, with all
  462.  *  nodes to the left of n ending up in the left subtree, and all nodes
  463.  *  to the right of n ending up in the right subtree; the left branch of
  464.  *  the right subtree and the right branch of the left subtree are
  465.  *  shortened in the process
  466.  *
  467.  *  this code assumes that n is not NULL and is in q; it can sometimes
  468.  *  detect n not in q and complain
  469.  */
  470.  
  471. void
  472. splay( n, q )
  473.  
  474. register SPBLK * n;
  475. SPTREE * q;
  476.  
  477. {
  478.     register SPBLK * up;    /* points to the node being dealt with */
  479.     register SPBLK * prev;    /* a descendent of up, already dealt with */
  480.     register SPBLK * upup;    /* the parent of up */
  481.     register SPBLK * upupup;    /* the grandparent of up */
  482.     register SPBLK * left;    /* the top of left subtree being built */
  483.     register SPBLK * right;    /* the top of right subtree being built */
  484.  
  485.     n->cnt++;    /* bump reference count */
  486.  
  487.     left = n->leftlink;
  488.     right = n->rightlink;
  489.     prev = n;
  490.     up = prev->uplink;
  491.  
  492.     q->splays++;
  493.  
  494.     while( up != NULL )
  495.     {
  496.     q->splayloops++;
  497.  
  498.         /* walk up the tree towards the root, splaying all to the left of
  499.        n into the left subtree, all to right into the right subtree */
  500.  
  501.         upup = up->uplink;
  502.         if( up->leftlink == prev )    /* up is to the right of n */
  503.     {
  504.             if( upup != NULL && upup->leftlink == up )  /* rotate */
  505.         {
  506.                 upupup = upup->uplink;
  507.                 upup->leftlink = up->rightlink;
  508.                 if( upup->leftlink != NULL )
  509.             upup->leftlink->uplink = upup;
  510.                 up->rightlink = upup;
  511.                 upup->uplink = up;
  512.                 if( upupup == NULL )
  513.             q->root = up;
  514.         else if( upupup->leftlink == upup )
  515.             upupup->leftlink = up;
  516.         else
  517.             upupup->rightlink = up;
  518.                 up->uplink = upupup;
  519.                 upup = upupup;
  520.             }
  521.             up->leftlink = right;
  522.             if( right != NULL )
  523.         right->uplink = up;
  524.             right = up;
  525.  
  526.         }
  527.     else                /* up is to the left of n */
  528.     {
  529.             if( upup != NULL && upup->rightlink == up )    /* rotate */
  530.         {
  531.                 upupup = upup->uplink;
  532.                 upup->rightlink = up->leftlink;
  533.                 if( upup->rightlink != NULL )
  534.             upup->rightlink->uplink = upup;
  535.                 up->leftlink = upup;
  536.                 upup->uplink = up;
  537.                 if( upupup == NULL )
  538.             q->root = up;
  539.         else if( upupup->rightlink == upup )
  540.             upupup->rightlink = up;
  541.         else
  542.             upupup->leftlink = up;
  543.                 up->uplink = upupup;
  544.                 upup = upupup;
  545.             }
  546.             up->rightlink = left;
  547.             if( left != NULL )
  548.         left->uplink = up;
  549.             left = up;
  550.         }
  551.         prev = up;
  552.         up = upup;
  553.     }
  554.  
  555. # ifdef DEBUG
  556.     if( q->root != prev )
  557.     {
  558. /*    fprintf(stderr, " *** bug in splay: n not in q *** " ); */
  559.     abort();
  560.     }
  561. # endif
  562.  
  563.     n->leftlink = left;
  564.     n->rightlink = right;
  565.     if( left != NULL )
  566.     left->uplink = n;
  567.     if( right != NULL )
  568.     right->uplink = n;
  569.     q->root = n;
  570.     n->uplink = NULL;
  571.  
  572. } /* splay */
  573.  
  574.