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