Related Books
Books / Introduction to C Programming Language / Chapter 14
Pointers
Pointers provided an abstraction for memory addresses. A pointer value specifies a location, but also has a type associated with it at compile time that allows the compiler to keep track of what is stored at that memory address. C uses pointers for a variety of tasks that are handled more abstractly in other programming languages, like returning extra values from functions or constructing arrays.
Memory and addresses
Memory in a typical modern computer is divided into two classes: a small number of registers, which live on the CPU chip and perform specialized functions like keeping track of the location of the next machine code instruction to execute or the current stack frame, and main memory, which (mostly) lives outside the CPU chip and which stores the code and data of a running program. When the CPU wants to fetch a value from a particular location in main memory, it must supply an address: a 32-bit or 64-bit unsigned integer on typical current architectures, referring to one of up to 232 or 264 distinct 8-bit locations in the memory. These integers can be manipulated like any other integer; in C, they appear as pointers, a family of types that can be passed as arguments, stored in variables, returned from functions, etc.
Pointer variables
A pointer variable is a variable that holds a pointer, just like an int variable is a variable that holds an int.
Declaring a pointer variable
The convention is C is that the declaration of a complex type looks like its use. To declare a pointer-valued variable, write a declaration for the thing that it points to, but include a * before the variable name:
int *pointerToInt;
double *pointerToDouble;
char *pointerToChar;
char **pointerToPointerToChar;
These declarations create four pointer variables, named pointerToInt, pointerToDouble, pointerToChar, and pointerToPointerToChar. On a typical 64-bit machine, each will be allocated 8 bytes, enough to represent an address in memory.
The contents of these variables are initially arbitrary. To use them safely, you will need to compute the address of something and assign it to the variable.
Assigning to pointer variables
Declaring a pointer-valued variable allocates space to hold the pointer but not to hold anything it points to. Like any other variable in C, a pointer-valued variable will initially contain garbage—in this case, the address of a location that might or might not contain something important. To initialize a pointer variable, you have to assign to it the address of something that already exists. Typically this is done using the & (address-of) operator:
int n; /* an int variable */
int *p; /* a pointer to an int */
p = &n; /* p now points to n */
Using a pointer
Pointer variables can be used in two ways. The simplest way is to get their value as with any other variable. This value will be an address, which can be stored in another pointer variable of the same type.
int n; /* an int variable */
int *p; /* a pointer to an int */
int *q; /* another pointer to an int */
p = &n; /* p now points to n */
q = p; /* q now points to n as well */
But more often you will want to work on the value stored at the location pointed to. You can do this by using the * (dereference) operator, which acts as an inverse of the address-of operator:
int n; /* an int variable */
int *p; /* a pointer to an int */
p = &n; /* p now points to n */
*p = 2; /* sets n to 2 */
*p = *p + *p; /* sets n to 4 */
The * operator binds very tightly, so you can usually use *p anywhere you could use the variable it points to without worrying about parentheses. However, a few operators, such as the -- and ++ operators and the . operator used to unpack structs, bind tighter. These require parentheses if you want the * to take precedence.
(*p)++; /* increment the value pointed to by p */
*p++; /* WARNING: increments p itself */
Printing pointers
You can print a pointer value using printf with the %p format specifier. To do so, you should convert the pointer to the generic pointer type void * first using a cast, although on machines that don’t have different representations for different pointer types, this may not be necessary.
Here is a short program that prints out some pointer values:
#include <stdio.h>
#include <stdlib.h>
int G = 0; /* a global variable, stored in BSS segment */
int
main(int argc, char **argv)
{
static int s; /* static local variable, stored in BSS segment */
int a; /* automatic variable, stored on stack */
int *p; /* pointer variable for malloc below */
/* obtain a block big enough for one int from the heap */
p = malloc(sizeof(int));
printf("&G = %p\n", (void *) &G);
printf("&s = %p\n", (void *) &s);
printf("&a = %p\n", (void *) &a);
printf("&p = %p\n", (void *) &p);
printf("p = %p\n", (void *) p);
printf("main = %p\n", (void *) main);
free(p);
return 0;
}
examples/pointers/lookingAtPointers.c
When I run this on a Mac OS X 10.6 machine after compiling with gcc, the output is:
&G = 0x100001078
&s = 0x10000107c
&a = 0x7fff5fbff2bc
&p = 0x7fff5fbff2b0
p = 0x100100080
main = 0x100000e18
The interesting thing here is that we can see how the compiler chooses to allocate space for variables based on their storage classes. The global variable G and the static local variable s both persist between function calls, so they get placed in the BSS segment (see .bss) that starts somewhere around 0x100000000, typically after the code segment containing the actual code of the program. Local variables a and p are allocated on the stack, which grows down from somewhere near the top of the address space. The block returned from malloc that p points to is allocated off the heap, a region of memory that may also grow over time and starts after the BSS segment. Finally, main appears at 0x100000e18; this is in the code segment, which is a bit lower in memory than all the global variables.
The null pointer
The special value 0, known as the null pointer, may be assigned to a pointer of any type. It may or may not be represented by the actual address 0, but it will act like 0 in all contexts where an integer value is expected (e.g., it has the value false in an if or while statement). Null pointers are often used to indicate missing data or failed functions. Attempting to dereference a null pointer can have catastrophic effects, so it’s important to be aware of when you might be supplied with one.
Pointers and functions
A simple application of pointers is to get around C’s limit on having only one return value from a function. Because C arguments are copied, assigning a value to an argument inside a function has no effect on the outside. So the doubler function below doesn’t do much:
#include <stdio.h>
/* doesn't work */
void
doubler(int x)
{
x *= 2;
}
int
main(int argc, char **argv)
{
int y;
y = 1;
doubler(y); /* no effect on y */
printf("%d\n", y); /* prints 1 */
return 0;
}
examples/pointers/badDoubler.c
However, if instead of passing the value of y into doubler we pass a pointer to y, then the doubler function can reach out of its own stack frame to manipulate y itself:
#include <stdio.h>
void
doubler(int *x)
{
*x *= 2;
}
int
main(int argc, char **argv)
{
int y;
y = 1;
doubler(&y); /* sets y to 2 */
printf("%d\n", y); /* prints 2 */
return 0;
}
examples/pointers/goodDoubler.c
Generally, if you pass the value of a variable into a function (with no &), you can be assured that the function can’t modify your original variable. When you pass a pointer, you should assume that the function can and will change the variable’s value. If you want to write a function that takes a pointer argument but promises not to modify the target of the pointer, use const, like this:
void
printPointerTarget(const int *p)
{
printf("%d\n", *p);
}
The const qualifier tells the compiler that the target of the pointer shouldn’t be modified. This will cause it to return an error if you try to assign to it anyway:
void
printPointerTarget(const int *p)
{
*p = 5; /* produces compile-time error */
printf("%d\n", *p);
}
Passing const pointers is mostly used when passing large structures to functions, where copying a 32-bit pointer is cheaper than copying the thing it points to.
If you really want to modify the target anyway, C lets you “cast away const”:
void
printPointerTarget(const int *p)
{
*((int *) p) = 5; /* no compile-time error */
printf("%d\n", *p);
}
There is usually no good reason to do this. The one exception might be if the target of the pointer represents an abstract data type, and you want to modify its representation during some operation to optimize things somehow in a way that will not be visible outside the abstraction barrier, making it appear to leave the target constant.
Note that while it is safe to pass pointers down into functions, it is very dangerous to pass pointers up. The reason is that the space used to hold any local variable of the function will be reclaimed when the function exits, but the pointer will still point to the same location, even though something else may now be stored there. So this function is very dangerous:
int *
dangerous(void)
{
int n;
return &n; /* NO! */
}
...
*dangerous() = 12; /* writes 12 to some unknown location */
An exception is when you can guarantee that the location pointed to will survive even after the function exits, e.g. when the location is dynamically allocated using malloc (see below) or when the local variable is declared static:
int *
returnStatic(void)
{
static int n;
return &n;
}
...
*returnStatic() = 12; /* writes 12 to the hidden static variable */
Usually returning a pointer to a static local variable is not good practice, since the point of making a variable local is to keep outsiders from getting at it. If you find yourself tempted to do this, a better approach is to allocate a new block using malloc (see below) and return a pointer to that. The downside of the malloc method is that the caller has to promise to call free on the block later, or you will get a storage leak.
Pointer arithmetic and arrays
Because pointers are just numerical values, one can do arithmetic on them. Specifically, it is permitted to
- Add an integer to a pointer or subtract an integer from a pointer. The effect of
p+nwherepis a pointer andnis an integer is to compute the address equal topplusntimes the size of whateverppoints to (this is whyint *pointers andchar *pointers aren’t the same). - Subtract one pointer from another. The two pointers must have the same type (e.g. both
int *or bothchar *). The result is a signed integer value of typeptrdiff_t, equal to the numerical difference between the addresses divided by the size of the objects pointed to. - Compare two pointers using
==,!=,<,>,<=, or>=. - Increment or decrement a pointer using
++or--.
Arrays
The main application of pointer arithmetic in C is in arrays. An array is a block of memory that holds one or more objects of a given type. It is declared by giving the type of object the array holds followed by the array name and the size in square brackets:
int a[50]; /* array of 50 ints */
char *cp[100]; /* array of 100 pointers to char */
Declaring an array allocates enough space to hold the specified number of objects (e.g. 200 bytes for a above and 400 for cp—note that a char * is an address, so it is much bigger than a char). The number inside the square brackets must be a constant whose value can be determined at compile time.
The array name acts like a constant pointer to the zeroth element of the array. It is thus possible to set or read the zeroth element using *a. But because the array name is constant, you can’t assign to it:
1 *a = 12; /* sets zeroth element to 12 */
2
3 a = &n; /* #### DOESN'T WORK #### */
More common is to use square brackets to refer to a particular element of the array. The expression a[n] is defined to be equivalent to *(a+n); the index n (an integer) is added to the base of the array (a pointer), to get to the location of the n-th element of a. The implicit * then dereferences this location so that you can read its value (in a normal expression) or assign to it (on the left-hand side of an assignment operator). The effect is to allow you to use a[n] just as you would any other variable of type int (or whatever type a was declared as).
Note that C doesn’t do any sort of bounds checking. Given the declaration int a[50];, only indices from a[0] to a[49] can be used safely. However, the compiler will not blink at a[-12] or a[10000]. If you read from such a location you will get garbage data; if you write to it, you will overwrite god-knows-what, possibly trashing some other variable somewhere else in your program or some critical part of the stack (like the location to jump to when you return from a function). It is up to you as a programmer to avoid such buffer overruns, which can lead to very mysterious (and in the case of code that gets input from a network, security-damaging) bugs. The valgrind program can help detect such overruns in some cases.
Another curious feature of the definition of a[n] as identical to *(a+n) is that it doesn’t actually matter which of the array name or the index goes inside the braces. So all of a[0], *a, and 0[a] refer to the zeroth entry in a. Unless you are deliberately trying to obfuscate your code, it’s best to write what you mean.
Arrays and functions
Because array names act like pointers, they can be passed into functions that expect pointers as their arguments. For example, here is a function that computes the sum of all the values in an array a of size n:
/* compute the sum of the first n elements of array a */
int
sumArray(int n, const int *a)
{
int i;
int sum;
sum = 0;
for(i = 0; i < n; i++) {
sum += a[i];
}
return sum;
}
Note the use of const to promise that sumArray won’t modify the contents of a.
Another way to write the function header is to declare a as an array of unknown size:
/* return the sum of the values in a, an array of size n */
int
sumArray(int n, const int a[])
{
...
}
This has exactly the same meaning to the compiler as the previous definition. Even though normally the declarations int a[10] and int *a mean very different things (the first one allocates space to hold 10 ints, and prevents assigning a new value to a), in a function argument int a[] is just syntactic sugar for int *a. You can even modify what a points to inside sumArray by assigning to it. This will allow you to do things that you usually don’t want to do, like write this hideous routine:
/* return the sum of the first n values in a */
int
sumArray(int n, const int a[])
{
const int *an; /* pointer to first element not in a */
int sum;
sum = 0;
an = a+n;
while(a < an) {
sum += *a++;
}
return sum;
}
Multidimensional arrays
Arrays can themselves be members of arrays. The result is a multidimensional array, where a value in row i and column j is accessed by a[i][j].
There are actually two different ways to do this that both support the a[i][j] syntax. With standard C multidimensional arrays, the array is an array of one-dimensional arrays, each of which has the same fixed size. With an array of pointers, the array is an array of pointers, each of which points to the first element of a one-dimensional array. The standard approach is simpler to set up and avoids some extra time and space complexity, but it breaks down for very large arrays or when the rows of the array may have different lengths. We’ll describe how to do both, as well as a third option that represents a two-dimensional array directly as a one-dimensional array, at the cost of losing the standard a[i][j] lookup syntax.
Using built-in C arrays
Declaration is similar to one-dimensional arrays:
int a[3][6]; /* declares an array of 3 rows of 6 ints each */
This declaration produces an array of 18 int values, packed contiguously in memory. The interpretation is that a is an array of 3 objects, each of which is an array of 6 ints.
If we imagine the array to contain increasing values like this:
0 1 2 3 4 5
6 7 8 9 10 11
12 13 14 15 16 17
the actual positions in memory will look like this:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
^ ^ ^
a[0] a[1] a[2]
To look up a value, we do the usual array-indexing magic. Suppose we want to find a[1][4]. The name a acts as a pointer to the base of the array.The name a[1] says to skip ahead 1 times the size of the things pointed to by a, which are arrays of 6 ints each, for a total size of 24 bytes assuming 4-byte ints. For a[1][4], we start at a[1] and move forward 4 times the size of the thing pointed to by a[1], which is an int; this puts us 24+16 bytes from a, the position of 10 in the picture above.
It’s useful to understand what is happening in this example, and for small arrays of fixed size there is no particular reason not to use C’s built-in arrays, but as soon as you start dealing with large arrays or arrays whose size is not fixed, you are better off doing something else. (This is true even if you use C99-style variable-length arrays.) Two possible approaches that you could try are using an malloc’d array of pointers to malloc’d rows, which has the advantage of preserving the a[i][j] syntax; and packing a two-dimensional array into a malloc’d one-dimensonal array, which has the advantage of preserving contiguity. Both approaches are described below.
Using an array of pointers to rows
Here we allocate each row separately using malloc and building a master list of pointers to rows, of type int **. The downside of this approach is that the array is no longer contiguous (which may affect cache performance) and it requires reading a pointer to find the location of a particular value, instead of just doing address arithmetic starting from the base address of the array. But elements can still be accessed using the a[i][j] syntax.
The naive way to do this is to allocate each row with a separate call to malloc. But since we know the total size of all of the rows, we can save both time and space by allocating one giant block and partitioning this block into rows ourselves. This may also help with cache performance since the array contents are all stored in one place, although we still have to follow a row pointer.
Note this can work even if the rows have different lengths (for example, if each is a null-terminated string), as long as we are careful to add up the lengths correctly and set the pointers to the right places.
Two examples of this approach are given below. The first builds a two-dimensional array of ints for any given number of rows and columns, while the second copies a collection of null-terminated strings into a single malloc’d block.
/* Demo program for malloc'd two-dimensional arrays */
#include <stdio.h>
#include <stdlib.h>
/* frees a 2d array created by malloc2d */
void
free2d(void **a)
{
/* free the rows */
free(a[0]);
/* then free array of pointers */
free(a);
}
/* returns a two-dimensional array with numRows rows and
* rowSize bytes per row, or 0 on allocation failure.
* The caller is responsible for freeing the result with free2d. */
void **
malloc2d(size_t numRows, size_t rowSize)
{
void **a;
size_t i;
/* a is an array of void * pointers that point to the rows */
a = malloc(sizeof(void *) * numRows);
if(a == 0) {
/* malloc failed */
return 0;
}
/* now allocate the actual rows */
/* the trick here is that we only allocate one big block */
a[0] = malloc(rowSize * numRows);
if(a[0] == 0) {
free(a);
return 0;
}
// fill in remaining row pointers
for(i = 1; i < numRows; i++) {
// compute offset to start of row i by hand
a[i] = a[0] + rowSize * i;
}
return a;
}
int
main(int argc, char **argv)
{
int rows;
int cols;
int **a;
int i;
int j;
if(argc != 3) {
fprintf(stderr, "Usage: %s rows cols\n", argv[0]);
return 1;
}
/* else */
rows = atoi(argv[1]);
cols = atoi(argv[2]);
/* note that void ** is not converted automatically,
* so we need an explicit cast */
a = (int **) malloc2d(rows, cols * sizeof(int));
if(a == 0) {
fprintf(stderr, "malloc2d failed, exiting\n");
return 2;
}
for(i = 0; i < rows; i++) {
for(j = 0; j < cols; j++) {
a[i][j] = i - j;
}
}
for(i = 0; i < rows; i++) {
for(j = 0; j < cols; j++) {
printf("%4d", a[i][j]);
}
putchar('\n');
}
free2d((void **) a); /* always clean up */
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// given n pointers to strings, pack copies of them
// into a single malloc'd block that can be accessed
// using bracket syntax
char **
packStrings(size_t n, char *s[])
{
size_t length = 0;
// compute total length including nulls
for(size_t i = 0; i < n; i++) {
length += strlen(s[i]) + 1;
}
// allocate a block big enough for pointers and strings
char **s2 = malloc(sizeof(char *) * n + length);
// this is a pointer to where the strings are copied
// after the n pointers
char *top = (char *) (s2 + n);
// copy the strings and fill in the pointer array
for(size_t i = 0; i < n; i++) {
strcpy(top, s[i]);
s2[i] = top;
top += strlen(s[i]) + 1;
}
return s2;
}
void
freePackedStrings(char **s)
{
free(s);
}
int
main(int argc, char **argv)
{
// pack argv, then print it out from the copied version
char **argv2 = packStrings(argc, argv);
for(int i = 0; i < argc; i++) {
puts(argv2[i]);
}
freePackedStrings(argv2);
return 0;
}
Using a one-dimensional array
A third approach is to store a two-dimensional array in a one-dimensional array, and do the indexing arithmetic ourselves. Since this requires keeping track of the dimensions of the array as well as the contents, it helps to be able to wrap up these values in a struct (see Structs), and possibly even hide the details of the construction behind an abstract data type. Typically we will provide operations to create an array with given dimensions, to destroy an array (freeing any space we malloc’d), and to obtain a pointer to a particular location in an array, which we can then use to operate on that location.
The advantages of this approach are that the contents of the array are packed contiguously and that address lookup doesn’t require following multiple pointers, which becomes particularly helpful if we generalize to more than two dimensions. We can also enforce bounds checking for safety (although at the cost of some time). The main disadvantage is that we lose access to the a[i][j] syntax.
An example of a simple implementation of a two-dimensional array is given below.
/* Demo program for packed two-dimensional arrays */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct flat2d {
size_t rows; // number of rows
size_t cols; // number of columns
int data[]; // data, stored at end of struct
};
// malloc and return flat2d of given dimensions
// array is not initialized!
struct flat2d *
flat2dCreate(size_t rows, size_t cols)
{
struct flat2d *a;
a = malloc(sizeof(struct flat2d) + sizeof(int) * rows * cols);
assert(a);
a->rows = rows;
a->cols = cols;
return a;
}
// free space used by a
void
flat2dDestroy(struct flat2d *a)
{
free(a);
}
// return a pointer to a[i][j]
// or 0 if i or j is out of bounds
int *
flat2dRef(struct flat2d *a, size_t i, size_t j)
{
if(i >= a->rows || j >= a->cols) {
return 0;
} else {
return &a->data[i * a->cols + j];
}
}
int
main(int argc, char **argv)
{
int rows;
int cols;
struct flat2d *a;
int i;
int j;
if(argc != 3) {
fprintf(stderr, "Usage: %s rows cols\n", argv[0]);
return 1;
}
/* else */
rows = atoi(argv[1]);
cols = atoi(argv[2]);
a = flat2dCreate(rows, cols);
for(i = 0; i < rows; i++) {
for(j = 0; j < cols; j++) {
*flat2dRef(a, i, j) = i - j;
}
}
for(i = 0; i < rows; i++) {
for(j = 0; j < cols; j++) {
printf("%4d", *flat2dRef(a, i, j));
}
putchar('\n');
}
flat2dDestroy(a);
return 0;
}
Variable-length arrays
C99 adds the feature of variable-length arrays, where the size of the array is determined at run-time. These can only appear as local variables in procedures (automatic variables) or in argument lists. In the case of variable-length arrays in argument lists, it is also necessary that the length of the array be computable from previous arguments.
For example, we could make the length of the array explicit in our sumArray function:
/* return the sum of the values in a, an array of size n */
int
sumArray(int n, const int a[n])
{
int i;
int sum;
sum = 0;
for(i = 0; i < n; i++) {
sum += a[i];
}
return sum;
}
This doesn’t accomplish much, because the length of the array is not used. However, it does become useful if we have a two-dimensional array, as otherwise there is no way to compute the length of each row:
int
sumMatrix(int rows, int cols, const int m[rows][cols])
{
int i;
int j;
int sum;
sum = 0;
for(i = 0; i < rows; i++) {
for(j = 0; j < cols; j++) {
sum += a[i][j];
}
}
return sum;
}
Here the fact that each row of m is known to be an array of cols many ints makes the implicit pointer computation in a[i][j] actually work. It is considerably more difficult to to this in ANSI C; the simplest approach is to pack m into a one-dimensional array and do the address computation explicitly:
int
sumMatrix(int rows, int cols, const int a[])
{
int i;
int j;
int sum;
sum = 0;
for(i = 0; i < rows; i++) {
for(j = 0; j < cols; j++) {
sum += a[i*cols + j];
}
}
return sum;
}
Variable-length arrays can sometimes be used for run-time storage allocation, as an alternative to malloc and free (see below). A variable-length array allocated as a local variable will be deallocated when the containing scope (usually a function body, but maybe just a compound statement marked off by braces) exits. One consequence of this is that you can’t return a variable-length array from a function.
Here is an example of code using this feature:
/* reverse an array in place */
void
reverseArray(int n, int a[n])
{
/* algorithm: copy to a new array in reverse order */
/* then copy back */
int i;
int copy[n];
for(i = 0; i < n; i++) {
/* the -1 is needed to that a[0] goes to a[n-1] etc. */
copy[n-i-1] = a[i];
}
for(i = 0; i < n; i++) {
a[i] = copy[i];
}
}
Why you shouldn’t use variable-length arrays
While using variable-length arrays can simplify code in some cases, as a general programming practice it is extremely dangerous. The reason is that, unlike allocations through malloc, variable-length array allocations are typically allocated on the stack (which is often more constrainted than the heap) and have no way of reporting failure. So if there isn’t enough room for your variable-length array, odds are you won’t find out until a segmentation fault occurs somewhere later in your code when you try to use it.
(As an additional annoyance, gdb is confused by two-dimensional variable-length arrays.)
Here’s a safer version of the above routine, using malloc and free.
/* reverse an array in place */
void
reverseArray(int n, int a[n])
{
/* algorithm: copy to a new array in reverse order */
/* then copy back */
int i;
int *copy;
copy = (int *) malloc(n * sizeof(int));
assert(copy); /* or some other error check */
for(i = 0; i < n; i++) {
/* the -1 is needed to that a[0] goes to a[n-1] etc. */
copy[n-i-1] = a[i];
}
for(i = 0; i < n; i++) {
a[i] = copy[i];
}
free(copy);
}
Pointers to void
A special pointer type is void *, a “pointer to void”. Such pointers are declared in the usual way:
void *nothing; /* pointer to nothing */
Unlike ordinary pointers, you can’t dereference a void * pointer or do arithmetic on it, because the compiler doesn’t know what type it points to. However, you are allowed to use a void * as a kind of “raw address” pointer value that you can store arbitrary pointers in. It is permitted to assign to a void * variable from an expression of any pointer type; conversely, a void * pointer value can be assigned to a pointer variable of any type. An example is the return value of malloc or the argument to free, both of which are declared as void *. (Note that K&R suggests using an explicit cast for the return value of malloc. This has since been acknowledged by the authors to be an error, which arose from the need for a cast prior to the standardization of void * in ANSI C.)
int *block;
block = malloc(sizeof(int) * 12); /* void * converted to int * before assignment */
free(block); /* int * converted to void * before passing to free */
If you need to use a void * pointer as a pointer of a particular type in an expression, you can cast it to the appropriate type by prefixing it with a type name in parentheses, like this:
int a[50]; /* typical array of ints */
void *p; /* dangerous void pointer */
a[12] = 17; /* save that valuable 17 */
p = a; /* p now holds base address of a */
printf("%d\n", ((int *) p)[12]); /* get 17 back */
Usually if you have to start writing casts, it’s a sign that you are doing something wrong, and you run the danger of violating the type system—say, by tricking the compiler into treating a block of bits that are supposed to be an int as four chars. But violating the type system like this will be necessary for some applications, because even the weak type system in C turns out to be too restrictive for writing certain kinds of “generic” code that work on values of arbitrary types.
Alignment
One issue with casting pointers to and from void * is that you may violate the alignment restrictions for a particular kind of pointer on some architectures.
Back in the 8-bit era of the 1970s, a single load or store operation would access a single byte of memory, and because some data (chars) are still only one byte wide, C pointers retain the ability to address individual bytes. But present-day memory architectures typically have a wider data path, and the CPU may load or store as many as 8 bytes (64 bits) in a single operation. This makes it natural to organize memory into 4-byte or 8-byte words even though addresses still refer to individual bytes. The effect of the memory architecture is that the address of memory words must be aligned to a multiple of the word size: so with 4-byte words, the address 0x1037ef44 (a multiple of 4) could refer to a full word, but 0x1037ef45 (one more than a multiple of 4) could only be used to refer to a byte within a word.
What this means for a C program depends on your particular CPU and compiler. If you try to use something like 0x1037ef45 as an int *, one of three things might happen:
- The CPU might load the 4 bytes starting at this address, using two accesses to memory to piece together the full
intout of fragments of words. This is done on Intel architectures, but costs performance. - The CPU might quietly zero out the last two bits of the address, loading from
0x1037ef44even though you asked for0x1037ef45. This happens on some other architectures, notably ARM. - The CPU might issue a run-time exception.
All of these outcomes are bad, and the C standard does not specify what happens if you try to dereference a pointer value that does not satisfy the alignment restrictions of its target type. Fortunately, unless you are doing very nasty things with casts, this is unlikely to come up, because any pointer value you will see in a typical program is likely to arise in one of three ways:
- By taking the address of some variable. This pointer will be appropriately aligned, because the compiler allocates space for each variable (including fields within
structs) with appropriate alignment. - By computing an offset address using pointer arithmetic either explicitly (
p + n) or implicitly (p[n]). In either case, as long as the base pointer is correctly aligned, the computed pointer will also be correctly aligned. - By obtaining a pointer to an allocated block of memory using
mallocor a similar function. Heremallocis designed to always return blocks with the maximum possible required alignment, just to avoid problems when you use the results elsewhere.
On many compilers, you can use __alignof(type) to get the alignment restriction for a particular type. This was formalized in C11 without the underscores: alignof. Usually if your code needs to include __alignof or alignof something has already gone wrong.
The other place where alignment can create issues is that if you make a struct with components with different alignment restrictions, you may end up with some empty space. For example, on a machine that enforces 4-byte alignment for ints, building a struct that contains a char and an int will give you something bigger than you might expect:
#include <stdio.h>
struct ci {
char c; /* offset 0 */
/* 3 unused bytes go here */
int i; /* offset 4 */
};
struct ic {
int i; /* offset 0 */
char c; /* offset 4 */
/* 3 unused bytes go here */
};
int
main(int argc, char **argv)
{
printf("sizeof(struct ci) == %lu\n", sizeof(struct ci));
printf("sizeof(struct ic) == %lu\n", sizeof(struct ic));
return 0;
}
examples/alignment/structPacking.c
$ gcc -Wall -o structPacking structPacking.c
$ ./structPacking
sizeof(struct ci) == 8
sizeof(struct ic) == 8
In both cases, the compiler packs in an extra 3 bytes to make the size of the struct a multiple of the worst alignment of any of its components. If it didn’t do this, you would have trouble as soon as you tried to make an array of these things.
Run-time storage allocation using malloc
C does not generally permit arrays to be declared with variable sizes. C also doesn’t let local variables outlive the function they are declared in. Both features can be awkward if you want to build data structures at run time that have unpredictable (perhaps even changing) sizes and that are intended to persist longer than the functions that create them. To build such structures, the standard C library provides the malloc routine, which returns a otherwise-unused block of space of a given size (in bytes).
Unlike local variables that expire when their function returns, you can use this space for whatever you want for as long as you want. When you are done with it, you should call the free routine to give it back. The malloc and free routines together act as brokers for space on the heap, which malloc will grow as needed by asking for more space from the operating system.
To use malloc, you must include stdlib.h at the top of your program. The declaration for malloc is
void *malloc(size_t);
where size_t is an integer type (often unsigned long). Calling malloc with an argument of n allocates and returns a pointer to the start of a block of n bytes if possible. If the system can’t give you the space you asked for (maybe you asked for more space than it has), malloc returns a null pointer. It is good practice to test the return value of malloc whenever you call it.
Because the return type of malloc is void *, its return value can be assigned to any variable with a pointer type. Computing the size of the block you need is your responsibility—and you will be punished for any mistakes with difficult-to-diagnose buffer overrun errors—but this task is made slightly easier by the built-in sizeof operator that allows you to compute the size in bytes of any particular data type. A typical call to malloc might thus look something like this:
#include <stdlib.h>
/* allocate and return a new integer array with n elements */
/* calls abort() if there isn't enough space */
int *
makeIntArray(int n)
{
int *a;
a = malloc(sizeof(int) * n);
if(a == 0) abort(); /* die on failure */
return a;
}
examples/pointers/makeIntArray.c
If you don’t want to do the multiplication yourself, or if you want to guarantee that the allocated data is initialized to zero, you can use calloc instead of malloc. The calloc function is also declared in stdlib.h and takes two arguments: the number of things to allocate, and the size of each thing. Here’s a version of makeIntArray that uses calloc.
#include <stdlib.h>
/* allocate and return a new integer array with n elements */
/* initializes array to zero */
/* calls abort() if there isn't enough space */
int *
makeIntArray(int n)
{
int *a;
a = calloc(n, sizeof(int));
if(a == 0) abort(); /* die on failure */
return a;
}
If you know that you want to initialize your data to zero (which means all zero bytes, which will translate to a zero or null value for typical C data types), calloc can be significantly more efficient than malloc. The reason is that zero-value memory pages can often be requested from the operating system without actually allocating space for them until they are written, so allocating huge blocks using calloc doesn’t take much more time than allocating small ones. If we used malloc and then initialized the blocks by hand, we would have to pay both the time cost of filling in all the initial values and the space cost of allocating pages that we might not actually need. So calloc is often a better choice in these cases. However, if you are planning on filling in all the data eventually, calloc just shifts the cost to the time when you write to the pages, so the difference mostly just affects whether you pay a big cost up front or spread it out over the execution of your program.
Whichever of malloc or calloc you use, when you are done with a block, you should return its space to the storage allocator using the free routine, also defined in stdlib.h. If you don’t do this, your program may quickly run out of space. The free routine takes a void * as its argument and returns nothing. It is good practice to write a matching destructor that de-allocates an object for each constructor (like makeIntArray) that makes one.
void
destroyIntArray(int *a)
{
free(a);
}
It is a serious error to do anything at all with a block after it has been freed. This is not necessarily because free modifies the contents of the block (although it might), but because when you free a block you are granting the storage allocator permission to hand the same block out in response to a future call to malloc, and you don’t want to step on whatever other part of your program is now trying to use that space.
It is also possible to grow or shrink a previously allocated block. This is done using the realloc function, which is declared as
void *realloc(void *oldBlock, size_t newSize);
The realloc function returns a pointer to the resized block. It may or may not allocate a new block. If there is room, it may leave the old block in place and return its argument. But it may allocate a new block and copy the contents of the old block, so you should assume that the old pointer has been freed.
Here’s a typical use of realloc to build an array that grows as large as it needs to be:
/* read numbers from stdin until there aren't any more */
/* returns an array of all numbers read, or null on error */
/* returns the count of numbers read in *count */
int *
readNumbers(int *count /* RETVAL */)
{
int mycount; /* number of numbers read */
int size; /* size of block allocated so far */
int *a; /* block */
int n; /* number read */
mycount = 0;
size = 1;
a = malloc(sizeof(int) * size); /* allocating zero bytes is tricky */
if(a == 0) return 0;
while(scanf("%d", &n) == 1) {
/* is there room? */
while(mycount >= size) {
/* double the size to avoid calling realloc for every number read */
size *= 2;
a = realloc(a, sizeof(int) * size);
if(a == 0) return 0;
}
/* put the new number in */
a[mycount++] = n;
}
/* now trim off any excess space */
a = realloc(a, sizeof(int) * mycount);
/* note: if a == 0 at this point we'll just return it anyway */
/* save out mycount */
*count = mycount;
return a;
}
examples/pointers/readNumbers.c
Because errors involving malloc and its friends can be very difficult to spot, it is recommended to test any program that uses malloc using valgrind.
Function pointers
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.
Function pointers are not used as much in C as in functional languages, but there are many common uses even in C code.
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:
/* a function taking two int arguments and returning an int */
int function(int x, int y);
/* a pointer to such a function */
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:
/* Functional "hello world" program */
#include <stdio.h>
int
main(int argc, char **argv)
{
/* function for emitting text */
int (*say)(const char *);
say = puts;
say("hello world");
return 0;
}
Callbacks
A callback is when we pass a function pointer into a function so that that function can call our function when some event happens or it needs to compute something.
A classic example is the comparison argument to qsort, from the standard library:
/* defined in stdlib.h */
void
qsort(
void *base,
size_t n,
size_t size,
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.
static int
compare_ints(void *key1, void *key2)
{
return *((int *) key1) - *((int *) key2);
}
int
sort_int_array(int *a, int n)
{
qsort(a, n, sizeof(*a), compare_ints);
}
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.
Dispatch tables
Dispatch tables are an alternative to gigantic if/else if or switch statements. The idea is to build an array of function pointers (or, more generally, some sort of dictionary data structure), and use the value we might otherwise be feeding to switch as an index into this array. Here is a simple example, which echoes most of the characters in its input intact, except for echoing every lowercase vowel twice:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
/*
* Demonstrate use of dispatch tables.
*/
/* print a character twice */
/* like putchar, returns character if successful or EOF on error */
int
putcharTwice(int c)
{
if(putchar(c) == EOF || putchar(c) == EOF) {
return EOF;
} else {
return c;
}
}
#define NUM_CHARS (UCHAR_MAX + 1) /* UCHAR_MAX is in limits.h */
int
main(int argc, char **argv)
{
/* this declares table as an array of function pointers */
int (*table[UCHAR_MAX+1])(int);
int i;
int c;
for(i = 0; i < UCHAR_MAX; i++) {
/* default is to call putchar */
table[i] = putchar;
}
/* but lower-case vowels show up twice */
table['a'] = putcharTwice;
table['e'] = putcharTwice;
table['i'] = putcharTwice;
table['o'] = putcharTwice;
table['u'] = putcharTwice;
while((c = getchar()) != EOF) {
table[c](c);
}
return 0;
}
examples/pointers/dispatchTable.c
And here is the program translating Shakespeare into mock-Swedish:
$ gcc -Wall -g3 -o dispatchTable dispatchTable.c
$ echo Now is the winter of our discontent made glorious summer by this sun of York. | ./dispatchTable
Noow iis thee wiinteer oof oouur diiscoonteent maadee glooriioouus suummeer by thiis suun oof Yoork.
In this particular case, we did a lot of work to avoid just writing a switch statement. But being able to build a dispatch table dynamically can be very useful sometimes. An example might be a graphical user interface where each button has an associated function. If buttons can be added by different parts of the program, using a table mapping buttons to functions allows a single dispatch routine to figure out where to route button presses.
(For some applications, we might want to pass additional information in to the function to change its behavior. This can be done by replacing the function pointers with closures.)
The restrict keyword
In C99, it is possible to declare that a pointer variable is the only way to reach its target as long as it is in scope. This is not enforced by the compiler; instead, it is a promise from the programmer to the compiler that any data reached through this point will not be changed by other parts of the code, which allows the compiler to optimize code in ways that are not possible if pointers might point to the same place (a phenomenon called pointer aliasing). For example, consider the following short function:
// write 1 + *src to *dst and return *src
int
copyPlusOne(int * restrict dst, int * restrict src)
{
*dst = *src + 1;
return *src;
}
For this function, the output of gcc -O3 -S includes one more instruction if the restrict qualifiers are removed. The reason is that if dst and src may point to the same location, src needs to be re-read for the return statement, in case it changed. But if they are guaranteed to point to different locations, the compiler can re-use the previous value it already has in one of the CPU registers.
For most code, this feature is useless, and potentially dangerous if someone calls your routine with aliased pointers. However, it may sometimes be possible to increase performance of time-critical code by adding a restrict keyword. The cost is that the code might no longer work if called with aliased pointers.
Curiously, C assumes that two pointers are never aliased if you have two arguments with different pointer types, neither of which is char * or void *. This is known as the strict aliasing rule and cannot be overridden from within the program source code: there is no unrestrict keyword. You probably only need to worry about this if you are casting pointers to different types and then passing the cast pointers around in the same context as the original pointers.
#/media/File:Tallrik_-_Ystad-2018.jpg){kind=link}