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