Some Pointers

The C programming language has a lot of neat features.  It simultaneously allows you to write programs at a fairly high level of abstraction and access the machine at the lowest level, just like assembly language.  The term "high level assembly language" has been used to describe it.  Programmers don't like it when the language gets in the way of what they are trying to do.  C rarely gets in the way of anything low-level, unlike most other high-level languages.  In fact, it rarely gets in the way of much of anything.  C allows you to do about anything you want.  Modern ANSI standard C has made it a bit more difficult, but safer, to do those things.  But the flavor is still there.  Being able to do anything you want will quickly get you into trouble.  ANSI C still allows it, but posts warning signs that you must acknowledge first.  Ignore them at your own risk.  This blog is about what happens when you ignore them without fully thinking that through.

Earlier this week I was asked to review some embedded interrupt code.  Code reviews are a mixed blessing: they are extremely useful and important, but you end up telling others how to do their job.  You can also pick up some new techniques by reviewing others' code, too, which is good.  Enough about code reviews.  Perhaps a later blog about them.  But this particular review prompted me to write this post.  

A "pointer" in a programming language is simply a variable that holds, instead of a useful value, an address of a piece of memory that (usually) holds the useful value.  You might need to think about that for a few seconds.  Pointers are one of the hardest things for many people to grasp.  A variable is normally associated with some value of some data type.  For instance in C:

int x;

declares a variable that will hold an integer. Simple enough.  Or this one, which declares an array of ten double values and puts those values into it:

double arr[10] = { 0.0, 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9};

By using the name of the variable, you get the value associated with it:

x = 5;

y = x;   // y now has the value 5 copied from x

But pointers are different.  A processor has a bunch of memory that can hold anything.  Think of the memory as an array of bytes.  That memory has no defined data type: it is up to the program to determine what value of what type goes where.  A pointer is an index of that array.  The pointer just "points into" the array of raw memory somewhere.  It is up to the programmer to decide what kind of value gets put into or taken out of that memory location.  This concept pretty much flies in the face of good programming as we have learned it over the last 50 years.  It breaks the abstraction our high level language is designed to give us in the interest of good, safe programming. Having a data type associated with a variable is important to good programming.  It gives the compiler the chance to check the data types used to make sure what you are doing makes sense.  If you have this code:

double d = 3.1415926538;

int i = d;

The compiler won't let you do that.  It knows you have a double value in d which cannot be assigned to an integer variable.  Allowing that would probably cause a nasty bug that would be difficult to find.

Pointers are extremely powerful and useful.  But they are very dangerous.  Almost every language has pointers in one form or another.  But most of the "improvements" over C have been to make pointers safer.  Java and C# claim to not have pointers and replace them with "references" which are really just a safer, more abstract form of pointers under the hood.  Even C has tried to make pointers safer.  The ANSI standard added some more type checking features to C that had been missing.  In C, you declare a pointer like this:

int *p_x;   // declare a pointer to an integer

The "*" means "pointer to."  The variable name, p_x, holds a pointer to an integer: just the address of where the integer is stored.  If you assign the variable to another, you get a copy of the address, not the value:

p_y = p_x;   // p_y now holds the same address of an integer, not an integer.

To get the value "pointed to" you have to "dereference" the pointer, but using the same "*" operator:

int x = *p_x;   // get the value pointed to by p_x into x

The p_x tells the compiler "here is an address of an integer" and the "*" tells it to get the integer stored there.  What we are doing is assigning a data type of "pointer to int" to the pointer.  The following code won't compile:

double *p_d;

int *p_i;  

p_i = p_d; // assign address of double to address of int: ERROR

The compiler sees that you are trying to assign the address of a double value to the pointer declared to point to an int.  That is an error.  It gives us a little safety net under our pointers.  There are plenty of circumstances this won't help, but it is a start.

However, C doesn't want to get in our way.  From the start, C allowed the programmer to do about anything.  ANSI C didn't change that much, but did make it necessary to tell the compiler "I know what I am doing here is dangerous, but do it anyway."  Sometimes we want to have a pointer to raw memory without having a data type attached to that memory.  In C we can do that.  ANSI C defined the "void" data type for just such things.  The void data type means, essentially, no data type, just raw memory:

void * p_v;  // declare a "void pointer" that points to raw memory

This can be quite handy, like a stick of dynamite.

You can assign any type of pointer to or from a void pointer, but the rules are a bit strange.  As dangerous as pointers are, void pointers are even more so.  Once a pointer is declared as void, the compiler has NO control over what it points to, and so can't check anything you do with that pointer!  If there were no restrictions on assigning void pointers we could do this:

double *p_d;     // declare a pointer to a double

*p_d = 3.1415;   // put 3.1415 into the memory pointed to by p_d

void *p_v;          // declare a pointer to void

p_v = p_d;        // assign address of double in p_d to address of void in p_v

int *p_i;            // declare p_i as a pointer to an integer

*p_i = *p_v;     // copy the value pointed to by p_v (a double!) to the integer pointed to by p_i

The compiler couldn't stop us and has no way of checking that the values make sense.  It will cheerfully copy the memory pointed to by p_d and p_v into the memory pointed to by p_i, which should be an integer.  Since floating point (double) values and integer values are stored in different formats, that will NOT be what we want!  We now have a nasty bug. Fortunately, the designers of C made it so the above won't compile.  The void pointer must be "cast" to a pointer of the appropriate type before the assignment can be made.  Tell the compiler "I know what I'm doing" if that is really what you want to do.

But we have only scratched the surface.  Pointers point to memory.  What all can be in memory?  Well, just about anything.  Where does the computer hold your code?  Yep, in memory!

Your code is held in memory, just like your data.  A pointer points to memory.  So a pointer can point to code.  Not all languages give you the opportunity to take advantage of that, but of course C does.
And, of course, it comes with a long list of dangers.  You can declare a "pointer to a function" that can then be "dereferenced" to call the function pointed to.  That is incredibly powerful!  You can now have a (pointer) variable that points to any function desired and call whatever function it is assigned.  One example, which is used in the C standard library, is a sorting function.  YOu can write the "world's best" sort function, but it normally will only sort one data type.  You will have to rewrite it for each and every data type you might want to sort.  But, the algorithm is the same for all data types.  The only difference is how to compare whether one value is greater than the other.  So, if you write the sort function to take a pointer to a function that compares the data type, returning an indication of whether one is greater than the other, you only have to write the comparison for each type.  Pass a pointer to that function when you call the sort function and you don't have to rewrite the sort function ever again!

It should be fairly obvious that the compare function will need to accept certain parameters so the function can call it properly.  The sort function might look something like this:

void worlds_best_sort(void *array_to_sort, COMPARE_FN *greater)

{

// some code

if ( greater (&array_to_sort[n], &array_to_sort[n+1]) ....

// some more code

}

Inside the sort function a call is made to the function passed in, "greater", to check if one value is greater than the other.  The "&" operator means "address of" and gives a pointer to the value on the right.  So the greater() function takes two pointers to the values it compares.  Perhaps it returns an int, a 1 if the first value is greater than the second, a 0 if not.  The pointer we pass must point to a function that takes these same parameters if we want it to actually work.  C lets us declare a pointer to a function and describes the function just like any other data type:

int (*compare_fn_p)(void *first, void *second);

That rather confusing line of code declares a pointer to a function named compare_fn_p.  The function pointed to will take two void pointers as parameters and return an int.  The parentheses around the *compare_fn_p tell the compiler we want a pointer to the function.  Without those parentheses the compiler would attach the "*" to the "int" and decide we were declaring a function (not a pointer to a function) that returned a pointer to an int.  Yes, it is very confusing.  It took me years to memorize that syntax.  To be even safer, C allows us to define a new type.  We can define all sorts of types and then declare variables of those new types.  That lets the compiler check our complex declarations for us and we don't have to memorize the often confusing declarations.  If we write this:

typedef int (*COMPARE_FN)( void *, void *);

we tell the compiler to define a type ("typedef") that is a pointer to a function that takes two void pointers as parameters and returns an int.  The name of the new type is COMPARE_FN.  Notice the typedef is just like the declaration above, except for the word "typedef" in front and the name of the new type is where the function pointer name was before.  The name, "COMPARE_FN," is what we used in the parameter list for the sort function above.  The sort function is expecting a pointer to a function that takes two void pointers and returns an int.  The compiler can check that any function pointer we pass points to the correct type of function, IF WE DECLARE THE FUNCTION PROPERLY!  If we write this function:

int compare_int( int * first, int *second);

and pass that to the function, it won't compile because the "function signature" doesn't match.

As you can see, these declarations get messy quick.  We could avoid a lot of these messy declarations by using void pointers: raw pointers to whatever.  DON'T!  ANY pointer, no matter what it points to, can be assigned to a void pointer.  It loses all type information when that is done.  We could declare our sort routine like this:

void worlds_best_sort(void *array_to_sorted, void *);

Now we can pass a pointer to ANY function, and indeed, any THING, as the parameter to the sort routine.  We wouldn't need to mess around with all those clumsy, confusing declarations of function pointer types.  But, the compiler can no longer help us out!  We could pass a pointer to printf() and the compiler would let us!  We could even pass a pointer to an int, which the program would try to run as a function!  But by declaring the type of function that can be used with a typdef declaration, we give the compiler the power to check on what we give it.  The same is true for other pointers, which can be just as disastrous.

I think the lesson here is that the C standard committee went to great lengths to graft some type checking onto a language that had very little, and still maintain compatability.  They also left the programmer with the power to circumvent the type checking when needed, but it is wise to do that only when absolutely necessary.  As I saw in the code review earlier this week, even profession programmers who have been doing it a long time get caught up with types and pointers.  If you aren't very familiar with pointers I urge you to learn about them: they are one of the most powerful aspects of C.  Whether you are new to pointers and/or programming or you have been at it for years, I even more strongly urge you to use the type checking given to us by the creators of C to make your pointers work right.  Pointers, by nature, are dangerous.  Let's make them as safe as we can.