Back to index

openldap  2.4.31
testtavl.c
Go to the documentation of this file.
00001 /* testavl.c - Test Tim Howes AVL code */
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 contributors include
00029  *   Howard Chu
00030  */
00031 
00032 #include "portable.h"
00033 
00034 #include <stdio.h>
00035 
00036 #include <ac/stdlib.h>
00037 #include <ac/string.h>
00038 
00039 #define AVL_INTERNAL
00040 #include "avl.h"
00041 
00042 static void ravl_print LDAP_P(( Avlnode *root, int depth, int thread ));
00043 static void myprint LDAP_P(( Avlnode *root ));
00044 static int avl_strcmp LDAP_P(( const void *s, const void *t ));
00045 
00046 int
00047 main( int argc, char **argv )
00048 {
00049        Avlnode       *tree = NULL, *n;
00050        char   command[ 10 ];
00051        char   name[ 80 ];
00052        char   *p;
00053 
00054        printf( "> " );
00055        while ( fgets( command, sizeof( command ), stdin ) != NULL ) {
00056               switch( *command ) {
00057               case 'n':     /* new tree */
00058                      ( void ) tavl_free( tree, free );
00059                      tree = NULL;
00060                      break;
00061               case 'p':     /* print */
00062                      ( void ) myprint( tree );
00063                      break;
00064               case 't':     /* traverse with first, next */
00065                      printf( "***\n" );
00066                      for ( n = tavl_end( tree, TAVL_DIR_LEFT );
00067                          n != NULL;
00068                             n = tavl_next( n, TAVL_DIR_RIGHT ))
00069                             printf( "%s\n", n->avl_data );
00070                      printf( "***\n" );
00071                      break;
00072               case 'f':     /* find */
00073                      printf( "data? " );
00074                      if ( fgets( name, sizeof( name ), stdin ) == NULL )
00075                             exit( EXIT_SUCCESS );
00076                      name[ strlen( name ) - 1 ] = '\0';
00077                      if ( (p = (char *) tavl_find( tree, name, avl_strcmp ))
00078                          == NULL )
00079                             printf( "Not found.\n\n" );
00080                      else
00081                             printf( "%s\n\n", p );
00082                      break;
00083               case 'i':     /* insert */
00084                      printf( "data? " );
00085                      if ( fgets( name, sizeof( name ), stdin ) == NULL )
00086                             exit( EXIT_SUCCESS );
00087                      name[ strlen( name ) - 1 ] = '\0';
00088                      if ( tavl_insert( &tree, strdup( name ), avl_strcmp, 
00089                          avl_dup_error ) != 0 )
00090                             printf( "\nNot inserted!\n" );
00091                      break;
00092               case 'd':     /* delete */
00093                      printf( "data? " );
00094                      if ( fgets( name, sizeof( name ), stdin ) == NULL )
00095                             exit( EXIT_SUCCESS );
00096                      name[ strlen( name ) - 1 ] = '\0';
00097                      if ( tavl_delete( &tree, name, avl_strcmp ) == NULL )
00098                             printf( "\nNot found!\n" );
00099                      break;
00100               case 'q':     /* quit */
00101                      exit( EXIT_SUCCESS );
00102                      break;
00103               case '\n':
00104                      break;
00105               default:
00106                      printf("Commands: insert, delete, print, new, quit\n");
00107               }
00108 
00109               printf( "> " );
00110        }
00111 
00112        return( 0 );
00113 }
00114 
00115 static const char bfc_array[] = "\\-/";
00116 static const char *bfcs = bfc_array+1;
00117 
00118 static void ravl_print( Avlnode *root, int depth, int thread )
00119 {
00120        int    i;
00121 
00122        if ( root && !thread )
00123        ravl_print( root->avl_link[1], depth+1, root->avl_bits[1] == AVL_THREAD );
00124 
00125        for ( i = 0; i < depth; i++ )
00126               printf( "   " );
00127        if ( thread )
00128               printf( "~" );
00129        else if ( root )
00130               printf( "%c", bfcs[root->avl_bf] );
00131        else
00132               printf( " " );
00133        if ( !root) {
00134               printf( ".\n" );
00135               return;
00136        }
00137        printf( "%s\n", (char *) root->avl_data );
00138 
00139        if ( !thread )
00140        ravl_print( root->avl_link[0], depth+1, root->avl_bits[0] == AVL_THREAD );
00141 }
00142 
00143 static void myprint( Avlnode *root )
00144 {
00145        printf( "********\n" );
00146 
00147        if ( root == 0 )
00148               printf( "\tNULL\n" );
00149        else
00150               ravl_print( root, 0, 0 );
00151 
00152        printf( "********\n" );
00153 }
00154 
00155 static int avl_strcmp( const void *s, const void *t )
00156 {
00157        return strcmp( s, t );
00158 }