Back to index

openldap  2.4.31
tavl.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 2005-2012 The OpenLDAP Foundation.
00006  * Portions Copyright (c) 2005 by Howard Chu, Symas Corp.
00007  * All rights reserved.
00008  *
00009  * Redistribution and use in source and binary forms, with or without
00010  * modification, are permitted only as authorized by the OpenLDAP
00011  * Public License.
00012  *
00013  * A copy of this license is available in the file LICENSE in the
00014  * top-level directory of the distribution or, alternatively, at
00015  * <http://www.OpenLDAP.org/license.html>.
00016  */
00017 /* ACKNOWLEDGEMENTS:
00018  * This work was initially developed by Howard Chu for inclusion
00019  * in OpenLDAP software.
00020  */
00021 
00022 #include "portable.h"
00023 
00024 #include <limits.h>
00025 #include <stdio.h>
00026 #include <ac/stdlib.h>
00027 
00028 #ifdef CSRIMALLOC
00029 #define ber_memalloc malloc
00030 #define ber_memrealloc realloc
00031 #define ber_memfree free
00032 #else
00033 #include "lber.h"
00034 #endif
00035 
00036 #define AVL_INTERNAL
00037 #include "avl.h"
00038 
00039 /* Maximum tree depth this host's address space could support */
00040 #define MAX_TREE_DEPTH      (sizeof(void *) * CHAR_BIT)
00041 
00042 static const int avl_bfs[] = {LH, RH};
00043 
00044 /*
00045  * Threaded AVL trees - for fast in-order traversal of nodes.
00046  */
00047 /*
00048  * tavl_insert -- insert a node containing data data into the avl tree
00049  * with root root.  fcmp is a function to call to compare the data portion
00050  * of two nodes.  it should take two arguments and return <, >, or == 0,
00051  * depending on whether its first argument is <, >, or == its second
00052  * argument (like strcmp, e.g.).  fdup is a function to call when a duplicate
00053  * node is inserted.  it should return 0, or -1 and its return value
00054  * will be the return value from avl_insert in the case of a duplicate node.
00055  * the function will be called with the original node's data as its first
00056  * argument and with the incoming duplicate node's data as its second
00057  * argument.  this could be used, for example, to keep a count with each
00058  * node.
00059  *
00060  * NOTE: this routine may malloc memory
00061  */
00062 int
00063 tavl_insert( Avlnode ** root, void *data, AVL_CMP fcmp, AVL_DUP fdup )
00064 {
00065     Avlnode *t, *p, *s, *q, *r;
00066     int a, cmp, ncmp;
00067 
00068        if ( *root == NULL ) {
00069               if (( r = (Avlnode *) ber_memalloc( sizeof( Avlnode ))) == NULL ) {
00070                      return( -1 );
00071               }
00072               r->avl_link[0] = r->avl_link[1] = NULL;
00073               r->avl_data = data;
00074               r->avl_bf = EH;
00075               r->avl_bits[0] = r->avl_bits[1] = AVL_THREAD;
00076               *root = r;
00077 
00078               return( 0 );
00079        }
00080 
00081     t = NULL;
00082     s = p = *root;
00083 
00084        /* find insertion point */
00085     while (1) {
00086               cmp = fcmp( data, p->avl_data );
00087               if ( cmp == 0 )
00088                      return (*fdup)( p->avl_data, data );
00089 
00090               cmp = (cmp > 0);
00091               q = avl_child( p, cmp );
00092               if (q == NULL) {
00093                      /* insert */
00094                      if (( q = (Avlnode *) ber_memalloc( sizeof( Avlnode ))) == NULL ) {
00095                             return( -1 );
00096                      }
00097                      q->avl_link[cmp] = p->avl_link[cmp];
00098                      q->avl_link[!cmp] = p;
00099                      q->avl_data = data;
00100                      q->avl_bf = EH;
00101                      q->avl_bits[0] = q->avl_bits[1] = AVL_THREAD;
00102 
00103                      p->avl_link[cmp] = q;
00104                      p->avl_bits[cmp] = AVL_CHILD;
00105                      break;
00106               } else if ( q->avl_bf ) {
00107                      t = p;
00108                      s = q;
00109               }
00110               p = q;
00111     }
00112 
00113     /* adjust balance factors */
00114     cmp = fcmp( data, s->avl_data ) > 0;
00115        r = p = s->avl_link[cmp];
00116        a = avl_bfs[cmp];
00117 
00118        while ( p != q ) {
00119               cmp = fcmp( data, p->avl_data ) > 0;
00120               p->avl_bf = avl_bfs[cmp];
00121               p = p->avl_link[cmp];
00122        }
00123 
00124        /* checks and balances */
00125 
00126        if ( s->avl_bf == EH ) {
00127               s->avl_bf = a;
00128               return 0;
00129        } else if ( s->avl_bf == -a ) {
00130               s->avl_bf = EH;
00131               return 0;
00132     } else if ( s->avl_bf == a ) {
00133               cmp = (a > 0);
00134               ncmp = !cmp;
00135               if ( r->avl_bf == a ) {
00136                      /* single rotation */
00137                      p = r;
00138                      if ( r->avl_bits[ncmp] == AVL_THREAD ) {
00139                             r->avl_bits[ncmp] = AVL_CHILD;
00140                             s->avl_bits[cmp] = AVL_THREAD;
00141                      } else {
00142                             s->avl_link[cmp] = r->avl_link[ncmp];
00143                             r->avl_link[ncmp] = s;
00144                      }
00145                      s->avl_bf = 0;
00146                      r->avl_bf = 0;
00147               } else if ( r->avl_bf == -a ) {
00148                      /* double rotation */
00149                      p = r->avl_link[ncmp];
00150                      if ( p->avl_bits[cmp] == AVL_THREAD ) {
00151                             p->avl_bits[cmp] = AVL_CHILD;
00152                             r->avl_bits[ncmp] = AVL_THREAD;
00153                      } else {
00154                             r->avl_link[ncmp] = p->avl_link[cmp];
00155                             p->avl_link[cmp] = r;
00156                      }
00157                      if ( p->avl_bits[ncmp] == AVL_THREAD ) {
00158                             p->avl_bits[ncmp] = AVL_CHILD;
00159                             s->avl_link[cmp] = p;
00160                             s->avl_bits[cmp] = AVL_THREAD;
00161                      } else {
00162                             s->avl_link[cmp] = p->avl_link[ncmp];
00163                             p->avl_link[ncmp] = s;
00164                      }
00165                      if ( p->avl_bf == a ) {
00166                             s->avl_bf = -a;
00167                             r->avl_bf = 0;
00168                      } else if ( p->avl_bf == -a ) {
00169                             s->avl_bf = 0;
00170                             r->avl_bf = a;
00171                      } else {
00172                             s->avl_bf = 0;
00173                             r->avl_bf = 0;
00174                      }
00175                      p->avl_bf = 0;
00176               }
00177               /* Update parent */
00178               if ( t == NULL )
00179                      *root = p;
00180               else if ( s == t->avl_right )
00181                      t->avl_right = p;
00182               else
00183                      t->avl_left = p;
00184     }
00185 
00186   return 0;
00187 }
00188 
00189 void*
00190 tavl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
00191 {
00192        Avlnode *p, *q, *r, *top;
00193        int side, side_bf, shorter, nside = -1;
00194 
00195        /* parent stack */
00196        Avlnode *pptr[MAX_TREE_DEPTH];
00197        unsigned char pdir[MAX_TREE_DEPTH];
00198        int depth = 0;
00199 
00200        if ( *root == NULL )
00201               return NULL;
00202 
00203        p = *root;
00204 
00205        while (1) {
00206               side = fcmp( data, p->avl_data );
00207               if ( !side )
00208                      break;
00209               side = ( side > 0 );
00210               pdir[depth] = side;
00211               pptr[depth++] = p;
00212 
00213               if ( p->avl_bits[side] == AVL_THREAD )
00214                      return NULL;
00215               p = p->avl_link[side];
00216        }
00217        data = p->avl_data;
00218 
00219        /* If this node has two children, swap so we are deleting a node with
00220         * at most one child.
00221         */
00222        if ( p->avl_bits[0] == AVL_CHILD && p->avl_bits[1] == AVL_CHILD &&
00223               p->avl_link[0] && p->avl_link[1] ) {
00224 
00225               /* find the immediate predecessor <q> */
00226               q = p->avl_link[0];
00227               side = depth;
00228               pdir[depth++] = 0;
00229               while (q->avl_bits[1] == AVL_CHILD && q->avl_link[1]) {
00230                      pdir[depth] = 1;
00231                      pptr[depth++] = q;
00232                      q = q->avl_link[1];
00233               }
00234               /* swap links */
00235               r = p->avl_link[0];
00236               p->avl_link[0] = q->avl_link[0];
00237               q->avl_link[0] = r;
00238 
00239               q->avl_link[1] = p->avl_link[1];
00240               p->avl_link[1] = q;
00241 
00242               p->avl_bits[0] = q->avl_bits[0];
00243               p->avl_bits[1] = q->avl_bits[1];
00244               q->avl_bits[0] = q->avl_bits[1] = AVL_CHILD;
00245 
00246               q->avl_bf = p->avl_bf;
00247 
00248               /* fix stack positions: old parent of p points to q */
00249               pptr[side] = q;
00250               if ( side ) {
00251                      r = pptr[side-1];
00252                      r->avl_link[pdir[side-1]] = q;
00253               } else {
00254                      *root = q;
00255               }
00256               /* new parent of p points to p */
00257               if ( depth-side > 1 ) {
00258                      r = pptr[depth-1];
00259                      r->avl_link[1] = p;
00260               } else {
00261                      q->avl_link[0] = p;
00262               }
00263 
00264               /* fix right subtree: successor of p points to q */
00265               r = q->avl_link[1];
00266               while ( r->avl_bits[0] == AVL_CHILD && r->avl_link[0] )
00267                      r = r->avl_link[0];
00268               r->avl_link[0] = q;
00269        }
00270 
00271        /* now <p> has at most one child, get it */
00272        if ( p->avl_link[0] && p->avl_bits[0] == AVL_CHILD ) {
00273               q = p->avl_link[0];
00274               /* Preserve thread continuity */
00275               r = p->avl_link[1];
00276               nside = 1;
00277        } else if ( p->avl_link[1] && p->avl_bits[1] == AVL_CHILD ) {
00278               q = p->avl_link[1];
00279               r = p->avl_link[0];
00280               nside = 0;
00281        } else {
00282               q = NULL;
00283               if ( depth > 0 )
00284                      r = p->avl_link[pdir[depth-1]];
00285               else
00286                      r = NULL;
00287        }
00288 
00289        ber_memfree( p );
00290 
00291        /* Update child thread */
00292        if ( q ) {
00293               for ( ; q->avl_bits[nside] == AVL_CHILD && q->avl_link[nside];
00294                      q = q->avl_link[nside] ) ;
00295               q->avl_link[nside] = r;
00296        }
00297        
00298        if ( !depth ) {
00299               *root = q;
00300               return data;
00301        }
00302 
00303        /* set the child into p's parent */
00304        depth--;
00305        p = pptr[depth];
00306        side = pdir[depth];
00307        p->avl_link[side] = q;
00308 
00309        if ( !q ) {
00310               p->avl_bits[side] = AVL_THREAD;
00311               p->avl_link[side] = r;
00312        }
00313 
00314        top = NULL;
00315        shorter = 1;
00316   
00317        while ( shorter ) {
00318               p = pptr[depth];
00319               side = pdir[depth];
00320               nside = !side;
00321               side_bf = avl_bfs[side];
00322 
00323               /* case 1: height unchanged */
00324               if ( p->avl_bf == EH ) {
00325                      /* Tree is now heavier on opposite side */
00326                      p->avl_bf = avl_bfs[nside];
00327                      shorter = 0;
00328                 
00329               } else if ( p->avl_bf == side_bf ) {
00330               /* case 2: taller subtree shortened, height reduced */
00331                      p->avl_bf = EH;
00332               } else {
00333               /* case 3: shorter subtree shortened */
00334                      if ( depth )
00335                             top = pptr[depth-1]; /* p->parent; */
00336                      else
00337                             top = NULL;
00338                      /* set <q> to the taller of the two subtrees of <p> */
00339                      q = p->avl_link[nside];
00340                      if ( q->avl_bf == EH ) {
00341                             /* case 3a: height unchanged, single rotate */
00342                             if ( q->avl_bits[side] == AVL_THREAD ) {
00343                                    q->avl_bits[side] = AVL_CHILD;
00344                                    p->avl_bits[nside] = AVL_THREAD;
00345                             } else {
00346                                    p->avl_link[nside] = q->avl_link[side];
00347                                    q->avl_link[side] = p;
00348                             }
00349                             shorter = 0;
00350                             q->avl_bf = side_bf;
00351                             p->avl_bf = (- side_bf);
00352 
00353                      } else if ( q->avl_bf == p->avl_bf ) {
00354                             /* case 3b: height reduced, single rotate */
00355                             if ( q->avl_bits[side] == AVL_THREAD ) {
00356                                    q->avl_bits[side] = AVL_CHILD;
00357                                    p->avl_bits[nside] = AVL_THREAD;
00358                             } else {
00359                                    p->avl_link[nside] = q->avl_link[side];
00360                                    q->avl_link[side] = p;
00361                             }
00362                             shorter = 1;
00363                             q->avl_bf = EH;
00364                             p->avl_bf = EH;
00365 
00366                      } else {
00367                             /* case 3c: height reduced, balance factors opposite */
00368                             r = q->avl_link[side];
00369                             if ( r->avl_bits[nside] == AVL_THREAD ) {
00370                                    r->avl_bits[nside] = AVL_CHILD;
00371                                    q->avl_bits[side] = AVL_THREAD;
00372                             } else {
00373                                    q->avl_link[side] = r->avl_link[nside];
00374                                    r->avl_link[nside] = q;
00375                             }
00376 
00377                             if ( r->avl_bits[side] == AVL_THREAD ) {
00378                                    r->avl_bits[side] = AVL_CHILD;
00379                                    p->avl_bits[nside] = AVL_THREAD;
00380                                    p->avl_link[nside] = r;
00381                             } else {
00382                                    p->avl_link[nside] = r->avl_link[side];
00383                                    r->avl_link[side] = p;
00384                             }
00385 
00386                             if ( r->avl_bf == side_bf ) {
00387                                    q->avl_bf = (- side_bf);
00388                                    p->avl_bf = EH;
00389                             } else if ( r->avl_bf == (- side_bf)) {
00390                                    q->avl_bf = EH;
00391                                    p->avl_bf = side_bf;
00392                             } else {
00393                                    q->avl_bf = EH;
00394                                    p->avl_bf = EH;
00395                             }
00396                             r->avl_bf = EH;
00397                             q = r;
00398                      }
00399                      /* a rotation has caused <q> (or <r> in case 3c) to become
00400                       * the root.  let <p>'s former parent know this.
00401                       */
00402                      if ( top == NULL ) {
00403                             *root = q;
00404                      } else if (top->avl_link[0] == p) {
00405                             top->avl_link[0] = q;
00406                      } else {
00407                             top->avl_link[1] = q;
00408                      }
00409                      /* end case 3 */
00410                      p = q;
00411               }
00412               if ( !depth )
00413                      break;
00414               depth--;
00415        } /* end while(shorter) */
00416 
00417        return data;
00418 }
00419 
00420 /*
00421  * tavl_free -- traverse avltree root, freeing the memory it is using.
00422  * the dfree() is called to free the data portion of each node.  The
00423  * number of items actually freed is returned.
00424  */
00425 
00426 int
00427 tavl_free( Avlnode *root, AVL_FREE dfree )
00428 {
00429        int    nleft, nright;
00430 
00431        if ( root == 0 )
00432               return( 0 );
00433 
00434        nleft = tavl_free( avl_lchild( root ), dfree );
00435 
00436        nright = tavl_free( avl_rchild( root ), dfree );
00437 
00438        if ( dfree )
00439               (*dfree)( root->avl_data );
00440        ber_memfree( root );
00441 
00442        return( nleft + nright + 1 );
00443 }
00444 
00445 /*
00446  * tavl_find -- search avltree root for a node with data data.  the function
00447  * cmp is used to compare things.  it is called with data as its first arg 
00448  * and the current node data as its second.  it should return 0 if they match,
00449  * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2.
00450  */
00451 
00452 /*
00453  * tavl_find2 - returns Avlnode instead of data pointer.
00454  * tavl_find3 - as above, but returns Avlnode even if no match is found.
00455  *                          also set *ret = last comparison result, or -1 if root == NULL.
00456  */
00457 Avlnode *
00458 tavl_find3( Avlnode *root, const void *data, AVL_CMP fcmp, int *ret )
00459 {
00460        int    cmp = -1, dir;
00461        Avlnode *prev = root;
00462 
00463        while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
00464               prev = root;
00465               dir = cmp > 0;
00466               root = avl_child( root, dir );
00467        }
00468        *ret = cmp;
00469        return root ? root : prev;
00470 }
00471 
00472 Avlnode *
00473 tavl_find2( Avlnode *root, const void *data, AVL_CMP fcmp )
00474 {
00475        int    cmp;
00476 
00477        while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
00478               cmp = cmp > 0;
00479               root = avl_child( root, cmp );
00480        }
00481        return root;
00482 }
00483 
00484 void*
00485 tavl_find( Avlnode *root, const void* data, AVL_CMP fcmp )
00486 {
00487        int    cmp;
00488 
00489        while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
00490               cmp = cmp > 0;
00491               root = avl_child( root, cmp );
00492        }
00493 
00494        return( root ? root->avl_data : 0 );
00495 }
00496 
00497 /* Return the leftmost or rightmost node in the tree */
00498 Avlnode *
00499 tavl_end( Avlnode *root, int dir )
00500 {
00501        if ( root ) {
00502               while ( root->avl_bits[dir] == AVL_CHILD )
00503                      root = root->avl_link[dir];
00504        }
00505        return root;
00506 }
00507 
00508 /* Return the next node in the given direction */
00509 Avlnode *
00510 tavl_next( Avlnode *root, int dir )
00511 {
00512        if ( root ) {
00513               int c = root->avl_bits[dir];
00514 
00515               root = root->avl_link[dir];
00516               if ( c == AVL_CHILD ) {
00517                      dir ^= 1;
00518                      while ( root->avl_bits[dir] == AVL_CHILD )
00519                             root = root->avl_link[dir];
00520               }
00521        }
00522        return root;
00523 }