Pointers and arrays

Addresses

Memory, a sequence of cells

For the program, memory is a long sequence of numbered bytes. A byte's number is its address. An int variable takes up four consecutive bytes (on today's machines). Its address is that of the first one. To follow by hand what a program does, you can write this memory down in a table, one row per variable: that is the supplementary chapter that follows this one, “The memory table”.

Two operators are enough to handle them:

• &x gives the address of x: this is referencing;
• *p denotes what is found at the address contained in p: this is dereferencing.

#include <stdio.h>

int main(void)
{
    int a = 42;
    int *p = &a;

    printf("a = %d, *p = %d\n", a, *p);
    *p = 7;
    printf("a = %d, *p = %d\n", a, *p);
    printf("&a = %p, p = %p\n", (void *)&a, (void *)p);
    return 0;
}

a = 42, *p = 42
a = 7, *p = 7
&a = 0x7ffd8d1802dc, p = 0x7ffd8d1802dc

p contains the address of a. So writing into *p is writing into a. The %p format prints an address; it expects a void *, hence the conversion. The printed address changes from one run to the next: the system places the stack at a different spot at each start, to make attackers' lives harder.

Lvalues

*p is used in two ways, depending on its place in the assignment:

• on the right of the = (or in any expression), *p is the value stored at the address: b = 1 + *p;;
• on the left of the =, *p denotes the cell at that address, where the result is stored: *p = 7;.

You can only take the address of an lvalue. &x, &t[4], &s.champ make sense; &42 or &(x + 1) do not: they are computed values, stored nowhere.

char buf[32];
char *s = &buf[4];   /* s points to the fifth character of buf */

* and & are the inverse of each other: *&a is a itself.

Passing by address

In C, a function's arguments are always passed by value: the function receives a copy. So this function swaps nothing:

#include <stdio.h>

void echanger_faux(int a, int b)
{
    int c = a;
    a = b;
    b = c;
}

int main(void)
{
    int x = 0, y = 42;

    echanger_faux(x, y);
    printf("x = %d, y = %d\n", x, y);
    return 0;
}

x = 0, y = 42

It swapped its copies a and b, which vanish on return. For a function to modify a variable of the caller, you pass it the address of the variable:

#include <stdio.h>

/* echanger(a, b) swaps the integers pointed to by a and b */
void echanger(int *a, int *b)
{
    int c = *a;
    *a = *b;
    *b = c;
}

int main(void)
{
    int x = 0, y = 42;

    printf("x = %d, y = %d\n", x, y);
    echanger(&x, &y);
    printf("x = %d, y = %d\n", x, y);
    return 0;
}

x = 0, y = 42
x = 42, y = 0

Two things to notice. The function works on *a and *b, the cells pointed to. And the caller writes &x and &y: it is at the call that you see a variable may be modified. This is how the “global parameters” (passed by reference) of the algorithmic language are translated. scanf("%d", &n) works the same way: scanf must store what it reads in n, so it needs its address.

Pointer types

Declaring

The star goes in front of the variable's name, and it only applies to that variable:

int x, *y, t[32];

declares an integer x, a pointer to integer y, and an array of 32 integers t. The order does not matter: int *y, x, t[32]; declares exactly the same thing.

When a pointer on its own represents an abstract piece of data (a linked list, a tree), it is often hidden behind a type alias, with typedef. We will come back to this in chapter 4.

The null pointer

NULL (defined in stddef.h, and also in stdio.h and stdlib.h) is an address that designates no cell. A pointer that points to nothing must be NULL. Dereferencing NULL is an error: on Linux, the program is killed by the system (“segmentation fault”).

An uninitialised pointer, on the other hand, is not NULL: it contains anything at all, and dereferencing it writes anywhere.

void *

void * is the type of “untyped” addresses: an address, saying nothing about what lies behind it. Any pointer (to data) converts to void * and back, without an explicit conversion. You cannot dereference a void *: you would not know how many bytes to read, nor how to interpret them.

The typical example is malloc, which reserves memory without knowing what will be put in it:

void *malloc(size_t size);

Its result is stored directly in a pointer of the desired type: int *t = malloc(10 * sizeof (int));.

Arrays

An array is not a pointer

int t[10];

reserves ten consecutive integers, that is 40 bytes. There is no hidden pointer anywhere: t is the name of that block. But in almost every expression, t is converted to the address of its first cell, &t[0], of type int *. The array is said to decay into a pointer. That is why you can write int *p = t;.

This conversion does not take place in two cases: under sizeof, and under &. You can see the difference with sizeof, which gives the size in bytes:

#include <stdio.h>

void f(int t[])
{
    printf("dans f : sizeof t = %zu\n", sizeof t);
}

int main(void)
{
    int t[10];
    int *p = t;

    printf("sizeof t = %zu\n", sizeof t);
    printf("sizeof p = %zu\n", sizeof p);
    printf("nombre de cases : %zu\n", sizeof t / sizeof t[0]);
    f(t);
    return 0;
}

sizeof t = 40
sizeof p = 8
nombre de cases : 10
dans f : sizeof t = 8

In main, t really is an array of 40 bytes, and p a pointer of 8 bytes (on a 64-bit machine). But in f, t only measures 8 bytes: a parameter declared as an array is a pointer. void f(int t[]) and void f(int *t) are exactly the same declaration. A function never receives an array, only the address of its first cell; so it cannot know its size, you have to pass it. gcc -Wall points this out, as it happens:

taille.c:5:48: warning: 'sizeof' on array function parameter 't' will return size of 'int *'

That is why this program does not compile with -Werror: it is there to show the trap.

Accessing cells

The access t[i] is defined by pointer arithmetic: t[i] is, by definition, *(t + i). So it works just as well on an array as on a pointer. Two consequences:

• No check is made on indices. t[10] on a ten-cell array reads (or writes) the memory that follows the array.
• A negative index is accepted by the compiler: p[-1] is *(p - 1), the preceding cell. That is correct if p points into the middle of an array, and undefined behaviour otherwise.

Two-dimensional arrays

int t[4][3] is an array of 4 rows, each an array of 3 integers. The 12 integers are stored row by row, one after the other:

#include <stdio.h>

/* sum of the cells of a matrix with h rows and 3 columns */
int somme_matrice(int t[][3], size_t h)
{
    int r = 0;
    for (size_t j = 0; j < h; j++)
        for (size_t i = 0; i < 3; i++)
            r += t[j][i];
    return r;
}

int main(void)
{
    int t[4][3];
    int n = 0;

    for (size_t y = 0; y < 4; y++)
        for (size_t x = 0; x < 3; x++)
            t[y][x] = ++n;

    for (size_t y = 0; y < 4; y++) {
        for (size_t x = 0; x < 3; x++)
            printf("%02d ", t[y][x]);
        printf("\n");
    }
    printf("\nsomme = %d\n\n", somme_matrice(t, 4));

    /* the same memory, read as 12 integers in a row */
    int *lin = &t[0][0];
    for (size_t k = 0; k < 12; k++)
        printf("%02d ", lin[k]);
    printf("\n");
    return 0;
}

01 02 03 
04 05 06 
07 08 09 
10 11 12 

somme = 78

01 02 03 04 05 06 07 08 09 10 11 12 

To find t[j][i], the compiler computes the offset j * 3 + i: it must know the width of a row. That is why the parameter is written int t[][3]: the first dimension may stay empty (the parameter is a pointer to rows of 3 integers), not the second. A function written this way can only handle matrices with 3 columns.

For a matrix whose two dimensions are only known at run time, everything is stored in a one-dimensional array, and you compute the offset yourself:

/* the cell (x, y) of a matrix of width w, stored row by row */
int lire_case(const int t[], size_t w, size_t x, size_t y)
{
    return t[x + y * w];
}

The width w is necessary, and sufficient, to find each cell.

Pointer arithmetic

Adding an integer n to a pointer moves it forward by n elements, not by n bytes: if p is an int *, p + 1 is the address of the next integer, 4 bytes further on.

#include <stdio.h>

int main(void)
{
    int t[4] = {10, 20, 30, 40};
    int *p = t;
    char *c = (char *)t;

    printf("p     = %p\n", (void *)p);
    printf("p + 1 = %p\n", (void *)(p + 1));
    printf("c + 1 = %p\n", (void *)(c + 1));
    printf("*(p + 2) = %d, t[2] = %d, 2[t] = %d\n", *(p + 2), t[2], 2[t]);
    printf("&t[3] - &t[0] = %td\n", &t[3] - &t[0]);
    for (int *q = t; q < t + 4; q++)
        printf("%d ", *q);
    printf("\n");
    return 0;
}

p     = 0x7ffe6e904bb0
p + 1 = 0x7ffe6e904bb4
c + 1 = 0x7ffe6e904bb1
*(p + 2) = 30, t[2] = 30, 2[t] = 30
&t[3] - &t[0] = 3
10 20 30 40 

• p + 1 moves forward by 4 bytes, c + 1 by just one: the same address, seen as int * or as char *.
• *(p + 2) and t[2] are the same thing. And since t[2] is *(t + 2), it is also *(2 + t), hence 2[t]: a curiosity never to be written, but one that shows clearly that [] is only a shorthand.
• The difference of two pointers into the same array is a number of elements (of type ptrdiff_t, printed with %td).
• You can walk through an array with a pointer, up to the address that follows the last cell, t + 4. That particular address is allowed to exist and to be compared, not to be dereferenced.

Character strings

An array of characters terminated by zero

A string, in C, is a sequence of characters terminated by the null character '\0' (byte 0). There is no string type: you handle an array of char, or a pointer to its first character. All the functions of string.h (strlen, strcpy, strcmp…) move forward until the '\0': a string without it makes them read the memory that follows, until they happen to hit a null byte.

So "bonjour" takes up 8 bytes: seven letters and the final zero.

Literal or array

char *s1 = "bonjour";
char s2[] = "bonjour";

These two lines look alike and do not do the same thing at all.

• s1 is a pointer, initialised with the address of a literal string. The literal is stored by the compiler in a read-only area (chapter 3). You can read s1[0], but writing to it is undefined behaviour, and on Linux the program is killed.
• s2 is an array of 8 characters, initialised by copying the literal. It belongs to the program, and you can modify it.

#include <stdio.h>

int main(void)
{
    char *s1 = "bonjour";
    char s2[] = "bonjour";

    s2[0] = 'B';
    printf("%s %s\n", s1, s2);
    printf("sizeof s1 = %zu, sizeof s2 = %zu\n", sizeof s1, sizeof s2);
    s1[0] = 'B';
    printf("%s\n", s1);
    return 0;
}

bonjour Bonjour
sizeof s1 = 8, sizeof s2 = 8
Segmentation fault (core dumped)

Both sizeofs are 8, but by coincidence: 8 bytes for the pointer s1, 8 characters for the array s2. The compiler says nothing about s1[0] = 'B': for historical reasons, a literal has type char[], not const char[]. The -Wwrite-strings option makes it a const char[], and gcc then flags the initialisation of s1.

const

const promises that a value will not be modified, and the compiler enforces the promise.

const char *s = "chaine";
s[0] = 'C';

error: assignment of read-only location '*s'

const char *s reads “s is a pointer to constant chars”: it is what is pointed to that must not change. s itself can change, and point elsewhere. (A pointer that cannot change is written char *const s, which is rarer.)

A const parameter tells the reader, right from the signature, that the function does not modify what is passed to it:

size_t longueur(const char *s)
{
    size_t n = 0;
    while (s[n] != '\0')
        n++;
    return n;
}