contrib/bind-9.3/lib/bind/isc/tree.c

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