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