Generic data structures and algorithms

The idea is simple. If you have some code, you can customize it a little by preprocessor macros. You can change constants, data types it operates on, whole expressions, or you can compile parts of the code conditionally. You can generate new function names using macros.

So if you provide few macros for data types, function names and parameters and include some code using them, it gets modified by it and a code for a specific data type is created. Then you can provide new macros and include it again, to get another version of the code, with different function names and types.

The use is best explained with an example, so we will suppose there is a header file array.h, which contains a generic array data type and an indexing function, which returns a pointer to n’th element.

To get an array of integers, we need to provide macro for used data type and macro that will provide prefixes for identifier names. Then we include the file. Then we could get another array with unsigned integers, so we will do the same:

This will generate the data types (presumably intarray_t and uintarray_t) and the index functions (intarray_index and uintarray_index). We can use them like anything else.

Maybe the ARRAY_PREFIX deserves some attention. When the header file wants to generate an identifier, it uses this macro with some name. Then the macro takes the name, adds a prefix to it and returns the new identifier, so ARRAY_PREFIX(t) will generate intarray_t in the first case and uintarray_t in the second. This allows having more than one instance of the same data structure or algorithm, because it generates different identifiers for them.

A similar macro is needed for every generic header in libUCW.

For those who want to write their own or are just interested, how it works, here is the array.h header and some description to it.

There are few things that are worth noticing. The first two lines define the data type. The macro (ARRAY_A_TYPE) is only for convenience inside the header, since such type names can be used quite often inside the header (if it is large).

Then there is the function with its name generated (do not get scared by the double parenthesis, ones will be eaten by the macro, the second ones are real function parameters). The function is static, since more than one .c file might want to use the same header with the same prefix — each one generates it’s own instance.

And the end just undefines all the macros, so user may define them again and get another instance of the data structure.

Also note it is not protected against multiple inclusion in the usual way (eg. #ifndef ARRAY_H …), since multiple inclusion is desired — it generates multiple versions of the data structure.