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
main(int argc,char ** argv)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
ravl_print(TAvlnode * root,int depth,int thread)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
myprint(TAvlnode * root)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
avl_strcmp(const void * s,const void * t)160 static int avl_strcmp( const void *s, const void *t )
161 {
162 return strcmp( s, t );
163 }
164