Being Generic In C

One of the strengths of C++ is its support for Generic Programming using templates. The idea is that you can apply a general algorithm to a chunk of data, regardless of the specifics of the operation you want to apply to the data and even without regard to the type of data itself. This has the advantages of giving the programmer less code to write, debug and, most importantly, makes the code's intent clearer.

However, what a lot of programmers don't appreciate is that you can use a similar style of programming in C. In fact, a couple of the C runtime library functions, qsort and bsearch already use this style - the functions are general algorithms that can apply to arbitrary data using a user specified comparison method. There are some tradeoffs I'll discuss later which still makes C++ a better platform for generic programming, but if you're stuck without an ANSI standard C++ compiler you can simplify your C code a lot using these techniques.

Implementing for_each in C

As an example of how to write generic algorithms in C, let's have a go at writing a function to implement something like the C++ standard library for_each algorithm. For more information on the for_each algorithm have a look in "The C++ programming language" by Bjarne Stroustrup, 3rd edition. At its most simplistic level, for_each is the application of an operation to each element of a collection of data.

If we look at concrete examples of algorithms being applied to collections of data, we should be able to work out the common thing that makes a for_each algorithm. As for_each is relatively simple, a couple of examples should be enough. Incidentally, you can apply the same technique to writing new algorithms in C++ - write a concrete implementation of a function and then parameterise the types of the algorithms arguments.

void display_int_array( const int *start, const int *const end )
{
	while( start < end ) printf( "%d\n", *start++ );
}

struct string_node
{
struct string_node *next;
	const char *text;
};

void write_to_file( struct string_node *start, struct string_node *end, FILE *write_to )
{
	for( ; start != end ; start = start->next ) fputs( write_to, start->text );
}

If you compare these examples, you can see there's a current value (*start or start->text), an operation to perform on this value (printf or fputs) , a way of getting the next value (start ++ or start->next) and a termination condition (start == end in both cases). This suggests that we could write for_each along the lines of:

void for_each( void *start,
	void *end,
	void *(*next)( void *),
	void (*operation)( void * ) )
{
	for( ; start != end; start = next(start) ) operation( start );
}

With this function, we could display an array of integers (Example 1 revisited) by defining two functions to be used as parameters in the for_each function call:

void *next_int( void *p )
{
	return (int *)p + 1;
}

void display_int( void *p )
{
	printf( "%d\n", *(int *)p );
}

Then, elsewhere in the code we can use the

int int_array[500];

/* Code to set up the array */

for_each( int_array, int_array + sizeof int_array, next_int, display_int );

The implementation of the linked list string write is something for anyone interested to try!

Drawbacks of Generic Programming in C

As you can see from the implementation of for_each, using generic programming in C is not without a cost. The update for the loop has changed to a function call and we have an extra level of function calling to do to perform the operation. It's fairly likely that the generic code will be bigger, slower and take more stack space. We would be unlikely to suffer so much in C++ as most templates expand inline and / or use partial template specialisation to reduce their footprint and increase the efficiency.

As well as the run time cost, there is a potential compile time cost. Unlike the C++ version there is no parameter type checking - as start and end are void pointers they defeat any type checking we might want done. When using this method, you have to be vigilant that some of the extra casting you have to do doesn't compromise the intent of your code.

However, given these restrictions, using generic programming with C can be a real benefit. Windows programmers might like to consider how they could simplify the "switch statements from hell" that crop up in most Windows C programs.

Last modified 24-02-02 by Ashley