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

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