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

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