C: Pointers

You can access the slides 🖼️ for this lecture.

Here we will cover a central concept in C: pointers. They allow the programmer to manipulate memory quite directly. We will start by defining what a pointer is, and we’ll see in what scenarios using pointers is required or beneficial.

The Virtual Address Space

As you know, each program running on the CPU accesses memory with load and store instructions. These target memory locations called addresses, and the set of addresses a program can read from and write to is named the virtual address space. It is very large; for Linux on 64-bit processors, it ranges from address 0 to 128 TB. Its size is unrelated to the amount of physical memory present in the machine; in fact, most of these virtual addresses are not mapped to physical memory. Each slot in the address space can hold 1 byte, and is indexed by a unique address:

There is one address space for each program in the system. Address spaces are private, and programs do not see each other’s address spaces.

An address is thus a unique location in memory addressable by the program. The address of a variable is that of the first byte holding this variable. You can obtain the address of a variable with the & operator:

int x = 42;

printf("0x%x\n", &x);  // print the address of x in hexadecimal

If we assume the following memory layout:

Then, in the example above, the address of x being the address of the first byte holding it, the program will print 0xd35442fc.

Pointers: Definition

Now we can define what a pointer is: a pointer is simply a variable whose value is an address. It can be the address of another variable, or of any other byte of the address space – including parts of the address space containing nothing.

A pointer is declared with the * operator, preceded by the type of the data it references, for example here we have ptr which is a pointer of int, so its type is int *:

int x = 42;
int *ptr = &x;        // ptr is a pointer of int and _points to_ x
printf("%d\n", *ptr); // dereference ptr, print the value of x

ptr holds the address of x; we say that ptr points to x.

A key operation we can realise on a pointer is to access the memory it points to. This is realised with the * operator; in the code above, we use it to print the value of x through ptr. The action of accessing the data pointed to by a pointer with the * operator is called dereferencing the pointer.

If we look at how things are laid out in memory we’ll get the following:

Our integer x is located somewhere in memory, and assuming we are on x86-64, its size is 4 bytes. The address of x is that of the first byte holding it: 0xd35442fc. When ptr is set to point to x, its value is set to that address, and we can represent this relationship on the diagram with an arrow: ptr points to x. Notice also that the size of pointers on a given architecture is the width of the memory address bus: 8 bytes on modern 64-bit CPUs.

Now that we know what pointers are, let’s see in what situations they are beneficial.

Passing References Across Functions

Argument Passing in C. In C, upon a function call, a copy of the arguments is made in memory to create the parameters of the called function. Check out this example which is a naive attempt at swapping the value of two variables in main:

int swap(int a, int b) {
  int tmp = a;
  a = b;
  b = tmp;
}

int main() {
  x = 10;
  y = 100;
  swap(x, y);
  printf("x=%d, y=%d\n", x, y); // x is still 10 and y is still 100: the swap operated
                               // on a and b in the function swap's stack frame
}

x and y are passed as arguments to swap, which exchanges the values of its parameters a and b. If we run this program, we’ll see that the values of x and y are unchanged after the function call. Indeed, when swap was called, the program made copies of the values of x and y for the parameters a and b, swapped the copies’ values, and then discarded these copies as the function swap returned:

Accessing the Calling Context with References. If we actually want swap to exchange the values of x and y in main’s memory, we need to pass their addresses, and not their values, as parameters:

int swap(int *a, int *b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

int main() {
  x = 10;
  y = 100;
  swap(&x, &y);
  printf("x=%d, y=%d\n", x, y);
}

Here we have updated the function’s parameter types to be pointers to integers, and the swap is now realised on the pointed-to values by dereferencing the pointers. In main, we no longer pass x and y to the function but rather their addresses, obtained with the & operator.

If you run this program, you will see that the values of x and y are successfully swapped after the call to swap. What happens is that a copy of the addresses of x and y is created for the pointers a and b. So we have a pointing to x, and b pointing to y. By dereferencing these pointers, the swap function is able to update the pointed-to values and perform the swap within the area of memory allocated for the main function:

“Returning” Several Values. The previous example showed us how pointers can be used to let a function manipulate its calling context. This is useful in several scenarios, for example you need pointers when you want a function to transmit back to its calling context (i.e., “return”) more than a single value, or to return complex data structures or arrays. We can study an example here, with the multiply_and_divide function taking 2 numbers n1 and n2 as parameters. We want this function to “return” three things:

1. The product of n1 by n2
2. The result of the division of n1 by n2
3. An error code indicating the success or failure (if n2 is 0) of the operation

We can’t achieve that with a traditional single return statement. We rather use pointers:

// we want this function to "return" 3 things: the product and quotient of n1 by n2,
// as well as an error code in case the division is impossible
int multiply_and_divide(int n1, int n2, int *product, int *quotient) {
    if(n2 == 0) return -1;      // Can't divide if n2 is 0
    *product = n1 * n2;
    *quotient = n1 / n2;
    return 0;
}

int main(int argc, char **argv) {
    int p, q, a = 5, b = 10;
    if(multiply_and_divide(a, b, &p, &q) == 0) {
        printf("10*5 = %d\n", p); printf("10/5 = %d\n", q);
    }
}

multiply_and_divide stores the product and quotient of n1 and n2 in variables allocated by the caller, whose addresses are passed as the third and fourth parameters. The function also returns an error code to indicate the success/failure of the operation.

Lightweight Function Calls with Large Data Structures.

Another key point is that passing or returning a pointer to/from a function is also very quick: a pointer is an address, so its size is just 8 bytes on modern 64-bit architectures. If you need to pass or return large data structures, consider rather passing pointers to the objects in question, which is much more efficient than passing the values of the large data structures as parameters/return values. If their size is large, the copies that must happen 1) for the parameters upon a function call and 2) for the return value upon function return will be very costly, both in terms of execution time and regarding memory consumption.

C Arrays are Pointers

In C, arrays are implemented under the hood with pointers. The variable representing an array is a pointer to the first byte of the array in memory:

void negate_int_array(int *ptr, int size) { // function taking a pointer as parameter
    for(int i=0; i<size; i++)               // also need the size to iterate properly
        ptr[i] = -ptr[i];      // use square brackets like a standard array
                               // equivalent to *(ptr+i) = -(*(ptr+i))
}

int main(int argc, char **argv) {
    int array[] = {1, 2, 3, 4, 5, 6, 7};
    negate_int_array(array, 7); // to get the pointer just use the array's name
    for(int i=0; i<7; i++)
        printf("array[%d] = %d\n", i, array[i]);
    return 0;
}

In the example above, in main we define an array of integers with 7 elements, and we pass it as a parameter to negate_int_array, which negates all elements of the array. As you can see, this function takes a pointer to an integer as parameter. Within the function’s body, that pointer is indexed with square brackets, like a standard array. This is equivalent to summing an offset i to the pointer and dereferencing the result. As you can see, the array array and the pointer ptr are equivalent: they both represent a pointer to the first byte of the array in memory:

Custom Data Structures and Pointers

In C, we very often create pointers to custom data structures. Here we have an example with ptr pointing to ms.

typedef struct {
    int x;
    float f;
    char *s;
} my_struct;

my_struct ms = {42, 2.5, "hello"};
my_struct *ptr = &ms;

printf("%d\n", (*ptr).x); // prints "42"

To access a field of ms, we need to dereference the pointer first with the * operator, then access the field with the . operator. Parentheses are needed here because of operator precedence. Writing all this is a bit cumbersome, so as a shortcut you can use the arrow operator ->, which both dereferences the pointer on its left and accesses the field on its right:

printf("%s\n", ptr->s);   // prints "hello", equivalent to (*ptr).s

Pointers Chains

Because a pointer is a variable, it can itself be pointed to by another pointer. We talk in that case of a pointer of pointer. And with this we can create pointer chains linking memory locations. Consider the following code:

int value = 42;         // integer
int *ptr1 = &value;     // pointer of integer
int **ptr2 = &ptr1;     // pointer of pointer of integer
int ***ptr3 = &ptr2;    // pointer of pointer of pointer of integer

printf("ptr1: %p, *ptr1: %d\n", ptr1, *ptr1);
printf("ptr2: %p, *ptr2: %p, **ptr2: %d\n", ptr2, *ptr2, **ptr2);
printf("ptr3: %p, *ptr3: %p, **ptr3: %p, ***ptr3: %d\n",
        ptr3, *ptr3, **ptr3, ***ptr3);

We have an integer value. ptr1 is a pointer of int, i.e., an int *, and points to the integer. Then we want to have something that points to ptr1: that’s a pointer of pointer of int, an int **. It’s ptr2, whose value is the address of ptr1. Then we create another level in the chain with ptr3, which is a pointer of pointer of pointer of int, an int ***, pointing to ptr2. And next we print the value of each pointer in the chain and what they point to. The chain can be illustrated as follows:

Function Pointers

Function pointers are a special type of pointer that reference functions. Rather than taking the address of some data, they take the address of machine code. More precisely, a function pointer pointing to function f takes as value the address of the first byte of machine code of the function f. Consider the following example:

#include <stdio.h>

void greet_v1(char *name) {
  printf("Good morning, %s!\n", name);
}

void greet_v2(char *name) {
  printf("Good evening, %s!\n", name);
}

int main() {
  // declare a function pointer to a function that returns void
  // and takes a char * as parameter:
  void (*func_ptr)(char *);  
  char *username = "Pierre";
    
  func_ptr = greet_v1;  // set func_ptr to point to greet_v1
  func_ptr(username);   // call greet_v1 through the pointer

  func_ptr = greet_v2;  // set func_ptr to point to greet_v2
  func_ptr(username);   // call greet_v2 through the pointer

  return 0;
}

A function pointer is declared with the return type of the pointed function (here void), the name of the pointer (here func_ptr), and the type or types of parameters of the pointed function, here a single parameter char *. A function pointer can then be set to point to various functions fitting the prototype it was defined with; here we make it point to greet_v1 and then greet_v2. This is a simple assignment using the function name to obtain its address. The function pointer can be called by using its name as one would do for a function.