home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 35 Internet / 35-Internet.zip / radi116c.zip / radius116c / src / radius / tree.c < prev    next >
C/C++ Source or Header  |  1999-01-01  |  12KB  |  534 lines
  1. #ifndef LINT
  2. static char RCSid[] = "$Id: tree.c,v 8.6 1997/09/26 17:56:11 halley Exp $";
  3. #endif
  4.  
  5. /*
  6.  * tree - balanced binary tree library
  7.  *
  8.  * mn  28Dec98 Custom adaptation for RADIUS-OS2.
  9.  * vix 05apr94 [removed vixie.h dependencies; cleaned up formatting, names]
  10.  * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes]
  11.  * vix 23jun86 [added delete uar to add for replaced nodes]
  12.  * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224]
  13.  * vix 06feb86 [added tree_mung()]
  14.  * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221]
  15.  * vix 14dec85 [written]
  16.  */
  17.  
  18. /*
  19.  * This program text was created by Paul Vixie using examples from the book:
  20.  * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN
  21.  * 0-13-022005-1.  Any errors in the conversion from Modula-2 to C are Paul
  22.  * Vixie's.
  23.  */
  24.  
  25. /*
  26.  * Portions Copyright (c) 1996,1997 by Internet Software Consortium.
  27.  *
  28.  * Permission to use, copy, modify, and distribute this software for any
  29.  * purpose with or without fee is hereby granted, provided that the above
  30.  * copyright notice and this permission notice appear in all copies.
  31.  *
  32.  * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS
  33.  * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
  34.  * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE
  35.  * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
  36.  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  37.  * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
  38.  * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  39.  * SOFTWARE.
  40.  */
  41.  
  42. /*#define        DEBUG    "tree"*/
  43.  
  44. #include <stdio.h>
  45. #include <stdlib.h>
  46.  
  47. #include "shrmemry.h"
  48. #include "tree.h"
  49.  
  50.  
  51. #ifdef DEBUG
  52. static int    debugDepth = 0;
  53. static char    *debugFuncs[256];
  54. # define ENTER(proc) { \
  55.             debugFuncs[debugDepth] = proc; \
  56.             fprintf(stderr, "ENTER(%d:%s.%s)\n", \
  57.                 debugDepth, DEBUG,
  58.                 debugFuncs[debugDepth]); \
  59.             debugDepth++; \
  60.         }
  61. # define RET(value) { \
  62.             debugDepth--; \
  63.             fprintf(stderr, "RET(%d:%s.%s)\n", \
  64.                 debugDepth, DEBUG, \
  65.                 debugFuncs[debugDepth]); \
  66.             return (value); \
  67.         }
  68. # define RETV { \
  69.             debugDepth--; \
  70.             fprintf(stderr, "RETV(%d:%s.%s)\n", \
  71.                 debugDepth, DEBUG, \
  72.                 debugFuncs[debugDepth]); \
  73.             return; \
  74.         }
  75. # define MSG(msg)    fprintf(stderr, "MSG(%s)\n", msg);
  76. #else
  77. # define ENTER(proc)    ;
  78. # define RET(value)    return (value);
  79. # define RETV        return;
  80. # define MSG(msg)    ;
  81. #endif
  82.  
  83. #ifndef TRUE
  84. # define TRUE        1
  85. # define FALSE        0
  86. #endif
  87.  
  88. static tree *    sprout(tree **, tree_t, int *, int (*)(), void (*)());
  89. static int    delete(tree **, int (*)(), tree_t, void (*)(), int *, int *);
  90. static void    del(tree **, int *, tree **, void (*)(), int *);
  91. static void    bal_L(tree **, int *);
  92. static void    bal_R(tree **, int *);
  93.  
  94. void
  95. tree_init(tree **ppr_tree) {
  96.     ENTER("tree_init")
  97.     *ppr_tree = NULL;
  98.     RETV
  99. }
  100.     
  101. tree_t
  102. tree_srch(tree **ppr_tree, int (*pfi_compare)(), tree_t    p_user) {
  103.     ENTER("tree_srch")
  104.  
  105.     if (*ppr_tree) {
  106.         int i_comp = (*pfi_compare)(p_user, (**ppr_tree).data);
  107.  
  108.         if (i_comp > 0)
  109.             RET(tree_srch(&(**ppr_tree).right,
  110.                       pfi_compare,
  111.                       p_user))
  112.  
  113.         if (i_comp < 0)
  114.             RET(tree_srch(&(**ppr_tree).left,
  115.                       pfi_compare,
  116.                       p_user))
  117.  
  118.         /* not higher, not lower... this must be the one.
  119.          */
  120.         RET((**ppr_tree).data)
  121.     }
  122.  
  123.     /* grounded. NOT found.
  124.      */
  125.     RET(NULL)
  126. }
  127.  
  128. tree_t
  129. tree_add(tree **ppr_tree, int (*pfi_compare)(),
  130.      tree_t p_user, void (*pfv_uar)())
  131. {
  132.     int i_balance = FALSE;
  133.  
  134.     ENTER("tree_add")
  135.     if (!sprout(ppr_tree, p_user, &i_balance, pfi_compare, pfv_uar))
  136.         RET(NULL)
  137.     RET(p_user)
  138. }
  139.  
  140. int
  141. tree_delete(tree **ppr_p, int (*pfi_compare)(),
  142.         tree_t p_user, void    (*pfv_uar)())
  143. {
  144.     int i_balance = FALSE, i_uar_called = FALSE;
  145.  
  146.     ENTER("tree_delete");
  147.     RET(delete(ppr_p, pfi_compare, p_user, pfv_uar,
  148.            &i_balance, &i_uar_called))
  149. }
  150.  
  151.  
  152. typedef int __cdecl Callback(char *);
  153.  
  154.  
  155. int tree_trav(tree **ppr_tree, Callback pfi_uar) {
  156.           /* int (*pfi_uar)(char *)) { */
  157.     ENTER("tree_trav")
  158.  
  159.     if (!*ppr_tree)
  160.         RET(TRUE)
  161.  
  162.     if (!tree_trav(&(**ppr_tree).left, pfi_uar))
  163.         RET(FALSE)
  164.     if (!(*pfi_uar)((**ppr_tree).data))
  165.         RET(FALSE)
  166.     if (!tree_trav(&(**ppr_tree).right, pfi_uar))
  167.         RET(FALSE)
  168.     RET(TRUE)
  169. }
  170.  
  171. void
  172. tree_mung(tree **ppr_tree, void    (*pfv_uar)()) {
  173.     ENTER("tree_mung")
  174.     if (*ppr_tree) {
  175.         tree_mung(&(**ppr_tree).left, pfv_uar);
  176.         tree_mung(&(**ppr_tree).right, pfv_uar);
  177.         if (pfv_uar)
  178.             (*pfv_uar)((**ppr_tree).data);
  179.         SHfree(*ppr_tree);
  180.         *ppr_tree = NULL;
  181.     }
  182.     RETV
  183. }
  184.  
  185. static tree *
  186. sprout(tree **ppr, tree_t p_data, int *pi_balance,
  187.        int (*pfi_compare)(), void (*pfv_delete)())
  188. {
  189.     tree *p1, *p2, *sub;
  190.     int cmp;
  191.  
  192.     ENTER("sprout")
  193.  
  194.     /* are we grounded?  if so, add the node "here" and set the rebalance
  195.      * flag, then exit.
  196.      */
  197.     if (!*ppr) {
  198.         MSG("grounded. adding new node, setting h=true")
  199.         *ppr = (tree *) SHmalloc(sizeof(tree));
  200.         if (*ppr) {
  201.             (*ppr)->left = NULL;
  202.             (*ppr)->right = NULL;
  203.             (*ppr)->bal = 0;
  204.             (*ppr)->data = p_data;
  205.             *pi_balance = TRUE;
  206.         }
  207.         RET(*ppr);
  208.     }
  209.  
  210.     /* compare the data using routine passed by caller.
  211.      */
  212.     cmp = (*pfi_compare)(p_data, (*ppr)->data);
  213.  
  214.     /* if LESS, prepare to move to the left.
  215.      */
  216.     if (cmp < 0) {
  217.         MSG("LESS. sprouting left.")
  218.         sub = sprout(&(*ppr)->left, p_data, pi_balance,
  219.                  pfi_compare, pfv_delete);
  220.         if (sub && *pi_balance) {    /* left branch has grown */
  221.             MSG("LESS: left branch has grown")
  222.             switch ((*ppr)->bal) {
  223.             case 1:
  224.                 /* right branch WAS longer; bal is ok now */
  225.                 MSG("LESS: case 1.. bal restored implicitly")
  226.                 (*ppr)->bal = 0;
  227.                 *pi_balance = FALSE;
  228.                 break;
  229.             case 0:
  230.                 /* balance WAS okay; now left branch longer */
  231.                 MSG("LESS: case 0.. balnce bad but still ok")
  232.                 (*ppr)->bal = -1;
  233.                 break;
  234.             case -1:
  235.                 /* left branch was already too long. rebal */
  236.                 MSG("LESS: case -1: rebalancing")
  237.                 p1 = (*ppr)->left;
  238.                 if (p1->bal == -1) {        /* LL */
  239.                     MSG("LESS: single LL")
  240.                     (*ppr)->left = p1->right;
  241.                     p1->right = *ppr;
  242.                     (*ppr)->bal = 0;
  243.                     *ppr = p1;
  244.                 } else {            /* double LR */
  245.                     MSG("LESS: double LR")
  246.  
  247.                     p2 = p1->right;
  248.                     p1->right = p2->left;
  249.                     p2->left = p1;
  250.  
  251.                     (*ppr)->left = p2->right;
  252.                     p2->right = *ppr;
  253.  
  254.                     if (p2->bal == -1)
  255.                         (*ppr)->bal = 1;
  256.                     else
  257.                         (*ppr)->bal = 0;
  258.  
  259.                     if (p2->bal == 1)
  260.                         p1->bal = -1;
  261.                     else
  262.                         p1->bal = 0;
  263.                     *ppr = p2;
  264.                 } /*else*/
  265.                 (*ppr)->bal = 0;
  266.                 *pi_balance = FALSE;
  267.             } /*switch*/
  268.         } /*if*/
  269.         RET(sub)
  270.     } /*if*/
  271.  
  272.     /* if MORE, prepare to move to the right.
  273.      */
  274.     if (cmp > 0) {
  275.         MSG("MORE: sprouting to the right")
  276.         sub = sprout(&(*ppr)->right, p_data, pi_balance,
  277.                  pfi_compare, pfv_delete);
  278.         if (sub && *pi_balance) {
  279.             MSG("MORE: right branch has grown")
  280.  
  281.             switch ((*ppr)->bal) {
  282.             case -1:
  283.                 MSG("MORE: balance was off, fixed implicitly")
  284.                 (*ppr)->bal = 0;
  285.                 *pi_balance = FALSE;
  286.                 break;
  287.             case 0:
  288.                 MSG("MORE: balance was okay, now off but ok")
  289.                 (*ppr)->bal = 1;
  290.                 break;
  291.             case 1:
  292.                 MSG("MORE: balance was off, need to rebalance")
  293.                 p1 = (*ppr)->right;
  294.                 if (p1->bal == 1) {        /* RR */
  295.                     MSG("MORE: single RR")
  296.                     (*ppr)->right = p1->left;
  297.                     p1->left = *ppr;
  298.                     (*ppr)->bal = 0;
  299.                     *ppr = p1;
  300.                 } else {            /* double RL */
  301.                     MSG("MORE: double RL")
  302.  
  303.                     p2 = p1->left;
  304.                     p1->left = p2->right;
  305.                     p2->right = p1;
  306.  
  307.                     (*ppr)->right = p2->left;
  308.                     p2->left = *ppr;
  309.  
  310.                     if (p2->bal == 1)
  311.                         (*ppr)->bal = -1;
  312.                     else
  313.                         (*ppr)->bal = 0;
  314.  
  315.                     if (p2->bal == -1)
  316.                         p1->bal = 1;
  317.                     else
  318.                         p1->bal = 0;
  319.  
  320.                     *ppr = p2;
  321.                 } /*else*/
  322.                 (*ppr)->bal = 0;
  323.                 *pi_balance = FALSE;
  324.             } /*switch*/
  325.         } /*if*/
  326.         RET(sub)
  327.     } /*if*/
  328.  
  329.     /* not less, not more: this is the same key!  replace...
  330.      */
  331.     MSG("FOUND: Replacing data value")
  332.     *pi_balance = FALSE;
  333.     if (pfv_delete)
  334.         (*pfv_delete)((*ppr)->data);
  335.     (*ppr)->data = p_data;
  336.     RET(*ppr)
  337. }
  338.  
  339. static int
  340. delete(tree **ppr_p, int (*pfi_compare)(), tree_t p_user,
  341.        void (*pfv_uar)(), int *pi_balance, int *pi_uar_called)
  342. {
  343.     tree *pr_q;
  344.     int i_comp, i_ret;
  345.  
  346.     ENTER("delete")
  347.  
  348.     if (*ppr_p == NULL) {
  349.         MSG("key not in tree")
  350.         RET(FALSE)
  351.     }
  352.  
  353.     i_comp = (*pfi_compare)((*ppr_p)->data, p_user);
  354.     if (i_comp > 0) {
  355.         MSG("too high - scan left")
  356.         i_ret = delete(&(*ppr_p)->left, pfi_compare, p_user, pfv_uar,
  357.                    pi_balance, pi_uar_called);
  358.         if (*pi_balance)
  359.             bal_L(ppr_p, pi_balance);
  360.     } else if (i_comp < 0) {
  361.         MSG("too low - scan right")
  362.         i_ret = delete(&(*ppr_p)->right, pfi_compare, p_user, pfv_uar,
  363.                    pi_balance, pi_uar_called);
  364.         if (*pi_balance)
  365.             bal_R(ppr_p, pi_balance);
  366.     } else {
  367.         MSG("equal")
  368.         pr_q = *ppr_p;
  369.         if (pr_q->right == NULL) {
  370.             MSG("right subtree null")
  371.             *ppr_p = pr_q->left;
  372.             *pi_balance = TRUE;
  373.         } else if (pr_q->left == NULL) {
  374.             MSG("right subtree non-null, left subtree null")
  375.             *ppr_p = pr_q->right;
  376.             *pi_balance = TRUE;
  377.         } else {
  378.             MSG("neither subtree null")
  379.             del(&pr_q->left, pi_balance, &pr_q,
  380.                 pfv_uar, pi_uar_called);
  381.             if (*pi_balance)
  382.                 bal_L(ppr_p, pi_balance);
  383.         }
  384.         if (!*pi_uar_called && pfv_uar)
  385.             (*pfv_uar)(pr_q->data);
  386.         SHfree(pr_q);
  387.         i_ret = TRUE;
  388.     }
  389.     RET(i_ret)
  390. }
  391.  
  392. static void
  393. del(tree **ppr_r, int *pi_balance, tree **ppr_q,
  394.     void (*pfv_uar)(), int *pi_uar_called)
  395. {
  396.     ENTER("del")
  397.  
  398.     if ((*ppr_r)->right != NULL) {
  399.         del(&(*ppr_r)->right, pi_balance, ppr_q,
  400.             pfv_uar, pi_uar_called);
  401.         if (*pi_balance)
  402.             bal_R(ppr_r, pi_balance);
  403.     } else {
  404.         if (pfv_uar)
  405.             (*pfv_uar)((*ppr_q)->data);
  406.         *pi_uar_called = TRUE;
  407.         (*ppr_q)->data = (*ppr_r)->data;
  408.         *ppr_q = *ppr_r;
  409.         *ppr_r = (*ppr_r)->left;
  410.         *pi_balance = TRUE;
  411.     }
  412.  
  413.     RETV
  414. }
  415.  
  416. static void
  417. bal_L(tree **ppr_p, int *pi_balance) {
  418.     tree *p1, *p2;
  419.     int b1, b2;
  420.  
  421.     ENTER("bal_L")
  422.     MSG("left branch has shrunk")
  423.  
  424.     switch ((*ppr_p)->bal) {
  425.     case -1:
  426.         MSG("was imbalanced, fixed implicitly")
  427.         (*ppr_p)->bal = 0;
  428.         break;
  429.     case 0:
  430.         MSG("was okay, is now one off")
  431.         (*ppr_p)->bal = 1;
  432.         *pi_balance = FALSE;
  433.         break;
  434.     case 1:
  435.         MSG("was already off, this is too much")
  436.         p1 = (*ppr_p)->right;
  437.         b1 = p1->bal;
  438.         if (b1 >= 0) {
  439.             MSG("single RR")
  440.             (*ppr_p)->right = p1->left;
  441.             p1->left = *ppr_p;
  442.             if (b1 == 0) {
  443.                 MSG("b1 == 0")
  444.                 (*ppr_p)->bal = 1;
  445.                 p1->bal = -1;
  446.                 *pi_balance = FALSE;
  447.             } else {
  448.                 MSG("b1 != 0")
  449.                 (*ppr_p)->bal = 0;
  450.                 p1->bal = 0;
  451.             }
  452.             *ppr_p = p1;
  453.         } else {
  454.             MSG("double RL")
  455.             p2 = p1->left;
  456.             b2 = p2->bal;
  457.             p1->left = p2->right;
  458.             p2->right = p1;
  459.             (*ppr_p)->right = p2->left;
  460.             p2->left = *ppr_p;
  461.             if (b2 == 1)
  462.                 (*ppr_p)->bal = -1;
  463.             else
  464.                 (*ppr_p)->bal = 0;
  465.             if (b2 == -1)
  466.                 p1->bal = 1;
  467.             else
  468.                 p1->bal = 0;
  469.             *ppr_p = p2;
  470.             p2->bal = 0;
  471.         }
  472.     }
  473.     RETV
  474. }
  475.  
  476. static void
  477. bal_R(tree **ppr_p, int *pi_balance) {
  478.     tree *p1, *p2;
  479.     int b1, b2;
  480.  
  481.     ENTER("bal_R")
  482.     MSG("right branch has shrunk")
  483.     switch ((*ppr_p)->bal) {
  484.     case 1:
  485.         MSG("was imbalanced, fixed implicitly")
  486.         (*ppr_p)->bal = 0;
  487.         break;
  488.     case 0:
  489.         MSG("was okay, is now one off")
  490.         (*ppr_p)->bal = -1;
  491.         *pi_balance = FALSE;
  492.         break;
  493.     case -1:
  494.         MSG("was already off, this is too much")
  495.         p1 = (*ppr_p)->left;
  496.         b1 = p1->bal;
  497.         if (b1 <= 0) {
  498.             MSG("single LL")
  499.             (*ppr_p)->left = p1->right;
  500.             p1->right = *ppr_p;
  501.             if (b1 == 0) {
  502.                 MSG("b1 == 0")
  503.                 (*ppr_p)->bal = -1;
  504.                 p1->bal = 1;
  505.                 *pi_balance = FALSE;
  506.             } else {
  507.                 MSG("b1 != 0")
  508.                 (*ppr_p)->bal = 0;
  509.                 p1->bal = 0;
  510.             }
  511.             *ppr_p = p1;
  512.         } else {
  513.             MSG("double LR")
  514.             p2 = p1->right;
  515.             b2 = p2->bal;
  516.             p1->right = p2->left;
  517.             p2->left = p1;
  518.             (*ppr_p)->left = p2->right;
  519.             p2->right = *ppr_p;
  520.             if (b2 == -1)
  521.                 (*ppr_p)->bal = 1;
  522.             else
  523.                 (*ppr_p)->bal = 0;
  524.             if (b2 == 1)
  525.                 p1->bal = -1;
  526.             else
  527.                 p1->bal = 0;
  528.             *ppr_p = p2;
  529.             p2->bal = 0;
  530.         }
  531.     }
  532.     RETV
  533. }
  534.