Discussion :

[Krystal_]

Bonjour tout le monde,

Tout à coup j'ai eu une subite envie de faire une petite fonction permettant de lire une chaînes de caractères de taille variable sur stdin (et plus généralement, sur un FILE *).
Le comportement de la fonction est le suivant :
- La fonction prend un paramètre, le flux (FILE *) sur lequel la chaîne de caractères sera lue
- La fonction retournera un char *, l'adresse du premier caractère lu ou NULL si une erreur survient
- Si une erreur survient, le flux sera consommé (= lecture des caractères juqu'à ce qu'on tombe sur \n ou EOF)
La signature de la fonction sera donc la suivante : char * get_line(FILE *);

N'ayant pas trouvé grand chose sur la lecture de chaînes de caractères de taille variable, j'ai du faire chauffer mes méninges et trouver un algorithme, espèrons qu'il soit potable.
Ne sachant pas trop comment écrire cela en pseudo-code, je vais le faire avec de bonnes vieilles phrases.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
/*
D'abord on va allouer un espace mémoire de taille arbitraire (32 octets) pouvant stocker des char.
Si l'allocation a réussie, on va pouvoir lire le flux caractère par caractère.
    Tant qu'on ne rencontre pas \n ou EOF :
         Si l'espace alloué n'est pas suffisant, on va augmenter la taille de l'espace précédemment alloué (+ 32 octets).
         Si l'allocation a échouée, on va libérer l'espace précédemment alloué, consommer le flux et sortir de la boucle.
S'il n'y a pas eu d'erreur d'allocation, on rajoute le \0 à la chaîne de caractères.
On retourne un pointeur sur le premier élément de l'espace alloué ou NULL s'il y a eu une erreur d'allocation.
*/

Première question, est-ce que cet algorithme semble correct, potable ?
Pour la réallocation, j'ai vu certains codes qui doublaient la taille de l'espace alloué au lieu de l'agrandir d'un nombre fixe d'octets. Y a-t-il une méthode préférable à l'autre, ou est-ce dépendant de la situation ? Et si c'est dépendant de la situation, quelle méthode répondrait le mieux à la problématique actuelle ?

Passons maintenant à l'implémentation en C :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
/* /Document/C/str/mstr.h */
#ifndef MSTR_H_INCLUDED
#define MSTR_H_INCLUDED
 
#include <stdlib.h>
#include <stdio.h>
 
#define MSTR_ALLOC_BLOCK_SIZE 32
 
char * get_line(FILE *);
 
#endif /* MSTR_H_INCLUDED */

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/* /Document/C/str/mstr.c */
#include "mstr.h"
 
char * get_line(FILE * stream) {
    /* Allocation du bloc de depart */
    size_t size = MSTR_ALLOC_BLOCK_SIZE;
    char * s = malloc(size);
 
    /* Si l'allocation a reussie */
    if(s != NULL) {
        size_t i;
        int c;
 
        /* On lit tous les caractères jusqu'a \n ou EOF */
        for(i = 0; (c = fgetc(stream)) != '\n' && c != EOF; i++) {
            /* Si l'espace alloue n'est plus suffisant
               on essaie de l'agrandir */
            if(i >= size) {
                char * tmp = realloc(s, size += MSTR_ALLOC_BLOCK_SIZE);
 
                /* Si l'allocation a reussie, on recupere le pointeur
                   Sinon on libere l'espace precedemment alloue,
                   on vide le buffer du flux et on sort du while */
                if(tmp != NULL) {
                    s = tmp;
                }
                else {
                    free(s);
                    s = NULL;
                    while((c = fgetc(stream)) != '\n' && c != EOF) {
                    }
                    break;
                }
            }
            s[i] = (char)c;
        }
        /* On ajoute le \0 terminal a la chaine recuperee */
        if(s != NULL) {
            s[i] = '\0';
        }
    }
 
    return s;
}

Qu'en pensez-vous ?
Le code semble fonctionner. Semble car j'avoue avoir un peu de mal pour les tests unitaires.. Est-il possible de faire échouer volontairement un malloc/realloc ?

Dernière petite chose, j'ai eu beau lutter, un warning persiste à la compilation.. J'utilise code::block avec les options de compilations suivantes (GNU/CSS compiler) : -Wall -Wextra -ansi -O -Wwrite-strings -Wstrict-prototypes -Wuninitialized -Wunreachable-code


Et voici le warning en question :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
/*
\Documents\C\str\mstr.c||In function `get_line':|
\Documents\C\str\mstr.c|10|warning: will never be executed|
||=== Build finished: 0 errors, 1 warnings ===|
*/

J'ai demandé à une connaissance de compiler, il a utilisé le même compilateur (mais je ne sais pas si c'est la même version par contre) avec les mêmes options, et point de warning chez lui.

Merci d'avoir pris le temps de me lire et merci d'avance pour vos futures réponses. =)

Cordialement, Krystal_.

[3DArchi]

Première question, est-ce que cet algorithme semble correct, potable ?

Peut être perfectible, mais ça semble répondre à ton problème.

Pour la réallocation, j'ai vu certains codes qui doublaient la taille de l'espace alloué au lieu de l'agrandir d'un nombre fixe d'octets. Y a-t-il une méthode préférable à l'autre, ou est-ce dépendant de la situation ?

C'est dépendant de la situation. D'autres méthodes diminuent l'espace supplémentaire alloué en se basant sur l'heuristique que plus on avance, plus on est prêt d'arriver.

Et si c'est dépendant de la situation, quelle méthode répondrait le mieux à la problématique actuelle ?

Ta solution, car dans le pire des cas tu risque de doubler la taille de ton buffer pour 1 octet (et d'avoir le risque d'un échec de réallocation).

Passons maintenant à l'implémentation en C :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
/* /Document/C/str/mstr.h */
#ifndef MSTR_H_INCLUDED
#define MSTR_H_INCLUDED
 
#include <stdlib.h>
#include <stdio.h>

En général, on évite les includes dans les .h.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
/* /Document/C/str/mstr.c */
       for(i = 0; (c = fgetc(stream)) != '\n' && c != EOF; i++) {

Attention EOF peut aussi signifier une erreur de lecture (http://www.cplusplus.com/reference/c...dio/fgetc.html).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
                   /*Sinon on libere l'espace precedemment alloue,
                   on vide le buffer du flux et on sort du while */
                else {
                    free(s);
                    s = NULL;
                    while((c = fgetc(stream)) != '\n' && c != EOF) {
                    }
                    break;
                }

Pourquoi?

Le code semble fonctionner. Semble car j'avoue avoir un peu de mal pour les tests unitaires.. Est-il possible de faire échouer volontairement un malloc/realloc ?

Pour les testsU tu dois réécrire les fonctions que tu appelle pour justement pouvoir en contrôler le résultat.
Le moteur de testU est indépendant de ton appli et se content d'appeler ta fonction.

Dernière petite chose, j'ai eu beau lutter, un warning persiste à la compilation.. J'utilise code::block avec les options de compilations suivantes (GNU/CSS compiler) : -Wall -Wextra -ansi -O -Wwrite-strings -Wstrict-prototypes -Wuninitialized -Wunreachable-code


Et voici le warning en question :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
/*
\Documents\C\str\mstr.c||In function `get_line':|
\Documents\C\str\mstr.c|10|warning: will never be executed|
||=== Build finished: 0 errors, 1 warnings ===|
*/

J'ai pas de réponse assurée. La seule certitude c'est que c'est lié à -Wunreachable-code. Mais, ça n'explique pas tout. Je dirais qu'il considère size_t i; comme une instruction alors que ça n'est qu'une déclaration de variable. D'ailleurs, si tu mets size_t i = 0; ton warning disparait.

[Emmanuel Delahaye]

En général, on évite les includes dans les .h.

Absurde. La vraie règle de bon sens est "on met ce qui est nécessaire et suffisant". Ici,

• <stdio.h> est nécessaire pour FILE
• <stdlib.h> est inutile
• la macro est inutile

[Krystal_]

Peut être perfectible, mais ça semble répondre à ton problème.

Aurais-tu des pistes/idées pour l'améliorer ?

Attention EOF peut aussi signifier une erreur de lecture (http://www.cplusplus.com/reference/c...dio/fgetc.html).

En effet, oubli de ma part.

Pourquoi?

C'est le comportement souhaité.
Soit tout se passe bien et on retourne la chaîne, soit quelque chose se passe mal (allocation, erreur de lecture) et on consomme le flux, on libère l'espace aloué et on retourne NULL.

-Boucle infinie lors d'un test basique :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include <stdio.h>
#include <stdlib.h>
 
#include "mstr.h"
 
int main (void)
{
   FILE *fp = fopen ("in.txt", "r");
 
   if (fp != NULL)
   {
      char *line;
      while ((line = fget_line (fp)) != NULL)
      {
         printf ("'%s'\n", line);
         free (line);
      }
      fclose (fp);
   }
   return 0;
}

avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
 
a
ab
a b
abcdefghijklmnopqrstuvwxyz

En effet, je n'avais pas prévu le cas ou fgetc() retournerait EOF dès son premier appel.

J'ai intégré tes dernières modifs. Ceci fonctionne :

http://delahaye.emmanuel.free.fr/forums/Krystal_

Merci bien. Mais si la ligne qu'on est en train de lire ne se termine pas par \n, elle est zappée. Ce choix n'est-il pas un peu dangereux si on lit des fichiers édité avec des logiciels comme le bloc note de Windows ?
Aussi, par rapport à la réallocation, pourquoi privilégier une multiplication par deux de l'espace alloué ?

[Emmanuel Delahaye]

Et voici le warning en question :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
/*
\Documents\C\str\mstr.c||In function `get_line':|
\Documents\C\str\mstr.c|10|warning: will never be executed|
||=== Build finished: 0 errors, 1 warnings ===|
*/

J'ai demandé à une connaissance de compiler, il a utilisé le même compilateur (mais je ne sais pas si c'est la même version par contre) avec les mêmes options, et point de warning chez lui.

Merci d'avoir pris le temps de me lire et merci d'avance pour vos futures réponses. =)

Cordialement, Krystal_.

Ce warning est probablement du à l'optimiseur. Pas grave.

Par contre :

- Le nom de la fonction devrait être fget_line() pour être cohérent :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
void *fget_line(FILE *fp);
 
#define get_line() fget_line (stdin)

- <stdlib.h> n'a rien à faire dans "mstr.h"

- la définition de MSTR_ALLOC_BLOCK_SIZE n'a rien à faire dans "mstr.h"

-Boucle infinie lors d'un test basique :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include <stdio.h>
#include <stdlib.h>
 
#include "mstr.h"
 
int main (void)
{
   FILE *fp = fopen ("in.txt", "r");
 
   if (fp != NULL)
   {
      char *line;
      while ((line = fget_line (fp)) != NULL)
      {
         printf ("'%s'\n", line);
         free (line);
      }
      fclose (fp);
   }
   return 0;
}

avec

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
 
a
ab
a b
abcdefghijklmnopqrstuvwxyz

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

         s[i] = (char) c;

cast inutile.

J'ai intégré tes dernières modifs. Ceci fonctionne :

http://delahaye.emmanuel.free.fr/forums/Krystal_

[Franck.H]

N'ayant pas trouvé grand chose sur la lecture de chaînes de caractères de taille variable, j'ai du faire chauffer mes méninges et trouver un algorithme, espèrons qu'il soit potable.
Ne sachant pas trop comment écrire cela en pseudo-code, je vais le faire avec de bonnes vieilles phrases.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
/*
D'abord on va allouer un espace mémoire de taille arbitraire (32 octets) pouvant stocker des char.
Si l'allocation a réussie, on va pouvoir lire le flux caractère par caractère.
    Tant qu'on ne rencontre pas \n ou EOF :
         Si l'espace alloué n'est pas suffisant, on va augmenter la taille de l'espace précédemment alloué (+ 32 octets).
         Si l'allocation a échouée, on va libérer l'espace précédemment alloué, consommer le flux et sortir de la boucle.
S'il n'y a pas eu d'erreur d'allocation, on rajoute le \0 à la chaîne de caractères.
On retourne un pointeur sur le premier élément de l'espace alloué ou NULL s'il y a eu une erreur d'allocation.
*/

Tu peux éventuellement utiliser l'allocation par Progression géométrique cependant, avec cette méthode tu risque d'avoir un peu plus d'allocation, la règle simplifiée de cette méthode:

new_size = old_size + old_size / 2

Le lien vers le document PDF de Jean-Marc.Bourguet sur la formule complète et détaillée (si t'es très bon en maths ): http://www.bourguet.org/realloc.pdf

Je l'ai déjà utilisée et je peut dire que c'est très pratique mais tu auras surement plus de demandes d'allocation que d'allouer en taille fixe !

[Krystal_]

J'ai donc le choix entre :
- Beaucoup d'allocation mais peu d'espace perdu (taille += taille / 2)
- Peu d'allocation mais beaucoup d'espace perdu (taille *= 2)
- Nombre moyen d'allocation et quantité moyenne d'espace perdu (taille += BLOC_SIZE)

La possibilité de choisir est une vraie torture quand on n'a pas les informations requises pour faire ce choix. J'aurais tendance à choisir la troisième méthode, puisque, de mon point de vue, elle n'est jamais la plus mauvaise. Mais elle n'est jamais la meilleure non plus..

Évidemment, il y a peut-être des subtilités sur l'allocation dont je n'ai pas connaissance.

Merci pour le pdf, mais je ne vois pas comment il passe de la première ligne de son inéquation à la seconde. La suite ça va par contre.

Edit : pour le fun, et parce que ça permet de vérifier qu'on a bien compris/retenu les choses, j'ai refait le code de mstr.c.
J'en ai profité pour permettre de ne pas devoir terminer la dernière ligne par \n.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdlib.h>
 
#include "mstr.h"
 
#define ALLOC_BLOCK_SIZE 32
 
static void fclean(FILE * stream) {
    int c;
 
    while((c = fgetc(stream)) != '\n' && c != EOF) {
    }
}
 
char * fget_line(FILE * stream) {
    size_t size = ALLOC_BLOCK_SIZE;
    char * s = malloc(size);
 
    /* si l'allocation s'est bien passee */
    if(s != NULL) {
        int c;
        size_t i = 0;
 
        /* s'il n'y a pas de caracteres dans le flux, on termine tout */
        if((c = fgetc(stream)) == EOF) {
            free(s), s = NULL;
            fclean(stream);
        }
        /* s'il y a des caracteres dans le flux on le lit */
        else {
            do {
                /* si l'espace alloue n'est plus suffiant, on realloue */
                if(i == size - 1) {
                    char * tmp = realloc(s, size + ALLOC_BLOCK_SIZE);
 
                    /* s'il y a eu erreur d'allocation,
                       on libere l'espace precedemment alloue,
                       on vide le flux et on retourne NULL */
                    if(tmp != NULL) {
                        s = tmp;
                        size += ALLOC_BLOCK_SIZE;
                    }
                    else {
                        free(s), s = NULL;
                        fclean(stream);
                    }
                }
 
                s[i] = c;
                i++;
            } while((c = fgetc(stream)) != '\n' && c != EOF);
        }
        /* s'il y a eu une erreur de lecture,
           on libere l'espace precedemment alloue,
           on vide le buffer et on retourne NULL */
        if(ferror(stream) != 0) {
            free(s), s = NULL;
            fclean(stream);
        }
        /* s'il n'y a pas eu d'erreur de lecture/allocation,
           on rajoute le \0 terminal */
        if(s != NULL) {
            s[i] = '\0';
        }
    }
 
    return s;
}

[dj.motte]

Salut,

Mais cette fameuse construction rend tout aussi bien de la saisie au clavier comme de la lecture des fichiers ?

[Emmanuel Delahaye]

Salut,

Mais cette fameuse construction rend tout aussi bien de la saisie au clavier comme de la lecture des fichiers ?

Oui. Il suffit de passer stdin en paramètre. C'est un scoop ?

[3DArchi]

J'ai donc le choix entre :
- Beaucoup d'allocation mais peu d'espace perdu (taille += taille / 2)
- Peu d'allocation mais beaucoup d'espace perdu (taille *= 2)
- Nombre moyen d'allocation et quantité moyenne d'espace perdu (taille += BLOC_SIZE)

La possibilité de choisir est une vraie torture quand on n'a pas les informations requises pour faire ce choix. J'aurais tendance à choisir la troisième méthode, puisque, de mon point de vue, elle n'est jamais la plus mauvaise. Mais elle n'est jamais la meilleure non plus..

Là il faut sortir du C pour regarder l'utilisation de ta fonction. Dans 80% des cas tu auras:
1/ des données de BLOC_SIZE +-20% -> taille += taille / 2
2/ des données < BLOC_SIZE -> taille += taille / 2
3/ des données < BLOC_SIZE mais quand c'est plus grand c'est vraiment plus grand: taille *= 2 ou taille += BLOC_SIZE
...
En fait, il faut utiliser l'environnement métier pour déterminer quel choix est le plus pertinent dans ton cas réel d'utilisation.

Le choix des noms de tes fonctions: fget_line, fclean. Ca ressemble à des fonctions standards. Ca peut être perturbant. Moi, je préfère MSTR_fget_line et MSTR_fclean, par exemple. On voit tout de suite qu'il s'agit d'une fonction de ton module.

Tu fais, en gros, if(fin ou erreur) alors ... else do ... while(!fin et !erreur). Normalement tu peux reformuler en while(!fin et !erreur)... Ca devrait suffire.

Qqs commentaires mineurs dans le code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdlib.h>

#include "mstr.h"

#define ALLOC_BLOCK_SIZE 32

static void fclean(FILE * stream) {
    int c;

    while((c = fgetc(stream)) != '\n' && c != EOF) {
    }
}

char * fget_line(FILE * stream) {
    size_t size = ALLOC_BLOCK_SIZE;
    char * s = malloc(size);

    /* si l'allocation s'est bien passee */
    if(s != NULL) {
        int c;
        size_t i = 0;

        /* s'il n'y a pas de caracteres dans le flux, on termine tout */
        if((c = fgetc(stream)) == EOF) {
            free(s), s = NULL;
            fclean(stream);
        }
        /* s'il y a des caracteres dans le flux on le lit */
        else {
            do {
                /* si l'espace alloue n'est plus suffiant, on realloue */
                if(i == size - 1) {
/* Moi, je préfère souvent des i >= size - 1, mais c'est un choix perso (>= sera plus souvent vérifié que ==) */
                    char * tmp = realloc(s, size + ALLOC_BLOCK_SIZE);

                    /* s'il y a eu erreur d'allocation,
                       on libere l'espace precedemment alloue,
                       on vide le flux et on retourne NULL */
                    if(tmp != NULL) {
                        s = tmp;
                        size += ALLOC_BLOCK_SIZE;
                    }
                    else {
                        free(s), s = NULL;
/*Le ',' est une faute de frappe? Préfère le ';': free(s); s = NULL;*/
                        fclean(stream);
                    }
                }

                s[i] = c;
                i++;
            } while((c = fgetc(stream)) != '\n' && c != EOF);
        }
        /* s'il y a eu une erreur de lecture,
           on libere l'espace precedemment alloue,
           on vide le buffer et on retourne NULL */
        if(ferror(stream) != 0) {
            free(s), s = NULL;
            fclean(stream);
        }
        /* s'il n'y a pas eu d'erreur de lecture/allocation,
           on rajoute le \0 terminal */
        if(s != NULL) {
            s[i] = '\0';
        }
    }

    return s;
}

PS/HS:

Absurde.

C'est vrai, ça fait de beaux graphes d'inclusion.

[Emmanuel Delahaye]

Le choix des noms de tes fonctions: fget_line, fclean. Ca ressemble à des fonctions standards. Ca peut être perturbant. Moi, je préfère MSTR_fget_line et MSTR_fclean, par exemple. On voit tout de suite qu'il s'agit d'une fonction de ton module.

+1

[dj.motte]

Salut,

Personnellement je ne me servirais jamais d'une telle fonction pour lire un fichier. Pour stdin à la rigueur, sans plus.

C'est le truc ressassé depuis l'antiquité, mais la subtilité réside dans le nom de la fonction. Faut-il dire fget_line ou my_get_fline, ou encore get_the_fline ? Personne n'aurait la subtilité de l'appeler alonso_la_linea...

Enfin cette fonction ne permet pas de quantifier ce que l'on lit dans le flux. Pour un fichier on peut ne souhaiter lire que les 150 premiers octets par exemple