#include <search.h>
#include <string.h>
#include <stdio.h>


#define STRSZ    10000
#define NODSZ    500


struct node {      /* Pointers to these are stored in the tree. */
    char    *string;
    int     length;
};


char   string_space[STRSZ];  /* Space to store strings. */
struct node nodes[NODSZ];    /* Nodes to store. */
void  *root = NULL;          /* This points to the root. */


int main(int argc, char *argv[])
{
    char   *strptr = string_space;
    struct node    *nodeptr = nodes;
    void   *inserted;
    void   print_node(const void *, VISIT, int);
    int    i = 0, node_compare(const void *, const void *);


    while (gets(strptr) != NULL && i < NODSZ)  {
        /* Set node. */
        nodeptr->string = strptr;
        nodeptr->length = strlen(strptr);
        /* Put node into the tree. */
        inserted = tsearch((void *)nodeptr, (void **)&root,
            node_compare);
        if (*(struct node **)inserted != nodeptr)
            printf("duplicate key; new node not created\n");
        else {
            /* Adjust pointers, so we do not overwrite tree. */
            strptr += nodeptr->length + 1;
            nodeptr++;
            i++;
        }
    }
    twalk(root, print_node);
    /* Delete all nodes in the tree */
    while (root != NULL)
        tdelete(*(struct node **)root, &root, node_compare);
    return 0;
}


/*
 *  This routine compares two nodes, based on an
 *  alphabetical ordering of the string field.
 */
int
node_compare(const void *node1, const void *node2)
{
    return strcmp(((const struct node *) node1)->string,
        ((const struct node *) node2)->string);
}


/*
 *  This routine prints out a node, the second time
 *  twalk encounters it or if it is a leaf.
 */
void
print_node(const void *ptr, VISIT order, int level)
{
    const struct node *p = *(const struct node **) ptr;


    if (order == postorder || order == leaf)  {
        (void) printf("string = %s,  length = %d\n",
            p->string, p->length);
    }
}