1/* testavl.c - Test Tim Howes AVL code */ 2/* $OpenLDAP$ */ 3/* This work is part of OpenLDAP Software <http://www.openldap.org/>. 4 * 5 * Copyright 1998-2011 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). 29 */ 30 31#include "portable.h" 32 33#include <stdio.h> 34 35#include <ac/stdlib.h> 36#include <ac/string.h> 37 38#define AVL_INTERNAL 39#define AVL_NONREENTRANT 40#include "avl.h" 41 42static void ravl_print LDAP_P(( Avlnode *root, int depth )); 43static void myprint LDAP_P(( Avlnode *root )); 44static int avl_strcmp LDAP_P(( const void *s, const void *t )); 45 46int 47main( int argc, char **argv ) 48{ 49 Avlnode *tree = NULL; 50 char command[ 10 ]; 51 char name[ 80 ]; 52 char *p; 53 54 printf( "> " ); 55 while ( fgets( command, sizeof( command ), stdin ) != NULL ) { 56 switch( *command ) { 57 case 'n': /* new tree */ 58 ( void ) avl_free( tree, free ); 59 tree = NULL; 60 break; 61 case 'p': /* print */ 62 ( void ) myprint( tree ); 63 break; 64 case 't': /* traverse with first, next */ 65#ifdef AVL_NONREENTRANT 66 printf( "***\n" ); 67 for ( p = (char * ) avl_getfirst( tree ); 68 p != NULL; 69 p = (char *) avl_getnext()) 70 printf( "%s\n", p ); 71 printf( "***\n" ); 72#else 73 printf( "*** reentrant interface not implemented ***" ); 74#endif 75 break; 76 case 'f': /* find */ 77 printf( "data? " ); 78 if ( fgets( name, sizeof( name ), stdin ) == NULL ) 79 exit( EXIT_SUCCESS ); 80 name[ strlen( name ) - 1 ] = '\0'; 81 if ( (p = (char *) avl_find( tree, name, avl_strcmp )) 82 == NULL ) 83 printf( "Not found.\n\n" ); 84 else 85 printf( "%s\n\n", p ); 86 break; 87 case 'i': /* insert */ 88 printf( "data? " ); 89 if ( fgets( name, sizeof( name ), stdin ) == NULL ) 90 exit( EXIT_SUCCESS ); 91 name[ strlen( name ) - 1 ] = '\0'; 92 if ( avl_insert( &tree, strdup( name ), avl_strcmp, 93 avl_dup_error ) != 0 ) 94 printf( "\nNot inserted!\n" ); 95 break; 96 case 'd': /* delete */ 97 printf( "data? " ); 98 if ( fgets( name, sizeof( name ), stdin ) == NULL ) 99 exit( EXIT_SUCCESS ); 100 name[ strlen( name ) - 1 ] = '\0'; 101 if ( avl_delete( &tree, name, avl_strcmp ) == NULL ) 102 printf( "\nNot found!\n" ); 103 break; 104 case 'q': /* quit */ 105 exit( EXIT_SUCCESS ); 106 break; 107 case '\n': 108 break; 109 default: 110 printf("Commands: insert, delete, print, new, quit\n"); 111 } 112 113 printf( "> " ); 114 } 115 116 return( 0 ); 117} 118 119static void ravl_print( Avlnode *root, int depth ) 120{ 121 int i; 122 123 if ( root == 0 ) 124 return; 125 126 ravl_print( root->avl_right, depth+1 ); 127 128 for ( i = 0; i < depth; i++ ) 129 printf( " " ); 130 printf( "%s %d\n", (char *) root->avl_data, root->avl_bf ); 131 132 ravl_print( root->avl_left, depth+1 ); 133} 134 135static void myprint( Avlnode *root ) 136{ 137 printf( "********\n" ); 138 139 if ( root == 0 ) 140 printf( "\tNULL\n" ); 141 else 142 ravl_print( root, 0 ); 143 144 printf( "********\n" ); 145} 146 147static int avl_strcmp( const void *s, const void *t ) 148{ 149 return strcmp( s, t ); 150} 151