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