This is the README file for the "treedef.h" and "treedef.c" example
of generic programming using macros in standard C.  These source files,
when used correctly, let the client define instantiations of a "tree"
data type parametrized on the type of their 'data' fields.  The effect
is similar, although not directly analogous, to the C++ 'template'
construct.
  The client must provide the following parameters to the "treedef"
template.  The example shows how to do this in two cases -- "inttree"
and "strtree" -- in a structured way.  You don't have to follow this
pattern exactly, but it will probably work best.
  The macros are:

    #define TREE_NAME        foo

The name of the 'struct' which will hold a node of the tree.

    #define TREE_TYPE(v)     T v

The type parameter T, the type of the data stored in the tree.
This may be a complex type, such as '#define TREE_TYPE(v) int (*v)()'.
Notice the lack of a semicolon on this and all following macros.

    #define TREE_CMPR(x,y)   (strcmp(*(x), *(y)))

The comparison algorithm.  'x' and 'y' are pointers to objects
of type T stored in the tree.  This macro must evaluate to a
negative number, zero, or a positive number, as the value pointed
to by 'x' is less than, equal to, or greater than the value pointed
to by 'y', respectively.

  The following macros DO NOT need to be defined; they will be
replaced by the default actions shown, if left undefined.

    #define TREE_COPY(x,y)   (*x = *y)

The item-copying algorithm.  'x' and 'y' are pointers to objects
of type T.  This macro must assign the value of the object pointed
to by 'y', to the object pointed to by 'x'.  For example, if T is
an array type, 'TREE_COPY' might perform a 'memcpy'.  In the
"strtree" example, 'TREE_COPY' performs a deep copy by calling
'malloc'.
  Notice that if T is an array type, regardless of whether you
intend to use the 'foo_*cpy' functions, you must provide a binding
for this macro, because the default will produce a compilation
error.  It is perfectly fine to '#define TREE_COPY' to the empty
string, or to '(void)0'.

    #define TREE_KILL(x)

The item-destructor algorithm.  'x' is a pointer to an object of
type T stored in the tree.  This macro must do everything necessary
to clean up any memory associated with that object.  For example,
the "strtree" example defines 'TREE_KILL' to 'free(*x)'.

  All of the arguments to these macros may be assumed to be atomic
expressions, or wrapped in parentheses before the call to the macro;
and the arguments will not have side effects.  No argument may be
assumed to be an lvalue.  All arguments may be assumed to have the
correct types (e.g., an argument described as a pointer to T will
always be of type 'T *').


  The example source code hides the structure of 'struct foo' from
the client, and only provides access to it through the following
functions:

    struct foo *foo_insert ( struct foo **root, T data )

Inserts the object 'data' into the tree pointed to by 'root'; 'root'
is the address of a 'struct foo *' which represents the base of the
tree.  If a node 'n' already exists in the tree such that
'TREE_CMPR(&n->data, &data)' equals zero, then the old data will be
overwritten with the new data, after calling 'TREE_KILL' if necessary.
  The macro 'TREE_COPY' will be called, if it has been defined.
  This function returns a pointer to the newly added or modified node,
or 'NULL' on error.

    struct foo *foo_find ( struct foo *root, T data )

Finds and returns a pointer to the tree node 'n' such that
'TREE_CMPR(&n->data, &data)' equals zero.  Returns 'NULL' if no
such node exists in the tree.

    struct foo *foo_insertcpy ( struct foo **root, T *data )

Performs the same task as 'foo_insert', except that it receives
a pointer to the key object rather than a copy of it.  Returns
a pointer to the new node, as detailed in the comments on
'foo_insert'.

    struct foo *foo_findcpy ( struct foo *root, T *data )

Performs the same task as 'foo_find', except that it receives a
pointer to the key object rather than a copy of it.  Returns a
pointer into the tree, as detailed in the comments on 'foo_find'.

    size_t foo_count ( struct foo *root )

Returns the number of nodes in the tree, or zero if 'root' is
the null pointer.

    void foo_foreach ( struct foo *root, void (*prefix)(T *),
                       void (*infix)(T *), void (*postfix)(T *) )

Performs the three specified actions on every node in the tree,
in the appropriate order.  That is, first we perform 'prefix'
on the data in the root node; then we recursively call 'foo_foreach'
on the left subtree; then we perform 'infix' on the data in the
root; then we recurse down the right subtree; and finally we
perform 'postfix' on the data in the root.
  If any of 'prefix', 'infix', 'postfix' are 'NULL', then no
action is taken whenever that function should normally be called.
Thus, one might print the nodes of a tree in infix order by
invoking 'Ttree_foreach(myTtree, NULL, printT, NULL)' for some
appropriate function 'printT'.

    void foo_kill ( struct foo *root )

Calls TREE_KILL, if it has been defined, for every node in the
tree; simultaneously, deconstructs the tree itself, returning
the allocated nodes to the free store.  Disposes of the tree.