usr/src/lib/libresolv2/common/isc/tree.c

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