1 /* $NetBSD: testtavl.c,v 1.2 2021/08/14 16:14:56 christos Exp $ */ 2 3 /* testavl.c - Test Tim Howes AVL code */ 4 /* $OpenLDAP$ */ 5 /* This work is part of OpenLDAP Software <http://www.openldap.org/>. 6 * 7 * Copyright 1998-2021 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 <sys/cdefs.h> 35 __RCSID("$NetBSD: testtavl.c,v 1.2 2021/08/14 16:14:56 christos Exp $"); 36 37 #include "portable.h" 38 39 #include <stdio.h> 40 41 #include <ac/stdlib.h> 42 #include <ac/string.h> 43 44 #define AVL_INTERNAL 45 #include "ldap_avl.h" 46 47 static void ravl_print LDAP_P(( TAvlnode *root, int depth, int thread )); 48 static void myprint LDAP_P(( TAvlnode *root )); 49 static int avl_strcmp LDAP_P(( const void *s, const void *t )); 50 51 int 52 main( int argc, char **argv ) 53 { 54 TAvlnode *tree = NULL, *n; 55 char command[ 10 ]; 56 char name[ 80 ]; 57 char *p; 58 59 printf( "> " ); 60 while ( fgets( command, sizeof( command ), stdin ) != NULL ) { 61 switch( *command ) { 62 case 'n': /* new tree */ 63 ( void ) ldap_tavl_free( tree, free ); 64 tree = NULL; 65 break; 66 case 'p': /* print */ 67 ( void ) myprint( tree ); 68 break; 69 case 't': /* traverse with first, next */ 70 printf( "***\n" ); 71 for ( n = ldap_tavl_end( tree, TAVL_DIR_LEFT ); 72 n != NULL; 73 n = ldap_tavl_next( n, TAVL_DIR_RIGHT )) 74 printf( "%s\n", n->avl_data ); 75 printf( "***\n" ); 76 break; 77 case 'f': /* find */ 78 printf( "data? " ); 79 if ( fgets( name, sizeof( name ), stdin ) == NULL ) 80 exit( EXIT_SUCCESS ); 81 name[ strlen( name ) - 1 ] = '\0'; 82 if ( (p = (char *) ldap_tavl_find( tree, name, avl_strcmp )) 83 == NULL ) 84 printf( "Not found.\n\n" ); 85 else 86 printf( "%s\n\n", p ); 87 break; 88 case 'i': /* insert */ 89 printf( "data? " ); 90 if ( fgets( name, sizeof( name ), stdin ) == NULL ) 91 exit( EXIT_SUCCESS ); 92 name[ strlen( name ) - 1 ] = '\0'; 93 if ( ldap_tavl_insert( &tree, strdup( name ), avl_strcmp, 94 ldap_avl_dup_error ) != 0 ) 95 printf( "\nNot inserted!\n" ); 96 break; 97 case 'd': /* delete */ 98 printf( "data? " ); 99 if ( fgets( name, sizeof( name ), stdin ) == NULL ) 100 exit( EXIT_SUCCESS ); 101 name[ strlen( name ) - 1 ] = '\0'; 102 if ( ldap_tavl_delete( &tree, name, avl_strcmp ) == NULL ) 103 printf( "\nNot found!\n" ); 104 break; 105 case 'q': /* quit */ 106 exit( EXIT_SUCCESS ); 107 break; 108 case '\n': 109 break; 110 default: 111 printf("Commands: insert, delete, print, new, quit\n"); 112 } 113 114 printf( "> " ); 115 } 116 117 return( 0 ); 118 } 119 120 static const char bfc_array[] = "\\-/"; 121 static const char *bfcs = bfc_array+1; 122 123 static void ravl_print( TAvlnode *root, int depth, int thread ) 124 { 125 int i; 126 127 if ( root && !thread ) 128 ravl_print( root->avl_link[1], depth+1, root->avl_bits[1] == AVL_THREAD ); 129 130 for ( i = 0; i < depth; i++ ) 131 printf( " " ); 132 if ( thread ) 133 printf( "~" ); 134 else if ( root ) 135 printf( "%c", bfcs[root->avl_bf] ); 136 else 137 printf( " " ); 138 if ( !root) { 139 printf( ".\n" ); 140 return; 141 } 142 printf( "%s\n", (char *) root->avl_data ); 143 144 if ( !thread ) 145 ravl_print( root->avl_link[0], depth+1, root->avl_bits[0] == AVL_THREAD ); 146 } 147 148 static void myprint( TAvlnode *root ) 149 { 150 printf( "********\n" ); 151 152 if ( root == 0 ) 153 printf( "\tNULL\n" ); 154 else 155 ravl_print( root, 0, 0 ); 156 157 printf( "********\n" ); 158 } 159 160 static int avl_strcmp( const void *s, const void *t ) 161 { 162 return strcmp( s, t ); 163 } 164