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