git.sur5r.net Git - openldap/blob - libraries/libavl/avl.c

   1 /* avl.c - routines to implement an avl tree */
   2 /*
   3  * Copyright (c) 1993 Regents of the University of Michigan.
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms are permitted
   7  * provided that this notice is preserved and that due credit is given
   8  * to the University of Michigan at Ann Arbor. The name of the University
   9  * may not be used to endorse or promote products derived from this
  10  * software without specific prior written permission. This software
  11  * is provided ``as is'' without express or implied warranty.
  12  */
  13
  14 #include "portable.h"
  15
  16 #ifndef lint
  17 static char copyright[] = "@(#) Copyright (c) 1993 Regents of the University of Michigan.\nAll rights reserved.\n";
  18 static char avl_version[] = "AVL library version 1.0\n";
  19 #endif
  20
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <sys/types.h>
  24
  25 #include "avl.h"
  26
  27 #define ROTATERIGHT(x)  { \
  28         Avlnode *tmp;\
  29         if ( *(x) == NULL || (*(x))->avl_left == NULL ) {\
  30                 (void) printf("RR error\n"); exit(1); \
  31         }\
  32         tmp = (*(x))->avl_left;\
  33         (*(x))->avl_left = tmp->avl_right;\
  34         tmp->avl_right = *(x);\
  35         *(x) = tmp;\
  36 }
  37 #define ROTATELEFT(x)   { \
  38         Avlnode *tmp;\
  39         if ( *(x) == NULL || (*(x))->avl_right == NULL ) {\
  40                 (void) printf("RL error\n"); exit(1); \
  41         }\
  42         tmp = (*(x))->avl_right;\
  43         (*(x))->avl_right = tmp->avl_left;\
  44         tmp->avl_left = *x;\
  45         *(x) = tmp;\
  46 }
  47
  48 /*
  49  * ravl_insert - called from avl_insert() to do a recursive insert into
  50  * and balance of an avl tree.
  51  */
  52
  53 static
  54 int ravl_insert( iroot, data, taller, fcmp, fdup, depth )
  55     Avlnode     **iroot;
  56     caddr_t     data;
  57     int         *taller;
  58     IFP         fcmp;           /* comparison function */
  59     IFP         fdup;           /* function to call for duplicates */
  60     int         depth;
  61 {
  62         int     rc, cmp, tallersub;
  63         Avlnode *l, *r;
  64
  65         if ( *iroot == 0 ) {
  66                 if ( (*iroot = (Avlnode *) malloc( sizeof( Avlnode ) ))
  67                     == NULL ) {
  68                         return( -1 );
  69                 }
  70                 (*iroot)->avl_left = 0;
  71                 (*iroot)->avl_right = 0;
  72                 (*iroot)->avl_bf = 0;
  73                 (*iroot)->avl_data = data;
  74                 *taller = 1;
  75                 return( 0 );
  76         }
  77
  78         cmp = (*fcmp)( data, (*iroot)->avl_data );
  79
  80         /* equal - duplicate name */
  81         if ( cmp == 0 ) {
  82                 *taller = 0;
  83                 return( (*fdup)( (*iroot)->avl_data, data ) );
  84         }
  85
  86         /* go right */
  87         else if ( cmp > 0 ) {
  88                 rc = ravl_insert( &((*iroot)->avl_right), data, &tallersub,
  89                    fcmp, fdup, depth );
  90                 if ( tallersub )
  91                         switch ( (*iroot)->avl_bf ) {
  92                         case LH : /* left high - balance is restored */
  93                                 (*iroot)->avl_bf = EH;
  94                                 *taller = 0;
  95                                 break;
  96                         case EH : /* equal height - now right heavy */
  97                                 (*iroot)->avl_bf = RH;
  98                                 *taller = 1;
  99                                 break;
 100                         case RH : /* right heavy to start - right balance */
 101                                 r = (*iroot)->avl_right;
 102                                 switch ( r->avl_bf ) {
 103                                 case LH : /* double rotation left */
 104                                         l = r->avl_left;
 105                                         switch ( l->avl_bf ) {
 106                                         case LH : (*iroot)->avl_bf = EH;
 107                                                   r->avl_bf = RH;
 108                                                   break;
 109                                         case EH : (*iroot)->avl_bf = EH;
 110                                                   r->avl_bf = EH;
 111                                                   break;
 112                                         case RH : (*iroot)->avl_bf = LH;
 113                                                   r->avl_bf = EH;
 114                                                   break;
 115                                         }
 116                                         l->avl_bf = EH;
 117                                         ROTATERIGHT( (&r) )
 118                                         (*iroot)->avl_right = r;
 119                                         ROTATELEFT( iroot )
 120                                         *taller = 0;
 121                                         break;
 122                                 case EH : /* This should never happen */
 123                                         break;
 124                                 case RH : /* single rotation left */
 125                                         (*iroot)->avl_bf = EH;
 126                                         r->avl_bf = EH;
 127                                         ROTATELEFT( iroot )
 128                                         *taller = 0;
 129                                         break;
 130                                 }
 131                                 break;
 132                         }
 133                 else
 134                         *taller = 0;
 135         }
 136
 137         /* go left */
 138         else {
 139                 rc = ravl_insert( &((*iroot)->avl_left), data, &tallersub,
 140                    fcmp, fdup, depth );
 141                 if ( tallersub )
 142                         switch ( (*iroot)->avl_bf ) {
 143                         case LH : /* left high to start - left balance */
 144                                 l = (*iroot)->avl_left;
 145                                 switch ( l->avl_bf ) {
 146                                 case LH : /* single rotation right */
 147                                         (*iroot)->avl_bf = EH;
 148                                         l->avl_bf = EH;
 149                                         ROTATERIGHT( iroot )
 150                                         *taller = 0;
 151                                         break;
 152                                 case EH : /* this should never happen */
 153                                         break;
 154                                 case RH : /* double rotation right */
 155                                         r = l->avl_right;
 156                                         switch ( r->avl_bf ) {
 157                                         case LH : (*iroot)->avl_bf = RH;
 158                                                   l->avl_bf = EH;
 159                                                   break;
 160                                         case EH : (*iroot)->avl_bf = EH;
 161                                                   l->avl_bf = EH;
 162                                                   break;
 163                                         case RH : (*iroot)->avl_bf = EH;
 164                                                   l->avl_bf = LH;
 165                                                   break;
 166                                         }
 167                                         r->avl_bf = EH;
 168                                         ROTATELEFT( (&l) )
 169                                         (*iroot)->avl_left = l;
 170                                         ROTATERIGHT( iroot )
 171                                         *taller = 0;
 172                                         break;
 173                                 }
 174                                 break;
 175                         case EH : /* equal height - now left heavy */
 176                                 (*iroot)->avl_bf = LH;
 177                                 *taller = 1;
 178                                 break;
 179                         case RH : /* right high - balance is restored */
 180                                 (*iroot)->avl_bf = EH;
 181                                 *taller = 0;
 182                                 break;
 183                         }
 184                 else
 185                         *taller = 0;
 186         }
 187
 188         return( rc );
 189 }
 190
 191 /*
 192  * avl_insert -- insert a node containing data data into the avl tree
 193  * with root root.  fcmp is a function to call to compare the data portion
 194  * of two nodes.  it should take two arguments and return <, >, or == 0,
 195  * depending on whether its first argument is <, >, or == its second
 196  * argument (like strcmp, e.g.).  fdup is a function to call when a duplicate
 197  * node is inserted.  it should return 0, or -1 and its return value
 198  * will be the return value from avl_insert in the case of a duplicate node.
 199  * the function will be called with the original node's data as its first
 200  * argument and with the incoming duplicate node's data as its second
 201  * argument.  this could be used, for example, to keep a count with each
 202  * node.
 203  *
 204  * NOTE: this routine may malloc memory
 205  */
 206
 207 int avl_insert( root, data, fcmp, fdup )
 208     Avlnode     **root;
 209     caddr_t     data;
 210     IFP         fcmp;
 211     IFP         fdup;
 212 {
 213         int     taller;
 214
 215         return( ravl_insert( root, data, &taller, fcmp, fdup, 0 ) );
 216 }
 217
 218 /*
 219  * right_balance() - called from delete when root's right subtree has
 220  * been shortened because of a deletion.
 221  */
 222
 223 static int
 224 right_balance( root )
 225     Avlnode     **root;
 226 {
 227         int     shorter = -1;
 228         Avlnode *r, *l;
 229
 230         switch( (*root)->avl_bf ) {
 231         case RH:        /* was right high - equal now */
 232                 (*root)->avl_bf = EH;
 233                 shorter = 1;
 234                 break;
 235         case EH:        /* was equal - left high now */
 236                 (*root)->avl_bf = LH;
 237                 shorter = 0;
 238                 break;
 239         case LH:        /* was right high - balance */
 240                 l = (*root)->avl_left;
 241                 switch ( l->avl_bf ) {
 242                 case RH : /* double rotation left */
 243                         r = l->avl_right;
 244                         switch ( r->avl_bf ) {
 245                         case RH :
 246                                 (*root)->avl_bf = EH;
 247                                 l->avl_bf = LH;
 248                                 break;
 249                         case EH :
 250                                 (*root)->avl_bf = EH;
 251                                 l->avl_bf = EH;
 252                                 break;
 253                         case LH :
 254                                 (*root)->avl_bf = RH;
 255                                 l->avl_bf = EH;
 256                                 break;
 257                         }
 258                         r->avl_bf = EH;
 259                         ROTATELEFT( (&l) )
 260                         (*root)->avl_left = l;
 261                         ROTATERIGHT( root )
 262                         shorter = 1;
 263                         break;
 264                 case EH : /* right rotation */
 265                         (*root)->avl_bf = LH;
 266                         l->avl_bf = RH;
 267                         ROTATERIGHT( root );
 268                         shorter = 0;
 269                         break;
 270                 case LH : /* single rotation right */
 271                         (*root)->avl_bf = EH;
 272                         l->avl_bf = EH;
 273                         ROTATERIGHT( root )
 274                         shorter = 1;
 275                         break;
 276                 }
 277                 break;
 278         }
 279
 280         return( shorter );
 281 }
 282
 283 /*
 284  * left_balance() - called from delete when root's left subtree has
 285  * been shortened because of a deletion.
 286  */
 287
 288 static
 289 int left_balance( root )
 290     Avlnode     **root;
 291 {
 292         int     shorter = -1;
 293         Avlnode *r, *l;
 294
 295         switch( (*root)->avl_bf ) {
 296         case LH:        /* was left high - equal now */
 297                 (*root)->avl_bf = EH;
 298                 shorter = 1;
 299                 break;
 300         case EH:        /* was equal - right high now */
 301                 (*root)->avl_bf = RH;
 302                 shorter = 0;
 303                 break;
 304         case RH:        /* was right high - balance */
 305                 r = (*root)->avl_right;
 306                 switch ( r->avl_bf ) {
 307                 case LH : /* double rotation left */
 308                         l = r->avl_left;
 309                         switch ( l->avl_bf ) {
 310                         case LH :
 311                                 (*root)->avl_bf = EH;
 312                                 r->avl_bf = RH;
 313                                 break;
 314                         case EH :
 315                                 (*root)->avl_bf = EH;
 316                                 r->avl_bf = EH;
 317                                 break;
 318                         case RH :
 319                                 (*root)->avl_bf = LH;
 320                                 r->avl_bf = EH;
 321                                 break;
 322                         }
 323                         l->avl_bf = EH;
 324                         ROTATERIGHT( (&r) )
 325                         (*root)->avl_right = r;
 326                         ROTATELEFT( root )
 327                         shorter = 1;
 328                         break;
 329                 case EH : /* single rotation left */
 330                         (*root)->avl_bf = RH;
 331                         r->avl_bf = LH;
 332                         ROTATELEFT( root );
 333                         shorter = 0;
 334                         break;
 335                 case RH : /* single rotation left */
 336                         (*root)->avl_bf = EH;
 337                         r->avl_bf = EH;
 338                         ROTATELEFT( root )
 339                         shorter = 1;
 340                         break;
 341                 }
 342                 break;
 343         }
 344
 345         return( shorter );
 346 }
 347
 348 /*
 349  * ravl_delete() - called from avl_delete to do recursive deletion of a
 350  * node from an avl tree.  It finds the node recursively, deletes it,
 351  * and returns shorter if the tree is shorter after the deletion and
 352  * rebalancing.
 353  */
 354
 355 static caddr_t
 356 ravl_delete( root, data, fcmp, shorter )
 357     Avlnode     **root;
 358     caddr_t     data;
 359     IFP         fcmp;
 360     int         *shorter;
 361 {
 362         int     shortersubtree = 0;
 363         int     cmp;
 364         caddr_t savedata;
 365         Avlnode *minnode, *savenode;
 366
 367         if ( *root == NULLAVL )
 368                 return( 0 );
 369
 370         cmp = (*fcmp)( data, (*root)->avl_data );
 371
 372         /* found it! */
 373         if ( cmp == 0 ) {
 374                 savenode = *root;
 375                 savedata = savenode->avl_data;
 376
 377                 /* simple cases: no left child */
 378                 if ( (*root)->avl_left == 0 ) {
 379                         *root = (*root)->avl_right;
 380                         *shorter = 1;
 381                         free( (char *) savenode );
 382                         return( savedata );
 383                 /* no right child */
 384                 } else if ( (*root)->avl_right == 0 ) {
 385                         *root = (*root)->avl_left;
 386                         *shorter = 1;
 387                         free( (char *) savenode );
 388                         return( savedata );
 389                 }
 390
 391                 /*
 392                  * avl_getmin will return to us the smallest node greater
 393                  * than the one we are trying to delete.  deleting this node
 394                  * from the right subtree is guaranteed to end in one of the
 395                  * simple cases above.
 396                  */
 397
 398                 minnode = (*root)->avl_right;
 399                 while ( minnode->avl_left != NULLAVL )
 400                         minnode = minnode->avl_left;
 401
 402                 /* swap the data */
 403                 (*root)->avl_data = minnode->avl_data;
 404                 minnode->avl_data = savedata;
 405
 406                 savedata = ravl_delete( &(*root)->avl_right, data, fcmp,
 407                     &shortersubtree );
 408
 409                 if ( shortersubtree )
 410                         *shorter = right_balance( root );
 411                 else
 412                         *shorter = 0;
 413         /* go left */
 414         } else if ( cmp < 0 ) {
 415                 if ( (savedata = ravl_delete( &(*root)->avl_left, data, fcmp,
 416                     &shortersubtree )) == 0 ) {
 417                         *shorter = 0;
 418                         return( 0 );
 419                 }
 420
 421                 /* left subtree shorter? */
 422                 if ( shortersubtree )
 423                         *shorter = left_balance( root );
 424                 else
 425                         *shorter = 0;
 426         /* go right */
 427         } else {
 428                 if ( (savedata = ravl_delete( &(*root)->avl_right, data, fcmp,
 429                     &shortersubtree )) == 0 ) {
 430                         *shorter = 0;
 431                         return( 0 );
 432                 }
 433
 434                 if ( shortersubtree )
 435                         *shorter = right_balance( root );
 436                 else
 437                         *shorter = 0;
 438         }
 439
 440         return( savedata );
 441 }
 442
 443 /*
 444  * avl_delete() - deletes the node containing data (according to fcmp) from
 445  * the avl tree rooted at root.
 446  */
 447
 448 caddr_t
 449 avl_delete( root, data, fcmp )
 450     Avlnode     **root;
 451     caddr_t     data;
 452     IFP         fcmp;
 453 {
 454         int     shorter;
 455
 456         return( ravl_delete( root, data, fcmp, &shorter ) );
 457 }
 458
 459 static
 460 int avl_inapply( root, fn, arg, stopflag )
 461     Avlnode     *root;
 462     IFP         fn;
 463     caddr_t     arg;
 464     int         stopflag;
 465 {
 466         if ( root == 0 )
 467                 return( AVL_NOMORE );
 468
 469         if ( root->avl_left != 0 )
 470                 if ( avl_inapply( root->avl_left, fn, arg, stopflag )
 471                     == stopflag )
 472                         return( stopflag );
 473
 474         if ( (*fn)( root->avl_data, arg ) == stopflag )
 475                 return( stopflag );
 476
 477         if ( root->avl_right == 0 )
 478                 return( AVL_NOMORE );
 479         else
 480                 return( avl_inapply( root->avl_right, fn, arg, stopflag ) );
 481 }
 482
 483 static
 484 int avl_postapply( root, fn, arg, stopflag )
 485     Avlnode     *root;
 486     IFP         fn;
 487     caddr_t     arg;
 488     int         stopflag;
 489 {
 490         if ( root == 0 )
 491                 return( AVL_NOMORE );
 492
 493         if ( root->avl_left != 0 )
 494                 if ( avl_postapply( root->avl_left, fn, arg, stopflag )
 495                     == stopflag )
 496                         return( stopflag );
 497
 498         if ( root->avl_right != 0 )
 499                 if ( avl_postapply( root->avl_right, fn, arg, stopflag )
 500                     == stopflag )
 501                         return( stopflag );
 502
 503         return( (*fn)( root->avl_data, arg ) );
 504 }
 505
 506 static
 507 int avl_preapply( root, fn, arg, stopflag )
 508     Avlnode     *root;
 509     IFP         fn;
 510     caddr_t     arg;
 511     int         stopflag;
 512 {
 513         if ( root == 0 )
 514                 return( AVL_NOMORE );
 515
 516         if ( (*fn)( root->avl_data, arg ) == stopflag )
 517                 return( stopflag );
 518
 519         if ( root->avl_left != 0 )
 520                 if ( avl_preapply( root->avl_left, fn, arg, stopflag )
 521                     == stopflag )
 522                         return( stopflag );
 523
 524         if ( root->avl_right == 0 )
 525                 return( AVL_NOMORE );
 526         else
 527                 return( avl_preapply( root->avl_right, fn, arg, stopflag ) );
 528 }
 529
 530 /*
 531  * avl_apply -- avl tree root is traversed, function fn is called with
 532  * arguments arg and the data portion of each node.  if fn returns stopflag,
 533  * the traversal is cut short, otherwise it continues.  Do not use -6 as
 534  * a stopflag, as this is what is used to indicate the traversal ran out
 535  * of nodes.
 536  */
 537
 538 int avl_apply( root, fn, arg, stopflag, type )
 539     Avlnode     *root;
 540     IFP         fn;
 541     caddr_t     arg;
 542     int         stopflag;
 543     int         type;
 544 {
 545         switch ( type ) {
 546         case AVL_INORDER:
 547                 return( avl_inapply( root, fn, arg, stopflag ) );
 548         case AVL_PREORDER:
 549                 return( avl_preapply( root, fn, arg, stopflag ) );
 550         case AVL_POSTORDER:
 551                 return( avl_postapply( root, fn, arg, stopflag ) );
 552         default:
 553                 fprintf( stderr, "Invalid traversal type %d\n", type );
 554                 return( -1 );
 555         }
 556
 557         /* NOTREACHED */
 558 }
 559
 560 /*
 561  * avl_prefixapply - traverse avl tree root, applying function fprefix
 562  * to any nodes that match.  fcmp is called with data as its first arg
 563  * and the current node's data as its second arg.  it should return
 564  * 0 if they match, < 0 if data is less, and > 0 if data is greater.
 565  * the idea is to efficiently find all nodes that are prefixes of
 566  * some key...  Like avl_apply, this routine also takes a stopflag
 567  * and will return prematurely if fmatch returns this value.  Otherwise,
 568  * AVL_NOMORE is returned.
 569  */
 570
 571 int avl_prefixapply( root, data, fmatch, marg, fcmp, carg, stopflag )
 572     Avlnode     *root;
 573     caddr_t     data;
 574     IFP         fmatch;
 575     caddr_t     marg;
 576     IFP         fcmp;
 577     caddr_t     carg;
 578     int         stopflag;
 579 {
 580         int     cmp;
 581
 582         if ( root == 0 )
 583                 return( AVL_NOMORE );
 584
 585         cmp = (*fcmp)( data, root->avl_data, carg );
 586         if ( cmp == 0 ) {
 587                 if ( (*fmatch)( root->avl_data, marg ) == stopflag )
 588                         return( stopflag );
 589
 590                 if ( root->avl_left != 0 )
 591                         if ( avl_prefixapply( root->avl_left, data, fmatch,
 592                             marg, fcmp, carg, stopflag ) == stopflag )
 593                                 return( stopflag );
 594
 595                 if ( root->avl_right != 0 )
 596                         return( avl_prefixapply( root->avl_right, data, fmatch,
 597                             marg, fcmp, carg, stopflag ) );
 598                 else
 599                         return( AVL_NOMORE );
 600
 601         } else if ( cmp < 0 ) {
 602                 if ( root->avl_left != 0 )
 603                         return( avl_prefixapply( root->avl_left, data, fmatch,
 604                             marg, fcmp, carg, stopflag ) );
 605         } else {
 606                 if ( root->avl_right != 0 )
 607                         return( avl_prefixapply( root->avl_right, data, fmatch,
 608                             marg, fcmp, carg, stopflag ) );
 609         }
 610
 611         return( AVL_NOMORE );
 612 }
 613
 614 /*
 615  * avl_free -- traverse avltree root, freeing the memory it is using.
 616  * the dfree() is called to free the data portion of each node.  The
 617  * number of items actually freed is returned.
 618  */
 619
 620 int avl_free( root, dfree )
 621     Avlnode     *root;
 622     IFP         dfree;
 623 {
 624         int     nleft, nright;
 625
 626         if ( root == 0 )
 627                 return( 0 );
 628
 629         nleft = nright = 0;
 630         if ( root->avl_left != 0 )
 631                 nleft = avl_free( root->avl_left, dfree );
 632
 633         if ( root->avl_right != 0 )
 634                 nright = avl_free( root->avl_right, dfree );
 635
 636         if ( dfree )
 637                 (*dfree)( root->avl_data );
 638
 639         return( nleft + nright + 1 );
 640 }
 641
 642 /*
 643  * avl_find -- search avltree root for a node with data data.  the function
 644  * cmp is used to compare things.  it is called with data as its first arg
 645  * and the current node data as its second.  it should return 0 if they match,
 646  * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2.
 647  */
 648
 649 caddr_t
 650 avl_find( root, data, fcmp )
 651     Avlnode     *root;
 652     caddr_t     data;
 653     IFP fcmp;
 654 {
 655         int     cmp;
 656
 657         while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
 658                 if ( cmp < 0 )
 659                         root = root->avl_left;
 660                 else
 661                         root = root->avl_right;
 662         }
 663
 664         return( root ? root->avl_data : 0 );
 665 }
 666
 667 /*
 668  * avl_find_lin -- search avltree root linearly for a node with data data.
 669  * the function cmp is used to compare things.  it is called with data as its
 670  * first arg and the current node data as its second.  it should return 0 if
 671  * they match, non-zero otherwise.
 672  */
 673
 674 caddr_t
 675 avl_find_lin( root, data, fcmp )
 676     Avlnode     *root;
 677     caddr_t     data;
 678     IFP         fcmp;
 679 {
 680         caddr_t res;
 681
 682         if ( root == 0 )
 683                 return( NULL );
 684
 685         if ( (*fcmp)( data, root->avl_data ) == 0 )
 686                 return( root->avl_data );
 687
 688         if ( root->avl_left != 0 )
 689                 if ( (res = avl_find_lin( root->avl_left, data, fcmp ))
 690                     != NULL )
 691                         return( res );
 692
 693         if ( root->avl_right == 0 )
 694                 return( NULL );
 695         else
 696                 return( avl_find_lin( root->avl_right, data, fcmp ) );
 697 }
 698
 699 static caddr_t  *avl_list;
 700 static int      avl_maxlist;
 701 static int      avl_nextlist;
 702
 703 #define AVL_GRABSIZE    100
 704
 705 /* ARGSUSED */
 706 static
 707 int avl_buildlist( data, arg )
 708     caddr_t     data;
 709     int arg;
 710 {
 711         static int      slots;
 712
 713         if ( avl_list == (caddr_t *) 0 ) {
 714                 avl_list = (caddr_t *) malloc(AVL_GRABSIZE * sizeof(caddr_t));
 715                 slots = AVL_GRABSIZE;
 716                 avl_maxlist = 0;
 717         } else if ( avl_maxlist == slots ) {
 718                 slots += AVL_GRABSIZE;
 719                 avl_list = (caddr_t *) realloc( (char *) avl_list,
 720                     (unsigned) slots * sizeof(caddr_t));
 721         }
 722
 723         avl_list[ avl_maxlist++ ] = data;
 724
 725         return( 0 );
 726 }
 727
 728 /*
 729  * avl_getfirst() and avl_getnext() are provided as alternate tree
 730  * traversal methods, to be used when a single function cannot be
 731  * provided to be called with every node in the tree.  avl_getfirst()
 732  * traverses the tree and builds a linear list of all the nodes,
 733  * returning the first node.  avl_getnext() returns the next thing
 734  * on the list built by avl_getfirst().  This means that avl_getfirst()
 735  * can take a while, and that the tree should not be messed with while
 736  * being traversed in this way, and that multiple traversals (even of
 737  * different trees) cannot be active at once.
 738  */
 739
 740 caddr_t
 741 avl_getfirst( root )
 742     Avlnode     *root;
 743 {
 744         if ( avl_list ) {
 745                 free( (char *) avl_list);
 746                 avl_list = (caddr_t *) 0;
 747         }
 748         avl_maxlist = 0;
 749         avl_nextlist = 0;
 750
 751         if ( root == 0 )
 752                 return( 0 );
 753
 754         (void) avl_apply( root, avl_buildlist, (caddr_t) 0, -1, AVL_INORDER );
 755
 756         return( avl_list[ avl_nextlist++ ] );
 757 }
 758
 759 caddr_t
 760 avl_getnext()
 761 {
 762         if ( avl_list == 0 )
 763                 return( 0 );
 764
 765         if ( avl_nextlist == avl_maxlist ) {
 766                 free( (caddr_t) avl_list);
 767                 avl_list = (caddr_t *) 0;
 768                 return( 0 );
 769         }
 770
 771         return( avl_list[ avl_nextlist++ ] );
 772 }
 773
 774 int avl_dup_error()
 775 {
 776         return( -1 );
 777 }
 778
 779 int avl_dup_ok()
 780 {
 781         return( 0 );
 782 }