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 int
  54 ravl_insert(
  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 {
  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
 209 avl_insert( Avlnode **root, caddr_t data, IFP fcmp, IFP fdup )
 210 {
 211         int     taller;
 212
 213         return( ravl_insert( root, data, &taller, fcmp, fdup, 0 ) );
 214 }
 215
 216 /*
 217  * right_balance() - called from delete when root's right subtree has
 218  * been shortened because of a deletion.
 219  */
 220
 221 static int
 222 right_balance( 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 int
 286 left_balance( Avlnode **root )
 287 {
 288         int     shorter = -1;
 289         Avlnode *r, *l;
 290
 291         switch( (*root)->avl_bf ) {
 292         case LH:        /* was left high - equal now */
 293                 (*root)->avl_bf = EH;
 294                 shorter = 1;
 295                 break;
 296         case EH:        /* was equal - right high now */
 297                 (*root)->avl_bf = RH;
 298                 shorter = 0;
 299                 break;
 300         case RH:        /* was right high - balance */
 301                 r = (*root)->avl_right;
 302                 switch ( r->avl_bf ) {
 303                 case LH : /* double rotation left */
 304                         l = r->avl_left;
 305                         switch ( l->avl_bf ) {
 306                         case LH :
 307                                 (*root)->avl_bf = EH;
 308                                 r->avl_bf = RH;
 309                                 break;
 310                         case EH :
 311                                 (*root)->avl_bf = EH;
 312                                 r->avl_bf = EH;
 313                                 break;
 314                         case RH :
 315                                 (*root)->avl_bf = LH;
 316                                 r->avl_bf = EH;
 317                                 break;
 318                         }
 319                         l->avl_bf = EH;
 320                         ROTATERIGHT( (&r) )
 321                         (*root)->avl_right = r;
 322                         ROTATELEFT( root )
 323                         shorter = 1;
 324                         break;
 325                 case EH : /* single rotation left */
 326                         (*root)->avl_bf = RH;
 327                         r->avl_bf = LH;
 328                         ROTATELEFT( root );
 329                         shorter = 0;
 330                         break;
 331                 case RH : /* single rotation left */
 332                         (*root)->avl_bf = EH;
 333                         r->avl_bf = EH;
 334                         ROTATELEFT( root )
 335                         shorter = 1;
 336                         break;
 337                 }
 338                 break;
 339         }
 340
 341         return( shorter );
 342 }
 343
 344 /*
 345  * ravl_delete() - called from avl_delete to do recursive deletion of a
 346  * node from an avl tree.  It finds the node recursively, deletes it,
 347  * and returns shorter if the tree is shorter after the deletion and
 348  * rebalancing.
 349  */
 350
 351 static caddr_t
 352 ravl_delete( Avlnode **root, caddr_t data, IFP fcmp, int *shorter )
 353 {
 354         int     shortersubtree = 0;
 355         int     cmp;
 356         caddr_t savedata;
 357         Avlnode *minnode, *savenode;
 358
 359         if ( *root == NULLAVL )
 360                 return( 0 );
 361
 362         cmp = (*fcmp)( data, (*root)->avl_data );
 363
 364         /* found it! */
 365         if ( cmp == 0 ) {
 366                 savenode = *root;
 367                 savedata = savenode->avl_data;
 368
 369                 /* simple cases: no left child */
 370                 if ( (*root)->avl_left == 0 ) {
 371                         *root = (*root)->avl_right;
 372                         *shorter = 1;
 373                         free( (char *) savenode );
 374                         return( savedata );
 375                 /* no right child */
 376                 } else if ( (*root)->avl_right == 0 ) {
 377                         *root = (*root)->avl_left;
 378                         *shorter = 1;
 379                         free( (char *) savenode );
 380                         return( savedata );
 381                 }
 382
 383                 /*
 384                  * avl_getmin will return to us the smallest node greater
 385                  * than the one we are trying to delete.  deleting this node
 386                  * from the right subtree is guaranteed to end in one of the
 387                  * simple cases above.
 388                  */
 389
 390                 minnode = (*root)->avl_right;
 391                 while ( minnode->avl_left != NULLAVL )
 392                         minnode = minnode->avl_left;
 393
 394                 /* swap the data */
 395                 (*root)->avl_data = minnode->avl_data;
 396                 minnode->avl_data = savedata;
 397
 398                 savedata = ravl_delete( &(*root)->avl_right, data, fcmp,
 399                     &shortersubtree );
 400
 401                 if ( shortersubtree )
 402                         *shorter = right_balance( root );
 403                 else
 404                         *shorter = 0;
 405         /* go left */
 406         } else if ( cmp < 0 ) {
 407                 if ( (savedata = ravl_delete( &(*root)->avl_left, data, fcmp,
 408                     &shortersubtree )) == 0 ) {
 409                         *shorter = 0;
 410                         return( 0 );
 411                 }
 412
 413                 /* left subtree shorter? */
 414                 if ( shortersubtree )
 415                         *shorter = left_balance( root );
 416                 else
 417                         *shorter = 0;
 418         /* go right */
 419         } else {
 420                 if ( (savedata = ravl_delete( &(*root)->avl_right, data, fcmp,
 421                     &shortersubtree )) == 0 ) {
 422                         *shorter = 0;
 423                         return( 0 );
 424                 }
 425
 426                 if ( shortersubtree )
 427                         *shorter = right_balance( root );
 428                 else
 429                         *shorter = 0;
 430         }
 431
 432         return( savedata );
 433 }
 434
 435 /*
 436  * avl_delete() - deletes the node containing data (according to fcmp) from
 437  * the avl tree rooted at root.
 438  */
 439
 440 caddr_t
 441 avl_delete( Avlnode **root, caddr_t data, IFP fcmp )
 442 {
 443         int     shorter;
 444
 445         return( ravl_delete( root, data, fcmp, &shorter ) );
 446 }
 447
 448 static int
 449 avl_inapply( Avlnode *root, IFP fn, caddr_t arg, int stopflag )
 450 {
 451         if ( root == 0 )
 452                 return( AVL_NOMORE );
 453
 454         if ( root->avl_left != 0 )
 455                 if ( avl_inapply( root->avl_left, fn, arg, stopflag )
 456                     == stopflag )
 457                         return( stopflag );
 458
 459         if ( (*fn)( root->avl_data, arg ) == stopflag )
 460                 return( stopflag );
 461
 462         if ( root->avl_right == 0 )
 463                 return( AVL_NOMORE );
 464         else
 465                 return( avl_inapply( root->avl_right, fn, arg, stopflag ) );
 466 }
 467
 468 static int
 469 avl_postapply( Avlnode *root, IFP fn, caddr_t arg, int stopflag )
 470 {
 471         if ( root == 0 )
 472                 return( AVL_NOMORE );
 473
 474         if ( root->avl_left != 0 )
 475                 if ( avl_postapply( root->avl_left, fn, arg, stopflag )
 476                     == stopflag )
 477                         return( stopflag );
 478
 479         if ( root->avl_right != 0 )
 480                 if ( avl_postapply( root->avl_right, fn, arg, stopflag )
 481                     == stopflag )
 482                         return( stopflag );
 483
 484         return( (*fn)( root->avl_data, arg ) );
 485 }
 486
 487 static int
 488 avl_preapply( Avlnode *root, IFP fn, caddr_t arg, int stopflag )
 489 {
 490         if ( root == 0 )
 491                 return( AVL_NOMORE );
 492
 493         if ( (*fn)( root->avl_data, arg ) == stopflag )
 494                 return( stopflag );
 495
 496         if ( root->avl_left != 0 )
 497                 if ( avl_preapply( root->avl_left, fn, arg, stopflag )
 498                     == stopflag )
 499                         return( stopflag );
 500
 501         if ( root->avl_right == 0 )
 502                 return( AVL_NOMORE );
 503         else
 504                 return( avl_preapply( root->avl_right, fn, arg, stopflag ) );
 505 }
 506
 507 /*
 508  * avl_apply -- avl tree root is traversed, function fn is called with
 509  * arguments arg and the data portion of each node.  if fn returns stopflag,
 510  * the traversal is cut short, otherwise it continues.  Do not use -6 as
 511  * a stopflag, as this is what is used to indicate the traversal ran out
 512  * of nodes.
 513  */
 514
 515 int
 516 avl_apply( Avlnode *root, IFP fn, caddr_t arg, int stopflag, int type )
 517 {
 518         switch ( type ) {
 519         case AVL_INORDER:
 520                 return( avl_inapply( root, fn, arg, stopflag ) );
 521         case AVL_PREORDER:
 522                 return( avl_preapply( root, fn, arg, stopflag ) );
 523         case AVL_POSTORDER:
 524                 return( avl_postapply( root, fn, arg, stopflag ) );
 525         default:
 526                 fprintf( stderr, "Invalid traversal type %d\n", type );
 527                 return( -1 );
 528         }
 529
 530         /* NOTREACHED */
 531 }
 532
 533 /*
 534  * avl_prefixapply - traverse avl tree root, applying function fprefix
 535  * to any nodes that match.  fcmp is called with data as its first arg
 536  * and the current node's data as its second arg.  it should return
 537  * 0 if they match, < 0 if data is less, and > 0 if data is greater.
 538  * the idea is to efficiently find all nodes that are prefixes of
 539  * some key...  Like avl_apply, this routine also takes a stopflag
 540  * and will return prematurely if fmatch returns this value.  Otherwise,
 541  * AVL_NOMORE is returned.
 542  */
 543
 544 int
 545 avl_prefixapply(
 546     Avlnode     *root,
 547     caddr_t     data,
 548     IFP         fmatch,
 549     caddr_t     marg,
 550     IFP         fcmp,
 551     caddr_t     carg,
 552     int         stopflag
 553 )
 554 {
 555         int     cmp;
 556
 557         if ( root == 0 )
 558                 return( AVL_NOMORE );
 559
 560         cmp = (*fcmp)( data, root->avl_data, carg );
 561         if ( cmp == 0 ) {
 562                 if ( (*fmatch)( root->avl_data, marg ) == stopflag )
 563                         return( stopflag );
 564
 565                 if ( root->avl_left != 0 )
 566                         if ( avl_prefixapply( root->avl_left, data, fmatch,
 567                             marg, fcmp, carg, stopflag ) == stopflag )
 568                                 return( stopflag );
 569
 570                 if ( root->avl_right != 0 )
 571                         return( avl_prefixapply( root->avl_right, data, fmatch,
 572                             marg, fcmp, carg, stopflag ) );
 573                 else
 574                         return( AVL_NOMORE );
 575
 576         } else if ( cmp < 0 ) {
 577                 if ( root->avl_left != 0 )
 578                         return( avl_prefixapply( root->avl_left, data, fmatch,
 579                             marg, fcmp, carg, stopflag ) );
 580         } else {
 581                 if ( root->avl_right != 0 )
 582                         return( avl_prefixapply( root->avl_right, data, fmatch,
 583                             marg, fcmp, carg, stopflag ) );
 584         }
 585
 586         return( AVL_NOMORE );
 587 }
 588
 589 /*
 590  * avl_free -- traverse avltree root, freeing the memory it is using.
 591  * the dfree() is called to free the data portion of each node.  The
 592  * number of items actually freed is returned.
 593  */
 594
 595 int
 596 avl_free( Avlnode *root, IFP dfree )
 597 {
 598         int     nleft, nright;
 599
 600         if ( root == 0 )
 601                 return( 0 );
 602
 603         nleft = nright = 0;
 604         if ( root->avl_left != 0 )
 605                 nleft = avl_free( root->avl_left, dfree );
 606
 607         if ( root->avl_right != 0 )
 608                 nright = avl_free( root->avl_right, dfree );
 609
 610         if ( dfree )
 611                 (*dfree)( root->avl_data );
 612
 613         return( nleft + nright + 1 );
 614 }
 615
 616 /*
 617  * avl_find -- search avltree root for a node with data data.  the function
 618  * cmp is used to compare things.  it is called with data as its first arg
 619  * and the current node data as its second.  it should return 0 if they match,
 620  * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2.
 621  */
 622
 623 caddr_t
 624 avl_find( Avlnode *root, caddr_t data, IFP fcmp )
 625 {
 626         int     cmp;
 627
 628         while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
 629                 if ( cmp < 0 )
 630                         root = root->avl_left;
 631                 else
 632                         root = root->avl_right;
 633         }
 634
 635         return( root ? root->avl_data : 0 );
 636 }
 637
 638 /*
 639  * avl_find_lin -- search avltree root linearly for a node with data data.
 640  * the function cmp is used to compare things.  it is called with data as its
 641  * first arg and the current node data as its second.  it should return 0 if
 642  * they match, non-zero otherwise.
 643  */
 644
 645 caddr_t
 646 avl_find_lin( Avlnode *root, caddr_t data, IFP fcmp )
 647 {
 648         caddr_t res;
 649
 650         if ( root == 0 )
 651                 return( NULL );
 652
 653         if ( (*fcmp)( data, root->avl_data ) == 0 )
 654                 return( root->avl_data );
 655
 656         if ( root->avl_left != 0 )
 657                 if ( (res = avl_find_lin( root->avl_left, data, fcmp ))
 658                     != NULL )
 659                         return( res );
 660
 661         if ( root->avl_right == 0 )
 662                 return( NULL );
 663         else
 664                 return( avl_find_lin( root->avl_right, data, fcmp ) );
 665 }
 666
 667 static caddr_t  *avl_list;
 668 static int      avl_maxlist;
 669 static int      avl_nextlist;
 670
 671 #define AVL_GRABSIZE    100
 672
 673 /* ARGSUSED */
 674 static int
 675 avl_buildlist( caddr_t data, int arg )
 676 {
 677         static int      slots;
 678
 679         if ( avl_list == (caddr_t *) 0 ) {
 680                 avl_list = (caddr_t *) malloc(AVL_GRABSIZE * sizeof(caddr_t));
 681                 slots = AVL_GRABSIZE;
 682                 avl_maxlist = 0;
 683         } else if ( avl_maxlist == slots ) {
 684                 slots += AVL_GRABSIZE;
 685                 avl_list = (caddr_t *) realloc( (char *) avl_list,
 686                     (unsigned) slots * sizeof(caddr_t));
 687         }
 688
 689         avl_list[ avl_maxlist++ ] = data;
 690
 691         return( 0 );
 692 }
 693
 694 /*
 695  * avl_getfirst() and avl_getnext() are provided as alternate tree
 696  * traversal methods, to be used when a single function cannot be
 697  * provided to be called with every node in the tree.  avl_getfirst()
 698  * traverses the tree and builds a linear list of all the nodes,
 699  * returning the first node.  avl_getnext() returns the next thing
 700  * on the list built by avl_getfirst().  This means that avl_getfirst()
 701  * can take a while, and that the tree should not be messed with while
 702  * being traversed in this way, and that multiple traversals (even of
 703  * different trees) cannot be active at once.
 704  */
 705
 706 caddr_t
 707 avl_getfirst( Avlnode *root )
 708 {
 709         if ( avl_list ) {
 710                 free( (char *) avl_list);
 711                 avl_list = (caddr_t *) 0;
 712         }
 713         avl_maxlist = 0;
 714         avl_nextlist = 0;
 715
 716         if ( root == 0 )
 717                 return( 0 );
 718
 719         (void) avl_apply( root, avl_buildlist, (caddr_t) 0, -1, AVL_INORDER );
 720
 721         return( avl_list[ avl_nextlist++ ] );
 722 }
 723
 724 caddr_t
 725 avl_getnext( void )
 726 {
 727         if ( avl_list == 0 )
 728                 return( 0 );
 729
 730         if ( avl_nextlist == avl_maxlist ) {
 731                 free( (caddr_t) avl_list);
 732                 avl_list = (caddr_t *) 0;
 733                 return( 0 );
 734         }
 735
 736         return( avl_list[ avl_nextlist++ ] );
 737 }
 738
 739 int
 740 avl_dup_error( void )
 741 {
 742         return( -1 );
 743 }
 744
 745 int
 746 avl_dup_ok( void )
 747 {
 748         return( 0 );
 749 }