Saisie de caractères "illimitée"

Version imprimable

Bonjour à tous,

J'ai essayé de faire un programme permettant une saisie de caractère "illimitée" sur l'entrée standard.
Le comportement me paraît bon, mais je tenais quand même à vous montrer le code pour voir si je n'avais pas commis une bourde (je n'ai pas l'habitude d'utiliser realloc()).

Code:

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
#include <stdio.h>
#include <stdlib.h>
 
int main(void)
{
   size_t size = 2;
   char *s = malloc (size);
 
   if(s != NULL)
   {
      int c;
      int fin = 0;
      size_t i = 0;
      while((c = getchar()) != '\n' && c != EOF && !fin)
      {
         if(i >= size-1)
         {
            size *= 1.5;
            char *p_tmp = realloc(s, size);
 
            if(p_tmp != NULL)
            {
               s = p_tmp;
               s[i++] = c;
            }
            else
            {
               fin = 1;
            }
         }
         else
         {
            s[i++] = c;
         }
      }
 
      s[i] = '\0';
      printf("saisie : %s\n", s);
   }
   else
   {
      printf("erreur d'allocation memoire\n");
   }
 
   return 0;
}

Voyez-vous des corrections à effectuer ?
Par avance, merci.

01/07/2007, 15h29
Zavonen
Je remarque que la taille du buffer croit de manière exponentielle:
Code:

1 2 size *= 1.5; char *p_tmp = realloc(s, size);
Ne vaudrait-il pas mieux quelque chose de plus progressif (par exemple une croissance arithmétique) ?
01/07/2007, 15h40
odsen.s
Citation:
Envoyé par Zavonen

Je remarque que la taille du buffer croit de manière exponentielle:

Code:

1 2 size *= 1.5; char *p_tmp = realloc(s, size);

Ne vaudrait-il pas mieux quelque chose de plus progressif (par exemple une croissance arithmétique) ?
D'après ce que j'ai lu ici et là, il vaut mieux multiplier par un nombre inférieur au nombre d'or. On peut donc utiliser 1.5 comme facteur de multiplication. Je ne me rappelle plus bien la raison, mais c'est préférable à ajouter de l'espace pour chaque caractère.
01/07/2007, 17h13
Zavonen

Vous commencez à deux et vous multipliez par 1.5 à chaque fois.
Voici donc les tailles successives allouées ou réallouées:
2 3 4 6 9 13 19 28 32 48 64
96 128 192 288 bon...
Si vous avez besoin de 300 caractères vous en mobiliserez 432 soit 132 de trop, et le pourcentage ne fera que croitre avec la longueur de la chaine.
En fait il faudrait connaitre a priori:
la longueur moyenne des chaines que vous entrez
la taille minimale
la taille maximale
pour décider de la bonne stratégie.
01/07/2007, 17h19
odsen.s

Citation:

En fait il faudrait connaitre a priori:
la longueur moyenne des chaines que vous entrez
la taille minimale
la taille maximale
pour décider de la bonne stratégie.

Justement, le but du programme est de pouvoir saisir entièrement une chaîne de longueur inconnue, donc pas de taille minimale ou maximale.
Après, s'il y a des moyens de réallouer de l'espace mémoire avec moins de "pertes", et en limitant le nombre de réallocations comme ici, je suis preneur. :)
01/07/2007, 18h02
Zavonen
Je me suis peut être mal fait comprendre:
Dans tous les cas on proposera un système qui ne se bloque pas, mais la discussion porte sur mode de croissance du buffer.
Moi je proposerais une croissance arithmétique du genre:
Code:

1 2 size += 50; char *p_tmp = realloc(s, size);
qui assurerait que l'espace maximal perdu reste inférieur à 50 octets.
NB: realloc est très rapide, imperceptible pendant une opération de saisie

Citation:

Envoyé par odsen.s

J'ai essayé de faire un programme permettant une saisie de caractère "illimitée" sur l'entrée standard.
<...>
Voyez-vous des corrections à effectuer ?
Par avance, merci.

Première chose à faire : une fonction :

Code:

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
 
#include <stdio.h>
#include <stdlib.h>
 
char *get_line (void)
{
   size_t size = 2;
   char *s = malloc (size);
 
   if (s != NULL)
   {
      int c;
      int fin = 0;
      size_t i = 0;
      while ((c = getchar ()) != '\n' && c != EOF && !fin)
      {
         if (i >= size - 1)
         {
            size *= 1.5;
            char *p_tmp = realloc (s, size);
 
            if (p_tmp != NULL)
            {
               s = p_tmp;
               s[i++] = c;
            }
            else
            {
               fin = 1;
            }
         }
         else
         {
            s[i++] = c;
         }
      }
 
      s[i] = '\0';
   }
   return s;
}
 
int main (void)
{
   char *s = get_line ();
   if (s != NULL)
   {
      printf ("s='%s'\n", s);
      free (s);
   }
   else
   {
      printf ("erreur d'allocation memoire\n");
   }
   return 0;
}

Malgré une instrumentation poussée (au prix d'une légère modification)

Code:

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
70
71
72
73
74
75
76
77
78
79
80
81
 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
 
#define get_line() fget_line (stdin)
 
char *fget_line (FILE * fp)
{
   size_t size = 2;
   char *s = malloc (size);
 
   if (s != NULL)
   {
      int c;
      int fin = 0;
      size_t i = 0;
 
      memset (s, '?', size);
 
      while ((c = fgetc (fp)) != '\n' && c != EOF && !fin)
      {
         if (i >= size - 1)
         {
            char *p_tmp = realloc (s, size * 1.5);
 
            if (p_tmp != NULL)
            {
               /* ne pas factoriser. Calculs entiers... */
               memset (p_tmp + size, '?', (size * 1.5) - size);
               size *= 1.5;
               s = p_tmp;
               assert (i < size - 1);
/* -ed-
               s[i++] = c;
   a eviter
*/
               s[i] = c;
               i++;
            }
            else
            {
               fin = 1;
            }
         }
         else
         {
            assert (i < size - 1);
            s[i] = c;
            i++;
         }
      }
 
      assert (i < size);
      s[i] = '\0';
   }
   return s;
}
 
int main (void)
{
   int fin = 0;
   while (!fin)
   {
      char *s = get_line ();
      if (s != NULL)
      {
         printf ("s='%s'\n", s);
         fin = *s == 0;
         free (s);
 
      }
      else
      {
         printf ("erreur d'allocation memoire\n");
         fin = 1;
      }
   }
   return 0;
}

Je n'ai pas pu mettre ce code en défaut.

01/07/2007, 18h48
Emmanuel Delahaye
Citation:
Envoyé par Zavonen

Je me suis peut être mal fait comprendre:
Dans tous les cas on proposera un système qui ne se bloque pas, mais la discussion porte sur mode de croissance du buffer.
Moi je proposerais une croissance arithmétique du genre:

Code:

1 2 size += 50; char *p_tmp = realloc(s, size);

qui assurerait que l'espace maximal perdu reste inférieur à 50 octets.
NB: realloc est très rapide,
Loin de là !

Citation:

imperceptible pendant une opération de saisie

Mais pas pendant une lecture de ligne si elle est très longue (html, par exemple...)

Des calculs savants ont démontré que la croissance devrait être géométrique et la raison égale au nombre d'or PHI (1.618...).
01/07/2007, 19h09
odsen.s

Merci bien pour ces tests Emmanuel :)
01/07/2007, 19h23
Emmanuel Delahaye
Citation:

Envoyé par odsen.s

Merci bien pour ces tests Emmanuel :)

Juste une remarque. Le comportement en cas d'erreur de réallocation fait que les caractères non lus restent dans le flux. Ce n'est pas une mauvaise chose, mais ça doit être précisé dans la spec, et, à mon sens, cette information devrait être récupérable, car il faut pouvoir agir en conséquences.

Code:

char *fget_line(FILE *fp, int *p_err)

avec différentes valeurs pour *p_err :
- OK
- EOF
- FILE_ERROR
- MEM_ERROR
etc.

D'ailleurs, est-ce que la fin de lecture est bien traitée ?
01/07/2007, 20h58
odsen.s

Citation:

Envoyé par Emmanuel Delahaye

Juste une remarque. Le comportement en cas d'erreur de réallocation fait que les caractères non lus restent dans le flux. Ce n'est pas une mauvaise chose, mais ça doit être précisé dans la spec, et, à mon sens, cette information devrait être récupérable, car il faut pouvoir agir en conséquences.
<...>

Exact.
Cependant, je ne souhaite pas aller aussi loin.
En effet, je n'intègre pas cette fonction dans un projet.
Je suis en ce moment en train de réaliser sur mon site une liste d'exercices en C pour les débutants qui souhaiteraient mettre en application leurs connaissances.
La réalisation de cette fonction me paraissait être une bonne application de malloc() + realloc(), mais je ne pense pas exiger un retour d'erreur. Lire les caractères restants pour vider le flux me paraît par contre une bonne idée.

J'oubliais, juste une question :
Code:

1 2 3 4 5 6 /* -ed- s[i++] = c; a eviter */ s[i] = c; i++;
Est-ce uniquement une question de lisibilité ?

02/07/2007, 09h50
Emmanuel Delahaye
Citation:
Envoyé par odsen.s

J'oubliais, juste une question :

Code:

1 2 3 4 5 6 /* -ed- s[i++] = c; a eviter */ s[i] = c; i++;

Est-ce uniquement une question de lisibilité ?
Oui, et c'est une catastrophe quand c'est utilisé comme paramètre de fonction...
02/07/2007, 11h45
odsen.s

Citation:

Envoyé par Emmanuel Delahaye

Oui, et c'est une catastrophe quand c'est utilisé comme paramètre de fonction...

Ok, merci.
02/07/2007, 12h12
Médinoc

Citation:

Envoyé par Emmanuel Delahaye

Des calculs savants ont démontré que la croissance devrait être géométrique et la raison égale au nombre d'or PHI (1.618...).

Je n'ai rien lu sur l'égalité, mais je sais que ce nombre ne doit pas être dépassé.
Quant à l'égalité, il y a fort à parier que c'est la valeur optimale. Mais comme il s'agira toujours d'une approximation, il ne faut pas oublier que l'arrondit doit obligatoirement être fait par défaut et non pas excès.
02/07/2007, 14h42
gege2061

Citation:

Envoyé par Médinoc

Je n'ai rien lu sur l'égalité, mais je sais que ce nombre ne doit pas être dépassé.
Quant à l'égalité, il y a fort à parier que c'est la valeur optimale. Mais comme il s'agira toujours d'une approximation, il ne faut pas oublier que l'arrondit doit obligatoirement être fait par défaut et non pas excès.

Réallocation géométrique et nombre d'or ;)