Data structures

Structures

Grouping fields

A structure groups several values, possibly of different types, under a single name. Each one is a field.

#include <stdio.h>

struct point
{
    int x;
    int y;
};

typedef struct point t_point;

void translater(t_point *p, int dx, int dy)
{
    p->x += dx;
    p->y += dy;
}

int main(void)
{
    t_point a = { 1, 2 };
    t_point b = a;          /* field-by-field copy */
    translater(&a, 10, 10);
    printf("a = (%d, %d), b = (%d, %d)\n", a.x, a.y, b.x, b.y);
    printf("sizeof (t_point) = %zu\n", sizeof (t_point));
    return 0;
}

a = (11, 12), b = (1, 2)
sizeof (t_point) = 8

• struct point is the name of the type. It can be given a shorter name with typedef: typedef struct point t_point; makes t_point a synonym for struct point. The t_ prefix is only a convention, to recognise a type name at a glance.
• a.x designates the field x of the structure a.
• When you have a pointer p to a structure, p->x designates the field x of the structure pointed to. It is an abbreviation of (*p).x; the parentheses are necessary, because . takes precedence over *.
• The assignment b = a copies the whole structure. Modifying a afterwards does not change b. The same goes when a structure is passed to a function: it receives a copy. For translater to modify the caller's point, it must be given its address (chapter 2).

Recursive structures

A linked list is made of links; each link contains a value and the address of the next link. A structure cannot contain itself (it would be of infinite size), but it can contain a pointer to a structure of its own type:

typedef struct s_liste *t_liste;

struct s_liste
{
    int     val;
    t_liste suivant;
};

The typedef can come before the definition of the structure: to declare a pointer to struct s_liste, the compiler does not need to know its fields, since all pointers have the same size.

Here, the typedef does not name the structure, but a pointer to it. A list is the address of its first link, and the empty list is the pointer NULL. This is exactly Caml's list: NULL plays the role of [], and a link that of x :: reste.

Abstract types

Hiding the representation

Each data structure is stored in its own module, as in chapter 1: a header that announces the operations, a source file that defines them. The important point is what goes in the header.

liste.h:

#ifndef LISTE_H
#define LISTE_H

#include <stddef.h>

typedef struct s_liste *t_liste;

#define liste_vide() (NULL)
#define est_vide(l) ((l) == NULL)

t_liste ajouter(int x, t_liste l);
int     tete(t_liste l);
t_liste queue(t_liste l);
size_t  longueur(t_liste l);
t_liste chercher(int x, t_liste l);
void    inserer(int x, t_liste *l);
void    detruire(t_liste l);

#endif

The header says that t_liste is a pointer to a struct s_liste, but not what that structure contains. Its definition is in liste.c, and nowhere else. A file that includes liste.h can declare lists, pass them to the module's functions, but cannot write l->val: the compiler refuses, it does not know the fields.

The benefit is the same as with Caml's modules: you can change the representation (add a field, switch from a list to an array) without touching the code that uses it. And no one can break the structure's invariants by going and modifying a field by hand.

liste.c:

#include <stdio.h>
#include <stdlib.h>
#include "liste.h"

struct s_liste
{
    int     val;
    t_liste suivant;
};

t_liste ajouter(int x, t_liste l)
{
    t_liste t = malloc(sizeof (struct s_liste));
    if (t == NULL)
    {
        perror("ajouter");
        exit(1);
    }
    t->val = x;
    t->suivant = l;
    return t;
}

int tete(t_liste l)
{
    return l->val;
}

t_liste queue(t_liste l)
{
    return l->suivant;
}

size_t longueur(t_liste l)
{
    size_t n = 0;
    for (; l != NULL; l = l->suivant)
        n++;
    return n;
}

t_liste chercher(int x, t_liste l)
{
    while (l != NULL && l->val != x)
        l = l->suivant;
    return l;
}

void detruire(t_liste l)
{
    while (l != NULL)
    {
        t_liste t = l;
        l = l->suivant;
        free(t);
    }
}

ajouter makes a new link on the heap with malloc (chapter 3), and checks that it got it. chercher returns the link that contains x, or NULL. detruire frees the links one by one; you must keep the address of the next one before freeing the current link, because after free(t), reading t->suivant is forbidden.

tete and queue do not check that the list is non-empty: it is up to the caller to do so, with est_vide. This is written in the header's comment, or a test is added that stops the program.

A program that uses it

essai_liste.c:

#include <stdio.h>
#include "liste.h"

void afficher(t_liste l)
{
    for (; !est_vide(l); l = queue(l))
        printf("%d ", tete(l));
    printf("\n");
}

int main(void)
{
    t_liste l = liste_vide();
    int valeurs[] = { 5, 1, 4, 1, 9, 2, 6 };

    for (size_t i = 0; i < sizeof valeurs / sizeof valeurs[0]; i++)
        inserer(valeurs[i], &l);
    afficher(l);
    printf("longueur : %zu\n", longueur(l));
    printf("9 %s\n", chercher(9, l) != NULL ? "trouvé" : "absent");
    printf("3 %s\n", chercher(3, l) != NULL ? "trouvé" : "absent");
    detruire(l);
    return 0;
}

afficher only uses the operations of the header. sizeof valeurs / sizeof valeurs[0] is the number of cells in the array: its total size divided by that of one cell (this only works on a real array, not on a pointer, chapter 2).

The Makefile can rely on make's implicit rules, since it already knows how to build a .o from a .c: you only need to give the dependencies. $@ is the target, $^ the list of its prerequisites.

CC = gcc
CFLAGS = -std=c11 -Wall -Wextra -Werror -O2

essai_liste: essai_liste.o liste.o
	$(CC) -o $@ $^

essai_liste.o: essai_liste.c liste.h
liste.o: liste.c liste.h

clean:
	rm -f essai_liste *.o

$ make
gcc -std=c11 -Wall -Wextra -Werror -O2   -c -o essai_liste.o essai_liste.c
gcc -std=c11 -Wall -Wextra -Werror -O2   -c -o liste.o liste.c
gcc -o essai_liste essai_liste.o liste.o
$ ./essai_liste
1 1 2 4 5 6 9
longueur : 7
9 trouvé
3 absent

Passing a list to a function

By value, or by address

In C, all parameters are passed by value: the function receives a copy. For a pointer, it is a copy of the pointer, which designates the same links. So the function can modify the links; it cannot modify the caller's variable that contains the pointer.

void vider_rate(t_liste l)
{
    detruire(l);
    l = liste_vide();       /* only changes the copy */
}

void vider(t_liste *l)
{
    detruire(*l);
    *l = liste_vide();      /* changes the caller's variable */
}

After vider_rate(l), the links are freed, but the caller's variable l still contains the address of the old first link: it is a dangling pointer, which must never be followed again. After vider(&l), l is NULL.

Algorithmic languages often distinguish input parameters (passed by value) from input-output parameters (passed by reference, which the procedure may modify). C has no passing by reference: it is simulated by passing the address of the variable, as for echange in chapter 2. A function that must change which link is at the head of the list therefore receives a t_liste *.

There are two ways of returning a new start of list:

• return it as the result: t_liste ajouter(int x, t_liste l), called as l = ajouter(x, l);;
• receive the list by address: void inserer(int x, t_liste *l), called as inserer(x, &l);. This is the only solution when the result is already used for something else, or so that the caller cannot forget the assignment.

Inserting into a sorted list

inserer adds x at its place in a list sorted in increasing order. The first idea distinguishes two cases: insertion at the head, which changes the caller's variable, and insertion further on, which changes the suivant field of the previous link.

void inserer(int x, t_liste *l)
{
    if (*l == NULL || (*l)->val >= x)
        *l = ajouter(x, *l);
    else
    {
        t_liste prec = *l;
        while (prec->suivant != NULL && prec->suivant->val < x)
            prec = prec->suivant;
        prec->suivant = ajouter(x, prec->suivant);
    }
}

We stop on the previous link (the one whose next is too large, or does not exist), because it is its suivant field that must be modified.

But both cases do the same thing: replace a pointer (the caller's variable, or a suivant field) with the address of a new link. If we keep the address of that pointer rather than the link, there is only one case left:

void inserer(int x, t_liste *l)
{
    while (*l != NULL && (*l)->val < x)
        l = &(*l)->suivant;
    *l = ajouter(x, *l);
}

At the start, l points to the caller's variable. At each turn, it moves on to the suivant field of the current link. When we stop, *l is the pointer to replace, whichever it is. &(*l)->suivant reads &((*l)->suivant): the address of the suivant field of link *l.

Reading a signature

C uses the star for many things: passing by address, an array, a string, a linked structure, a generic pointer. Looking at f(int *p), you cannot tell which. Hence a few conventions, so that a function's signature says by itself how to use it:

• Data structures: the pointer is hidden by a typedef (t_liste, t_arbre). No star.
• Arrays: in a parameter, int t[] means exactly the same thing as int *t. Write the brackets for an array.
• Strings: they are arrays of characters; write char s[], or const char *s when the function does not modify it.
• What is left is the explicit star: it signals passing by address, a variable of the caller that the function will modify, or more rarely a generic pointer void *.

A few signatures, and what they say:

/* t_liste is abstract: we do not need to know it is a pointer. */
t_liste ajouter(int x, t_liste l);

/* The head of the list may change: the list is passed by address. */
void inserer(int x, t_liste *l);

/* v is an array; *somme will receive a second result. The function
 * probably returns the number of elements, and stores their sum in *somme.
 * But how does it know the size of v? A parameter is missing. */
size_t compter_sommer(int v[], int *somme);

One ambiguity remains: is char *t[] an array of strings, or the address of a string that will be modified? The syntax does not say. It is the former (argv, in int main(int argc, char *argv[]), is an array of strings), but only a comment, or a typedef, can tell the reader.

A generic swap

echange(int *a, int *b) swaps two integers. To swap two values of any type, we go through void *, and must then give the size of the values, since void * does not know it. The copy is done byte by byte, with memcpy:

#include <stdlib.h>
#include <string.h>

void echange_gen(void *a, void *b, size_t taille)
{
    void *tmp = malloc(taille);
    if (tmp == NULL)
        abort();
    memcpy(tmp, a, taille);
    memcpy(a, b, taille);
    memcpy(b, tmp, taille);
    free(tmp);
}

double u = 1.5, v = 2.5;
echange_gen(&u, &v, sizeof u);          /* u = 2.5, v = 1.5 */

char *s = "bonjour", *t = "au revoir";
echange_gen(&s, &t, sizeof s);          /* swaps the two pointers */

This is how the generic functions of the standard library, such as qsort, are written. Type checking is lost: nothing prevents passing a wrong size. And for two integers, it is much slower than echange.

A queue

A queue is a list where you add at one end and remove at the other: first in, first out. For both operations to take constant time, you need access to both ends. A trick allows it with a single pointer: the list is circular, and we keep the address of the last link. Its next is the first.

flowchart LR
    F([f]) --> C
    A[first] --> B[second] --> C[last] --> A

We store void * in it, so as to be able to put any data in it: trees, strings…

file.h:

#ifndef FILE_H
#define FILE_H

typedef struct s_file *t_file;

#define file_vide() (NULL)
#define file_est_vide(f) ((f) == NULL)

t_file enfiler(void *x, t_file f);
void  *defiler(t_file *f);

#endif

file.c:

#include <stdio.h>
#include <stdlib.h>
#include "file.h"

struct s_file
{
    void  *val;
    t_file suivant;
};

/* f points to the last link; the last one points to the first. */
t_file enfiler(void *x, t_file f)
{
    t_file t = malloc(sizeof (struct s_file));
    if (t == NULL)
    {
        perror("enfiler");
        exit(1);
    }
    t->val = x;
    if (f == NULL)
        t->suivant = t;
    else
    {
        t->suivant = f->suivant;
        f->suivant = t;
    }
    return t;
}

void *defiler(t_file *f)
{
    t_file premier = (*f)->suivant;
    void  *x = premier->val;
    if (premier == *f)
        *f = NULL;
    else
        (*f)->suivant = premier->suivant;
    free(premier);
    return x;
}

• enfiler (enqueue) inserts the new link after the last one, so between the last and the first, and the new link becomes the last: we return it. A queue of a single link points to itself.
• defiler (dequeue) removes the first link (the next of the last one). It already returns the value, so it receives the queue by address in order to be able to modify it. If the first was also the last, the queue becomes empty.

char  *mots[] = { "un", "deux", "trois" };
t_file f = file_vide();

for (int i = 0; i < 3; i++)
    f = enfiler(mots[i], f);
while (!file_est_vide(f))
    printf("%s\n", (char *)defiler(&f));

un
deux
trois

Binary trees

The module

A binary tree is either empty, or made of a node that carries a key and two subtrees. Same principle as the list: the empty tree is NULL.

arbre.h:

#ifndef ARBRE_H
#define ARBRE_H

#include <stddef.h>

typedef struct s_arbre *t_arbre;

t_arbre noeud(int cle, t_arbre g, t_arbre d);
int     hauteur(t_arbre a);
size_t  taille(t_arbre a);
void    afficher_profondeur(t_arbre a);
void    afficher_largeur(t_arbre a);
void    detruire_arbre(t_arbre a);

#endif

The beginning of arbre.c:

#include <stdio.h>
#include <stdlib.h>
#include "file.h"
#include "arbre.h"

struct s_arbre
{
    int     cle;
    t_arbre g, d;
};

t_arbre noeud(int cle, t_arbre g, t_arbre d)
{
    t_arbre a = malloc(sizeof (struct s_arbre));
    if (a == NULL)
    {
        perror("noeud");
        exit(1);
    }
    a->cle = cle;
    a->g = g;
    a->d = d;
    return a;
}

size_t taille(t_arbre a)
{
    return a == NULL ? 0 : 1 + taille(a->g) + taille(a->d);
}

void detruire_arbre(t_arbre a)
{
    if (a == NULL)
        return;
    detruire_arbre(a->g);
    detruire_arbre(a->d);
    free(a);
}

Recursive functions are written as in Caml: one case for the empty tree, one case for the node. detruire_arbre frees both subtrees before the node, since it is in the node that their addresses are stored.

The height, and a trap with integers

By convention, a leaf (a node without children) has height 0, and the empty tree -1. So the height is a signed integer:

int hauteur(t_arbre a)
{
    if (a == NULL)
        return -1;
    int hg = hauteur(a->g);
    int hd = hauteur(a->d);
    return 1 + (hg > hd ? hg : hd);
}

Two traversals

The depth-first traversal visits a node, then its whole left subtree, then its whole right subtree. We print each key indented according to its depth:

static void profondeur(t_arbre a, int decalage)
{
    if (a == NULL)
        return;
    printf("%*s%d\n", decalage, "", a->cle);
    profondeur(a->g, decalage + 2);
    profondeur(a->d, decalage + 2);
}

void afficher_profondeur(t_arbre a)
{
    profondeur(a, 0);
}

%*s prints a string over a width given as an argument: here the empty string, padded with decalage spaces. static makes profondeur invisible outside arbre.c: it is an auxiliary function, which has no place in the header.

The breadth-first traversal visits the nodes level by level: the root, then its children, then its grandchildren. We use the queue: remove a node, print it, add its children at the end of the queue. To start a new line at the end of each level, we put a marker in the queue, NULL: when it is removed, the whole level has been printed, and the whole next level is in the queue, behind it.

void afficher_largeur(t_arbre a)
{
    if (a == NULL)
        return;
    t_file f = file_vide();
    f = enfiler(a, f);
    f = enfiler(NULL, f);
    while (!file_est_vide(f))
    {
        t_arbre t = defiler(&f);
        if (t != NULL)
        {
            printf("%d ", t->cle);
            if (t->g != NULL)
                f = enfiler(t->g, f);
            if (t->d != NULL)
                f = enfiler(t->d, f);
        }
        else
        {
            printf("\n");
            if (!file_est_vide(f))
                f = enfiler(NULL, f);
        }
    }
}

t_arbre a = noeud(1,
                  noeud(2, noeud(4, NULL, NULL), NULL),
                  noeud(3, noeud(5, NULL, NULL), noeud(6, NULL, NULL)));

printf("taille %zu, hauteur %d\n", taille(a), hauteur(a));
afficher_profondeur(a);
afficher_largeur(a);
detruire_arbre(a);

taille 6, hauteur 2
1
  2
    4
  3
    5
    6
1
2 3
4 5 6

The program is compiled with both modules: gcc -std=c11 -Wall -Wextra -Werror essai_arbre.c arbre.c file.c.

A variable-size vector

Chapter 3 introduced the dynamic vector: an array allocated on the heap, enlarged with realloc when it is full, by doubling its capacity. Here is the complete version, as an abstract type.

vecteur.h:

#ifndef VECTEUR_H
#define VECTEUR_H

#include <stddef.h>

typedef struct s_vecteur *t_vecteur;

t_vecteur vecteur_nouveau(void);
void      vecteur_ajouter(t_vecteur v, int x);
int       vecteur_lire(t_vecteur v, size_t i);
size_t    vecteur_longueur(t_vecteur v);
void      vecteur_detruire(t_vecteur v);

#endif

vecteur.c:

#include <stdio.h>
#include <stdlib.h>
#include "vecteur.h"

struct s_vecteur
{
    size_t longueur;    /* cells in use */
    size_t capacite;    /* cells allocated */
    int   *cases;
};

static void *allouer(void *p, size_t n)
{
    p = realloc(p, n);
    if (p == NULL)
    {
        perror("vecteur");
        exit(1);
    }
    return p;
}

t_vecteur vecteur_nouveau(void)
{
    t_vecteur v = allouer(NULL, sizeof (struct s_vecteur));
    v->longueur = 0;
    v->capacite = 1;
    v->cases = allouer(NULL, sizeof (int));
    return v;
}

void vecteur_ajouter(t_vecteur v, int x)
{
    if (v->longueur == v->capacite)
    {
        v->capacite *= 2;
        v->cases = allouer(v->cases, v->capacite * sizeof (int));
    }
    v->cases[v->longueur++] = x;
}

int vecteur_lire(t_vecteur v, size_t i)
{
    if (i >= v->longueur)
    {
        fprintf(stderr, "vecteur_lire : indice %zu hors limites\n", i);
        exit(1);
    }
    return v->cases[i];
}

size_t vecteur_longueur(t_vecteur v)
{
    return v->longueur;
}

void vecteur_detruire(t_vecteur v)
{
    free(v->cases);
    free(v);
}

• realloc(NULL, n) behaves like malloc(n): a single function allouer serves both purposes, and checks the result.
• Because the type is abstract, vecteur_lire can check the index, which C never does on an array. No one can get round the check by reading v->cases[i] directly.
• vecteur_detruire frees the array then the structure: in the other order, we would read v->cases in an area already freed.

t_vecteur v = vecteur_nouveau();
for (int i = 0; i < 1000; i++)
    vecteur_ajouter(v, i * i);
printf("%zu cases, la dernière vaut %d\n",
       vecteur_longueur(v), vecteur_lire(v, vecteur_longueur(v) - 1));
vecteur_lire(v, 1000);

1000 cases, la dernière vaut 998001
vecteur_lire : indice 1000 hors limites