                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page   1
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	      1 
	      2 /*****************************************************************************
	      3  *
	      4  * Tree.C
	      5  *
	      6  *****************************************************************************/
	      7 
	      8 /*****************************************************************************
	      9  *
	     10  * Headers
	     11  *
	     12  *****************************************************************************/
	     13 
	     14 #include <stdio.h>
	    396 
	    397 #include "intrinsic.h"
	    428 #include "mem.h"
	    443 #include "tree.h"
	    517 
	    518 /*****************************************************************************
	    519  *
	    520  * Local Constants and Macros
	    521  *
	    522  *****************************************************************************/
	    523 
	    524 #define LIB$_KEYALRINS   1409057
	    525 
	    526 #if defined(VMS) || defined(__GNUC__)
	    527 #define _PROTOTYPES_
	    528 #endif
	    529 
	    530 /*****************************************************************************
	    531  *
	    532  * Local Declarations
	    533  *
	    534  *****************************************************************************/
	    535 
	    536 static Tree mms_xfree_tree = NULL;
	    537 static Tree mms_global_root;
	    538 static Tree mms_tree_node;
	    539 static int  mms_tree_fcn1,mms_tree_fcn2;
	    540 
	    541 /*****************************************************************************
	    542  *
	    543  * Local Prototypes
	    544  *
	    545  *****************************************************************************/
	    546 
	    547 #ifdef _PROTOTYPES_
	    548 static int  mms_i_tree_alloc          (int key, int *ptr);
	    549 static int  mms_internal_traverse     (Tree node);
	    550 static int  mms_internal_traverse2    (Tree node);
	    551 static int  mms_tree_default_compare  (String k, Tree t);
	    552 static int  mms_tree_default_key      (String k, Tree t);
	    553 static int  mms_tree_idefault_compare (int k, Tree t);
	    554 static int  mms_tree_idefault_key     (int k, Tree t);
	    555 static int  xmms_tree_balance1        (Tree *root, int *h);

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page   2
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	    556 static int  xmms_tree_balance2        (Tree *root, int *h);
	    557 static int  xmms_tree_insert          (Tree *root, String key, int *ins_flag,
	    558                                        IPFN comp_fcn, IPFN alloc_fcn, 
	    559                                        Tree *rptr, Pointer data);
	    560 #else
       X    561 static int  mms_i_tree_alloc          ();
       X    562 static int  mms_internal_traverse     ();
       X    563 static int  mms_internal_traverse2    ();
       X    564 static int  mms_tree_default_compare  ();
       X    565 static int  mms_tree_default_key      ();
       X    566 static int  mms_tree_idefault_compare ();
       X    567 static int  mms_tree_idefault_key     ();
       X    568 static int  xmms_tree_balance1        ();
       X    569 static int  xmms_tree_balance2        ();
       X    570 static int  xmms_tree_insert          ();
       X    571 #endif
	    572 
	    573 /*****************************************************************************
	    574  *
	    575  * DeallocTreeNode
	    576  *
	    577  *****************************************************************************/
	    578 
	    579 #ifdef _PROTOTYPES_
	    580 extern int DeallocTreeNode (Tree ptr)
	    581 #else
       X    582 extern int DeallocTreeNode (ptr)
       X    583 
       X    584   Tree ptr;
       X    585 #endif
	    586 
	    587 {
	    588   ptr->left      = mms_xfree_tree;
	    589   mms_xfree_tree = ptr;
	    590 
	    591   return(Success);
	    592 }
	    593 
	    594 /*****************************************************************************
	    595  *
	    596  * DeallocTree
	    597  *
	    598  *****************************************************************************/
	    599 
	    600 #ifdef _PROTOTYPES_
	    601 extern Status DeallocTree (Tree ptr)
	    602 #else
       X    603 extern Status DeallocTree (ptr)
       X    604 
       X    605   Tree ptr;
       X    606 #endif
	    607 
	    608 {
	    609   /* TBD */
	    610 
	    611   /* done */
	    612   return (Failure);

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page   3
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	    613 }
	    614 
	    615 /*****************************************************************************
	    616  *
	    617  * TreeInsert
	    618  *
	    619  *****************************************************************************/
	    620 
	    621 #ifdef _PROTOTYPES_
	    622 extern Tree TreeInsert (int *inskey, Tree *tree, String key, Pointer data,
	    623                  IPFN comp_fcn, IPFN key_fcn)
	    624 #else
       X    625 extern Tree TreeInsert (inskey, tree, key, data, comp_fcn, key_fcn)
       X    626 
       X    627   int     *inskey;
       X    628   Tree    *tree;
       X    629   String   key;
       X    630   Pointer  data;
       X    631   IPFN     comp_fcn;
       X    632   IPFN     key_fcn;
       X    633 #endif
	    634 
	    635 {
	    636   int         i,j,k;
	    637   int         mms_tree_default_compare(),mms_tree_default_key();
	    638   int         mms_tree_idefault_compare(),mms_tree_idefault_key();
	    639   int         (*cfcn)(),(*kfcn)();
	    640   Tree        t1;
	    641   int         mms_i_tree_alloc();
	    642 
	    643   if (((int) comp_fcn) == 1) cfcn = mms_tree_idefault_compare;
	    644   else if ((int) comp_fcn)   cfcn = comp_fcn;
	    645   else                       cfcn = mms_tree_default_compare;
	    646   if (((int) key_fcn) == 1)  kfcn = mms_tree_idefault_key;
	    647   else if ((int) key_fcn)    kfcn = key_fcn;
	    648   else                        kfcn = mms_tree_default_key;
	    649   j = *inskey;
	    650   i = xmms_tree_insert (tree,key,&j,cfcn,mms_i_tree_alloc,&t1,0);
	    651   *inskey = 0;
	    652   if (i == LIB$_KEYALRINS && !t1->extra) {
	    653     t1->extra = 1;
	    654     t1->data = data;
	    655   }
	    656   else if (i == LIB$_KEYALRINS) *inskey = 1;
	    657   else {
	    658     t1->extra = 1;
	    659     t1->data = data;
	    660     (*kfcn)(key,t1);
	    661   }
	    662 
	    663   return(t1);
	    664 }
	    665 
	    666 /*****************************************************************************
	    667  *
	    668  * mms_tree_default_compare
	    669  *

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page   4
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	    670  *****************************************************************************/
	    671 
	    672 #ifdef _PROTOTYPES_
	    673 static int mms_tree_default_compare (String k, Tree t)
	    674 #else
       X    675 static int mms_tree_default_compare (k, t)
       X    676 
       X    677   String k;
       X    678   Tree   t;
       X    679 #endif
	    680 
	    681 {
	    682   return (strcmp(k,TreeKey(t)));
	    683 }
	    684 
	    685 /*****************************************************************************
	    686  *
	    687  * mms_tree_default_key
	    688  *
	    689  *****************************************************************************/
	    690 
	    691 #ifdef _PROTOTYPES_
	    692 static int mms_tree_default_key (String k, Tree t)
	    693 #else
       X    694 static int mms_tree_default_key (k, t)
       X    695 
       X    696   String k;
       X    697   Tree   t;
       X    698 #endif
	    699 
	    700 {
	    701   String s;
	    702 
	    703   s = (String) MemAlloc (strlen(k) + 1, NoInitialize);
	    704   strcpy (s, k);
	    705   TreeKey(t) = s;
	    706   return(Success);
	    707 }
	    708 
	    709 /*****************************************************************************
	    710  *
	    711  * mms_tree_idefault_compare
	    712  *
	    713  *****************************************************************************/
	    714 
	    715 #ifdef _PROTOTYPES_
	    716 static int mms_tree_idefault_compare (int k, Tree t)
	    717 #else
       X    718 static int mms_tree_idefault_compare (k, t)
       X    719 
       X    720   int  k;
       X    721   Tree t;
       X    722 #endif
	    723 
	    724 {
	    725   return (k - ((int) TreeKey(t)));
	    726 }

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page   5
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	    727 
	    728 /*****************************************************************************
	    729  *
	    730  * mms_tree_idefault_key
	    731  *
	    732  *****************************************************************************/
	    733 
	    734 #ifdef _PROTOTYPES_
	    735 static int mms_tree_idefault_key (int k, Tree t)
	    736 #else
       X    737 static int mms_tree_idefault_key (k, t)
       X    738 
       X    739   int  k;
       X    740   Tree t;
       X    741 #endif
	    742 
	    743 {
	    744   TreeKey(t) = (String) k;
	    745   return(Success);
	    746 }
	    747 
	    748 /*****************************************************************************
	    749  *
	    750  * mms_i_tree_alloc
	    751  *
	    752  *****************************************************************************/
	    753 
	    754 #ifdef _PROTOTYPES_
	    755 static int mms_i_tree_alloc (int key, int *ptr)
	    756 #else
       X    757 static int mms_i_tree_alloc (key, ptr)
       X    758 
       X    759   int  key;
       X    760   int *ptr;
       X    761 #endif
	    762 
	    763 {
	    764   int  i,j,k;
	    765   Tree t1;
	    766 
	    767   if (mms_xfree_tree) {
	    768     *ptr           = (int) mms_xfree_tree;
	    769     mms_xfree_tree = mms_xfree_tree->left;
	    770   }
	    771   else {
	    772     *ptr = (int) MemAlloc (sizeof(_Tree), NoInitialize);
	    773   }
	    774 
	    775   return(Success);
	    776 }
	    777 
	    778 /*****************************************************************************
	    779  *
	    780  * TreeTraverse
	    781  *
	    782  *****************************************************************************/
	    783 

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page   6
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	    784 #ifdef _PROTOTYPES_
	    785 extern Status TreeTraverse (Tree tree, IPFN fcn)
	    786 #else
       X    787 extern Status TreeTraverse (tree, fcn)
       X    788 
       X    789   Tree tree;
       X    790   IPFN fcn;
       X    791 #endif
	    792 
	    793 {
	    794   int         stack[24][2];
	    795   int         stack_size;
	    796   Tree        ptr,ptr2;
	    797   int         i,j;
	    798 
	    799   ptr        = tree;
	    800   stack_size = 0;
	    801 
	    802   if (!ptr) return(1);
	    803 
	    804   stack[stack_size][0] = (int) (ptr);
	    805   stack[stack_size][1] = 0;
	    806   stack_size += 1;
	    807 
	    808   while (stack_size) {
	    809 
	    810     i = stack_size - 1;
	    811 
	    812     ptr = (Tree) stack[i][0];
	    813 
	    814     if (stack[i][1] == 0) {
	    815       if (TreeLeft(ptr)) {
	    816         stack[stack_size][0] = (int) (TreeLeft(ptr));
	    817         stack[stack_size][1] = 0;
	    818         stack_size += 1;
	    819       }
	    820       stack[i][1] = 1;
	    821     }
	    822     else {
	    823       if (fcn) {
	    824         j = (*fcn) (ptr);
	    825         if (!(j & 1)) break;
	    826       }
	    827       stack_size -= 1;
	    828       if (TreeRight(ptr)) {
	    829         stack[stack_size][0] = (int) (TreeRight(ptr));
	    830         stack[stack_size][1] = 0;
	    831         stack_size += 1;
	    832       }
	    833     }
	    834   }
	    835 
	    836   return(Success);
	    837 }
	    838 
	    839 /*****************************************************************************
	    840  *

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page   7
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	    841  * mms_internal_traverse
	    842  *
	    843  *****************************************************************************/
	    844 
	    845 #ifdef _PROTOTYPES_
	    846 static int mms_internal_traverse (Tree tree)
	    847 #else
       X    848 static int mms_internal_traverse (tree)
       X    849 
       X    850   Tree tree;
       X    851 #endif
	    852 
	    853 {
	    854   printf ("`%s' %d\n",TreeKey(tree),TreeData(tree));
	    855 
	    856   return(Success);
	    857 }
	    858 
	    859 /*****************************************************************************
	    860  *
	    861  * mms_internal_traverse2
	    862  *
	    863  *****************************************************************************/
	    864 
	    865 #ifdef _PROTOTYPES_
	    866 static int mms_internal_traverse2 (Tree tree)
	    867 #else
       X    868 static int mms_internal_traverse2 (tree)
       X    869 
       X    870   Tree tree;
       X    871 #endif
	    872 
	    873 {
	    874   printf ("%s\n",TreeKey(tree));
	    875 
	    876   return(Success);
	    877 }
	    878 
	    879 /*****************************************************************************
	    880  *
	    881  * TreeFind
	    882  *
	    883  *****************************************************************************/
	    884 
	    885 #ifdef _PROTOTYPES_
	    886 extern Tree TreeFind (Tree tree, String key, IPFN comp_fcn)
	    887 #else
       X    888 extern Tree TreeFind (tree, key, comp_fcn)
       X    889 
       X    890   Tree   tree;
       X    891   String key;
       X    892   IPFN   comp_fcn;
       X    893 #endif
	    894 
	    895 {
	    896   Tree ptr;
	    897   int  i;

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page   8
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	    898 
	    899   ptr = tree;
	    900 
	    901   while (ptr) {
	    902     if (!comp_fcn)                  i = strcmp(key,TreeKey(ptr));
	    903     else if (((int) comp_fcn) == 1) i = ((int)key) - ((int)(TreeKey(ptr)));
	    904     else                            i = (*comp_fcn)(key,(ptr));
	    905     if (!i) break;
	    906     else if (i < 0) ptr = TreeLeft(ptr);
	    907     else            ptr = TreeRight(ptr);
	    908   }
	    909 
	    910   return(ptr);
	    911 }
	    912 
	    913 /*****************************************************************************
	    914  *
	    915  * TreeReplaceData
	    916  *
	    917  *****************************************************************************/
	    918 
	    919 #ifdef _PROTOTYPES_
	    920 extern int TreeReplaceData (Tree tptr,Pointer newdata, IPFN fcn)
	    921 #else
       X    922 extern int TreeReplaceData (tptr, newdata, fcn)
       X    923 
       X    924   Tree    tptr;
       X    925   Pointer newdata;
       X    926   IPFN    fcn;
       X    927 #endif
	    928 
	    929 {
	    930   int  i,j,k;
	    931   Tree tree;
	    932 
	    933   tree = tptr;
	    934 
	    935   if (fcn) (*fcn)(tree->data);
	    936   tree->data = newdata;
	    937 
	    938   return(Success);
	    939 }
	    940 
	    941 /*****************************************************************************
	    942  *
	    943  * xmms_tree_find
	    944  *
	    945  *****************************************************************************/
	    946 
	    947 #ifdef _PROTOTYPES_
	    948 static int xmms_tree_find (Tree ptr,String key,IPFN comp_fcn)
	    949 #else
       X    950 static int xmms_tree_find (ptr, key, comp_fcn)
       X    951 
       X    952   Tree   ptr;
       X    953   String key;
       X    954   IPFN   comp_fcn;

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page   9
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

       X    955 #endif
	    956 
	    957 
	    958 {
	    959   int i;
	    960 
	    961   while (ptr) {
	    962     i = (*comp_fcn)(key,(ptr));
	    963     if (!i) break;
	    964     else if (i < 0) ptr = TreeLeft(ptr);
	    965     else            ptr = TreeRight(ptr);
	    966   }
	    967 
	    968   return((int) ptr);
	    969 }
	    970 
	    971 /*****************************************************************************
	    972  *
	    973  * xmms_tree_insert
	    974  *
	    975  *****************************************************************************/
	    976 
	    977 #ifdef _PROTOTYPES_
	    978 static int xmms_tree_insert (Tree *root, String key, int *ins_flag,
	    979                              IPFN comp_fcn, IPFN alloc_fcn, Tree *rptr,
	    980                              Pointer data)
	    981 #else
       X    982 static int xmms_tree_insert (root, key, ins_flag, comp_fcn, alloc_fcn,
       X    983                              rptr, data)
       X    984 
       X    985   Tree   *root;
       X    986   String  key;
       X    987   int    *ins_flag;
       X    988   IPFN    comp_fcn;
       X    989   IPFN    alloc_fcn;
       X    990   Tree   *rptr;
       X    991   Pointer data;
       X    992 #endif
	    993 
	    994 {
	    995   int         i,j,k;
	    996   static int  stack[256][2];
	    997   static int  stack_ptr;
	    998   int         h;
	    999   int         dup_flag;
	   1000   int         inserted;
	   1001   int         return_ptr;
	   1002   int         return_value;
	   1003   Tree       *tptr;
	   1004   Tree        ptr,ptr2,ptr3;
	   1005 
	   1006   return_value          = 1;
	   1007   h                     = 0;
	   1008   dup_flag              = *ins_flag;
	   1009   stack_ptr             = 0;
	   1010   inserted              = 0;
	   1011   return_ptr            = 0;

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page  10
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	   1012   stack[stack_ptr][0]   = (int) root;
	   1013   stack[stack_ptr++][1] = 0;
	   1014 
	   1015   while (stack_ptr) {
	   1016 
	   1017     stack_ptr--;
	   1018     tptr = (Tree *) stack[stack_ptr][0];
	   1019     ptr  = *tptr;
	   1020 
	   1021     if (stack[stack_ptr][1] == 0) {
	   1022       if (ptr) i = (*comp_fcn) (key,(ptr));
	   1023       else     i = 0;
	   1024       if (!ptr) {
	   1025         (*alloc_fcn) (key,&ptr2);
	   1026         ptr2->left    = ptr2->right = NULL;
	   1027         ptr2->data    = data;
	   1028         ptr2->extra   = 0;
	   1029         ptr2->balance = 0;
	   1030         *tptr         = ptr2;
	   1031         return_ptr    = (int) ptr2;
	   1032         h             = 1;
	   1033         inserted      = 1;
	   1034       }
	   1035       else if (!i && !dup_flag) {
	   1036         inserted     = 0;
	   1037         return_ptr   = (int) ptr;
	   1038         return_value = LIB$_KEYALRINS;
	   1039       }
	   1040       else if (i < 1) {
	   1041         stack[stack_ptr][0] = (int) tptr;
	   1042         stack[stack_ptr][1] = 1;
	   1043         stack_ptr++;
	   1044         stack[stack_ptr][0] = (int) (&(TreeLeft(ptr)));
	   1045         stack[stack_ptr][1] = 0;
	   1046         stack_ptr++;
	   1047       }
	   1048       else {
	   1049         stack[stack_ptr][0] = (int) tptr;
	   1050         stack[stack_ptr][1] = 2;
	   1051         stack_ptr++;
	   1052         stack[stack_ptr][0] = (int) (&(TreeRight(ptr)));
	   1053         stack[stack_ptr][1] = 0;
	   1054         stack_ptr++;
	   1055       }
	   1056     }
	   1057   
	   1058     else if (stack[stack_ptr][1] == 1) {
	   1059       if (h) {
	   1060         if (TreeBalance(ptr) == 1) {
	   1061           ptr->balance = 0;
	   1062           h = 0;
	   1063         }
	   1064         else if (TreeBalance(ptr) == 0) {
	   1065           ptr->balance = -1;
	   1066         }
	   1067         else if (TreeBalance(ptr) == -1) {
	   1068           ptr2 = ptr->left;

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page  11
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	   1069           if (TreeBalance(ptr2) == -1) { /* single LL rotation */
	   1070             TreeLeft(ptr)   = TreeRight(ptr2);
	   1071             TreeRight(ptr2) = ptr;
	   1072             TreeBalance(ptr)    = 0;
	   1073             ptr              = ptr2;
	   1074           }
	   1075           else { /* double LR rotation */
	   1076             ptr3             = TreeRight(ptr2);
	   1077             TreeRight(ptr2) = TreeLeft(ptr3);
	   1078             TreeLeft(ptr3)  = ptr2;
	   1079             TreeLeft(ptr)   = TreeRight(ptr3);
	   1080             TreeRight(ptr3) = ptr;
	   1081             if (ptr3->balance == -1) ptr->balance  = 1;
	   1082             else                          ptr->balance  = 0;
	   1083             if (ptr3->balance ==  1) ptr2->balance = -1;
	   1084             else                          ptr2->balance =  0;
	   1085             ptr = ptr3;
	   1086           }
	   1087           ptr->balance = 0;
	   1088           h     = 0;
	   1089           *tptr = ptr;
	   1090         }
	   1091       }
	   1092     }
	   1093   
	   1094     else if (stack[stack_ptr][1] == 2) {
	   1095       if (h) {
	   1096         if (ptr->balance == -1) {
	   1097           ptr->balance = 0;
	   1098           h                 = 0;
	   1099         }
	   1100         else if (ptr->balance == 0) {
	   1101           ptr->balance = 1;
	   1102         }
	   1103         else if (ptr->balance == 1) {
	   1104           ptr2 = ptr->right;
	   1105           if (ptr2->balance == 1) { /* single RR rotation */
	   1106             ptr->right   = ptr2->left;
	   1107             ptr2->left   = ptr;
	   1108             ptr->balance = 0;
	   1109             ptr          = ptr2;
	   1110           }
	   1111           else { /* double RL rotation */
	   1112             ptr3        = ptr2->left;
	   1113             ptr2->left  = ptr3->right;
	   1114             ptr3->right = ptr2;
	   1115             ptr->right  = ptr3->left;
	   1116             ptr3->left  = ptr;
	   1117             if (ptr3->balance ==  1) ptr->balance  = -1;
	   1118             else                     ptr->balance  =  0;
	   1119             if (ptr3->balance == -1) ptr2->balance = 1;
	   1120             else                     ptr2->balance = 0;
	   1121             ptr = ptr3;
	   1122           }
	   1123           ptr->balance = 0;
	   1124           h            = 0;
	   1125           *tptr        = ptr;

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page  12
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	   1126         }
	   1127       }
	   1128     }
	   1129   }
	   1130 
	   1131   *ins_flag = inserted;
	   1132   *rptr     = (Tree) return_ptr;
	   1133   return(return_value);
	   1134 }
	   1135 
	   1136 /*****************************************************************************
	   1137  *
	   1138  * xmms_tree_delete1
	   1139  *
	   1140  *****************************************************************************/
	   1141 
	   1142 #ifdef _PROTOTYPES_
	   1143 static int xmms_tree_delete1 (Tree *root, String key, int *h, 
	   1144                               IPFN comp_fcn, IPFN key_fcn, IPFN free_fcn)
	   1145 #else
       X   1146 static int xmms_tree_delete1 (root, key, h, comp_fcn, key_fcn, free_fcn)
       X   1147 
       X   1148   Tree   *root;
       X   1149   String  key;
       X   1150   int    *h;
       X   1151   IPFN    comp_fcn;
       X   1152   IPFN    key_fcn;
       X   1153   IPFN    free_fcn;
       X   1154 #endif
	   1155 
	   1156 {
	   1157   int  i,j,k;
	   1158   Tree q,p1,p2,p;
	   1159   int  b1,b2;
	   1160 
	   1161   if (!root) {
	   1162     *h = 0;
	   1163     return(0);
	   1164   }
	   1165 
	   1166   p = *root;
	   1167   if (!p) {
	   1168     *h = 0;
	   1169     return(0);
	   1170   }
	   1171 
	   1172   i = (*comp_fcn) (key,p);
	   1173   if (i < 0) {
	   1174     i = xmms_tree_delete1 (&(p->left),key,h,comp_fcn,key_fcn,free_fcn);
	   1175     if (*h) xmms_tree_balance1 (root,h);
	   1176     return(i);
	   1177   }
	   1178   else if (i > 0) {
	   1179     i = xmms_tree_delete1 (&(p->right),key,h,comp_fcn,key_fcn,free_fcn);
	   1180     if (*h) xmms_tree_balance2 (root,h);
	   1181     return(i);
	   1182   }

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page  13
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	   1183   else {
	   1184 
	   1185     q = p;
	   1186     if (!(q->right)) {
	   1187       *root = q->left;
	   1188       *h = 1;
	   1189       if (free_fcn) (*free_fcn) (q->data);
	   1190       DeallocTreeNode (q);
	   1191     }
	   1192     else if (!(q->left)) {
	   1193       *root = q->right;
	   1194       *h = 1;
	   1195       if (free_fcn) (*free_fcn) (q->data);
	   1196       DeallocTreeNode (q);
	   1197     }
	   1198     else {
	   1199       xmms_tree_del (&q,&(q->left),h,comp_fcn,key_fcn,free_fcn);
	   1200       *root = q;
	   1201       if (*h) xmms_tree_balance1 (root,h);
	   1202     }
	   1203     return(1);
	   1204   }
	   1205 }
	   1206 
	   1207 /*****************************************************************************
	   1208  *
	   1209  * xmms_tree_del
	   1210  *
	   1211  *****************************************************************************/
	   1212 
	   1213 #ifdef _PROTOTYPES_
	   1214 xmms_tree_del (Tree *root, Tree *root_r, int *h, IPFN comp_fcn, 
	   1215                IPFN key_fcn, IPFN free_fcn)
	   1216 #else
       X   1217 xmms_tree_del (root, root_r, h, comp_fcn, key_fcn, free_fcn)
       X   1218 
       X   1219   Tree  *root;
       X   1220   Tree  *root_r;
       X   1221   int   *h;
       X   1222   IPFN   comp_fcn;
       X   1223   IPFN   key_fcn;
       X   1224   IPFN   free_fcn;
       X   1225 #endif
	   1226 
	   1227 {
	   1228   Tree r;
	   1229 
	   1230   r = *root_r;
	   1231   if (r->right) {
	   1232     xmms_tree_del (root,&(r->right),h, comp_fcn, key_fcn, free_fcn);
	   1233     if (*h) xmms_tree_balance2 (root_r,h);
	   1234   }
	   1235   else {
	   1236     (*key_fcn) (r->key, (*root));
	   1237     (*root)->extra = r->extra;
	   1238     (*root)->data = r->data;
	   1239     *root_r = r->left;

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page  14
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	   1240     *h = 1;
	   1241     if (free_fcn) (*free_fcn) (r->data);
	   1242     DeallocTreeNode (r);
	   1243   }
	   1244 
	   1245   return(1);
	   1246 }
	   1247 
	   1248 /*****************************************************************************
	   1249  *
	   1250  * xmms_tree_balance1
	   1251  *
	   1252  *****************************************************************************/
	   1253 
	   1254 #ifdef _PROTOTYPES_
	   1255 static int xmms_tree_balance1 (Tree *root, int *h)
	   1256 #else
       X   1257 static int xmms_tree_balance1 (root, h)
       X   1258 
       X   1259   Tree *root;
       X   1260   int  *h;
       X   1261 #endif
	   1262 
	   1263 {
	   1264   Tree p,p1,p2;
	   1265   int  b1,b2;
	   1266 
	   1267   p = *root;
	   1268   if (p->balance == -1) p->balance = 0;
	   1269   else if (p->balance == 0) {
	   1270     p->balance = 1;
	   1271     *h = 0;
	   1272   }
	   1273   else if (p->balance == 1) {
	   1274     p1 = p->right;
	   1275     b1 = p1->balance;
	   1276     if (b1 >= 0) { /* single RR rotation */
	   1277       p->right = p1->left;
	   1278       p1->left = p;
	   1279       if (!b1) {
	   1280         p->balance = 1;
	   1281         p1->balance = -1;
	   1282         *h = 0;
	   1283       }
	   1284       else {
	   1285         p->balance = 0;
	   1286         p1->balance = 0;
	   1287       }
	   1288       p = p1;
	   1289       *root = p;
	   1290     }
	   1291     else { /* double RL rotation */
	   1292       p2 = p1->left;
	   1293       b2 = p2->balance;
	   1294       p1->left = p2->right;
	   1295       p2->right = p1;
	   1296       p->right = p2->left;

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page  15
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	   1297       p2->left = p;
	   1298       if (b2 == 1) p->balance = -1;
	   1299       else         p->balance = 0;
	   1300       if (b2 == -1) p1->balance = 1;
	   1301       else          p1->balance = 0;
	   1302       p = p2;
	   1303       p2->balance = 0;
	   1304       *root = p;
	   1305     }
	   1306   }
	   1307 
	   1308   return(1);
	   1309 }
	   1310 
	   1311 /*****************************************************************************
	   1312  *
	   1313  * xmms_tree_balance2
	   1314  *
	   1315  *****************************************************************************/
	   1316 
	   1317 #ifdef _PROTOTYPES_
	   1318 static int xmms_tree_balance2 (Tree *root, int *h)
	   1319 #else
       X   1320 static int xmms_tree_balance2 (root, h)
       X   1321 
       X   1322   Tree  *root;
       X   1323   int   *h;
       X   1324 #endif
	   1325 
	   1326 {
	   1327   Tree p,p1,p2;
	   1328   int  b1,b2;
	   1329 
	   1330   p = *root;
	   1331   if (p->balance == 1) p->balance = 0;
	   1332   else if (p->balance == 0) {
	   1333     p->balance = -1;
	   1334     *h = 0;
	   1335   }
	   1336   else if (p->balance == -1) {
	   1337     p1 = p->left;
	   1338     b1 = p1->balance;
	   1339     if (b1 <= 0) { /* single LL rotation */
	   1340       p->left = p1->right;
	   1341       p1->right = p;
	   1342       if (b1 == 0) {
	   1343         p->balance = -1;
	   1344         p1->balance = 1;
	   1345         *h = 0;
	   1346       }
	   1347       else {
	   1348         p->balance = 0;
	   1349         p1->balance = 0;
	   1350       }
	   1351       p = p1;
	   1352       *root = p;
	   1353     }

                                Source Listing                  24-APR-1996 13:22:50    DEC C T4.1-FT2                      Page  16
                                                                24-APR-1996 13:22:25    WORK$:[DAVENPORT.RTL]TREE.C;2

	   1354     else { /* double LR rotation */
	   1355       p2 = p1->right;
	   1356       b2 = p2->balance;
	   1357       p1->right = p2->left;
	   1358       p2->left = p1;
	   1359       p->left = p2->right;
	   1360       p2->right = p;
	   1361       if (b2 == -1) p->balance = 1;
	   1362       else          p->balance = 0;
	   1363       if (b2 == 1) p1->balance = -1;
	   1364       else         p1->balance = 0;
	   1365       p = p2;
	   1366       p2->balance = 0;
	   1367       *root = p;
	   1368     }
	   1369   }
	   1370 
	   1371   return(1);
	   1372 }


Command Line
------- ----

CC /NOANSI_ALIAS/ASSUME=(ACCURACY_SENSITIVE,ALIGNED_OBJECTS,WRITABLE_STRING_LITERALS)
/DEBUG=(SYMBOLS,TRACEBACK)/ENDIAN=LITTLE/EXTERN_MODEL=RELAXED_REFDEF/FLOAT=(
G_FLOAT)/GRANULARITY=QUADWORD/INSTRUCTION_SET=FLOATING_POINT/L_DOUBLE_SIZE=128
/LIST/NOMACHINE_CODE/MEMBER_ALIGNMENT/NAMES=UPPERCASE/NESTED_INCLUDE_DIRECTORY=INCLUDE_FILE
/OBJECT/NOOPTIMIZE/PREFIX=(ALL_ENTRIES)/PSECT_MODEL=NOMULTILANGUAGE/ROUNDING_MODE=NEAREST
/SHOW=(HEADER,SOURCE)/SIGNED_CHAR/STANDARD=VAXC/REENTRANCY=TOLERANT/WARNINGS
