/*
** COPYRIGHT (c) 1991 BY
** DIGITAL EQUIPMENT CORPORATION, MAYNARD, MASSACHUSETTS.
** ALL RIGHTS RESERVED.
**
** THIS SOFTWARE IS FURNISHED UNDER A LICENSE AND MAY BE USED AND COPIED
** ONLY  IN  ACCORDANCE  OF  THE  TERMS  OF  SUCH  LICENSE  AND WITH THE
** INCLUSION OF THE ABOVE COPYRIGHT NOTICE. THIS SOFTWARE OR  ANY  OTHER
** COPIES THEREOF MAY NOT BE PROVIDED OR OTHERWISE MADE AVAILABLE TO ANY
** OTHER PERSON.  NO TITLE TO AND  OWNERSHIP OF THE  SOFTWARE IS  HEREBY
** TRANSFERRED.
**
** THE INFORMATION IN THIS SOFTWARE IS  SUBJECT TO CHANGE WITHOUT NOTICE
** AND  SHOULD  NOT  BE  CONSTRUED  AS A COMMITMENT BY DIGITAL EQUIPMENT
** CORPORATION.
**
** DIGITAL ASSUMES NO RESPONSIBILITY FOR THE USE  OR  RELIABILITY OF ITS
** SOFTWARE ON EQUIPMENT WHICH IS NOT SUPPLIED BY DIGITAL.
**
*/

/*
**++
**  FACILITY:  CRTL
**
**  MODULE DESCRIPTION:
**
**	brute-force and mindless test program for the tsearch binary tree
**	manipulation routines. 
**
**  AUTHORS:
**
**      Stephen Hoffman
**
**  CREATION DATE:  12-Jun-1991
**
**  DESIGN ISSUES:
**
**	this module contains an assortment of insertion, deletion and tree
**	traversal requests.  If this module does not like the outcome of a
**	request, it prints a message and aborts.  Various status messages
**	are displayed for successes and failures.
**
**  MODIFICATION HISTORY:
**
**      {@tbs@}...
**--
*/

#include <search.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "tsearch.h"	/* only needed for reading the debugging flags */

struct tdata
    {
    long int tkey;
    long int tnum;
    long int tnum2;
    };
#ifndef NULL
#define NULL ((void *) 0)
#endif

/*
**  Declaration of the action routine.
*/
static void
jackson( struct tdata **now_serving,
    enum visit been_here_before, long int node_level );

/*
**  Declaration of the comparison routine
*/
static int
and_save( struct tdata *this, struct tdata *that );

/*
**  And declare some miscellaneous service routines.
*/
struct tdata *
get_a_node( long int key, long int flag );

static void
print_cond( struct tdata *t,
    long int fatal, long int this_or_that,
    char *this, char *that );

static void
print_abstract( struct tdata **t, char *msg );

static void
print_hexdump( char *t );

/*
**  Time to start the tests...
*/
main( long int argc, char *argv[], char *envp[] )
    {
    long int retstat;
    struct tdata *root = 0, *td, *ts;

    print_abstract( 0, "TSEARCH_TEST.C  V1.0-001" );
    print_abstract( 0, "Starting tests..." );

    /*
    **	What follows should be obvious -- we try a bunch of different
    **	operations in the hopes that we can trip up the routines under
    **	test.
    */

    td = get_a_node( 8192, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    ( ts, 1, (ts != NULL),
	"tsearch returned non-null (new tree formed).",
	"FATAL: tsearch returned null (error)." );

    td = get_a_node( 8192, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );
    if ( td == ts )
	print_abstract( &td, "ERROR: duplicate not detected." );

    td = get_a_node( 4096, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 10248, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 10244, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 10244, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    print_abstract( 0, "starting twalk operation." );
    twalk( (void *) root, jackson );

    td = get_a_node( 10244, 0 );
    print_abstract( &td, "starting tdelete deletion.  Using:" );
    ts = tdelete( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tdelete returned non-null (match).",
	"FATAL: tdelete returned null (no match)." );

    print_abstract( 0, "starting twalk operation." );
    twalk( (void *) root, jackson );

    td = get_a_node( 8192, 0 );
    print_abstract( &td, "starting tdelete deletion.  Using:" );
    ts = tdelete( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tdelete returned non-null (match).",
	"FATAL: tdelete returned null (no match)." );

    print_abstract( 0, "starting twalk operation." );
    twalk( (void *) root, jackson );

    td = get_a_node( 10244, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 10244, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );
    if ( td == ts )
	print_abstract( &td, "ERROR: duplicate not detected." );

    td = get_a_node( 10244, 0 );
    print_abstract( &td, "starting tfind search.  Using:" );
    ts = tfind( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tfind returned non-null (match).",
	"FATAL: tfind returned null (no match)." );

    print_abstract( 0, "starting twalk operation." );
    twalk( (void *) root, jackson );

    td = get_a_node( 10244, 0 );
    print_abstract( &td, "starting tdelete deletion.  Using:" );
    ts = tdelete( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tdelete returned non-null (match).",
	"FATAL: tdelete returned null (no match)." );

    print_abstract( 0, "starting twalk operation." );
    twalk( (void *) root, jackson );

    td = get_a_node( 10244, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 10246, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 10246, 0 );
    print_abstract( &td, "starting tdelete deletion.  Using:" );
    ts = tdelete( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tdelete returned non-null (match).",
	"FATAL: tdelete returned null (no match)." );

    print_abstract( 0, "starting twalk operation." );
    twalk( (void *) root, jackson );

    print_abstract( 0, "starting low-side deletion test." );

    td = get_a_node( 1024, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 1012, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 1048, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 1000, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 1026, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 1020, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 1028, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 1023, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 1025, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    print_abstract( 0, "starting twalk operation." );
    twalk( (void *) root, jackson );

    td = get_a_node( 1024, 0 );
    print_abstract( &td, "starting tdelete deletion.  Using:" );
    ts = tdelete( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tdelete returned non-null (match).",
	"FATAL: tdelete returned null (no match)." );

    print_abstract( 0, "starting twalk operation." );
    twalk( (void *) root, jackson );

    print_abstract( 0, "starting high-side deletion test." );

    td = get_a_node( 91024, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 91012, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 91048, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 91000, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 91026, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 91024, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 91020, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 91028, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 91023, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    td = get_a_node( 91025, 0 );
    print_abstract( &td, "starting tsearch insertion.  Using:" );
    ts = tsearch( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tsearch returned non-null (match).",
	"FATAL: tsearch returned null (no match)." );

    print_abstract( 0, "starting twalk operation." );
    twalk( (void *) root, jackson );

    td = get_a_node( 91024, 0 );
    print_abstract( &td, "starting tdelete deletion.  Using:" );
    ts = tdelete( td, (void *) &root, and_save );
    print_cond( ts, 1, (ts != NULL),
	"tdelete returned non-null (match).",
	"FATAL: tdelete returned null (no match)." );

    print_abstract( 0, "starting twalk operation." );
    twalk( (void *) root, jackson );


    print_abstract( 0, "test complete." );
#ifdef VMS
    return( 1 );
#else
    exit( 0 );
#endif
    }

/*
**  This is the compare routine.  This routine is an argument to
**  most of the routines of the tsearch ilk, the routines call
**  this routine to perform the key matching decision.
*/
static int
and_save( struct tdata *this, struct tdata *that )
    {
    struct tdata *here = this, *there = that;
    print_cond( here, 1, 1,
	"Comparison routine called.  Arguments are: ",
	"FATAL: print_cond failed. (and_save, ps:1)" );
    print_cond( there, 1, 1,
	0,
	"FATAL: print_cond failed. (and_save, ps:2)" );
    return( this->tkey - that->tkey );
    }

/*
**  Now for the action routine... 
**  This (mindless) one simply displays the arguments, node and contents.
*/
static void
jackson( struct tdata **now_serving,
    enum visit been_here_before, long int node_level )
    {
    char txt[30];

    txt[0] = 0;
    switch ( been_here_before )
	{
	case preorder:
	    strcpy( txt, "<preorder>");
	    break;
	case postorder:
	    strcpy( txt, "<postorder>");
	    break;
	case endorder:
	    strcpy( txt, "<endorder>");
	    break;
	case leaf:
	    strcpy( txt, "<leaf>");
	    break;
	default:
	    strcpy( txt, "<<bogus>>");
	    break;
	}

    printf("*   node: 0x%08.8x, <key: 0x%08.8x>, level: 0x%08.8x, %s.\r\n",
#if NODIFF
	((long int) (*now_serving)->tnum),
#else
	0x0deadcafe,
#endif
	((long int) (*now_serving)->tkey),
	((long int) node_level), ((char *) txt) );
#if NODIFF
    print_hexdump( (char *) now_serving );
#endif

    return;
    }

/*
**  Conditional print routine.
*/
static void
print_cond( struct tdata *t,
    long int fatal, long int this_or_that,
    char *this, char *that )
    {

    /*
    **	The this (success msg), that (failure msg) and t (the node in
    **	question) arguments are optional.
    */
    /*
    **	The this_or_that controls whether we print this, or that text.
    */
    if ( this_or_that )
	{
	/*
	**  Print this... The test was non-zero.
	*/
	if ( (long int) this )
	    printf( "* %s\r\n", this );

	if ( (long int ) t )
	    printf(
"*   node: 0x%08.8x, <key: 0x%08.8x>, number: 0x%08.8x\r\n",
#if NODIFF
		((long int) (t)),
#else
		0x0deadcafe,
#endif
		((long int) (t)->tkey),
		((long int) (t)->tnum) );
	}
    else
	{
	/*
	**  Print that... The test was non-zero. 
	*/
	if ( (long int) that )
	    printf( "* %s\r\n", that );
	if ( (long int ) t )
	    {
	    printf( 
"*   node: 0x%08.8x, <key: 0x%08.8x>, number: 0x%08.8x\r\n",
#if NODIFF
		((long int) (t)),
#else
		0x0deadcafe,
#endif
		((long int) (t)->tkey),
		((long int) (t)->tnum) );
	    }
	}
    /*
    **	Print out a hex dump of the node.  Then abort, if so requested.
    */
#if NODIFF
    print_hexdump( t );
#endif

    if (( !this_or_that ) && ( fatal ))
	abort();
    }

/*
**  Prints the contents of a node, and some text.
*/
static void
print_abstract( struct tdata **t, char *msg )
    {
    printf( "* \r\n" );
    if ( (long int ) msg )
    printf( "* %s\r\n", msg );
    if ( (long int ) t )
	{
	printf(
"*  node: 0x%08.8x, <key: 0x%08.8x>, number: 0x%08.8x\r\n",
#if NODIFF
	    ((long int) (*t)),
#else
	    0x0deadcafe,
#endif
	    ((long int) (*t)->tkey),
	    ((long int) (*t)->tnum) );
#if NODIFF
	print_hexdump( t );
#endif
	}
    }

/*
**  Prints a hexdump of the first twenty bytes.
*/
static void
print_hexdump( char *t )
    {
    char *q;
    int i;
    /*
    **	Check the contents of the variable for null, before we indirect
    **	through it and fall over.  Dereference the pointer one level, and 
    **	check for another null pointer.
    **
    **	K&R says evaluation occurs left-to-right, and that evaluation of
    **	boolean expressions stops as soon as the end condition is known.
    */
    if ( (long int) t )
	{
	q = t;
	printf( "*     hex dump (little endian format):\r\n" );
	printf( "*     " );
	for ( i = 19; i >= 0; i-- )
	    printf( "%02.2x ", *(((unsigned char *) q) + i));
	printf( "\r\n" );
	printf( "*     " );
	for ( i = 39; i >= 20; i-- )
	    printf( "%02.2x ", *(((unsigned char *) q) + i));
	printf( "\r\n" );
	}
    else
	{
	printf( "*   null pointer; no hex dump performed.\r\n" );
	}
    }
/*
**  Allocates a block of storage, and initializes the key (used for 
**  sorting and searching) and the flags (variable is named "f", it
**  is typically a sequence number) based on the argument.
*/
struct tdata *
get_a_node( long int key, long int flag )
    {
    static long int f = 0;
    struct tdata *t;

    t = calloc( sizeof (struct tdata), 1 );
    t->tkey = key;
    if ( flag )
	t->tnum = flag;
    else
	{
	t->tnum = t->tnum2 = f;
	f++;
	}

    print_abstract( &t, "Allocating and initializing a node" );

    return( t );
    }