Cours 3 : Structures de données en C, Types VS Classes de stockage, Arithmétique des pointeurs

Structures de données

SdD qu’on peut fabriquer dans un langage (exs) :

  • tableaux / records
    • en C : un zone où ont stockés des données d’un même type.
  • pointeurs
    • très élémentaire
    • envoie le contenu d’une adresse $A$ vers l’adresse que constitue ce contenu
    • en C : char * s;{.C} : pointeur vers une adresse contenant un “caractère” (interprété comme tel)
    • NB1: char * s;{.C} ⟶ pointe vers une zone où sont stockés des caractères
  • struct{.C}

Pq

movl $1, %eax
movl %eax, autre_dest

pcque de toute façon, on doit lire la valeur $1 depuis le bus.

Dans la mémoire :

i, c , ebp sauvegardé, ret, 3 = argc, argv

Syntaxe : char * argv[] $\sim$ char * * argv

Pq ?

En C, les déclarations de type sont plus difficiles qu’en Pascal :

char * s;
char c;

se lit s est une variable tq si j’écris *s, ça donne un char

Ex:

char *s[3];

tableau de taille 3 tq qui on suit son adresse, on arrive dans une zone de caractères.

NB :

  • le type de s est : char *[3];{.C}
  • &toto : retrouve l’adresse o est stocké toto
  • f= (int(*)(char *, int))&toto{.C} : type des fonctions char *, int ⟶ int

Pourquoi “à peu près pareil” et pas “exactement pareil” ?

Quand on fait une déclaration de variables en C (ex: int i) : fait en même temps :

  • type
  • classe de stockage : compilateur : taille de i = celle d’un int + comment on accède à l’objet

char * argv[] et char **argv : mm type, mais pas mm classe de stockage

1) argv = malloc(3*sizeof(char*)) : alloue 3 entrées, chacune de la taille d’un pointeur de char

PUIS : char **argv

⟶ argv : est stocké à l’adresse &argv

VS

2) char * argv[5] : argv : c’est l’adresse du tableau, directement.

⟹ normalement : *x = x[0] :

  • dans le premier cas, aucun problème : récupère &argv, y va et récupère argv, puis va dans *argv
  • dans le deuxième cas : *argv=argv[0] : aucun sens, car argv EST l’endroit où est le tableau (pas stocké dans une case, comme dans le cas précédent).

Petite astuce : quand on compile

while (i <= argc)
A

⟶ naïf :

compl i, argc
jle  #vers A
jmp  #tout à la fin
A
jmp #vers compl i, argc

mais MIEUX :

jmp #vers cmpl i, argc
A
cmpl i, argc
jle #vers jmp

$.main_3 : adresse où est main_3

NB : & : pas de perte de performance

=x ⟶ movl _, _ =&x ⟶ leal _, _

Arithmétique des pointeurs en C

Si x est un pointeur, i un entier :

Valeur de x+i = Valeur de x + Valeur de i $\times$ Sizeof(type des éléments x[i])

Pour accéder à la i-ème case du tableau pointé par x.

Valeur de x-i = Valeur de x - Valeur de i $\times$ Sizeof(type des éléments x[i])

⟹ x[i] = *(x+i)

Les Struct

struct point {
  double x;
  double y;
} ;

struct point p;
p.x;
p.y;

(double : flottants en 64bits)

⟶ produit cartésien en maths

NB: struct point {} ;{.C} est de type struct point{.C}, pas point

  • Si on veut que ce soit le cas : typedef struct point point;{.C}
type 'a list = nil
              | cons 'a * 'a list

nil= un pointeur (NULL)

[1;2;3] = cons(1, cons(2, cons(3, nil)))

pointeur vers 1 ⟶ pointeur vers 2, …

En C :

struct list {
  int val;
  struct list * next;
};

MAIS : en C, on a le droit d’utiliser un type que s’il a été défini avant.

MAIS : marche quand même : car en C : struct toto est accepté, pour tout toto (met un pointeur).

Type enum

Si on a un interrupteur :

type interrupteur = arriere | avant | arret

en C :

enum interrupteur {
  // ...
};

MAIS : pas une bonne idée, car en fait, C les implémente comme des entiers (embêtant pour caster dessus (ex: dans les switch), après)

(*q).x = q -> x

Type union

union {int n; double x;} z;

z.n, z.x ⟶ sont stockés au même endroit (/!\ : pas terrible, on peut écrire dans z.n depuis z.x)

Pointeurs dans les autres langages de programmation

Pour certains langages :

  • pointeurs ∈ syntaxe ⟹ dans la sémantique (ex: C)
  • pointeurs ∈ sémantique, mais pas syntaxe (ex: Java, Python)

NB :

a)

En Pascal : ressemble un peu à C, mais différent : opérations pas les mêmes :

  • pas d’arithmétique des pointeurs

MAIS : en Pascal : pointeurs ≠ pointeurs

b)

CamL : ref{.ocaml} ⟶ style impératif

En plus : récursivité terminale optimisée (sans pile : comme une boucle while)

ref let p = ref 25 in
...

p : int ref

⟶ alloue une case

%% Example code
graph TB
    p-->25;

CamL : alloue le pointeur à sa création, et nous force à spécifier la valeur à laquelle il est associé.

VS

C : on peut ne pas allouer le pointeur, et ne pas spécifier la valeur de la case sur laquelle il pointe.

!p

: lit la valeur le la case à laquelle est alloué p

p:=14

(expression de type unit) on n’écrit pas dans la variable p, on écrit dans la case sur laquelle p pointe.

%% Example code
graph LR
    p-->14;

NB : officiellement, on n’est pas censé pouvoir obtenir &p

MAIS :
module obj : méthode magic ⟹ obj.magic : 'a -> 'b

si a est une ref, retourne l’adresse où est le pointeur.

MAIS : Dangeureux, à cause du

Garbage Collector : Algorithme : Gère les adresses en libérant celles des variables plus utilisées. Libère la mémoire pour nous. (Garbage Collector : en canadien : Glaneur de Cellules)

Version simple : Mark and Sweep : Quand le programme n’a plus de mémoire : libère les variables plus utilisées.

Algo M&S :


Dans le graphe des adresses utilisées par le programme : il existe des racines, depuis lesquels on peut accéder à tous les sommets accessibles (algo linéaire (en nb de sommets) par marquage)

Puis : parcours de toutes les cases mémoires :

Si non allouées :
  on les libère
Sinon :
  on remet le marquage à 0

VS en CamL : Stop and Copy :

Algo S&C :

On divise la mémoire en deux demi-espaces : seul un sera utilisé pour allouer

Dans premier demi-espace :
  étape de "copy" : on copie les adresses normalement marquées dans le deuxième demi-espace

Puis : on change de demi-espace de travail ⟶ les données non accessibles n'y sont pas (car pas recopiées)

($N$ objets, $n$ accessibles)

M&S :

allocation/désallocation en $O(n+N)$

S&C

  • désallocation en temps constant.
  • MAIS : recopie en $O(n×\text{taille moyenne des objets})$
  • allocation très simple : l’indice du top de la pile n’est pas trop modifié

PUIS : analyse amortie pour le S&C ⟶ meilleur, si les données stockées n’ont pas une taille d’objet trop grande.

SUR le papier : M&S << S&C, mais en pratique :

  • accès à une case mémoire ⟶ pas en temps constant, à cause des caches ⟹ en pratique : M&S quasiment aussi bon.

CamL : langage bootstrapé (⟵ “to pull oneself from one’s bootstrap” ≃ auto-référence) : le compilateur CamL est en CamL.

CamL : écrit en CamL depuis el début.

CompCert : compilateur optimisant qui prend du code C ayant une sémantique en entrée et renvoie de l’assembleur ⟶ entièrement prouvé, et formellement : renvoie un code en assembleur ayant la même sémantique que le code C.

type 'a ref =
  { mutable contents : 'a};

type 'a list = nil (*[]*)
  | cons of 'a * 'a list
cons(1, cons(2,nil))

%% Subgraph example
graph TB
        subgraph one
        a1-->a2
        end
        subgraph two
        b1-->b2
        end
        subgraph three
        c1-->c2
        end
        c1-->a2

Th en CamL : Well Typed Programs Do Not Go Wrong

hypothèses : primitives du langage ont les types qui correspondent à leur spécification.

  1. Pointeurs $\sim$ tableaux ↩

Leave a comment