git.sur5r.net Git - openldap/blob - libraries/liblutil/testtavl.c

   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-2017 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 "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
  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 ) 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 = tavl_end( tree, TAVL_DIR_LEFT );
  67                             n != NULL;
  68                                 n = 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 *) 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 ( tavl_insert( &tree, strdup( name ), avl_strcmp,
  89                             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 ( 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
 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
 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
 155 static int avl_strcmp( const void *s, const void *t )
 156 {
 157         return strcmp( s, t );
 158 }