Puzzle 4

This is a long one. If you want to ease yourself into it, go and read the other ones for today which are much shorter and then come back to this one. Seriously - it’s a doozy. Pointers, one of the toughest part of C, is what we’ll be tackling today.

Basic Pointers

So you’ve had the past week to wrestle with pointers on your own, and no doubt you’ve all become something of self-made experts on the subject. So let’s have a rather simple warm-up puzzle. So what’s the output of this file?

#include <stdio.h>

int main() {
    int a = 5, b = 15;
    int *p1, *p2;

    p1 = &a;
    p2 = &b;
    *p1 = 10;
    *p2 = *p1;
    p1 = p2;
    *p1 = 20;

    printf("a: %d ", a);
    printf("b: %d\n", b);
    printf("p1: %p p2: %p\n", p1, p2);

    return 0;
}

Did you get it?

a: 10 b: 20
p1: 0x7fff58bbd754 p2: 0x7fff58bbd754

Of course, the particular pointer locations are irrelevant except in that p1 and p2 should be the same value; since the operating system is what allocates memory, these values should most likely be different each time you run the program. But in case you didn’t quite get the right answer, let’s break it down.

What’s a pointer? A pointer is just a variable that represents a location in memory. So after initializing a and b to 5 and 15 respectively, we create two addresses p1 and p2. How do we assign the two pointers to the addresses in which a and b are stored? We create a reference with the & operator. The error most novices make is that the reference operator can never be on the left side of the assignment operator. This makes logical sense - you can’t change the address in which something is stored. All you can do is instead copy the same information held at that address to a new location, and then later free whatever was held in the original location. Okay, so far so good.

The * operator is known as dereferencing a pointer. It means we’re accessing not the address represented by the pointer, but the value in memory represented by that address. Unlike the reference operator, the dereference operator can be present on either side of the assignment operator. So *p1 accesses the value that a stores; in this case, we’re functionally resetting a to be 10, and similarly we set b to the same value.

Here is the part that may have confused some of you. We set p1 to point to the same address to which p2 points, so they are both manipulating the area of memory in which b is stored. Then, we set that value to be 20, thus altering b. And that’s it!

So now that we’ve had this quick three-minute review of pointers, we’re ready for some better puzzles.

Pointer Disambiguation

This puzzle tests disambiguation of pointers. Fundamentally, we’re going to explore an array of type versus pointer to type. Here’s pointer_test.c. What’s the output?

#include <stdio.h>

int main(int argc, const char *argv[])
{
    int a[5] = { 1, 2, 3, 4, 5 };
    int *ptr = (int *)(&a + 1);

    printf("%d %d\n", *(a + 1), *(ptr - 1));

    return 0;
}

You may remember from the lecture that the variable that represents an array is actually a pointer referencing the zero-eth element in that array. So in this example, a is actually a pointer referencing a[0] - in this case, 1. By that logic, a + 1 merely references the next integer - a[1]; thus, the first integer printed is 2. That’s the easy part.

The next one is a little tougher. If you treated *ptr as a simple pointer to an integer – like you treated a – you’d be tempted to give the following incorrect explanation:

Since ptr points to the location of a, a + 1 merely points to the location of a[1]; thus, ptr - 1 goes back to referencing a[0]. So the second number printed must be 1.

Nope! The trick here is that ptr is not a pointer to an integer. It is a pointer to an array – which is entirely different. Pointer arithmetic on these two variables works entirely differently. A pointer to an integer, when incremented, will simply move up in memory by the number of bytes an integer represents. A pointer to an array, however, will move up in memory by the length of the array when incremented. Thus, when incremented, it moves up by five elements - to the slot in memory right after 5 in the array a. When decremented, however, printf is treating the output as a pointer to an integer, and not a pointer to an array. So when we subtract 1 inside the printf statement, ptr references a[4] instead of a[5], and dereferencing that gives us 5.

So the output is 2 5. Phew!

This puzzle is testing a concept known as pointer disambiguation, where the same pointer can be treated differently depending on the context. Let’s warm up our disambiguation skills with a little puzzle: What are the differences between the following three declarations.

int* arr1[8];
int (*arr2)[8];
int *(arr3[8]);

The first is an array of integer pointers - specifically, an array of length eight. The second is a pointer to an array of integers. And the third is the same as the first! So how the heck do we start evaluating these things? The difference here is critical. Operator precedence can be a rather esoteric subject – especially when function pointers get involved, as you’ll see next time – but there are a couple simple rules that can help you learn rather quickly how this works.

As the C Bible (K&R, as you all should know well by now) suggests using cdecl for any very complicated situations. It is wonderful, and you should definitely consider it.

Order of Operations

Order of operations seems fairly obvious, and in general we encounter fairly trivial examples. But what about when you get something like the following:

char *(*(**foo[][8])())[];

Let’s go through some examples.

long **foo[7];

As we go through the example, I’ll strikeout whatever we’ve delt with. We start with the variable, and end with the type. foo is ... long. Okay, simple enough. Now let’s fill in the middle.

long **foo[7];

“Array of” has the highest precedence, so we can and must go right. This gives us the sentence foo is array of 7 long.

long **foo[7]

Now, we’ve gone as far to the right as possible. This means we have no choice but to go left. foo is array of 7 pointer to long takes care of the first “pointer to”, but we have on last pointer. Here is the final result: foo is array of 7 pointer to pointer to long.

Think you’ve got the hang of it? Let’s try some really hairy examples to really get it down.

char * ( * ( * *foo [][8])())[];

We start as usual, with the variable and the simple type: foo is ... char. Sweet, let’s see what we have left.

char * ( * ( * *foo [][8])())[]

Since foo touches both “pointer to” and “array of”, we go right as much as we can. This gives us:

foo is array of array of 8 ... char

char * ( * ( * *foo [][8])())[]

Okay, now we have no choice but to go left. It has two “pointer to” phrases to add:

foo is array of array of 8 pointer to pointer to ... char

Leaving this:

char * ( * ( * *foo [][8])())[]

What do we do now!? There seems to be an empty set of parentheses? It must be a function call! This involves pointers to functions. Remember, we try and go right when we can. On the right is a function call, and on the left is a “pointer to”. Remember our rule – “function returning” has higher precedence. So here is our new sentence:

foo is array of array of 8 pointer to pointer to function returning ... char

This leaves us with the following:

char * ( * ( * *foo [][8]) () )[]

We would like to go right, but we have a set of parentheses that block our way. As you know, parens have a much higher precedence than anything else, so we must oblige and go left. This gives us the following:

foo is array of array of 8 pointer to pointer to function returning pointer to ... char

Which gives us this left over:

char * ( * ( * * foo [][8])() ) []

So all that’s left is an “array of” and a “pointer to”; as you well know, we can go right and then left, finishing off our sentence. That gives us the final result – the following mouthful:

foo is array of array of 8 pointer to pointer to function returning pointer to array of pointer to char

Wow!

Function Pointers

Thought we were done? We’re just getting started. What we say in the more complicated example there was a function pointer – a pointer to a function. These nasty beasts are unique to C; in higher languages like C++, you should use polymorphism and virtual functions; thus, function pointers have been exclusive to C. Lucky you.

Why do we have pointers to functions? There are lots of cases where it’s more useful to design a function to be general purpose; this way, the function you’re writing can accept any function as a parameter and simply call that function. The most common example is sorting. Your sort function can take a compare function as a parameter – this way, you can write seven small compare functions and just a single sorting function, rather than seven long sorting functions. This follows good coding design of factoring out code as well.

Let’s start with a simple example.

void (*foo)(int);

Here, foo is a pointer to a function that takes a single argument, an int, and returns void. The tip to make it easier is that you’re just writing out the function declaration but surrounding the function name by a set of parens. So foo would be declared like this:

void foo(int a);

Pretty simple! What about this?

void *(*foo)(int *);

Again, re-writing the function header helps.

void *foo (int * a);

One interesting thing about function pointers is that the reference operator (&) becomes optional, as does the dereference (*). Because why not. Pointers were too simple anyways.

void foo(int a) { return a; }

int main() {
    void (*func)(int);
    func = foo;
    func = &foo;
    
    func(5);
    (*func)(5);
    
    return 0;
}

Both ways of assigning func are legal, and both ways of calling func are also legal. Here are some guidelines to keep in mind when talking about pointers and specifically function pointers:

    void *foo;    // legal
    void foo();   // legal
    void foo;     // not legal
    void foo[];   // not legal
    char foo[1][2][3][4][5]  // legal
    char foo[]                    // legal
    char foo[][5]                // legal
    char foo[5][]                // not legal

But with function pointers, come abstract declarators. These wonderful little creatures are used in two places: casts, and arguments for sizeof. They look something like this:

int ( * ( * ) ( ) ) ( )

This is another wonderful moment of sublime

.

It seems unfair, certainly. I told you to always start at the variable name, which led to the logical conclusion of giving you an example without a variable name. Put away your inhaler and calm down. There are four rules that govern where a variable can be:

There’s actually only two places in the given example that a variable can be using those syntax rules.

int ( * ( * x ) x ( ) ) ( )

The two x’s represent the two possible locations of a variable. A quick look back at the fourth rule above tells us that there’s only one location, so we can read the abstract declarator as the following:

int (*(*foo)())()

which translates to:

foo is a pointer to function returning pointer to function returning int

So, after all this advice, when you’re reading some truly advanced C code, you won’t freak out when you see this:

BOOL (__stdcall *foo)(...); 

You’ll think - hey! This is simple – foo is a pointer to a __stdcall function returning BOOL . Piece of cake. I highly recommend you read this guide - it’s wonderful.

Multi-Dimensional Pointer Arithmetic

Multidimensional pointers aren’t too difficult. Let’s have a three dimensional array buffer, where each of the dimensions are 10. We could directly index into it:

char buffer[3][4][5];

Or we could use pointers

*( *( *( buffer + 3) + 4) + 5);

Here, buffer is a triple pointer; adding 3 moves it over to the third triple pointer. Dereferencing that gives us a double pointer, and adding four to that gives us the fourth double pointer. Dereferencing that gives us just a regular pointer, and adding five gives us the fifth pointer. Finally, one last dereference gives us just a regular char.

That’s pretty much it! Here’s one puzzle just to make sure you really understood the concept.

int main() {
    char arr[5][7][6];
    char (*p)[5][7][6] = &arr;

    printf("%d\n", (&arr + 1) - &arr);
    printf("%d\n", (char *)(&arr + 1) - (char *)&arr);
    printf("%d\n", (unsigned)(arr + 1) - (unsigned)arr);
    printf("%d\n", (unsigned)(p + 1) - (unsigned)p);

    return 0;
}

The output should be

1
210
42
210

Const Correctness

Why does this program give an error?

#include <stdio.h>
void foo(const char **p) { }
int main(int argc, char **argv) {
    foo(argv);
    return 0;
}

This program uses a const pointer. This simply means that while the pointer itself can be changed, the memory it touches cannot change in value. In other words, it’s not the pointer that’s a const, but rather what it points to. This is why the const appears before the *. If you put the const after the * (like int * const p_int = &x;) then you get a regular old pointer to an int, but this time the value of p_int cannot change. Thus, it’s the pointer that’s a const.

Here is a hint to the for the code example above.

char const        c = 'a';
char*             p = 0;
char const**      pp = &p; // not allowed in C
 
*pp = &c; // p now points to c.
*p = 'b'; // changing a const value!

The first code snippet would work perfectly fine, without any warning, if p were a single pointer instead of a double pointer. So why does this break with double pointers? This is known as const correctness in C. Although it is possible to cast from char * to const char * without warning, C will prohibit char ** to const char ** casting.

So why would this be prohibited? Imagine p is a char * – if so, logically, it could be used to modify whatever it’s pointing at. Imagine you have another pointer, pp that points to p. You could use pp to assign to p the address of a const char - you could even use p to modify the const char, which might even be in read-only memory!

So why use const? One misconception is that this can be utilized to make further optimizations. However, this is rarely the case. Usually, this is generally for conceptual clarity and readability.

Here is some further explanations of this issue in C. Oh, of course Alex Alain has another great tutorial.

Closing Thoughts

Here are some awesome resources about pointer arithmetic and an awesome video series by Stanford University.