qsort and Function Pointers in C

Overview

If qsort(...) looks intimidating, the main reason is that it uses a function pointer .

For this assignment, you do not need a deep general theory of function pointers. You only need one practical idea:

• qsort(...) sorts an array
• you give it another function that knows how to compare two elements
• qsort(...) calls that comparison function whenever it needs to decide which element should come first

That comparison function is a callback .

What qsort needs

The standard-library function looks like this:

void qsort(void *base, size_t count, size_t size,
           int (*compare)(const void *, const void *));

For Stage 1, the important arguments are:

• base: where the array starts
• count: how many elements are in the array
• size: how big each element is
• compare: the function qsort(...) should call to compare two elements

So a typical call looks like:

qsort(unique, unique_count, sizeof unique[0], compare_tokens);

Read that as:

“Sort the unique array, which has unique_count elements, each of size sizeof unique[0], using compare_tokens to decide the order.”

The compare function

The comparison function must return:

• a negative value if the first element should come before the second
• 0 if they are equal
• a positive value if the first element should come after the second

The skeleton code stores tokens something like this:

char unique[MAX_TOKENS][MAX_TOKEN_LENGTH + 1];

and provides the following helper function for you to use.

#include <string.h>

static int compare_tokens(const void *a, const void *b) {
    return strcmp((const char *)a, (const char *)b);
}

The only unfamiliar part is the cast.

qsort(...) passes each element as const void *, which means “here is a pointer, but I am not telling you its real element type”. Your job is to cast it back to the right kind of pointer before using it.

Here, each array element is one whole string slot:

char [MAX_TOKEN_LENGTH + 1]

so the comparator casts each input back to “pointer to an array of MAX_TOKEN_LENGTH + 1 characters”, then uses strcmp(...) on the resulting strings.

If that syntax feels dense, focus on the practical reading:

• a points at one stored token
• b points at one stored token
• strcmp(*a, *b) decides which token comes first lexicographically