/*
   Copyright David Anderson 2010-2014.
   This is free software.
   Permission hereby granted for anyone to copy or
   use this code for any purpose without restriction.
   Attribution may be given or may not, it is your choice.

   September 8, 2011: The tdelete example code was wrong in
   that it did not clean up entirely.  So was the tsearch
   example code.  Both are now fixed (it's surprisingly
   difficult to do this all correctly, but then the
   available documentation is at best a hint).

   The GNU/Linux tsearch man page (in the man-page 3.54
   edition) suggests that tdestroy() takes a pointer
   to a variable which points to the root.  In reality
   tdestroy() takes a pointer to the root.  As revealed
   by trying tdestroy() both ways.
   By man-pages release 5.5 the man page bug was fixed.
*/

/* tsearch()  tfind()  tdelete() twalk() tdestroy() example.
*/

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
/* __USE_GNU exposes the GNU tdestroy() function, a
   function that is not mentioned by the Single Unix
   Specification. */
#define __USE_GNU 1
#include <search.h>

/* The struct is trivially usable to implement a set or
   map (mapping an integer to a string).
   The following struct is the example basis
   because that is the capability I wanted to use.
   tsearch has no idea what data is involved, only the comparison function
   mt_compare_func() and the  free function mt_free_func()
   (passed in to tsearch calls) know what data is involved.
   Making tsearch very flexible indeed.

   Obviously the use of a struct is arbitrary, it is just
   an example.
*/

struct my_tentry {
    unsigned mt_key;
    /* When using this as a set of mt_key the mt_name
    field is set to 0 (NULL). */
    char * mt_name;
};

/* We allow a NULL name so this struct acts sort of like a set
   and sort of like a map.
*/
struct my_tentry *
make_my_tentry(unsigned k,char *name)
{
    struct my_tentry *mt =
        (struct my_tentry *)calloc(sizeof(struct my_tentry),1);
    if(!mt) {
        printf("calloc fail\n");
        exit(1);
    }
    mt->mt_key = k;
    if(name) {
        mt->mt_name = strdup(name);
    }
    return mt;
}
void
mt_free_func(void *mt_data)
{
    struct my_tentry *m = mt_data;
    if(!m) {
        return;
    }
    free(m->mt_name);
    free(mt_data);
    return;
}

int mt_compare_func(const void *l, const void *r)
{
    const struct my_tentry *ml = l;
    const struct my_tentry *mr = r;
    if(ml->mt_key < mr->mt_key) {
        return -1;
    }
    if(ml->mt_key > mr->mt_key) {
        return 1;
    }
    return 0;
}
void
walk_entry(const void *mt_data,VISIT x,int level)
{
    struct my_tentry *m = *(struct my_tentry **)mt_data;
    printf("<%d>Walk on node %s %u %s  \n",
        level,
        x == preorder?"preorder":
        x == postorder?"postorder":
        x == endorder?"endorder":
        x == leaf?"leaf":
        "unknown",
        m->mt_key,m->mt_name);
    return;
}


int main()
{
    unsigned i;
    void *tree1 = 0;
#define RECMAX 3

    for(i = 0 ; i < RECMAX ; ++i) {
        int k = 0;
        char kbuf[40];
        char dbuf[60];
        struct my_tentry *mt = 0;
        struct my_tentry *retval = 0;
        snprintf(kbuf,sizeof(kbuf),"%u",i);
        strcpy(dbuf," data for ");
        strcat(dbuf,kbuf);

        /*  Do it twice so we have test the case where
            tsearch adds and one
            where it finds an existing record. */
        for (k = 0; k < 2 ;++k) {
            mt = make_my_tentry(i,dbuf);
            errno = 0;
            /* tsearch adds an entry if its not present already. */
            retval = tsearch(mt,&tree1, mt_compare_func  );
            if(retval == 0) {
                /*  We cannot tell what sort of error this is */
                printf("Fail ENOMEM\n");
                exit(1);
            } else {
                /*  We must know if the allocated pointed
                    to space was saved in the tree or not. */
                struct my_tentry *re = 0;
                re = *(struct my_tentry **)retval;
                if(re != mt) {
                    /*  Space  NOT saved in the tree, 
                        it will leak unless we free it */
                    printf("found existing ok %u\n",i);
                    mt_free_func(mt);
                } else {
                    printf("insert ok %u\n",i);
                    /*  New entry mt was added, so
                        there is no leak possible. */
                }
            }
        }
    }
    for(i = 0 ; i < 5 ; ++i) {
        char kbuf[40];
        char dbuf[60];
        dbuf[0] = 0;
        struct my_tentry *mt = 0;
        struct my_tentry *retval = 0;

        snprintf(kbuf,sizeof(kbuf),"%u",i);
        mt = make_my_tentry(i,dbuf);
        retval = tfind(mt,&tree1,mt_compare_func);
        if(!retval) {
            /*  We cannot really tell if the lack of
                a value means 'not found' or 
                'internal error'. */
            /*  The test on i only relates to
                a limited size testcase here.
                Not to normal tfind use. */
            if(i < RECMAX) {
                printf("Fail TSRCH on %s is FAILURE\n",kbuf);
                exit(1);
            } else {
                printf("Fail TSRCH on %s is ok\n",kbuf);
            }
        } else {
            printf("found ok %u\n",i);
        }
        mt_free_func(mt);
    }
    twalk(tree1,walk_entry);
    {
        struct my_tentry *mt = 0;
        struct my_tentry *re3 = 0;
        void *r = 0;
        mt = make_my_tentry(1,0);
        r = tfind(mt,&tree1,mt_compare_func);
        if (r) {
            /*  This is what tdelete will delete.
                tdelete just removes the reference from
                the tree, it does not actually delete
                the memory for the entry itself.  */
            re3 = *(struct my_tentry **)r;
            r = tdelete(mt,&tree1,mt_compare_func);
            /* We don't want the 'test' node left around. */
            mt_free_func(mt);
            if(r) {
                struct my_tentry *re2 = 0;
                re2 = *(struct my_tentry **)r;
                printf("tdelete returned parent: %u %s\n",
                    re2->mt_key, re2->mt_name);
            } else {
                printf("tdelete returned NULL, tree now empty.\n");
            }
            /* Delete the content of the node that tdelete removed. */
            mt_free_func(re3);
        } else {
            /* There is no node like this to delete. */
            /* We don't want the 'test' node left around. */
            mt_free_func(mt);
        }
    }
    twalk(tree1,walk_entry);

    tdestroy(tree1,mt_free_func);
    tree1 = 0;
    printf("PASS tsearch test.\n");
    exit(0);
}