Back to index

openldap  2.4.31
avl.c
Go to the documentation of this file.
00001 /* avl.c - routines to implement an avl tree */
00002 /* $OpenLDAP$ */
00003 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
00004  *
00005  * Copyright 1998-2012 The OpenLDAP Foundation.
00006  * All rights reserved.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted only as authorized by the OpenLDAP
00010  * Public License.
00011  *
00012  * A copy of this license is available in the file LICENSE in the
00013  * top-level directory of the distribution or, alternatively, at
00014  * <http://www.OpenLDAP.org/license.html>.
00015  */
00016 /* Portions Copyright (c) 1993 Regents of the University of Michigan.
00017  * All rights reserved.
00018  *
00019  * Redistribution and use in source and binary forms are permitted
00020  * provided that this notice is preserved and that due credit is given
00021  * to the University of Michigan at Ann Arbor. The name of the University
00022  * may not be used to endorse or promote products derived from this
00023  * software without specific prior written permission. This software
00024  * is provided ``as is'' without express or implied warranty.
00025  */
00026 /* ACKNOWLEDGEMENTS:
00027  * This work was originally developed by the University of Michigan
00028  * (as part of U-MICH LDAP).  Additional significant contributors
00029  * include:
00030  *   Howard Y. Chu
00031  *   Hallvard B. Furuseth
00032  *   Kurt D. Zeilenga
00033  */
00034 
00035 #include "portable.h"
00036 
00037 #include <limits.h>
00038 #include <stdio.h>
00039 #include <ac/stdlib.h>
00040 
00041 #ifdef CSRIMALLOC
00042 #define ber_memalloc malloc
00043 #define ber_memrealloc realloc
00044 #define ber_memfree free
00045 #else
00046 #include "lber.h"
00047 #endif
00048 
00049 #define AVL_INTERNAL
00050 #include "avl.h"
00051 
00052 /* Maximum tree depth this host's address space could support */
00053 #define MAX_TREE_DEPTH      (sizeof(void *) * CHAR_BIT)
00054 
00055 static const int avl_bfs[] = {LH, RH};
00056 
00057 /*
00058  * avl_insert -- insert a node containing data data into the avl tree
00059  * with root root.  fcmp is a function to call to compare the data portion
00060  * of two nodes.  it should take two arguments and return <, >, or == 0,
00061  * depending on whether its first argument is <, >, or == its second
00062  * argument (like strcmp, e.g.).  fdup is a function to call when a duplicate
00063  * node is inserted.  it should return 0, or -1 and its return value
00064  * will be the return value from avl_insert in the case of a duplicate node.
00065  * the function will be called with the original node's data as its first
00066  * argument and with the incoming duplicate node's data as its second
00067  * argument.  this could be used, for example, to keep a count with each
00068  * node.
00069  *
00070  * NOTE: this routine may malloc memory
00071  */
00072 int
00073 avl_insert( Avlnode ** root, void *data, AVL_CMP fcmp, AVL_DUP fdup )
00074 {
00075     Avlnode *t, *p, *s, *q, *r;
00076     int a, cmp, ncmp;
00077 
00078        if ( *root == NULL ) {
00079               if (( r = (Avlnode *) ber_memalloc( sizeof( Avlnode ))) == NULL ) {
00080                      return( -1 );
00081               }
00082               r->avl_link[0] = r->avl_link[1] = NULL;
00083               r->avl_data = data;
00084               r->avl_bf = EH;
00085               *root = r;
00086 
00087               return( 0 );
00088        }
00089 
00090     t = NULL;
00091     s = p = *root;
00092 
00093        /* find insertion point */
00094     while (1) {
00095               cmp = fcmp( data, p->avl_data );
00096               if ( cmp == 0 )
00097                      return (*fdup)( p->avl_data, data );
00098 
00099               cmp = (cmp > 0);
00100               q = p->avl_link[cmp];
00101               if (q == NULL) {
00102                      /* insert */
00103                      if (( q = (Avlnode *) ber_memalloc( sizeof( Avlnode ))) == NULL ) {
00104                             return( -1 );
00105                      }
00106                      q->avl_link[0] = q->avl_link[1] = NULL;
00107                      q->avl_data = data;
00108                      q->avl_bf = EH;
00109 
00110                      p->avl_link[cmp] = q;
00111                      break;
00112               } else if ( q->avl_bf ) {
00113                      t = p;
00114                      s = q;
00115               }
00116               p = q;
00117     }
00118 
00119     /* adjust balance factors */
00120     cmp = fcmp( data, s->avl_data ) > 0;
00121        r = p = s->avl_link[cmp];
00122        a = avl_bfs[cmp];
00123 
00124        while ( p != q ) {
00125               cmp = fcmp( data, p->avl_data ) > 0;
00126               p->avl_bf = avl_bfs[cmp];
00127               p = p->avl_link[cmp];
00128        }
00129 
00130        /* checks and balances */
00131 
00132        if ( s->avl_bf == EH ) {
00133               s->avl_bf = a;
00134               return 0;
00135        } else if ( s->avl_bf == -a ) {
00136               s->avl_bf = EH;
00137               return 0;
00138     } else if ( s->avl_bf == a ) {
00139               cmp = (a > 0);
00140               ncmp = !cmp;
00141               if ( r->avl_bf == a ) {
00142                      /* single rotation */
00143                      p = r;
00144                      s->avl_link[cmp] = r->avl_link[ncmp];
00145                      r->avl_link[ncmp] = s;
00146                      s->avl_bf = 0;
00147                      r->avl_bf = 0;
00148               } else if ( r->avl_bf == -a ) {
00149                      /* double rotation */
00150                      p = r->avl_link[ncmp];
00151                      r->avl_link[ncmp] = p->avl_link[cmp];
00152                      p->avl_link[cmp] = r;
00153                      s->avl_link[cmp] = p->avl_link[ncmp];
00154                      p->avl_link[ncmp] = s;
00155 
00156                      if ( p->avl_bf == a ) {
00157                             s->avl_bf = -a;
00158                             r->avl_bf = 0;
00159                      } else if ( p->avl_bf == -a ) {
00160                             s->avl_bf = 0;
00161                             r->avl_bf = a;
00162                      } else {
00163                             s->avl_bf = 0;
00164                             r->avl_bf = 0;
00165                      }
00166                      p->avl_bf = 0;
00167               }
00168               /* Update parent */
00169               if ( t == NULL )
00170                      *root = p;
00171               else if ( s == t->avl_right )
00172                      t->avl_right = p;
00173               else
00174                      t->avl_left = p;
00175     }
00176 
00177   return 0;
00178 }
00179 
00180 void*
00181 avl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
00182 {
00183        Avlnode *p, *q, *r, *top;
00184        int side, side_bf, shorter, nside;
00185 
00186        /* parent stack */
00187        Avlnode *pptr[MAX_TREE_DEPTH];
00188        unsigned char pdir[MAX_TREE_DEPTH];
00189        int depth = 0;
00190 
00191        if ( *root == NULL )
00192               return NULL;
00193 
00194        p = *root;
00195 
00196        while (1) {
00197               side = fcmp( data, p->avl_data );
00198               if ( !side )
00199                      break;
00200               side = ( side > 0 );
00201               pdir[depth] = side;
00202               pptr[depth++] = p;
00203 
00204               p = p->avl_link[side];
00205               if ( p == NULL )
00206                      return p;
00207        }
00208        data = p->avl_data;
00209 
00210        /* If this node has two children, swap so we are deleting a node with
00211         * at most one child.
00212         */
00213        if ( p->avl_link[0] && p->avl_link[1] ) {
00214 
00215               /* find the immediate predecessor <q> */
00216               q = p->avl_link[0];
00217               side = depth;
00218               pdir[depth++] = 0;
00219               while (q->avl_link[1]) {
00220                      pdir[depth] = 1;
00221                      pptr[depth++] = q;
00222                      q = q->avl_link[1];
00223               }
00224               /* swap links */
00225               r = p->avl_link[0];
00226               p->avl_link[0] = q->avl_link[0];
00227               q->avl_link[0] = r;
00228 
00229               q->avl_link[1] = p->avl_link[1];
00230               p->avl_link[1] = NULL;
00231 
00232               q->avl_bf = p->avl_bf;
00233 
00234               /* fix stack positions: old parent of p points to q */
00235               pptr[side] = q;
00236               if ( side ) {
00237                      r = pptr[side-1];
00238                      r->avl_link[pdir[side-1]] = q;
00239               } else {
00240                      *root = q;
00241               }
00242               /* new parent of p points to p */
00243               if ( depth-side > 1 ) {
00244                      r = pptr[depth-1];
00245                      r->avl_link[1] = p;
00246               } else {
00247                      q->avl_link[0] = p;
00248               }
00249        }
00250 
00251        /* now <p> has at most one child, get it */
00252        q = p->avl_link[0] ? p->avl_link[0] : p->avl_link[1];
00253 
00254        ber_memfree( p );
00255 
00256        if ( !depth ) {
00257               *root = q;
00258               return data;
00259        }
00260 
00261        /* set the child into p's parent */
00262        depth--;
00263        p = pptr[depth];
00264        side = pdir[depth];
00265        p->avl_link[side] = q;
00266 
00267        top = NULL;
00268        shorter = 1;
00269   
00270        while ( shorter ) {
00271               p = pptr[depth];
00272               side = pdir[depth];
00273               nside = !side;
00274               side_bf = avl_bfs[side];
00275 
00276               /* case 1: height unchanged */
00277               if ( p->avl_bf == EH ) {
00278                      /* Tree is now heavier on opposite side */
00279                      p->avl_bf = avl_bfs[nside];
00280                      shorter = 0;
00281                 
00282               } else if ( p->avl_bf == side_bf ) {
00283               /* case 2: taller subtree shortened, height reduced */
00284                      p->avl_bf = EH;
00285               } else {
00286               /* case 3: shorter subtree shortened */
00287                      if ( depth )
00288                             top = pptr[depth-1]; /* p->parent; */
00289                      else
00290                             top = NULL;
00291                      /* set <q> to the taller of the two subtrees of <p> */
00292                      q = p->avl_link[nside];
00293                      if ( q->avl_bf == EH ) {
00294                             /* case 3a: height unchanged, single rotate */
00295                             p->avl_link[nside] = q->avl_link[side];
00296                             q->avl_link[side] = p;
00297                             shorter = 0;
00298                             q->avl_bf = side_bf;
00299                             p->avl_bf = (- side_bf);
00300 
00301                      } else if ( q->avl_bf == p->avl_bf ) {
00302                             /* case 3b: height reduced, single rotate */
00303                             p->avl_link[nside] = q->avl_link[side];
00304                             q->avl_link[side] = p;
00305                             shorter = 1;
00306                             q->avl_bf = EH;
00307                             p->avl_bf = EH;
00308 
00309                      } else {
00310                             /* case 3c: height reduced, balance factors opposite */
00311                             r = q->avl_link[side];
00312                             q->avl_link[side] = r->avl_link[nside];
00313                             r->avl_link[nside] = q;
00314 
00315                             p->avl_link[nside] = r->avl_link[side];
00316                             r->avl_link[side] = p;
00317 
00318                             if ( r->avl_bf == side_bf ) {
00319                                    q->avl_bf = (- side_bf);
00320                                    p->avl_bf = EH;
00321                             } else if ( r->avl_bf == (- side_bf)) {
00322                                    q->avl_bf = EH;
00323                                    p->avl_bf = side_bf;
00324                             } else {
00325                                    q->avl_bf = EH;
00326                                    p->avl_bf = EH;
00327                             }
00328                             r->avl_bf = EH;
00329                             q = r;
00330                      }
00331                      /* a rotation has caused <q> (or <r> in case 3c) to become
00332                       * the root.  let <p>'s former parent know this.
00333                       */
00334                      if ( top == NULL ) {
00335                             *root = q;
00336                      } else if (top->avl_link[0] == p) {
00337                             top->avl_link[0] = q;
00338                      } else {
00339                             top->avl_link[1] = q;
00340                      }
00341                      /* end case 3 */
00342                      p = q;
00343               }
00344               if ( !depth )
00345                      break;
00346               depth--;
00347        } /* end while(shorter) */
00348 
00349        return data;
00350 }
00351 
00352 static int
00353 avl_inapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
00354 {
00355        if ( root == 0 )
00356               return( AVL_NOMORE );
00357 
00358        if ( root->avl_left != 0 )
00359               if ( avl_inapply( root->avl_left, fn, arg, stopflag ) 
00360                   == stopflag )
00361                      return( stopflag );
00362 
00363        if ( (*fn)( root->avl_data, arg ) == stopflag )
00364               return( stopflag );
00365 
00366        if ( root->avl_right == 0 )
00367               return( AVL_NOMORE );
00368        else
00369               return( avl_inapply( root->avl_right, fn, arg, stopflag ) );
00370 }
00371 
00372 static int
00373 avl_postapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
00374 {
00375        if ( root == 0 )
00376               return( AVL_NOMORE );
00377 
00378        if ( root->avl_left != 0 )
00379               if ( avl_postapply( root->avl_left, fn, arg, stopflag ) 
00380                   == stopflag )
00381                      return( stopflag );
00382 
00383        if ( root->avl_right != 0 )
00384               if ( avl_postapply( root->avl_right, fn, arg, stopflag ) 
00385                   == stopflag )
00386                      return( stopflag );
00387 
00388        return( (*fn)( root->avl_data, arg ) );
00389 }
00390 
00391 static int
00392 avl_preapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
00393 {
00394        if ( root == 0 )
00395               return( AVL_NOMORE );
00396 
00397        if ( (*fn)( root->avl_data, arg ) == stopflag )
00398               return( stopflag );
00399 
00400        if ( root->avl_left != 0 )
00401               if ( avl_preapply( root->avl_left, fn, arg, stopflag ) 
00402                   == stopflag )
00403                      return( stopflag );
00404 
00405        if ( root->avl_right == 0 )
00406               return( AVL_NOMORE );
00407        else
00408               return( avl_preapply( root->avl_right, fn, arg, stopflag ) );
00409 }
00410 
00411 /*
00412  * avl_apply -- avl tree root is traversed, function fn is called with
00413  * arguments arg and the data portion of each node.  if fn returns stopflag,
00414  * the traversal is cut short, otherwise it continues.  Do not use -6 as
00415  * a stopflag, as this is what is used to indicate the traversal ran out
00416  * of nodes.
00417  */
00418 
00419 int
00420 avl_apply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag, int type )
00421 {
00422        switch ( type ) {
00423        case AVL_INORDER:
00424               return( avl_inapply( root, fn, arg, stopflag ) );
00425        case AVL_PREORDER:
00426               return( avl_preapply( root, fn, arg, stopflag ) );
00427        case AVL_POSTORDER:
00428               return( avl_postapply( root, fn, arg, stopflag ) );
00429        default:
00430               fprintf( stderr, "Invalid traversal type %d\n", type );
00431               return( -1 );
00432        }
00433 
00434        /* NOTREACHED */
00435 }
00436 
00437 /*
00438  * avl_prefixapply - traverse avl tree root, applying function fprefix
00439  * to any nodes that match.  fcmp is called with data as its first arg
00440  * and the current node's data as its second arg.  it should return
00441  * 0 if they match, < 0 if data is less, and > 0 if data is greater.
00442  * the idea is to efficiently find all nodes that are prefixes of
00443  * some key...  Like avl_apply, this routine also takes a stopflag
00444  * and will return prematurely if fmatch returns this value.  Otherwise,
00445  * AVL_NOMORE is returned.
00446  */
00447 
00448 int
00449 avl_prefixapply(
00450     Avlnode   *root,
00451     void*     data,
00452     AVL_CMP          fmatch,
00453     void*     marg,
00454     AVL_CMP          fcmp,
00455     void*     carg,
00456     int              stopflag
00457 )
00458 {
00459        int    cmp;
00460 
00461        if ( root == 0 )
00462               return( AVL_NOMORE );
00463 
00464        cmp = (*fcmp)( data, root->avl_data /* , carg */);
00465        if ( cmp == 0 ) {
00466               if ( (*fmatch)( root->avl_data, marg ) == stopflag )
00467                      return( stopflag );
00468 
00469               if ( root->avl_left != 0 )
00470                      if ( avl_prefixapply( root->avl_left, data, fmatch,
00471                          marg, fcmp, carg, stopflag ) == stopflag )
00472                             return( stopflag );
00473 
00474               if ( root->avl_right != 0 )
00475                      return( avl_prefixapply( root->avl_right, data, fmatch,
00476                          marg, fcmp, carg, stopflag ) );
00477               else
00478                      return( AVL_NOMORE );
00479 
00480        } else if ( cmp < 0 ) {
00481               if ( root->avl_left != 0 )
00482                      return( avl_prefixapply( root->avl_left, data, fmatch,
00483                          marg, fcmp, carg, stopflag ) );
00484        } else {
00485               if ( root->avl_right != 0 )
00486                      return( avl_prefixapply( root->avl_right, data, fmatch,
00487                          marg, fcmp, carg, stopflag ) );
00488        }
00489 
00490        return( AVL_NOMORE );
00491 }
00492 
00493 /*
00494  * avl_free -- traverse avltree root, freeing the memory it is using.
00495  * the dfree() is called to free the data portion of each node.  The
00496  * number of items actually freed is returned.
00497  */
00498 
00499 int
00500 avl_free( Avlnode *root, AVL_FREE dfree )
00501 {
00502        int    nleft, nright;
00503 
00504        if ( root == 0 )
00505               return( 0 );
00506 
00507        nleft = nright = 0;
00508        if ( root->avl_left != 0 )
00509               nleft = avl_free( root->avl_left, dfree );
00510 
00511        if ( root->avl_right != 0 )
00512               nright = avl_free( root->avl_right, dfree );
00513 
00514        if ( dfree )
00515               (*dfree)( root->avl_data );
00516        ber_memfree( root );
00517 
00518        return( nleft + nright + 1 );
00519 }
00520 
00521 /*
00522  * avl_find -- search avltree root for a node with data data.  the function
00523  * cmp is used to compare things.  it is called with data as its first arg 
00524  * and the current node data as its second.  it should return 0 if they match,
00525  * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2.
00526  */
00527 
00528 Avlnode *
00529 avl_find2( Avlnode *root, const void *data, AVL_CMP fcmp )
00530 {
00531        int    cmp;
00532 
00533        while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
00534               cmp = cmp > 0;
00535               root = root->avl_link[cmp];
00536        }
00537        return root;
00538 }
00539 
00540 void*
00541 avl_find( Avlnode *root, const void* data, AVL_CMP fcmp )
00542 {
00543        int    cmp;
00544 
00545        while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
00546               cmp = cmp > 0;
00547               root = root->avl_link[cmp];
00548        }
00549 
00550        return( root ? root->avl_data : 0 );
00551 }
00552 
00553 /*
00554  * avl_find_lin -- search avltree root linearly for a node with data data. 
00555  * the function cmp is used to compare things.  it is called with data as its
00556  * first arg and the current node data as its second.  it should return 0 if
00557  * they match, non-zero otherwise.
00558  */
00559 
00560 void*
00561 avl_find_lin( Avlnode *root, const void* data, AVL_CMP fcmp )
00562 {
00563        void*  res;
00564 
00565        if ( root == 0 )
00566               return( NULL );
00567 
00568        if ( (*fcmp)( data, root->avl_data ) == 0 )
00569               return( root->avl_data );
00570 
00571        if ( root->avl_left != 0 )
00572               if ( (res = avl_find_lin( root->avl_left, data, fcmp ))
00573                   != NULL )
00574                      return( res );
00575 
00576        if ( root->avl_right == 0 )
00577               return( NULL );
00578        else
00579               return( avl_find_lin( root->avl_right, data, fcmp ) );
00580 }
00581 
00582 /* NON-REENTRANT INTERFACE */
00583 
00584 static void*  *avl_list;
00585 static int    avl_maxlist;
00586 static int    avl_nextlist;
00587 
00588 #define AVL_GRABSIZE 100
00589 
00590 /* ARGSUSED */
00591 static int
00592 avl_buildlist( void* data, void* arg )
00593 {
00594        static int    slots;
00595 
00596        if ( avl_list == (void* *) 0 ) {
00597               avl_list = (void* *) ber_memalloc(AVL_GRABSIZE * sizeof(void*));
00598               slots = AVL_GRABSIZE;
00599               avl_maxlist = 0;
00600        } else if ( avl_maxlist == slots ) {
00601               slots += AVL_GRABSIZE;
00602               avl_list = (void* *) ber_memrealloc( (char *) avl_list,
00603                   (unsigned) slots * sizeof(void*));
00604        }
00605 
00606        avl_list[ avl_maxlist++ ] = data;
00607 
00608        return( 0 );
00609 }
00610 
00611 /*
00612  * avl_getfirst() and avl_getnext() are provided as alternate tree
00613  * traversal methods, to be used when a single function cannot be
00614  * provided to be called with every node in the tree.  avl_getfirst()
00615  * traverses the tree and builds a linear list of all the nodes,
00616  * returning the first node.  avl_getnext() returns the next thing
00617  * on the list built by avl_getfirst().  This means that avl_getfirst()
00618  * can take a while, and that the tree should not be messed with while
00619  * being traversed in this way, and that multiple traversals (even of
00620  * different trees) cannot be active at once.
00621  */
00622 
00623 void*
00624 avl_getfirst( Avlnode *root )
00625 {
00626        if ( avl_list ) {
00627               ber_memfree( (char *) avl_list);
00628               avl_list = (void* *) 0;
00629        }
00630        avl_maxlist = 0;
00631        avl_nextlist = 0;
00632 
00633        if ( root == 0 )
00634               return( 0 );
00635 
00636        (void) avl_apply( root, avl_buildlist, (void*) 0, -1, AVL_INORDER );
00637 
00638        return( avl_list[ avl_nextlist++ ] );
00639 }
00640 
00641 void*
00642 avl_getnext( void )
00643 {
00644        if ( avl_list == 0 )
00645               return( 0 );
00646 
00647        if ( avl_nextlist == avl_maxlist ) {
00648               ber_memfree( (void*) avl_list);
00649               avl_list = (void* *) 0;
00650               return( 0 );
00651        }
00652 
00653        return( avl_list[ avl_nextlist++ ] );
00654 }
00655 
00656 /* end non-reentrant code */
00657 
00658 
00659 int
00660 avl_dup_error( void* left, void* right )
00661 {
00662        return( -1 );
00663 }
00664 
00665 int
00666 avl_dup_ok( void* left, void* right )
00667 {
00668        return( 0 );
00669 }