[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. Basics

A function pointer, internally, is just the numerical address for the code for a function. When a function name is used by itself without parentheses, the value is a pointer to the function, just as the name of an array by itself is a pointer to its zeroth element. Function pointers can be stored in variables, structs, unions, and arrays and passed to and from functions just like any other pointer type. They can also be called: a variable of type function pointer can be used in place of a function name.

2. Function pointer declarations

A function pointer declaration looks like a function declaration, except that the function name is wrapped in parentheses and preceded by an asterisk. For example:

   1 /* a function taking two int arguments and returning an int */
   2 int function(int x, int y);
   3 
   4 /* a pointer to such a function */
   5 int (*pointer)(int x, int y);

As with function declarations, the names of the arguments can be omitted.

Here's a short program that uses function pointers:

   1 /* Functional "hello world" program */
   2 
   3 #include <stdio.h>
   4 
   5 int
   6 main(int argc, char **argv)
   7 {
   8     /* function for emitting text */
   9     int (*say)(const char *);
  10 
  11     say = puts;
  12 
  13     say("hello world");
  14 
  15     return 0;
  16 }

3. Applications

Function pointers are not used as much in C as in functional languages, but there are many common uses even in C code.

3.1. Callbacks

The classic example is qsort, from the standard library:

   1 /* defined in stdlib.h */
   2 void qsort(void *base, size_t n, size_t size,
   3     int (*cmp)(const void *key1, const void *key2));

This is a generic sorting routine that will sort any array in place. It needs to know (a) the base address of the array; (b) how many elements there are; (c) how big each element is; and (d) how to compare two elements. The only tricky part is supplying the comparison, which could involve arbitrarily-complex code. So we supply this code as a function with an interface similar to strcmp.

   1 static int
   2 compare_ints(void *key1, void *key2)
   3 {
   4     return *((int *) key1) - *((int *) key2);
   5 }
   6 
   7 int
   8 sort_int_array(int *a, int n)
   9 {
  10     qsort(a, n, sizeof(*a), compare_ints);
  11 }

Other examples might include things like registering an error handler for a library, instead of just having it call abort() or something equally catastrophic, or providing a cleanup function for freeing data passed into a data structure.

3.2. Dispatch tables

Alternative to gigantic if/else if or switch statements. See page 234 of KernighanPike for a good example of this.

3.3. Iterators

See C/Iterators.

4. Closures

A closure is a function plus some associated state. A simple way to implement closures in C is to use a static local variable, but then you only get one. Better is to allocate the state somewhere and pass it around with the function. For example, here's a simple functional implementation of infinite sequences, that generalizes the example in AbstractDataTypes:

   1 /* a sequence is an object that returns a new value each time it is called */
   2 struct sequence {
   3     int (*next)(void *data);
   4     void *data;
   5 };
   6 
   7 typedef struct sequence *Sequence;
   8 
   9 Sequence
  10 create_sequence(int (*next)(void *data), void *data)
  11 {
  12     Sequence s;
  13 
  14     s = malloc(sizeof(*s));
  15     assert(s);
  16 
  17     s->next = next;
  18     s->data = data;
  19 
  20     return s;
  21 }
  22 
  23 int
  24 sequence_next(Sequence s)
  25 {
  26     return s->next(s->data);
  27 }

And here are some examples of sequences:

   1 /* make a constant sequence that always returns x */
   2 static int
   3 constant_sequence_next(void *data)
   4 {
   5     return *((int *) data);
   6 }
   7 
   8 Sequence
   9 constant_sequence(int x)
  10 {
  11     int *data;
  12 
  13     data = malloc(sizeof(*data));
  14     if(data == 0) return 0;
  15 
  16     *data = x;
  17 
  18     return create_sequence(constant_sequence_next, data);
  19 }
  20 
  21 /* make a sequence x, x+a, x+2*a, x+3*a, ... */
  22 struct arithmetic_sequence_data {
  23     int cur;
  24     int step;
  25 };
  26 
  27 static int
  28 arithmetic_sequence_next(void *data)
  29 {
  30     struct arithmetic_sequence_data *d;
  31 
  32     d = data;
  33     d->cur += d->step;
  34 
  35     return d->cur;
  36 }
  37 
  38 Sequence
  39 arithmetic_sequence(int x, int a)
  40 {
  41     struct arithmetic_sequence_data *d;
  42 
  43     d = malloc(sizeof(*d));
  44     if(d == 0) return 0;
  45 
  46     d->cur = x - a;             /* back up so first value returned is x */
  47     d->step = a;
  48 
  49     return create_sequence(arithmetic_sequence_next, d);
  50 }
  51 
  52 /* Return the sum of two sequences */
  53 static int
  54 add_sequences_next(void *data)
  55 {
  56     Sequence *s;
  57 
  58     s = data;
  59     return sequence_next(s[0]) + sequence_next(s[1]);
  60 }
  61 
  62 Sequence
  63 add_sequences(Sequence s0, Sequence s1)
  64 {
  65     Sequence *s;
  66 
  67     s = malloc(2*sizeof(*s));
  68     if(s == 0) return 0;
  69 
  70     s[0] = s0;
  71     s[1] = s1;
  72 
  73     return create_sequence(add_sequences_next, s);
  74 }
  75 
  76 /* Return the sequence x, f(x), f(f(x)), ... */
  77 struct iterated_function_sequence_data {
  78     int x;
  79     int (*f)(int);
  80 }
  81 
  82 static int
  83 iterated_function_sequence_next(void *data)
  84 {
  85     struct iterated_function_sequence_data *d;
  86     int retval;
  87 
  88     d = data;
  89 
  90     retval = d->x;
  91     d->x = d->f(d->x);
  92 
  93     return retval;
  94 }
  95 
  96 Sequence
  97 iterated_function_sequence(int (*f)(int), int x0)
  98 {
  99     struct iterated_function_sequence_data *d;
 100 
 101     d = malloc(sizeof(*d));
 102     if(d == 0) return 0;
 103 
 104     d->x = x0;
 105     d->f = f;
 106 
 107     return create_sequence(iterated_function_sequence_next, d);
 108 }

Note that we haven't worried about how to free the data field inside a Sequence, and indeed it's not obvious that we can write a generic data-freeing routine since we don't know what structure it has. The solution is to add more function pointers to a Sequence, so that we can get the next value, get the sequence to destroy itself, etc. When we do so, we have gone beyond building a closure to building an object.

5. Objects

Here's an example of a hierarchy of counter objects. Each counter object has (at least) three operations: reset, next, and destroy. To call the next operation on counter c we include c and the first argument, e.g. c->next(c) (one could write a wrapper to enforce this).

The main trick is that we define a basic counter structure and then extend it to include additional data, using lots of pointer conversions to make everything work.

   1 /* use preprocessor to avoid rewriting these */
   2 #define COUNTER_FIELDS  \
   3     void (*reset)(struct counter *);    \
   4     int (*next)(struct counter *);      \
   5     void (*destroy)(struct counter *);
   6 
   7 struct counter {
   8     COUNTER_FIELDS
   9 };
  10 
  11 typedef struct counter *Counter;
  12 
  13 /* minimal counter--always returns zero */
  14 /* we don't even allocate this, just have one global one */
  15 static void noop(Counter c) { ; }
  16 static int return_zero(Counter c) { return 0; }
  17 static struct counter Zero_counter = { noop, return_zero, noop };
  18 
  19 Counter
  20 make_zero_counter(void)
  21 {
  22     return &Zero_counter;
  23 }
  24 
  25 /* a fancier counter that iterates a function sequence */
  26 /* this struct is not exported anywhere */
  27 struct ifs_counter {
  28 
  29     /* copied from struct counter declaration */
  30     COUNTER_FIELDS
  31 
  32     /* new fields */
  33     int init;
  34     int cur;
  35     int (*f)(int);      /* update rule */
  36 };
  37 
  38 static void
  39 ifs_reset(Counter c)
  40 {
  41     struct ifs_counter *ic;
  42 
  43     ic = (struct ifs_counter *) c;
  44 
  45     ic->cur = ic->init;
  46 }
  47 
  48 static void
  49 ifs_next(Counter c)
  50 {
  51     struct ifs_counter *ic;
  52     int ret;
  53 
  54     ic = (struct ifs_counter *) c;
  55 
  56     ret = ic->cur;
  57     ic->cur = ic->f(ic->cur);
  58 
  59     return ret;
  60 }
  61 
  62 Counter
  63 make_ifs_counter(int init, int (*f)(int))
  64 {
  65     struct ifs_counter *ic;
  66 
  67     ic = malloc(sizeof(*ic));
  68 
  69     ic->reset = ifs_reset;
  70     ic->next = ifs_next;
  71     ic->destroy = (void (*)(struct counter *)) free;
  72 
  73     ic->init = init;
  74     ic->cur = init;
  75     ic->f = f;
  76 
  77     /* it's always a Counter on the outside */
  78     return (Counter) ic;
  79 }

A typical use might be

   1 static int
   2 times2(int x)
   3 {
   4     return x*2;
   5 }
   6 
   7 void
   8 print_powers_of_2(void)
   9 {
  10     int i;
  11     Counter c;
  12 
  13     c = make_ifs_counter(1, times2);
  14 
  15     for(i = 0; i < 10; i++) {
  16         printf("%d\n", c->next(c));
  17     }
  18 
  19     c->reset(c);
  20 
  21     for(i = 0; i < 20; i++) {
  22         printf("%d\n", c->next(c));
  23     }
  24 
  25     c->destroy(c);
  26 }


CategoryProgrammingNotes


2014-06-17 11:57