CSCI 2021 Function Pointers Tutorial

C programmers constantly make use of pointers to various kinds of data. It less common to make use of Function Pointers, variables that refer to a function but can be redirected to point at a different function instead. However, certain patterns of problem can be addressed elegantly through use of function pointers. This brief tutorial and accompanying code is designed to give an overview of using function pointers and illustrate a few spots where they are used in the C standard library.

While functions themselves are a stream of bytes that represent instructions to perform, the value associated with function names in C is usually the starting address of the function's instructions. This is demonstrated at the top of main() in the fp_basics.c where the following line appears:

printf("main:      %p\n", main);       // print the 'value' associated with main, its address

which will render the following output when the program is compiled and run

> ./fp_basics
main:      0x563402b0415a
...

This representation of the "whole" function as its starting address is similar to the approach that C takes with arrays where the bare name associated with arrays is its starting address, a pointer value.

Since the starting address of functions is the same size (32-bits or 64-bits) as other pointer kinds, C supports Function Pointers as a type of variable albeit with somewhat obtuse syntax. This appears a few lines down in fp_basics.c in main().

  int (*func_ptr)(int) = NULL;           // initialize function pointer to NULL
  //| | |         +-> 1 arg, an int
  //| | +->name of pointer variable 
  //| +-> is a pointer to a function
  //+-> return type of function pointed to

A new variable func_ptr is introduced which initially has value NULL. According to the type of the variable

• It is a pointer to a function
• The function pointed at takes 1 argument, an integer
• The function pointed at returns an integer

This type specification is required so that at the location where the function is invoked through the pointer, the compiler can still generate the correct assembly code to call the function

• The compiler can pass arguments in the correct locations (register edi in x86-64)
• The compiler will know where to find the return value (register eax in x86-64)

The initial value for the function pointer is NULL but this can be changed by assigning it to an appropriate function.

  func_ptr = increment;                  // point instead to increment()
  printf("increment: %p\n", increment);
  printf("func_ptr:  %p\n", func_ptr);

which gives the following output when run.

increment: 0x563402b04139
func_ptr:  0x563402b04139

Finally, calling the function through the pointer uses the same syntax as standard function invocation:

  int reti = func_ptr(3);                // call function via pointer
  printf("func_ptr(3) = %d\n", reti);

giving output

func_ptr(3) = 4

Unlike standard functions, function pointers can be re-assigned. The results that they produce when called are then associated with the new function to which they point. This is demonstrated in the latter half of fp_basics.c.

  func_ptr = triple;                     // change function pointer to triple()
  printf("triple:    %p\n", triple);
  printf("func_ptr:  %p\n", func_ptr);
  int rett = func_ptr(3);                // call function via pointer
  printf("func_ptr(3) = %d\n", rett);

which gives the following output when run.

triple:    0x563402b04148
func_ptr:  0x563402b04148
func_ptr(3) = 9

The C standard library provides a general purpose implementation of the Quick Sort algorithm. According the manual page, this function has a somewhat intimidating prototype:

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

The many void* types present are to allow qsort() to be called with any type of data. A standard call is much easier to understand and tends to look something like this:

qsort(array, array_len, element_size, compare_func);
// array:        address of array to sort
// array_len:    number elements in the array (length)
// element_size: size in bytes of elements in the array
// compare_func: pointer to a function that will compare 2 elements

The 4th argument appears odd in the prototype for qsort() because it is a function pointer. compare_func(a,b) is intended to compare to elements in the array and indicate their sorting order. It should return one of the following kinds of integers

• compare_func(a,b) < 0 : Negative return indicate a sorts before b
• compare_func(a,b) = 0 : Zero return indicates a and b are equal, their sorting order doesn't matter
• compare_func(a,b) > 0 : Zero return indicates a sorts after b

This is a common idea that sees use in many programming environments including Java's Comparable and Comparator interfaces, OCaml array sorting, and most other sensible programming environments excluding Python which inexplicably decided to make this useful functionality hard to access in modern versions.

qsort_demo.c demonstrates use of qsort() on several types of data. The code starts with several simple comparison functions.

// compare two ints pointed to
int intcmp(const int *xp, const int *yp) { 
  return *xp - *yp;
}

// compare two ints pointed to, reverse order
int rev_intcmp(const int *xp, const int *yp) { 
  return *yp - *xp;
}

These functions take int* as arguments which is mildly problematic due to qsort() requiring the comparison to take void* arguments. This is repaired by creating a "convenience" type to allow casting of the integer comparison functions.

// convenience type to enable casting of typed comparisong functions
// to the void-ish functions expected by qsort()
typedef int (*cmp_t) (const void *, const void *);

Once established, one can call qsort() with the different comparison functions to sort in differing orders.

    int int_arr[10] = {1, 6, 5, 2, 3, 9, 4, 7, 8, 0};             // array of scrambled integers

    qsort((void*) int_arr, 10, sizeof(int), (cmp_t) intcmp);      // sort in ascending order
    ... //                                   ||||| 
    ... //                                   caste
    ... //                                   ||||| 
    qsort((void*) int_arr, 10, sizeof(int), (cmp_t) rev_intcmp);  // sort in descending order

Some standard C functions follow the comparison function convention required by qsort() to make them compatible. strcmp(() is one such function meaning it can be used with qsort() to sort strings.

    char *str_arr[5] = {"banana", "orange", "peach", "apple", "grape"};
    qsort((void*) str_arr, 5, sizeof(char *), (cmp_t) strcmp); 

Some situations arise in which the same body of code is meant to be run many times but with different functions called in the midst of it. Function pointers can help to solve this in an ideal way as they allow a true "variable" for the function call.

The file sort_floats.c demonstrates this idea. The main body of the the code wants to show how an array of floating point values is sorted according to different comparison functions. Several of these are appear at the top of the code.

int intcmp(int *xp, int *yp){           // compare two integers
  return -(*xp < *yp) + (*xp > *yp);    // a bit of trickiness to do int comparisons and generate -1,0,+1
}

int intcmp_rev(int *xp, int *yp){       // reverse integer compare
  return -(-(*xp < *yp) + (*xp > *yp)); 
}

int floatcmp(float *xp, float *yp){     // compare two floating point values
  return -(*xp < *yp) + (*xp > *yp);    // a bit of trickiness to do int comparisons and generate -1,0,+1
}

int floatcmp_rev(float *xp, float *yp){ // reverse float compare
  return -(-(*xp < *yp) + (*xp > *yp)); 
}

To facilitate easy iteration over these functions, a "table" is created of them, an array of structs where the name and address of the functions are stored.

typedef struct {                        // type to hold combo of string name and function pointer
  char *name;                           // name of the comparison to use
  cmp_t func;                           // function to use, takes (void*) args, returns an int
} compare_func_t;

compare_func_t cfuncs[] = {                            // table of comparison functions
  {.name="intcmp"       , .func=(cmp_t) intcmp      }, // castes required to coerce
  {.name="intcmp_rev"   , .func=(cmp_t) intcmp_rev  }, // different types of functions
  {.name="floatcmp"     , .func=(cmp_t) floatcmp    }, // to unifying type of struct
  {.name="floatcmp_rev" , .func=(cmp_t) floatcmp_rev}, // field
  {.name=NULL}                                         // 'null' terminate the table
};

Each instance of a compare_func_t has a cf.name string field and cf.func comparison function field. Note the use of casting which forces both the integer and floating point comparison functions to match the void* type required for this struct field.

Finally, the main() function goes through a loop using each of the functions in the table as an argument to qsort().

  for(int i=0; cfuncs[i].name != NULL; i++){           // iterate over table of comparison functions
    ...
    printf("sorting using '%s'\n", cfuncs[i].name);    // print name of function

    qsort((void*) arr, 10, sizeof(float),              // same 3 args each iter to qsort()
          cfuncs[i].func);                             // last arg varies: use a different compare func
    ...
  }

This results in sorting in different orders via qsort() according to the function pointer passed in.

Like qsort(), the C standard library bsearch() provides standard implementation of binary search. It also makes use of comparison function pointers to handle arbitrary searching within a sorted array of data.

       void *bsearch(const void *key, const void *base,
                     size_t nmemb, size_t size,
                     int (*compar)(const void *, const void *));