Back to index

openldap  2.4.31
Defines | Functions | Variables
avl.c File Reference
#include "portable.h"
#include <limits.h>
#include <stdio.h>
#include <ac/stdlib.h>
#include "lber.h"
#include "avl.h"

Go to the source code of this file.

Defines

#define AVL_INTERNAL
#define MAX_TREE_DEPTH   (sizeof(void *) * CHAR_BIT)
#define AVL_GRABSIZE   100

Functions

int avl_insert (Avlnode **root, void *data, AVL_CMP fcmp, AVL_DUP fdup)
voidavl_delete (Avlnode **root, void *data, AVL_CMP fcmp)
static int avl_inapply (Avlnode *root, AVL_APPLY fn, void *arg, int stopflag)
static int avl_postapply (Avlnode *root, AVL_APPLY fn, void *arg, int stopflag)
static int avl_preapply (Avlnode *root, AVL_APPLY fn, void *arg, int stopflag)
int avl_apply (Avlnode *root, AVL_APPLY fn, void *arg, int stopflag, int type)
int avl_prefixapply (Avlnode *root, void *data, AVL_CMP fmatch, void *marg, AVL_CMP fcmp, void *carg, int stopflag)
int avl_free (Avlnode *root, AVL_FREE dfree)
Avlnode * avl_find2 (Avlnode *root, const void *data, AVL_CMP fcmp)
voidavl_find (Avlnode *root, const void *data, AVL_CMP fcmp)
voidavl_find_lin (Avlnode *root, const void *data, AVL_CMP fcmp)
static int avl_buildlist (void *data, void *arg)
voidavl_getfirst (Avlnode *root)
voidavl_getnext (void)
int avl_dup_error (void *left, void *right)
int avl_dup_ok (void *left, void *right)

Variables

static const int avl_bfs [] = {LH, RH}
static void ** avl_list
static int avl_maxlist
static int avl_nextlist

Define Documentation

#define AVL_GRABSIZE   100

Definition at line 588 of file avl.c.

#define AVL_INTERNAL

Definition at line 49 of file avl.c.

#define MAX_TREE_DEPTH   (sizeof(void *) * CHAR_BIT)

Definition at line 53 of file avl.c.


Function Documentation

int avl_apply ( Avlnode *  root,
AVL_APPLY  fn,
void arg,
int  stopflag,
int  type 
)

Definition at line 420 of file avl.c.

{
       switch ( type ) {
       case AVL_INORDER:
              return( avl_inapply( root, fn, arg, stopflag ) );
       case AVL_PREORDER:
              return( avl_preapply( root, fn, arg, stopflag ) );
       case AVL_POSTORDER:
              return( avl_postapply( root, fn, arg, stopflag ) );
       default:
              fprintf( stderr, "Invalid traversal type %d\n", type );
              return( -1 );
       }

       /* NOTREACHED */
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int avl_buildlist ( void data,
void arg 
) [static]

Definition at line 592 of file avl.c.

{
       static int    slots;

       if ( avl_list == (void* *) 0 ) {
              avl_list = (void* *) ber_memalloc(AVL_GRABSIZE * sizeof(void*));
              slots = AVL_GRABSIZE;
              avl_maxlist = 0;
       } else if ( avl_maxlist == slots ) {
              slots += AVL_GRABSIZE;
              avl_list = (void* *) ber_memrealloc( (char *) avl_list,
                  (unsigned) slots * sizeof(void*));
       }

       avl_list[ avl_maxlist++ ] = data;

       return( 0 );
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* avl_delete ( Avlnode **  root,
void data,
AVL_CMP  fcmp 
)

Definition at line 181 of file avl.c.

{
       Avlnode *p, *q, *r, *top;
       int side, side_bf, shorter, nside;

       /* parent stack */
       Avlnode *pptr[MAX_TREE_DEPTH];
       unsigned char pdir[MAX_TREE_DEPTH];
       int depth = 0;

       if ( *root == NULL )
              return NULL;

       p = *root;

       while (1) {
              side = fcmp( data, p->avl_data );
              if ( !side )
                     break;
              side = ( side > 0 );
              pdir[depth] = side;
              pptr[depth++] = p;

              p = p->avl_link[side];
              if ( p == NULL )
                     return p;
       }
       data = p->avl_data;

       /* If this node has two children, swap so we are deleting a node with
        * at most one child.
        */
       if ( p->avl_link[0] && p->avl_link[1] ) {

              /* find the immediate predecessor <q> */
              q = p->avl_link[0];
              side = depth;
              pdir[depth++] = 0;
              while (q->avl_link[1]) {
                     pdir[depth] = 1;
                     pptr[depth++] = q;
                     q = q->avl_link[1];
              }
              /* swap links */
              r = p->avl_link[0];
              p->avl_link[0] = q->avl_link[0];
              q->avl_link[0] = r;

              q->avl_link[1] = p->avl_link[1];
              p->avl_link[1] = NULL;

              q->avl_bf = p->avl_bf;

              /* fix stack positions: old parent of p points to q */
              pptr[side] = q;
              if ( side ) {
                     r = pptr[side-1];
                     r->avl_link[pdir[side-1]] = q;
              } else {
                     *root = q;
              }
              /* new parent of p points to p */
              if ( depth-side > 1 ) {
                     r = pptr[depth-1];
                     r->avl_link[1] = p;
              } else {
                     q->avl_link[0] = p;
              }
       }

       /* now <p> has at most one child, get it */
       q = p->avl_link[0] ? p->avl_link[0] : p->avl_link[1];

       ber_memfree( p );

       if ( !depth ) {
              *root = q;
              return data;
       }

       /* set the child into p's parent */
       depth--;
       p = pptr[depth];
       side = pdir[depth];
       p->avl_link[side] = q;

       top = NULL;
       shorter = 1;
  
       while ( shorter ) {
              p = pptr[depth];
              side = pdir[depth];
              nside = !side;
              side_bf = avl_bfs[side];

              /* case 1: height unchanged */
              if ( p->avl_bf == EH ) {
                     /* Tree is now heavier on opposite side */
                     p->avl_bf = avl_bfs[nside];
                     shorter = 0;
                
              } else if ( p->avl_bf == side_bf ) {
              /* case 2: taller subtree shortened, height reduced */
                     p->avl_bf = EH;
              } else {
              /* case 3: shorter subtree shortened */
                     if ( depth )
                            top = pptr[depth-1]; /* p->parent; */
                     else
                            top = NULL;
                     /* set <q> to the taller of the two subtrees of <p> */
                     q = p->avl_link[nside];
                     if ( q->avl_bf == EH ) {
                            /* case 3a: height unchanged, single rotate */
                            p->avl_link[nside] = q->avl_link[side];
                            q->avl_link[side] = p;
                            shorter = 0;
                            q->avl_bf = side_bf;
                            p->avl_bf = (- side_bf);

                     } else if ( q->avl_bf == p->avl_bf ) {
                            /* case 3b: height reduced, single rotate */
                            p->avl_link[nside] = q->avl_link[side];
                            q->avl_link[side] = p;
                            shorter = 1;
                            q->avl_bf = EH;
                            p->avl_bf = EH;

                     } else {
                            /* case 3c: height reduced, balance factors opposite */
                            r = q->avl_link[side];
                            q->avl_link[side] = r->avl_link[nside];
                            r->avl_link[nside] = q;

                            p->avl_link[nside] = r->avl_link[side];
                            r->avl_link[side] = p;

                            if ( r->avl_bf == side_bf ) {
                                   q->avl_bf = (- side_bf);
                                   p->avl_bf = EH;
                            } else if ( r->avl_bf == (- side_bf)) {
                                   q->avl_bf = EH;
                                   p->avl_bf = side_bf;
                            } else {
                                   q->avl_bf = EH;
                                   p->avl_bf = EH;
                            }
                            r->avl_bf = EH;
                            q = r;
                     }
                     /* a rotation has caused <q> (or <r> in case 3c) to become
                      * the root.  let <p>'s former parent know this.
                      */
                     if ( top == NULL ) {
                            *root = q;
                     } else if (top->avl_link[0] == p) {
                            top->avl_link[0] = q;
                     } else {
                            top->avl_link[1] = q;
                     }
                     /* end case 3 */
                     p = q;
              }
              if ( !depth )
                     break;
              depth--;
       } /* end while(shorter) */

       return data;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int avl_dup_error ( void left,
void right 
)

Definition at line 660 of file avl.c.

{
       return( -1 );
}

Here is the caller graph for this function:

int avl_dup_ok ( void left,
void right 
)

Definition at line 666 of file avl.c.

{
       return( 0 );
}
void* avl_find ( Avlnode *  root,
const void data,
AVL_CMP  fcmp 
)

Definition at line 541 of file avl.c.

{
       int    cmp;

       while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
              cmp = cmp > 0;
              root = root->avl_link[cmp];
       }

       return( root ? root->avl_data : 0 );
}

Here is the call graph for this function:

Avlnode* avl_find2 ( Avlnode *  root,
const void data,
AVL_CMP  fcmp 
)

Definition at line 529 of file avl.c.

{
       int    cmp;

       while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
              cmp = cmp > 0;
              root = root->avl_link[cmp];
       }
       return root;
}

Here is the call graph for this function:

void* avl_find_lin ( Avlnode *  root,
const void data,
AVL_CMP  fcmp 
)

Definition at line 561 of file avl.c.

{
       void*  res;

       if ( root == 0 )
              return( NULL );

       if ( (*fcmp)( data, root->avl_data ) == 0 )
              return( root->avl_data );

       if ( root->avl_left != 0 )
              if ( (res = avl_find_lin( root->avl_left, data, fcmp ))
                  != NULL )
                     return( res );

       if ( root->avl_right == 0 )
              return( NULL );
       else
              return( avl_find_lin( root->avl_right, data, fcmp ) );
}
int avl_free ( Avlnode *  root,
AVL_FREE  dfree 
)

Definition at line 500 of file avl.c.

{
       int    nleft, nright;

       if ( root == 0 )
              return( 0 );

       nleft = nright = 0;
       if ( root->avl_left != 0 )
              nleft = avl_free( root->avl_left, dfree );

       if ( root->avl_right != 0 )
              nright = avl_free( root->avl_right, dfree );

       if ( dfree )
              (*dfree)( root->avl_data );
       ber_memfree( root );

       return( nleft + nright + 1 );
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* avl_getfirst ( Avlnode *  root)

Definition at line 624 of file avl.c.

{
       if ( avl_list ) {
              ber_memfree( (char *) avl_list);
              avl_list = (void* *) 0;
       }
       avl_maxlist = 0;
       avl_nextlist = 0;

       if ( root == 0 )
              return( 0 );

       (void) avl_apply( root, avl_buildlist, (void*) 0, -1, AVL_INORDER );

       return( avl_list[ avl_nextlist++ ] );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 642 of file avl.c.

{
       if ( avl_list == 0 )
              return( 0 );

       if ( avl_nextlist == avl_maxlist ) {
              ber_memfree( (void*) avl_list);
              avl_list = (void* *) 0;
              return( 0 );
       }

       return( avl_list[ avl_nextlist++ ] );
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int avl_inapply ( Avlnode *  root,
AVL_APPLY  fn,
void arg,
int  stopflag 
) [static]

Definition at line 353 of file avl.c.

{
       if ( root == 0 )
              return( AVL_NOMORE );

       if ( root->avl_left != 0 )
              if ( avl_inapply( root->avl_left, fn, arg, stopflag ) 
                  == stopflag )
                     return( stopflag );

       if ( (*fn)( root->avl_data, arg ) == stopflag )
              return( stopflag );

       if ( root->avl_right == 0 )
              return( AVL_NOMORE );
       else
              return( avl_inapply( root->avl_right, fn, arg, stopflag ) );
}

Here is the caller graph for this function:

int avl_insert ( Avlnode **  root,
void data,
AVL_CMP  fcmp,
AVL_DUP  fdup 
)

Definition at line 73 of file avl.c.

{
    Avlnode *t, *p, *s, *q, *r;
    int a, cmp, ncmp;

       if ( *root == NULL ) {
              if (( r = (Avlnode *) ber_memalloc( sizeof( Avlnode ))) == NULL ) {
                     return( -1 );
              }
              r->avl_link[0] = r->avl_link[1] = NULL;
              r->avl_data = data;
              r->avl_bf = EH;
              *root = r;

              return( 0 );
       }

    t = NULL;
    s = p = *root;

       /* find insertion point */
    while (1) {
              cmp = fcmp( data, p->avl_data );
              if ( cmp == 0 )
                     return (*fdup)( p->avl_data, data );

              cmp = (cmp > 0);
              q = p->avl_link[cmp];
              if (q == NULL) {
                     /* insert */
                     if (( q = (Avlnode *) ber_memalloc( sizeof( Avlnode ))) == NULL ) {
                            return( -1 );
                     }
                     q->avl_link[0] = q->avl_link[1] = NULL;
                     q->avl_data = data;
                     q->avl_bf = EH;

                     p->avl_link[cmp] = q;
                     break;
              } else if ( q->avl_bf ) {
                     t = p;
                     s = q;
              }
              p = q;
    }

    /* adjust balance factors */
    cmp = fcmp( data, s->avl_data ) > 0;
       r = p = s->avl_link[cmp];
       a = avl_bfs[cmp];

       while ( p != q ) {
              cmp = fcmp( data, p->avl_data ) > 0;
              p->avl_bf = avl_bfs[cmp];
              p = p->avl_link[cmp];
       }

       /* checks and balances */

       if ( s->avl_bf == EH ) {
              s->avl_bf = a;
              return 0;
       } else if ( s->avl_bf == -a ) {
              s->avl_bf = EH;
              return 0;
    } else if ( s->avl_bf == a ) {
              cmp = (a > 0);
              ncmp = !cmp;
              if ( r->avl_bf == a ) {
                     /* single rotation */
                     p = r;
                     s->avl_link[cmp] = r->avl_link[ncmp];
                     r->avl_link[ncmp] = s;
                     s->avl_bf = 0;
                     r->avl_bf = 0;
              } else if ( r->avl_bf == -a ) {
                     /* double rotation */
                     p = r->avl_link[ncmp];
                     r->avl_link[ncmp] = p->avl_link[cmp];
                     p->avl_link[cmp] = r;
                     s->avl_link[cmp] = p->avl_link[ncmp];
                     p->avl_link[ncmp] = s;

                     if ( p->avl_bf == a ) {
                            s->avl_bf = -a;
                            r->avl_bf = 0;
                     } else if ( p->avl_bf == -a ) {
                            s->avl_bf = 0;
                            r->avl_bf = a;
                     } else {
                            s->avl_bf = 0;
                            r->avl_bf = 0;
                     }
                     p->avl_bf = 0;
              }
              /* Update parent */
              if ( t == NULL )
                     *root = p;
              else if ( s == t->avl_right )
                     t->avl_right = p;
              else
                     t->avl_left = p;
    }

  return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int avl_postapply ( Avlnode *  root,
AVL_APPLY  fn,
void arg,
int  stopflag 
) [static]

Definition at line 373 of file avl.c.

{
       if ( root == 0 )
              return( AVL_NOMORE );

       if ( root->avl_left != 0 )
              if ( avl_postapply( root->avl_left, fn, arg, stopflag ) 
                  == stopflag )
                     return( stopflag );

       if ( root->avl_right != 0 )
              if ( avl_postapply( root->avl_right, fn, arg, stopflag ) 
                  == stopflag )
                     return( stopflag );

       return( (*fn)( root->avl_data, arg ) );
}

Here is the caller graph for this function:

static int avl_preapply ( Avlnode *  root,
AVL_APPLY  fn,
void arg,
int  stopflag 
) [static]

Definition at line 392 of file avl.c.

{
       if ( root == 0 )
              return( AVL_NOMORE );

       if ( (*fn)( root->avl_data, arg ) == stopflag )
              return( stopflag );

       if ( root->avl_left != 0 )
              if ( avl_preapply( root->avl_left, fn, arg, stopflag ) 
                  == stopflag )
                     return( stopflag );

       if ( root->avl_right == 0 )
              return( AVL_NOMORE );
       else
              return( avl_preapply( root->avl_right, fn, arg, stopflag ) );
}

Here is the caller graph for this function:

int avl_prefixapply ( Avlnode *  root,
void data,
AVL_CMP  fmatch,
void marg,
AVL_CMP  fcmp,
void carg,
int  stopflag 
)

Definition at line 449 of file avl.c.

{
       int    cmp;

       if ( root == 0 )
              return( AVL_NOMORE );

       cmp = (*fcmp)( data, root->avl_data /* , carg */);
       if ( cmp == 0 ) {
              if ( (*fmatch)( root->avl_data, marg ) == stopflag )
                     return( stopflag );

              if ( root->avl_left != 0 )
                     if ( avl_prefixapply( root->avl_left, data, fmatch,
                         marg, fcmp, carg, stopflag ) == stopflag )
                            return( stopflag );

              if ( root->avl_right != 0 )
                     return( avl_prefixapply( root->avl_right, data, fmatch,
                         marg, fcmp, carg, stopflag ) );
              else
                     return( AVL_NOMORE );

       } else if ( cmp < 0 ) {
              if ( root->avl_left != 0 )
                     return( avl_prefixapply( root->avl_left, data, fmatch,
                         marg, fcmp, carg, stopflag ) );
       } else {
              if ( root->avl_right != 0 )
                     return( avl_prefixapply( root->avl_right, data, fmatch,
                         marg, fcmp, carg, stopflag ) );
       }

       return( AVL_NOMORE );
}

Here is the call graph for this function:


Variable Documentation

const int avl_bfs[] = {LH, RH} [static]

Definition at line 55 of file avl.c.

void* * avl_list [static]

Definition at line 584 of file avl.c.

int avl_maxlist [static]

Definition at line 585 of file avl.c.

int avl_nextlist [static]

Definition at line 586 of file avl.c.