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.