PineWiki
1. 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 integer on typical current architectures, referring to one of up to 232 distinct 8-bit locations in the memory. These 32-bit integers can be manipulated like any other 32-bit integer; in C, they appear as pointers, a family of types that can be passed as arguments, stored in variables, returned from functions, etc.
2. Pointer variables
2.1. 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:
1 int *pointerToInt;
2 double *pointerToDouble;
3 char *pointerToChar;
4 char **pointerToPointerToChar;
2.2. 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:
1 int n; /* an int variable */
2 int *p; /* a pointer to an int */
3
4 p = &n; /* p now points to n */
2.3. Using a pointer
Pointer variables can be used in two ways: to get their value (a pointer), e.g. if you want to assign an address to more than one pointer variable:
1 int n; /* an int variable */
2 int *p; /* a pointer to an int */
3 int *q; /* another pointer to an int */
4
5 p = &n; /* p now points to n */
6 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:
1 int n; /* an int variable */
2 int *p; /* a pointer to an int */
3
4 p = &n; /* p now points to n */
5
6 *p = 2; /* sets n to 2 */
7 *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 --, ++, and . (used in C/Structs) bind tighter, requiring parantheses if you want the * to take precedence.
1 (*p)++; /* increment the value pointed to by p */
2 *p++; /* WARNING: increments p itself */
3. 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 (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.
4. 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:
1 /* doesn't work */
2 void
3 doubler(int x)
4 {
5 x *= 2;
6 }
7
8 int
9 main(int argc, char **argv)
10 {
11 int y;
12
13 y = 1;
14
15 doubler(y); /* no effect on y */
16
17 printf("%d\n", y); /* prints 1 */
18 }
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:
1 void
2 doubler(int *x)
3 {
4 *x *= 2;
5 }
6
7 int
8 main(int argc, char **argv)
9 {
10 int y;
11
12 y = 1;
13
14 doubler(&y); /* sets y to 2 */
15
16 printf("%d\n", y); /* prints 2 */
17 }
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:
1 void
2 printPointerTarget(const int *p)
3 {
4 printf("%d\n", *p);
5 }
This is mostly used when passing larger structures to functions, where copying a 32-bit pointer is cheaper than copying the large structure it points to.
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:
1 int *
2 dangerous(void)
3 {
4 int n;
5
6 return &n; /* NO! */
7 }
8
9 ...
10
11 *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:
1 int *
2 returnStatic(void)
3 {
4 static int n;
5
6 return &n;
7 }
8
9 ...
10
11 *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.
5. 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+n where p is a pointer and n is an integer is to compute the address equal to p plus n times the size of whatever p points to (this is why int * pointers and char * pointers aren't the same).
Subtract one pointer from another. The two pointers must have the same type (e.g. both int * or both char *). The result is an integer value, 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 --.
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:
1 int a[50]; /* array of 50 ints */
2 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 (see C/valgrind).
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.
5.1. 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:
1 /* return the sum of the values in a, an array of size n */
2 int
3 sumArray(const int *a, int n)
4 {
5 int i;
6 int sum;
7
8 sum = 0;
9 for(i = 0; i < n; i++) {
10 sum += a[i];
11 }
12
13 return sum;
14 }
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:
1 /* return the sum of the values in a, an array of size n */
2 int
3 sumArray(const int a[], int n)
4 {
5 ...
6 }
This is essentially the same as the previous definition, the only difference being that modifying a inside sumArray will now be forbidden. This will generally only prevent things that you usually don't want to do, like writing this hideous routine:
1 /* return the sum of the values in a, an array of size n */
2 int
3 sumArray(const int *a, int n)
4 {
5 int *an; /* pointer to first element not in a */
6 int sum;
7
8 sum = 0;
9 an = a+n;
10
11 while(a < an) {
12 sum += *a++;
13 }
14
15 return sum;
16 }
It's probably worth being able to read code like this, but I don't personally recommend writing it.
6. Void pointers
A special pointer type is void *, a "pointer to void". Such pointers are declared in the usual way:
1 void *nothing; /* pointer to nothing */
Unlike ordinary pointers, you can't derefence 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.
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:
1 int a[50]; /* typical array of ints */
2 void *p; /* dangerous void pointer */
3
4 a[12] = 17; /* save that valuable 17 */
5 p = a; /* p now holds base address of a */
6
7 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.
7. Run-time storage allocation
C does not 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 asks the operating system for a block of space of a given size (in bytes). With a bit of pushing and shoving, this can be used to obtain a block of space that for all practical purposes acts just like an array.
To use malloc, you must include stdlib.h at the top of your program. The declaration for malloc is
1 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:
1 #include <stdlib.h>
2
3 /* allocate and return a new integer array with n elements */
4 /* calls abort() if there isn't enough space */
5 int *
6 makeIntArray(int n)
7 {
8 int *a;
9
10 a = malloc(sizeof(int) * n);
11
12 if(a == 0) abort(); /* die on failure */
13
14 return a;
15 }
When you are done with a malloc'd region, you should return the space to the system using the free routine, also defined in stdlib.h. If you don't do this, your program will 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.
1 void
2 destroyIntArray(int *a)
3 {
4 free(a);
5 }
It is a serious error to do anything at all with a block after it has been freed.
It is also possible to grow or shrink a previously allocated block. This is done using the realloc function, which is declared as
1 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:
1 /* read numbers from stdin until there aren't any more */
2 /* returns an array of all numbers read, or null on error */
3 /* returns the count of numbers read in *count */
4 int *
5 readNumbers(int *count /* RETVAL */)
6 {
7 int mycount; /* number of numbers read */
8 int size; /* size of block allocated so far */
9 int *a; /* block */
10 int n; /* number read */
11
12 mycount = 0;
13 size = 1;
14
15 a = malloc(sizeof(int) * size); /* allocating zero bytes is tricky */
16 if(a == 0) return 0;
17
18 while(scanf("%d", &n) == 1) {
19 /* is there room? */
20 while(mycount >= size) {
21 /* double the size to avoid calling realloc for every number read */
22 size *= 2;
23 a = realloc(a, sizeof(int) * size);
24 if(a == 0) return 0;
25 }
26
27 /* put the new number in */
28 a[mycount++] = n;
29 }
30
31 /* now trim off any excess space */
32 a = realloc(a, sizeof(int) * mycount);
33 /* note: if a == 0 at this point we'll just return it anyway */
34
35 /* save out mycount */
36 *count = mycount;
37
38 return a;
39 }
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 if possible. (See C/valgrind).
(See also C/DynamicStorageAllocation for some old notes on this subject.)