24.2 What are Function Pointers Good For?

In this section we'll list several situations where function pointers can be useful.

A common problem is sorting, that is, rearranging a set of items into a desired sequence. It's especially common for the set of items to be contained in an array. Suppose you were writing a function to sort an array of strings. Roughly speaking, the algorithm for sorting the elements of an array looks like this:

for all pairs of elements in the array if the pair is out of order swap them

In C, the outline of the function might therefore look like this:

	stringsort(char *strings[], int nstrings)
	{
	for( all pairs of elements i, j in strings )
		{
		if(strcmp(strings[i], strings[j]) > 0)
			{
			char *tmp = strings[i];
			strings[i] = strings[j];
			strings[j] = tmp;
			}
		}
	}

Remember, the library function strcmp compares two strings and returns either a negative number, zero, or a positive number depending on whether the first string was ``less than,'' the same as, or ``greater than'' the second string. If you haven't seen it before, the series of three assignments involving the temporary variable tmp is a standard idiom for swapping two items. (The more obvious pair of assignments

	strings[i] = strings[j];
	strings[j] = strings[i];

would just about as obviously not work, because the first line would obliterate strings[i] before the second line had a chance to assign it to string[j].)

Naturally, a real sort function implementing a real sorting algorithm will be a bit more elaborate; in particular, the details of how we choose which pairs of elements to compare (and in what order) can make a huge difference in how efficiently the function completes its job. We'll show a complete example in a minute, but for now, our more important focus is on the comparison step. The final ordering of the strings will depend on the strcmp function's definition of what it means for one string to be ``less than'' or ``greater than'' another. How strcmp compares strings (as we saw in chapter 8) is to look at them a character at a time, based on their values in the machine's character set (which is how C always treats characters). In ASCII, the character set that most computers use, the codes representing the letters are in order, so strcmp gives you something pretty close to alphabetical order, with the significant difference that all the upper-case letters come before the lower-case letters. So a string-sorting function built around strcmp would sort the words ``Zeppelin,'' ``able,'' ``baker,'' and ``Charlie'' into the order

Charlie
Zeppelin
able
baker

strcmp is quite useless for sorting strings which consist entirely of digits, because it goes from left to right, stopping when it finds the first difference, without regard to whether it was comparing the ten's digit of one number to the hundred's of another. For example, a strcmp-based sort would sort the strings "1", "2", "3", "4", "12", "24", and "234" into the order

Depending on circumstances, we might want our string sorting function to sort into the order that strcmp uses, or into ``dictionary'' order (that is, with all the a's together, both upper-case and lower-case), or into numeric order. We could pass our stringsort function a flag or code telling it which comparison strategy to use, although that would mean that whenever we invented a new comparison strategy, we would have to define a new code or flag value and rewrite stringsort. But, if we observe that the final ordering depends entirely on the behavior of the comparison function, a neater implementation is if we write our stringsort function to accept a pointer to the function which we want it to use to compare each pair of strings. It will go through its usual routine of comparing and exchanging, but whenever it makes the comparisons, the actual function it calls will be the function pointed to by the function pointer we hand it. Making it sort in a different order, according to a different comparison strategy, will then not require rewriting stringsort at all, but instead will just involve passing it a pointer to a different comparison function (after perhaps writing that function).

Here is a complete implementation of stringsort, which also accepts a pointer to the string comparison function:

void stringsort(char *strings[], int nstrings, int (*cmpfunc)())
{
int i, j;
int didswap;

do	{
	didswap = 0;
	for(i = 0; i < nstrings - 1; i++)
		{
		j = i + 1;
		if((*cmpfunc)(strings[i], strings[j]) > 0)
			{
			char *tmp = strings[i];
			strings[i] = strings[j];
			strings[j] = tmp;
			didswap = 1;
			}
		}
	} while(didswap);
}

(This code uses a fairly simpleminded sorting algorithm. It repeatedly compares adjacent pairs of elements, keeping track of whether it had to exchange any. If it makes it all the way through the array without exchanging any, it's done; otherwise, it has at least made progress, and it goes back for another pass. This is not the world's best algorithm; in fact it's not far from the infamous ``bubble sort.'' Although our focus here is on function pointers, not sorting, in a minute we'll take time out and look at a simple improvement to this algorithm which does make it a decent one.)

Now, if we have an array of strings

	char *array1[] = {"Zeppelin", "able", "baker", "Charlie"};

we can sort it into strcmp order by calling

	stringsort(array1, 4, strcmp);

Notice that in this call, we are not calling strcmp immediately; we are generating a pointer to strcmp, and passing that pointer as the third argument in our call to stringsort.

If we wanted to sort these words in ``dictionary'' order, we could write a version of strcmp which ignores case when comparing letters:

#include <ctype.h>

int dictstrcmp(char *str1, char *str2)
{
while(1)
	{
	char c1 = *str1++;
	char c2 = *str2++;

	if(isupper(c1))
		c1 = tolower(c1);

	if(isupper(c2))
		c2 = tolower(c2);

	if(c1 != c2)
		return c1 - c2;
	if(c1 == '\0')
		return 0;
	}
}

(The functions isupper and tolower are both from the standard library and are declared in <ctype.h>. isupper returns ``true'' if its argument is an upper-case letter, and tolower converts its argument to a lower-case letter.)

With dictstrcmp in hand, we can sort our array a different way:

	stringsort(array1, 4, dictstrcmp);

(Some C libraries contain case-independent versions of strcmp called stricmp or strcasecmp. Both of these would do the same thing as our dictstrcmp, although neither of them is standard.)

We can also write another string-comparison function which treats the strings as numbers, and compares them numerically:

int numstrcmp(char *str1, char *str2)
{
int n1 = atoi(str1);
int n2 = atoi(str2);
if(n1 < n2)       return -1;
else if(n1 == n2) return 0;
else	          return 1;
}

Then, we can sort an array of numeric strings correctly:

	char *array2[] = {"1", "234", "12", "3", "4", "24", "2"};
	stringsort(array2, 7, numstrcmp);

(As an aside, you will occasionaly see code which is supposed to compare two integers and return a negative, zero, or positive result--i.e. just like the numstrcmp function above--but which does so by the seemingly simpler technique of just saying

	return n1 - n2;

It turns out that this trick has a serious drawback. Suppose that n1 is 32000, and n2 is -32000. Then n1 - n2 is 64000, which is not guaranteed to fit in an int, and will overflow on some machines, producing an incorrect result. So the explicit comparison code such as numcmp used is considerably safer.)

Finally, since we've started looking at sorting functions, let's look at a simple improvement to the string sorting function we've just been using. It has been plodding along comparing adjacent elements, so when an element is far out of place, it takes many passes to percolate it to the correct position (one cell at a time). The improvement, based on the work of Donald L. Shell, is to compare pairs of more widely-separated elements at first, then proceed to compare more and more closely-situated elements, until on the last pass (or passes) we compare adjacent elements, as before. Since the earlier passes will have done more of the work (and more quickly), the later passes will just have to do the ``final cleanup.'' Here is the improvement:

void stringsort(char *strings[], int nstrings, int (*cmpfunc)())
{
int i, j, gap;
int didswap;

for(gap = nstrings / 2; gap > 0; gap /= 2)
	{
	do	{
		didswap = 0;
		for(i = 0; i < nstrings - gap; i++)
			{
			j = i + gap;
			if((*cmpfunc)(strings[i], strings[j]) > 0)
				{
				char *tmp = strings[i];
				strings[i] = strings[j];
				strings[j] = tmp;
				didswap = 1;
				}
			}
		} while(didswap);
	}
}

The inner loops are the same as before, except that where we had before always been computing j = i + 1, now we compute j = i + gap, where gap is a new variable (controlled by a third, outer loop) which starts out large (nstrings / 2), and then diminishes until it's 1. Although this code contains three nested loops instead of two, it will end up making far fewer trips through the inner loop, and so will execute faster.

The Standard C library contains a general-purpose sort function, qsort (declared in <stdlib.h>), which can sort any type of data (not just strings). It's a bit trickier to use (due to this generality), and you almost always have to write an auxiliary comparison function. For example, due to the generic way in which qsort calls your comparison function, you can't use strcmp directly even when you're sorting strings and would be satisfied with strcmp's ordering. Here is an auxiliary comparison function and the corresponding call to qsort which would behave like our earlier call to stringsort(array1, 4, strcmp):

/* compare strings via pointers */
int pstrcmp(const void *p1, const void *p2)
{
	return strcmp(*(char * const *)p1, *(char * const *)p2);
}

...

	qsort(array1, 4, sizeof(char *), pstrcmp);

When you call qsort, it calls your comparison function with pointers to the elements of your array. Since array1 is an array of pointers, the comparison function ends up receiving pointers to pointers. But qsort doesn't know that the array is an array of pointers; it's written so that it can sort arrays of anything. (That's why qsort's third argument is the size of the array element.) Since qsort doesn't know what the type of the elements being sorted is, it uses void pointers to those elements when it calls the comparison function. (The use of void pointers here recalls their use with malloc, where the situation is similar: malloc returns pointers to void because it doesn't know what type we'll use the pointers to point to.) In the ``wrapper'' function pstrcmp, we use the explicit cast (char * const *)to convert the void pointers which the function receives into pointers to (pointers to char) so that when we use one * operator to find out what they point to, we get one of the character pointers (char *) which we know our array1 array actually contains. We pass the resulting two char *'s to strcmp to do most of the work, but we have to do a bit of work first to recover the correct pointers. (The extra const in the cast (char * const *)keeps the compiler from complaining, since the pointers being passed in to the comparison function are actually const void *, meaning that although it may not be clear what they point to, it's guaranteed that we won't be using them to modify whatever it is they point to. We need to keep a level of const-ness in the converted pointers so that the compiler doesn't worry that we're going to accidentally use the converted pointers to modify what we shouldn't.)

That was a rather elaborate first example of what function pointers can be used for! Let's move on to some others.

Suppose you wanted a program to plot equations. You would give it a range of x and y values (perhaps -10 to 10 along each axis), and ask it to plot y = f(x) over that range (e.g. for -10 <= x <= 10). How would you tell it what function to plot? By a function pointer, of course! The plot function could then step its x variable over the range you specified, calling the function pointed to by your pointer each time it needed to compute y. You might call

	plot(-10, 10, -10, 10, sin)

to plot a sine wave, and

	plot(-10, 10, -10, 10, sqrt)

to plot the square root function.

(If you were to try to write this plot function, your first question would be how to draw lines or otherwise do graphics in C at all, and unfortunately this is one of the questions which the C language doesn't answer. There are potentially different ways of doing graphics, with different system functions to call, for every different kind of computer, operating system, and graphics device.)

One of the simplest (and allegedly least user-friendly) styles of user interfaces is the command line interface, or CLI. The user types a command, hits the RETURN key, and the system interprets the command. Often, the first ``word'' on the line is the command name, and any remaining words are ``arguments'' or ``option flags.'' The various shells under Unix, COMMAND.COM under MS-DOS, and the adventure game we've been writing are all examples of CLI's. If you sit down to write some code implementing a CLI, it's simple enough to read a line of text typed by the user, and simple enough to break it up into words. But how do you map the first word on the line to the code which implements that command? A straightforward, rather simpleminded way is to use a giant if/else chain:

	if(strcmp(command, "agitate") == 0)
		{ code for ``agitate'' command }
	else if(strcmp(command, "blend") == 0)
		{ code for ``blend'' command }
	else if(strcmp(command, "churn") == 0)
		{ code for ``churn'' command }
	...
	else	fprintf(stderr, "command not found\n");

This works, but can become unwieldy. Another technique is to write several separate functions, each implementing one command, and then to build a table (typically an array of structures) associating the command name as typed by the user with the function implementing that command. In the table, the command name is a string and the function is represented by a function pointer. With this table in hand, processing the user's command becomes a relatively simple matter of searching the table for the matching command string and then calling the corresponding pointed-to function. (We'll see an example of this technique in this week's assignment.)

Our last example concerns larger, more elaborate systems which manipulate many types of data. (Here, by ``types of data,'' I am referring to data structures used by the program, presumably implemented as structs, but in any case more elaborate than C's basic data types.) It is often the case that similar operations must be performed on dissimilar data types. The conventional way of implementing such operations is to have the code for each operation look at the data type it's operating on and adjust its behavior accordingly; in the worst case, each piece of code (for each operation) will have a long switch statement or if/else chain switching among n separate, different ways of performing the operation on n different data types. If a new data type is ever added, new cases must be added to all segments of the code implementing all of the operations.

Another way of organizing such code is to place one or more function pointers right there in the data structures describing each data type. These pointers point to functions which are streamlined and optimized for performing the operations on just one data type. (Each piece of data would obviously have its pointer(s) set to point to the function(s) for its own data type.) This idea is one of the cornerstones of Object-Oriented Programming. We could use a version of it in our adventure game, too: rather than writing new, global pieces of code implementing each new command verb we want to let the user type, and then making each of those pieces of code check all sorts of attributes to ensure that the command can't be used on inappropriate objects (``break water with cup'', ``light candle with bucket,'' etc.) we could attach special-purpose pieces of code to the individual objects themselves (via function pointers, of course) and arrange that the code would only fire up if the player were trying to use the relevant object.

Read sequentially: prev next up top