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-2021 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 "ldap_avl.h"
41
42 static void ravl_print LDAP_P(( TAvlnode *root, int depth, int thread ));
43 static void myprint LDAP_P(( TAvlnode *root ));
44 static int avl_strcmp LDAP_P(( const void *s, const void *t ));
45
46 int
main(int argc,char ** argv)47 main( int argc, char **argv )
48 {
49 TAvlnode *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 ) ldap_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 = ldap_tavl_end( tree, TAVL_DIR_LEFT );
67 n != NULL;
68 n = ldap_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 *) ldap_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 ( ldap_tavl_insert( &tree, strdup( name ), avl_strcmp,
89 ldap_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 ( ldap_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
115 static const char bfc_array[] = "\\-/";
116 static const char *bfcs = bfc_array+1;
117
ravl_print(TAvlnode * root,int depth,int thread)118 static void ravl_print( TAvlnode *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
myprint(TAvlnode * root)143 static void myprint( TAvlnode *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
avl_strcmp(const void * s,const void * t)155 static int avl_strcmp( const void *s, const void *t )
156 {
157 return strcmp( s, t );
158 }
159