summaryrefslogtreecommitdiffstats
path: root/libraries/liblutil/testtavl.c
blob: 330ed36b15c8193e4d4753b73d8266400f6e862b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/* testavl.c - Test Tim Howes AVL code */
/* $OpenLDAP$ */
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 *
 * Copyright 1998-2021 The OpenLDAP Foundation.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted only as authorized by the OpenLDAP
 * Public License.
 *
 * A copy of this license is available in the file LICENSE in the
 * top-level directory of the distribution or, alternatively, at
 * <http://www.OpenLDAP.org/license.html>.
 */
/* Portions Copyright (c) 1993 Regents of the University of Michigan.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that this notice is preserved and that due credit is given
 * to the University of Michigan at Ann Arbor. The name of the University
 * may not be used to endorse or promote products derived from this
 * software without specific prior written permission. This software
 * is provided ``as is'' without express or implied warranty.
 */
/* ACKNOWLEDGEMENTS:
 * This work was originally developed by the University of Michigan
 * (as part of U-MICH LDAP). Additional contributors include
 *   Howard Chu
 */

#include "portable.h"

#include <stdio.h>

#include <ac/stdlib.h>
#include <ac/string.h>

#define AVL_INTERNAL
#include "avl.h"

static void ravl_print LDAP_P(( Avlnode *root, int depth, int thread ));
static void myprint LDAP_P(( Avlnode *root ));
static int avl_strcmp LDAP_P(( const void *s, const void *t ));

int
main( int argc, char **argv )
{
	Avlnode	*tree = NULL, *n;
	char	command[ 10 ];
	char	name[ 80 ];
	char	*p;

	printf( "> " );
	while ( fgets( command, sizeof( command ), stdin ) != NULL ) {
		switch( *command ) {
		case 'n':	/* new tree */
			( void ) tavl_free( tree, free );
			tree = NULL;
			break;
		case 'p':	/* print */
			( void ) myprint( tree );
			break;
		case 't':	/* traverse with first, next */
			printf( "***\n" );
			for ( n = tavl_end( tree, TAVL_DIR_LEFT );
			    n != NULL;
				n = tavl_next( n, TAVL_DIR_RIGHT ))
				printf( "%s\n", n->avl_data );
			printf( "***\n" );
			break;
		case 'f':	/* find */
			printf( "data? " );
			if ( fgets( name, sizeof( name ), stdin ) == NULL )
				exit( EXIT_SUCCESS );
			name[ strlen( name ) - 1 ] = '\0';
			if ( (p = (char *) tavl_find( tree, name, avl_strcmp ))
			    == NULL )
				printf( "Not found.\n\n" );
			else
				printf( "%s\n\n", p );
			break;
		case 'i':	/* insert */
			printf( "data? " );
			if ( fgets( name, sizeof( name ), stdin ) == NULL )
				exit( EXIT_SUCCESS );
			name[ strlen( name ) - 1 ] = '\0';
			if ( tavl_insert( &tree, strdup( name ), avl_strcmp, 
			    avl_dup_error ) != 0 )
				printf( "\nNot inserted!\n" );
			break;
		case 'd':	/* delete */
			printf( "data? " );
			if ( fgets( name, sizeof( name ), stdin ) == NULL )
				exit( EXIT_SUCCESS );
			name[ strlen( name ) - 1 ] = '\0';
			if ( tavl_delete( &tree, name, avl_strcmp ) == NULL )
				printf( "\nNot found!\n" );
			break;
		case 'q':	/* quit */
			exit( EXIT_SUCCESS );
			break;
		case '\n':
			break;
		default:
			printf("Commands: insert, delete, print, new, quit\n");
		}

		printf( "> " );
	}

	return( 0 );
}

static const char bfc_array[] = "\\-/";
static const char *bfcs = bfc_array+1;

static void ravl_print( Avlnode *root, int depth, int thread )
{
	int	i;

	if ( root && !thread )
	ravl_print( root->avl_link[1], depth+1, root->avl_bits[1] == AVL_THREAD );

	for ( i = 0; i < depth; i++ )
		printf( "   " );
	if ( thread )
		printf( "~" );
	else if ( root )
		printf( "%c", bfcs[root->avl_bf] );
	else
		printf( " " );
	if ( !root) {
		printf( ".\n" );
		return;
	}
	printf( "%s\n", (char *) root->avl_data );

	if ( !thread )
	ravl_print( root->avl_link[0], depth+1, root->avl_bits[0] == AVL_THREAD );
}

static void myprint( Avlnode *root )
{
	printf( "********\n" );

	if ( root == 0 )
		printf( "\tNULL\n" );
	else
		ravl_print( root, 0, 0 );

	printf( "********\n" );
}

static int avl_strcmp( const void *s, const void *t )
{
	return strcmp( s, t );
}