Pointers

Source Files

The term pointer is a name that tends to instill fear in some students; however, consider that every byte in main memory is given a unique address from 0x00000000 to 0xffffffff on a 32-bit computer and from 0x0000000000000000 to 0xffffffffffffffff on a 64-bit computer. The 0x says that the digits that follow are hexadecimal digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f).

We will review pointers by first considering memory addresses, then storing addresses in variables, and finally some examples as to why we would want to do this.

Notice: the examples in this web site use the Unix operating system. The command-line prompt in Unix varies and can be templated by the user; however, I will be using % to indicate the prompt.

As a quick crash course in Unix: more is is a Unix command that prints the following file. The command-line compiler you will be using is the GNU C Compiler (gcc), and the default output of this compiler is the executable program a.out. For valid safety reasons, Unix will only execute programs directories that the user has specified (for example, /usr/local/bin/). To execute a file in the current directory, you must prefix the executable with ./ as in ./a.out.

Observing Addresses

For example, in C, every function name is assigned the address in memory for the first instruction for that function. Thus, if you call main or printf, the program knows where to go to start executing. For example, this simple program prints the addresses of the two functions int main() and int printf():

% more functions.c 
#include <stdio.h>

int main() {
        printf( "%p\n", main );
        printf( "%p\n", printf );

        return 0;
}
% gcc functions.c 
% ./a.out 
0x400498
0x4003a0
%

You will note the placeholder %p which differs from %d for integers and %f for floating-point numbers. In this case, it is a placeholder for a pointer.

If you were to look at main memory on a 32-bit computer, you would see a memory map as shown in Figure 1.

Figure 1. A memory map with two functions.

Another place that we can see the address is that of local variables: if i is defined as a local variable in a function, then when that function is executing, the variable must be stored somewhere in memory. To access that location, we can ask for the address of the variable: &i (think ampersand—address-of). For example,

% more local.c
#include <stdio.h>

int main() {
        int i = 5;
        printf( "%p\n", &i );

        return 0;
}
% gcc local.c
% ./a.out
0xfffffa5c

Thus, this local variable appears to be stored at the other end of memory as is shown in Figure 2.

Figure 2. A memory map with a local variable i.

Now that we have accessed various addresses, let's look at how we can also store such addresses.

Storing Addresses

You already know about variables: the variable

	int i = 42;

stores a 32-bit integer initialized to forty-two. If we can store integers, then why not store addresses? For example, could we not have a data type

	address adrs;      // This is wrong and for teaching purposes only.

and allow this variable to store either 32 or 64 bit addresses in main memory? That's all that a pointer is: it's a variable storing an address. We should also be able to print what is stored at that address:

	printf( "%p\n", adrs );

This would print either a 32- or 64-bit hexadecimal number.

Similarly, we should be able to assign to such a variable; for example,

	int i = 42;
	address adrs = &i;

In the above example, adrs would now be assigned 0xfffffa5c.

Now, storing an address is one thing, but what about determining what is stored at a particular memory location? Can we do the reverse; that is, interpret what is stored at the address as an integer or a floating-point number?

To ask what an address stores requires us also to tell the compiler what is being stored at a particular address. For example, using a variable that stores an arbitrary address could also allow

	double e = 2.71828182845904;
	address adrs = &e;

Thus, if you want to store an address, you must tell C what is being stored at that address as follows:

The unary operator * is used to access what is stored at a particular address. That same operator is used to indicate that a variable is a pointer:

	int i = 42;
	int *ptr = &i;
	printf( "%d\n", *ptr );

Note that int i suggests that by accessing the variable i, you get an integer. On the other hand, int *ptr says "to get an integer, you must access *ptr"; that is, ptr must be an address or, in the parlance of C, a pointer.

You can also assign to the memory location pointed to by the address:

	int i = 42;
	int *ptr = &i;
	*ptr = 91;
	printf( "%p == %p\n", &i, ptr );
	printf( "%d == %d\n", i, *ptr );

Running this, you will see that, as expected, changing what was stored at the address of i also changes i itself.

Hint: if pointers still bother you, always place a "ptr" or even just a "p" or "p_" in front of a variable name that is meant to be a pointer; that is, it is meant to store an address.

So What?

Up until now, there seems to be little point in storing an address: if we have variables, why do we need to know where they're stored, and if we can access a function by calling sin(3.14), why do we need the address of the function?

Example 1

One common example that will be used in this course is to create an array of functions. Suppose you have five error conditions coded by 0, 1, 2, 5, 9 and for each of these error conditions, you need to call an appropriate error handling function.

Constructing an example true to this description would only obfuscate what is going on, so the following example shows how a local variable can be declared to be an array of three pointers to functions that take doubles as arguments and return doubles. In this case, we will use three functions that are included in the math library (math.h): sin, cos, and tan.

% more fn_vector.c 
#include <stdio.h>
#include <math.h>

int main() {
        double x = 3.14;

	// An array of three pointers to functions:
	// 'arr_fn' is an array of three entries, each of which is a pointer to a function that takes a
	// double as an argument and returns a double.  This is not required for this class.
	// You don't need this for this class, but to convert C types to English, visit cdecl.org
        double (*arr_fn[3])( double );

        arr_fn[0] = sin;
        arr_fn[1] = cos;
        arr_fn[2] = tan;

        printf( "sin(%f) = %f, cos(%f) = %f, tan(%f) = %f\n",
                x, arr_fn[0](x), x, arr_fn[1](x), x, arr_fn[2](x) );

        return 0;
}
% gcc -lm fn_vector.c
% ./a.out 
sin(3.140000) = 0.001593, cos(3.140000) = -0.999999, tan(3.140000) = -0.001593

You will note that in order to use the math library, it was necessary to flag the compiler to link the math library -lm. At this point, you don't have to worry about this beyond: "If I use #include <stdio.h>, I must link the corresponding library using -lm."

Example 2

This, however, is not the most significant example: one real issue in with functions is that all local variables are collected when the function (or even block) exits. For example, in the function

int f() {
	int i;

	for ( i = 0; i < 10; ++i ) {
		int j;
	}

	// You can no longer access 'j' at this point.

	return 0;
}
// Once the function exits, 'i' is also no longer accessible.

Suppose you need a data structure for more time than is used in a single function, but there is no need for that data structure to exist for the entire duration of the program. For example, you might have a pair of integers indicating a pixel on a screen:

struct Pair { 
        int x, y;
};

int f() {
        struct Pair point;

        point.x = 91;
        point.y = 42;

        return 0;
}

This local variable point would be collected at the end of the function. What if it is necessary for this variable to exist for longer than the end of a single function? Here are two examples:

Consider MS Word: the user can create new or close existing documents at any time. When the user selects a new Blank Document from the New Document dialog, a data structure (actually, an instance of a class) describing that document must be created. Edits to the document are reflected in this data structure, and when the user closes the document (presumably after saving it), the memory for the data structure must be freed up for other use.
Consider an operating system: each time the user executes a new process by launching a program, the operating system must create a data structure to describe the characteristics of that process (who started executing it, when, where the program is located in main memory, etc.). When the process closes (either because the process exits or because it is killed), it is necessary to free up the memory of that data structure so that it can be used by something else.

In these cases, we cannot use local variables: instead, we will ask the operating system to allocate additional memory elsewhere so as to store a Pair. In this case, if each integer was four bytes, we would have to ask for eight bytes.

The way C makes such functionality available to the programmer is to provide the function malloc; named for memory allocation. Its argument is the number of bytes that are required and the return value is the address of the first byte in the allocated block of memory. This address should be assigned to a pointer so that it can be accessed later.

The following program has a function that allocates memory for a new Pair (to determine how much memory is required for a new Pair, the sizeof operator is used. When new_pair returns, it returns the address returned by malloc and thus, only the memory allocated for the pointer variable tmp_point is collected at the end of the call to new_pair(). In main(), we can still access the newly created Pair, we can modify its contents, and finally, when we no longer need the Pair, we can tell the operating system "We don't need this memory anymore" by calling free.

% more pair1.c
#include <stdio.h>
#include <stdlib.h>

struct Pair { 
        int x, y;
};

struct Pair *new_pair() {
        struct Pair *tmp_point = malloc( sizeof( struct Pair ) );

        (*tmp_point).x = 91;
        (*tmp_point).y = 42;

        return tmp_point;
}

int main() {
        struct Pair *ptr = new_pair();

        printf( "(%d, %d)\n", (*ptr).x, (*ptr).y );

        (*ptr).y = -42;

        printf( "(%d, %d)\n", (*ptr).x, (*ptr).y );

        free( ptr );
	ptr = NULL;

        return 0;
}
% gcc pair1.c
% ./a.out 
(91, 42)
(91, -42)

Note: While sizeof appears to work like a function, it is actually an operator no different than multiplication or addition, it simply has a longer name. All calls to the sizeof operator must be evaluated by the compiler: the data structure must be known and well defined at compile time.

Note: Recall that ptr is still just a local variable. After we call free, the variable is still assigned the address in question; only the memory is no longer allocated. In order to avoid accidentally accessing that memory again, we set ptr to the null pointer, i.e., the pointer to nothing. If we try accessing (*ptr).x, after this, the program will crash (a much better alternative than having potentially dangerous activity).

Example 2 Revisited

One of the ugliest features of C is that . has higher precedence than the unary *. Thus, *ptr.x is interpreted as *(ptr.x). Consequently, it is necessary to always use (*ptr).x when accessing the fields of a struct when one has only a pointer to that structure. To remove this ugliness, the operator -> was introduced which does the same as (*ptr).x: ptr->x. If we were to re-implement the above program using this new operator, it becomes significantly simplified in appearance:

% more pair2.c
#include <stdio.h>
#include <stdlib.h>

struct Pair { 
        int x, y;
};

struct Pair *new_pair() {
        struct Pair *tmp_point = malloc( sizeof( struct Pair ) );
	printf( "Allocating memory at %p\n", tmp_point );

        tmp_point->x = 91;
        tmp_point->y = 42;

        return tmp_point;
}

int main() {
        struct Pair *ptr = new_pair();

        printf( "(%d, %d)\n", ptr->x, ptr->y );

        ptr->y = -42;

        printf( "(%d, %d)\n", ptr->x, ptr->y );

        free( ptr );
	ptr = NULL;

        return 0;
}
% gcc pair2.c
% ./a.out 
Allocating memory at 0x172d5010
(91, 42)
(91, -42)

Example 3

We will now construct a simple linked list using the -> operator. This is a very simple linked list that only allows you to:

Initialize the linked list,
Access the front of the linked list,
Push something onto the front of the linked list,
Pop off the front entry of the linked list, and
Empty (or clear) the linked list.

Each item in the linked list is stored in a Node data structure and the linked list itself (List) contains a count together with a pointer to the first node. This data structure is, for the all intents and purposes, a stack-like data structure as you have probably seen in your previous course on algorithms and data structures.

% more List.c
#include <stdio.h>
#include <stdlib.h>

struct Node { 
        int element;
        struct Node *next;
};

struct List { 
        struct Node *head;
        int count;
};

// Initialize a new linked list:  set the count to zero and the head pointer to NULL.

void init( struct List *list ) {
        list->head = NULL;
        list->count = 0;
}

// Return the first element in the linked list.  If the list is empty, return 0.

int front( struct List *list ) {
        if ( list->count == 0 ) {
                return 0;
        }

        return list->head->element;
}

// Allocate memory for a new node storing the argument 'value' and setting its next
// pointer to the address of the current head of the linked list,
// then setting the head of the linked list to this new node and updating the count.

void push( struct List *list, int value ) {
        struct Node *nd = malloc( sizeof( struct Node ) );
	printf( "Allocating a new node at %p\n", nd );
        nd->element = value;
        nd->next = list->head;

        list->head = nd;
        ++(list->count);  // The parenthesis are not necessary, but it's much clearer
}

// If the linked list is empty, do nothing.
// Otherwise, temporarily store a pointer to the current head, updating the
// head of the linked list, decrement the count, and then free the memory
// for the stored node.

void pop( struct List *list ) {
        if ( list->count == 0 ) {
                return;
        }

        struct Node *nd = list->head;
        list->head = list->head->next;
        --(list->count);  // The parenthesis are not necessary, but it's much clearer

        free( nd );
}

// Clear the linked list by repeatedly calling 'pop' until the list is empty.

void clear( struct List *list ) {
	while ( list->count != 0 ) {
		pop( list );
	}
}

int main() {
        struct List *ls = malloc( sizeof( struct List ) );
	printf( "Allocating a new linked list at %p\n", ls );
        init( ls );

        push( ls, 5 );
        push( ls, 7 );
        printf( "Current head:  %d\n", front( ls ) );
        printf( "Current count:  %d\n", ls->count );
        pop( ls );
        printf( "Current head:  %d\n", front( ls ) );
        printf( "Current count:  %d\n", ls->count );

        clear( ls );
        printf( "Current count:  %d\n", ls->count );
        free( ls );

        return 0;
}

You will note that every time we push a new node onto the linked list, we must allocate memory for a new Node. Similarly, when we call pop, it is necessary to free memory. In the case of push, you will see that the memory allocated exists beyond the end of the function call. The output of this program is

% gcc List.c
% ./a.out
Allocating a new linked list at 0x186d6010
Allocating a new node at 0x186d6030
Allocating a new node at 0x186d6050
Current head:  7
Current count:  2
Current head:  5
Current count:  1
Current count:  0

The actual memory locations values may change for each execution, but for this run, the contents of memory would appear like that shown in Figure 3.

Figure 3. The memory map at the point at which the linked list has two elements.

You should recall that each byte stores two hexadecimal digits and that on this 32-bit machine, pointers and int are each four bytes in size. On a 64-bit computer, the pointers would occupy eight bytes.

Question: how would the memory map in Figure 3 change if pop() is called?

Note: It is beyond the scope of this course, but Figure 3 assumes a big-endian architecture (the most-significant byte comes first). Some computers will save the four bytes in the reverse order (least-significant byte first) to optimize, for example, addition: by placing the least-significant byte first, addition may be done in order as the least-significant bytes are added first, followed by the next-most-significant bytes, etc.

Arbitrary Pointers: `void *`

It is possible to declare a variable to be an arbitrary pointer:

	void *ptr;

however, such a variable can never be de-referenced—the compiler does not know whether the address is that of a 4-byte integer, an 8-byte double, or some other data structure. Thus, if such an address is to be used, it must be first assigned to a pointer variable that has a type or it must be cast:

	void *ptr;

	int *iptr = ptr;

	printf( "%d and %d\n", *iptr, *((int *)ptr) );

The second de-reference first has the local variable ptr cast to a pointer-to-an-integer (int *)ptr after which it can be de-referenced.

Exercise 1

Add a function to the linked list described above which takes an argument and returns either true or false based on whether or not the argument is in the list. The signature for this function will be

bool member( struct List *, int );

and you will have to include the standard Boolean header file in your List.c file:

#include <stdbool.h>

otherwise, bool, true, and false will not be defined.

Introduction to Computer Structures and Real-time Systems