1*cf1d77f7Schristos /* $NetBSD: testtavl.c,v 1.2 2021/08/14 16:14:56 christos Exp $ */
292cfeba6Schristos
392cfeba6Schristos /* testavl.c - Test Tim Howes AVL code */
492cfeba6Schristos /* $OpenLDAP$ */
592cfeba6Schristos /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
692cfeba6Schristos *
792cfeba6Schristos * Copyright 1998-2021 The OpenLDAP Foundation.
892cfeba6Schristos * All rights reserved.
992cfeba6Schristos *
1092cfeba6Schristos * Redistribution and use in source and binary forms, with or without
1192cfeba6Schristos * modification, are permitted only as authorized by the OpenLDAP
1292cfeba6Schristos * Public License.
1392cfeba6Schristos *
1492cfeba6Schristos * A copy of this license is available in the file LICENSE in the
1592cfeba6Schristos * top-level directory of the distribution or, alternatively, at
1692cfeba6Schristos * <http://www.OpenLDAP.org/license.html>.
1792cfeba6Schristos */
1892cfeba6Schristos /* Portions Copyright (c) 1993 Regents of the University of Michigan.
1992cfeba6Schristos * All rights reserved.
2092cfeba6Schristos *
2192cfeba6Schristos * Redistribution and use in source and binary forms are permitted
2292cfeba6Schristos * provided that this notice is preserved and that due credit is given
2392cfeba6Schristos * to the University of Michigan at Ann Arbor. The name of the University
2492cfeba6Schristos * may not be used to endorse or promote products derived from this
2592cfeba6Schristos * software without specific prior written permission. This software
2692cfeba6Schristos * is provided ``as is'' without express or implied warranty.
2792cfeba6Schristos */
2892cfeba6Schristos /* ACKNOWLEDGEMENTS:
2992cfeba6Schristos * This work was originally developed by the University of Michigan
3092cfeba6Schristos * (as part of U-MICH LDAP). Additional contributors include
3192cfeba6Schristos * Howard Chu
3292cfeba6Schristos */
3392cfeba6Schristos
3492cfeba6Schristos #include <sys/cdefs.h>
35*cf1d77f7Schristos __RCSID("$NetBSD: testtavl.c,v 1.2 2021/08/14 16:14:56 christos Exp $");
3692cfeba6Schristos
3792cfeba6Schristos #include "portable.h"
3892cfeba6Schristos
3992cfeba6Schristos #include <stdio.h>
4092cfeba6Schristos
4192cfeba6Schristos #include <ac/stdlib.h>
4292cfeba6Schristos #include <ac/string.h>
4392cfeba6Schristos
4492cfeba6Schristos #define AVL_INTERNAL
4592cfeba6Schristos #include "ldap_avl.h"
4692cfeba6Schristos
4792cfeba6Schristos static void ravl_print LDAP_P(( TAvlnode *root, int depth, int thread ));
4892cfeba6Schristos static void myprint LDAP_P(( TAvlnode *root ));
4992cfeba6Schristos static int avl_strcmp LDAP_P(( const void *s, const void *t ));
5092cfeba6Schristos
5192cfeba6Schristos int
main(int argc,char ** argv)5292cfeba6Schristos main( int argc, char **argv )
5392cfeba6Schristos {
5492cfeba6Schristos TAvlnode *tree = NULL, *n;
5592cfeba6Schristos char command[ 10 ];
5692cfeba6Schristos char name[ 80 ];
5792cfeba6Schristos char *p;
5892cfeba6Schristos
5992cfeba6Schristos printf( "> " );
6092cfeba6Schristos while ( fgets( command, sizeof( command ), stdin ) != NULL ) {
6192cfeba6Schristos switch( *command ) {
6292cfeba6Schristos case 'n': /* new tree */
6392cfeba6Schristos ( void ) ldap_tavl_free( tree, free );
6492cfeba6Schristos tree = NULL;
6592cfeba6Schristos break;
6692cfeba6Schristos case 'p': /* print */
6792cfeba6Schristos ( void ) myprint( tree );
6892cfeba6Schristos break;
6992cfeba6Schristos case 't': /* traverse with first, next */
7092cfeba6Schristos printf( "***\n" );
7192cfeba6Schristos for ( n = ldap_tavl_end( tree, TAVL_DIR_LEFT );
7292cfeba6Schristos n != NULL;
7392cfeba6Schristos n = ldap_tavl_next( n, TAVL_DIR_RIGHT ))
7492cfeba6Schristos printf( "%s\n", n->avl_data );
7592cfeba6Schristos printf( "***\n" );
7692cfeba6Schristos break;
7792cfeba6Schristos case 'f': /* find */
7892cfeba6Schristos printf( "data? " );
7992cfeba6Schristos if ( fgets( name, sizeof( name ), stdin ) == NULL )
8092cfeba6Schristos exit( EXIT_SUCCESS );
8192cfeba6Schristos name[ strlen( name ) - 1 ] = '\0';
8292cfeba6Schristos if ( (p = (char *) ldap_tavl_find( tree, name, avl_strcmp ))
8392cfeba6Schristos == NULL )
8492cfeba6Schristos printf( "Not found.\n\n" );
8592cfeba6Schristos else
8692cfeba6Schristos printf( "%s\n\n", p );
8792cfeba6Schristos break;
8892cfeba6Schristos case 'i': /* insert */
8992cfeba6Schristos printf( "data? " );
9092cfeba6Schristos if ( fgets( name, sizeof( name ), stdin ) == NULL )
9192cfeba6Schristos exit( EXIT_SUCCESS );
9292cfeba6Schristos name[ strlen( name ) - 1 ] = '\0';
9392cfeba6Schristos if ( ldap_tavl_insert( &tree, strdup( name ), avl_strcmp,
9492cfeba6Schristos ldap_avl_dup_error ) != 0 )
9592cfeba6Schristos printf( "\nNot inserted!\n" );
9692cfeba6Schristos break;
9792cfeba6Schristos case 'd': /* delete */
9892cfeba6Schristos printf( "data? " );
9992cfeba6Schristos if ( fgets( name, sizeof( name ), stdin ) == NULL )
10092cfeba6Schristos exit( EXIT_SUCCESS );
10192cfeba6Schristos name[ strlen( name ) - 1 ] = '\0';
10292cfeba6Schristos if ( ldap_tavl_delete( &tree, name, avl_strcmp ) == NULL )
10392cfeba6Schristos printf( "\nNot found!\n" );
10492cfeba6Schristos break;
10592cfeba6Schristos case 'q': /* quit */
10692cfeba6Schristos exit( EXIT_SUCCESS );
10792cfeba6Schristos break;
10892cfeba6Schristos case '\n':
10992cfeba6Schristos break;
11092cfeba6Schristos default:
11192cfeba6Schristos printf("Commands: insert, delete, print, new, quit\n");
11292cfeba6Schristos }
11392cfeba6Schristos
11492cfeba6Schristos printf( "> " );
11592cfeba6Schristos }
11692cfeba6Schristos
11792cfeba6Schristos return( 0 );
11892cfeba6Schristos }
11992cfeba6Schristos
12092cfeba6Schristos static const char bfc_array[] = "\\-/";
12192cfeba6Schristos static const char *bfcs = bfc_array+1;
12292cfeba6Schristos
ravl_print(TAvlnode * root,int depth,int thread)12392cfeba6Schristos static void ravl_print( TAvlnode *root, int depth, int thread )
12492cfeba6Schristos {
12592cfeba6Schristos int i;
12692cfeba6Schristos
12792cfeba6Schristos if ( root && !thread )
12892cfeba6Schristos ravl_print( root->avl_link[1], depth+1, root->avl_bits[1] == AVL_THREAD );
12992cfeba6Schristos
13092cfeba6Schristos for ( i = 0; i < depth; i++ )
13192cfeba6Schristos printf( " " );
13292cfeba6Schristos if ( thread )
13392cfeba6Schristos printf( "~" );
13492cfeba6Schristos else if ( root )
13592cfeba6Schristos printf( "%c", bfcs[root->avl_bf] );
13692cfeba6Schristos else
13792cfeba6Schristos printf( " " );
13892cfeba6Schristos if ( !root) {
13992cfeba6Schristos printf( ".\n" );
14092cfeba6Schristos return;
14192cfeba6Schristos }
14292cfeba6Schristos printf( "%s\n", (char *) root->avl_data );
14392cfeba6Schristos
14492cfeba6Schristos if ( !thread )
14592cfeba6Schristos ravl_print( root->avl_link[0], depth+1, root->avl_bits[0] == AVL_THREAD );
14692cfeba6Schristos }
14792cfeba6Schristos
myprint(TAvlnode * root)14892cfeba6Schristos static void myprint( TAvlnode *root )
14992cfeba6Schristos {
15092cfeba6Schristos printf( "********\n" );
15192cfeba6Schristos
15292cfeba6Schristos if ( root == 0 )
15392cfeba6Schristos printf( "\tNULL\n" );
15492cfeba6Schristos else
15592cfeba6Schristos ravl_print( root, 0, 0 );
15692cfeba6Schristos
15792cfeba6Schristos printf( "********\n" );
15892cfeba6Schristos }
15992cfeba6Schristos
avl_strcmp(const void * s,const void * t)16092cfeba6Schristos static int avl_strcmp( const void *s, const void *t )
16192cfeba6Schristos {
16292cfeba6Schristos return strcmp( s, t );
16392cfeba6Schristos }
164