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