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). Additional contributors include 29 * Howard Chu 30 */ 31 32#include "portable.h" 33 34#include <stdio.h> 35 36#include <ac/stdlib.h> 37#include <ac/string.h> 38 39#define AVL_INTERNAL 40#include "avl.h" 41 42static void ravl_print LDAP_P(( Avlnode *root, int depth, int thread )); 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, *n; 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 ) tavl_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 printf( "***\n" ); 66 for ( n = tavl_end( tree, TAVL_DIR_LEFT ); 67 n != NULL; 68 n = tavl_next( n, TAVL_DIR_RIGHT )) 69 printf( "%s\n", n->avl_data ); 70 printf( "***\n" ); 71 break; 72 case 'f': /* find */ 73 printf( "data? " ); 74 if ( fgets( name, sizeof( name ), stdin ) == NULL ) 75 exit( EXIT_SUCCESS ); 76 name[ strlen( name ) - 1 ] = '\0'; 77 if ( (p = (char *) tavl_find( tree, name, avl_strcmp )) 78 == NULL ) 79 printf( "Not found.\n\n" ); 80 else 81 printf( "%s\n\n", p ); 82 break; 83 case 'i': /* insert */ 84 printf( "data? " ); 85 if ( fgets( name, sizeof( name ), stdin ) == NULL ) 86 exit( EXIT_SUCCESS ); 87 name[ strlen( name ) - 1 ] = '\0'; 88 if ( tavl_insert( &tree, strdup( name ), avl_strcmp, 89 avl_dup_error ) != 0 ) 90 printf( "\nNot inserted!\n" ); 91 break; 92 case 'd': /* delete */ 93 printf( "data? " ); 94 if ( fgets( name, sizeof( name ), stdin ) == NULL ) 95 exit( EXIT_SUCCESS ); 96 name[ strlen( name ) - 1 ] = '\0'; 97 if ( tavl_delete( &tree, name, avl_strcmp ) == NULL ) 98 printf( "\nNot found!\n" ); 99 break; 100 case 'q': /* quit */ 101 exit( EXIT_SUCCESS ); 102 break; 103 case '\n': 104 break; 105 default: 106 printf("Commands: insert, delete, print, new, quit\n"); 107 } 108 109 printf( "> " ); 110 } 111 112 return( 0 ); 113} 114 115static const char bfc_array[] = "\\-/"; 116static const char *bfcs = bfc_array+1; 117 118static void ravl_print( Avlnode *root, int depth, int thread ) 119{ 120 int i; 121 122 if ( root && !thread ) 123 ravl_print( root->avl_link[1], depth+1, root->avl_bits[1] == AVL_THREAD ); 124 125 for ( i = 0; i < depth; i++ ) 126 printf( " " ); 127 if ( thread ) 128 printf( "~" ); 129 else if ( root ) 130 printf( "%c", bfcs[root->avl_bf] ); 131 else 132 printf( " " ); 133 if ( !root) { 134 printf( ".\n" ); 135 return; 136 } 137 printf( "%s\n", (char *) root->avl_data ); 138 139 if ( !thread ) 140 ravl_print( root->avl_link[0], depth+1, root->avl_bits[0] == AVL_THREAD ); 141} 142 143static void myprint( Avlnode *root ) 144{ 145 printf( "********\n" ); 146 147 if ( root == 0 ) 148 printf( "\tNULL\n" ); 149 else 150 ravl_print( root, 0, 0 ); 151 152 printf( "********\n" ); 153} 154 155static int avl_strcmp( const void *s, const void *t ) 156{ 157 return strcmp( s, t ); 158} 159