Implémentaion de "vector_enlarge(vector* v)"

Implémentaion de "vector_enlarge(vector* v)"

par Daniel Suter,
Number of replies: 2

Bonjour,


A la slide 24 du cours "pointeurs(2/5)", il est expliqué que la condition:

   if ((result.allocated > SIZE_MAX / sizeof(type_el)) || ... )

est là pour éviter toute erreur de overflow pouvant avoir lieu lors de l'appel à "realloc( ... )" à la ligne suivante.

Est ce que dans le cas ou notre type "type_el" s'cérit en mémoire sur uniquement 1 byte (par exemple avec un "char") un overflow pourrait se produire à la ligne précédante :

   result.allocated += VECTOR_PADDING;

sans que celui ci ne soit détecté ?
Admetons pour l'exemple que result.allocated = SIZE_MAX, dans ce cas, l'addition provoquera un overflow et result.allocated vaudra ensuite VECTOR_PADDDING qui est inférieur à SIZE_MAX.
Il me semble que la condition telle qu'elle est dans le cours ne fonctionne que si sizeof(type_el) > 1.

Est ce qu'il ne faudrait pas également rajouter une condition du type :

   result.allocated >= v->allocated

afin de s'assurer que la nouvelle valeur soit bien supérieur à l'ancienne ?


Merci d'avance

In reply to Daniel Suter

Re: Implémentaion de "vector_enlarge(vector* v)"

par Jean-Cédric Chappelier,

Si je comprends bien, vous questionnez l'overflow possible sur l'addition dans « result.allocated += VECTOR_PADDING; » (je ne suis pas sûr, car sizeof(type_el) n'a rien à voir là dedans, c'est plutôt la valeur de VECTOR_PADDING qui serait en cause).

En théorie vous pourriez avoir raison (typiquement si VECTOR_PADDING est trop grand [indépendamment de sizeof(type_el)]), mais en pratique ce n'est pas du tout possible pour des raisons d'ordre de grandeur.
Regardez déjà la carte mémoire du slide 4 : on est loin d'avoir toute la mémoire disponible pour le heap.
Mais plus concrètement : SIZE_MAX est 2^64 alors qu'un ordre de grandeur de la mémoire disponible (heap+stack) est de l'ordre de 2^47. Donc de toutes façons result.allocated et VECTOR_PADDING sont plus petits que ça.
Qui plus est, result.allocated compte un nombre d'item, pas une taille (c'est là que le facteur sizeof(type_el) intervient).

Pour le faire mathématiquement : result.allocated et VECTOR_PADDING sont inférieurs à 2^47 (sinon vous n'arriverez de toutes façons pas à alloc quoi que ce soit), donc result.allocated + VECTOR_PADDING est inférieur à 2^64 (et de loin ;-) ).

Est-ce clair ? Est-ce que ça répond à votre question (ou je n'ai rien compris) ?