1/* $NetBSD$ */ 2 3/* testavl.c - Test Tim Howes AVL code */ 4/* OpenLDAP: pkg/ldap/libraries/liblutil/testtavl.c,v 1.2.2.5 2010/04/13 20:23:07 kurt Exp */ 5/* This work is part of OpenLDAP Software <http://www.openldap.org/>. 6 * 7 * Copyright 1998-2010 The OpenLDAP Foundation. 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted only as authorized by the OpenLDAP 12 * Public License. 13 * 14 * A copy of this license is available in the file LICENSE in the 15 * top-level directory of the distribution or, alternatively, at 16 * <http://www.OpenLDAP.org/license.html>. 17 */ 18/* Portions Copyright (c) 1993 Regents of the University of Michigan. 19 * All rights reserved. 20 * 21 * Redistribution and use in source and binary forms are permitted 22 * provided that this notice is preserved and that due credit is given 23 * to the University of Michigan at Ann Arbor. The name of the University 24 * may not be used to endorse or promote products derived from this 25 * software without specific prior written permission. This software 26 * is provided ``as is'' without express or implied warranty. 27 */ 28/* ACKNOWLEDGEMENTS: 29 * This work was originally developed by the University of Michigan 30 * (as part of U-MICH LDAP). Additional contributors include 31 * Howard Chu 32 */ 33 34#include "portable.h" 35 36#include <stdio.h> 37 38#include <ac/stdlib.h> 39#include <ac/string.h> 40 41#define AVL_INTERNAL 42#include "avl.h" 43 44static void ravl_print LDAP_P(( Avlnode *root, int depth, int thread )); 45static void myprint LDAP_P(( Avlnode *root )); 46static int avl_strcmp LDAP_P(( const void *s, const void *t )); 47 48int 49main( int argc, char **argv ) 50{ 51 Avlnode *tree = NULL, *n; 52 char command[ 10 ]; 53 char name[ 80 ]; 54 char *p; 55 56 printf( "> " ); 57 while ( fgets( command, sizeof( command ), stdin ) != NULL ) { 58 switch( *command ) { 59 case 'n': /* new tree */ 60 ( void ) tavl_free( tree, free ); 61 tree = NULL; 62 break; 63 case 'p': /* print */ 64 ( void ) myprint( tree ); 65 break; 66 case 't': /* traverse with first, next */ 67 printf( "***\n" ); 68 for ( n = tavl_end( tree, TAVL_DIR_LEFT ); 69 n != NULL; 70 n = tavl_next( n, TAVL_DIR_RIGHT )) 71 printf( "%s\n", n->avl_data ); 72 printf( "***\n" ); 73 break; 74 case 'f': /* find */ 75 printf( "data? " ); 76 if ( fgets( name, sizeof( name ), stdin ) == NULL ) 77 exit( EXIT_SUCCESS ); 78 name[ strlen( name ) - 1 ] = '\0'; 79 if ( (p = (char *) tavl_find( tree, name, avl_strcmp )) 80 == NULL ) 81 printf( "Not found.\n\n" ); 82 else 83 printf( "%s\n\n", p ); 84 break; 85 case 'i': /* insert */ 86 printf( "data? " ); 87 if ( fgets( name, sizeof( name ), stdin ) == NULL ) 88 exit( EXIT_SUCCESS ); 89 name[ strlen( name ) - 1 ] = '\0'; 90 if ( tavl_insert( &tree, strdup( name ), avl_strcmp, 91 avl_dup_error ) != 0 ) 92 printf( "\nNot inserted!\n" ); 93 break; 94 case 'd': /* delete */ 95 printf( "data? " ); 96 if ( fgets( name, sizeof( name ), stdin ) == NULL ) 97 exit( EXIT_SUCCESS ); 98 name[ strlen( name ) - 1 ] = '\0'; 99 if ( tavl_delete( &tree, name, avl_strcmp ) == NULL ) 100 printf( "\nNot found!\n" ); 101 break; 102 case 'q': /* quit */ 103 exit( EXIT_SUCCESS ); 104 break; 105 case '\n': 106 break; 107 default: 108 printf("Commands: insert, delete, print, new, quit\n"); 109 } 110 111 printf( "> " ); 112 } 113 114 return( 0 ); 115} 116 117static const char bfc_array[] = "\\-/"; 118static const char *bfcs = bfc_array+1; 119 120static void ravl_print( Avlnode *root, int depth, int thread ) 121{ 122 int i; 123 124 if ( root && !thread ) 125 ravl_print( root->avl_link[1], depth+1, root->avl_bits[1] == AVL_THREAD ); 126 127 for ( i = 0; i < depth; i++ ) 128 printf( " " ); 129 if ( thread ) 130 printf( "~" ); 131 else if ( root ) 132 printf( "%c", bfcs[root->avl_bf] ); 133 else 134 printf( " " ); 135 if ( !root) { 136 printf( ".\n" ); 137 return; 138 } 139 printf( "%s\n", (char *) root->avl_data ); 140 141 if ( !thread ) 142 ravl_print( root->avl_link[0], depth+1, root->avl_bits[0] == AVL_THREAD ); 143} 144 145static void myprint( Avlnode *root ) 146{ 147 printf( "********\n" ); 148 149 if ( root == 0 ) 150 printf( "\tNULL\n" ); 151 else 152 ravl_print( root, 0, 0 ); 153 154 printf( "********\n" ); 155} 156 157static int avl_strcmp( const void *s, const void *t ) 158{ 159 return strcmp( s, t ); 160} 161