allocation dynamique avec pointeur sur pointeur

(tableau de chaines)

13 août 2008 à 7:01:26

Bonjour,

Je cherche a stocker un nombre indéterminé de chaines dans un tableau de type char[][] .

J'ai "extrapolé" la façon d'utiliser correctement l'allocation dynamique et la libération mémoire. Pouvez vous me dire s'il vous plait si ma methode est correcte ?

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

#define SIZEBUF 256

int main(void)
{
    char** tab = NULL;
    char buf[SIZEBUF];
    int nb_case = 0;

    puts ("Entrez les chaines (ENTREE pour echapper) :");
    /* saisie, tant que l'allocation fonctionne */
    while (fgets(buf, SIZEBUF, stdin) && *buf != '\n' && (tab = realloc(tab, nb_case+1)) != NULL && (tab[nb_case] = malloc(SIZEBUF)) != NULL)
    {
        strcpy(tab[nb_case], buf);
        printf("tab[%d] = %s\n", nb_case, tab[nb_case]);
        nb_case++;
    }
    /* liberation mémoire, d'abord chaque chaine et ensuite le tableau */
    while (nb_case >= 0)
    {
        free(tab[nb_case]);
        nb_case--;
    }
    free(tab);

    return 0;
}

Merci !

PS: Je sais qu'une liste chainée conviendrait aussi ici, mais ceci ne m'intéresse pas...

13 août 2008 à 9:09:06

Je suis pour le faire en 2 temps. D'abord on alloue une quantité minimale puis on fait la saisie et on réajuste la taille du tableau lorsque c'est nécessaire. En pratique, c'est très inefficace d'appeler realloc() à chaque tour de boucle pour ajouter une case au tableau. Voici comment je ferais:

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

#define SIZEBUF 256
#define TAB_INIT_SIZE 16

static int fclean(char *buffer, FILE *fp);
static int tab_realloc_if_necessary(char ***p_tab, size_t *p_size, 
        size_t nelems);
static void tab_free(char ***p_tab, size_t nelems);
static void tab_display(char **tab, size_t nelems);

int main(void)
{
    /* -tc- En pratique, tab, tab_size et nelems devraient etre encapsules
     * dans une structure
     */
    char ** tab = NULL;
    size_t tab_size = TAB_INIT_SIZE;
    size_t nelems = 0;
    int ret = EXIT_SUCCESS;

    /* -tc- On commence par allouer une quantite minimale */
    tab = malloc(tab_size * sizeof *tab);
    /* -tc- On verifie l'allocation */
    if (tab != NULL)
    {
        char buf[SIZEBUF] = "";
        int err = 0;

        puts ("Entrez les chaines (ENTREE pour echapper) :");

        while (err == 0 && fgets(buf, sizeof buf, stdin) != NULL)
        {
            fclean(buf, stdin);
            nelems++;

            if ((err = tab_realloc_if_necessary(&tab, &tab_size, nelems)) == 0)
            {
                /* -tc- strdup() n'est pas standard, mais POSIX.1, donc tres portable */
                tab[nelems-1] = strdup(buf);
                if (tab[nelems-1] == NULL)
                {
                    err = 1;
                }
            }
        }

        if (err != 1)
        {
            tab_display(tab, nelems);
            /* -tc- Suite du programme */
        }
        else
        {
            fprintf(stderr, "Erreur: pas assez de memoire !\n");
            ret = EXIT_FAILURE;
        }

        /* -tc- On libere la memoire */
        tab_free(&tab, nelems);
    }
    else
    {
        fprintf(stderr, "Erreur: pas assez de memoire !\n");
        ret = EXIT_FAILURE;
    }

    return ret;
}

/* -tc- Elimine le caractere de fin de ligne '\n' saisi par fgets() et purge le
   tampon du flux entrant fp en cas de saisie tronquee. Renvoit 1 si la saisie
   a ete tronquee et 0 sinon.*/
static int 
fclean(char *buffer, FILE *fp)
{
    int err = 0;

    if (buffer != NULL && fp != NULL)
    {
        /* -tc- On recherche le caractre de fin de ligne saisi par fgets() */
        char *pc = strchr(buffer, '\n');

        if (pc != NULL)
        {
            /* -tc- Si on le trouve, la saisie est complete et on elimine ce
               caractere qui ne nous interesse pas */
            *pc = 0;
        }
        else
        {
            /* -tc- Si on ne le trouve pas, la saisie a ete tronquee et on
               purge le tampon du flux d'entree standard pour ne pas perturber
               les saisies futures */
            int c;

            while ((c = fgetc(fp)) != '\n' && c != EOF)
            {
                /* -tc- Cette boucle lit le flux d'entree standard
                    caractere par caractere jusqu'a ce que '\n' ou EOF soit
                    rencontre. Chaque caractere lu est ignore. */
            }
            err = 1;
        }
    }
    return err;
}

/* -tc- Agrandit le tableau seulement si c'est necessaire */
static int 
tab_realloc_if_necessary(char ***p_tab, size_t *p_size, size_t nelems)
{
    int err = 0;

    if (p_tab != NULL && *p_tab != NULL && p_size != NULL)
    {
        if (nelems < *p_size)
        {
            /* -tc- Rien a faire dans ce cas */
        }
        else
        {
            char **tmp = NULL;
            char **self = *p_tab;
            size_t size = *p_size;

            /* -tc- On agrandit le tableau en progression geometrique */
            size = size + size / 2;
            *p_size = size;

            /* -tc- Toujours affecter le retour de realloc() a un pointeur
             * temporaire*/
            tmp = realloc(self, size * sizeof *self);
            if (tmp != NULL)
            {
                *p_tab = tmp;
            }
            else
            {
                /* -tc- Erreur: pas assez de memoire. On ne touche pas au
                 * tableau original et on retourne un code d'erreur
                 */
                err = 1;
            }
        }
    }

    return err;
}

/* -tc- Liberation de la memoire allouee pour le tableau de chaines de
 * caracteres*/
static void 
tab_free(char ***p_tab, size_t nelems)
{
    if (p_tab != NULL && *p_tab != NULL)
    {
        size_t i;
        char **self = *p_tab;

        /* -tc- On libere les chaines contenues dans le tableau */
        for (i = 0; i < nelems; i++)
        {
            free(self[i]), self[i] = NULL;
        }
        /* -tc- On libere le tableau lui-meme */
        free(*p_tab), *p_tab = NULL;

    }
}

/* -tc- Affiche le tableau */
static void 
tab_display(char **tab, size_t nelems)
{
    if (tab != NULL && nelems > 0)
    {
        size_t i;

        for (i = 0; i < nelems; i++)
        {
            puts(tab[i]);
        }
    }
}

En général, on préfère encapsuler les variables tab, tab_size et nelems de main() dans une structure. Cela permet de clarifier le code.

Thierry

-ed-

13 août 2008 à 9:44:06

Citation : yoch

Je cherche a stocker un nombre indéterminé de chaines dans un tableau de type char[][] .

Cette forme n'existe pas.

Soit c'est un tableau et les tailles doivent être précisées ou définies implicitement par l'initialisation :

/* correct */
int a[3];
int b[] = {0,0,0};
int c[2][3];
int d[][3] = {{0,0,0},{0,0,0}};

/* errone */
int e[];
int f[][];

Citation : Pas de titre

J'ai "extrapolé" la façon d'utiliser correctement l'allocation dynamique et la libération mémoire. Pouvez vous me dire s'il vous plait si ma methode est correcte ?

Ton code est trop compact. Il est difficile à lire et certaines variables sont réutilisées.

/* saisie, tant que l'allocation fonctionne */
   while (fgets (buf, SIZEBUF, stdin) && *buf != '\n'
          && (tab = realloc (tab, nb_case + 1)) != NULL
          && (tab[nb_case] = malloc (SIZEBUF)) != NULL)

Ça fout la trouille. Que se passe-t-il en cas d'echec d'allocation mémoire ? Comment est libéré ce qui a été alloué avant ?

Ceci est faux :

realloc (tab, nb_case + 1);

*alloc() ne connait pas les types. Il alloue des bytes. Il faut multiplier le nombre d'éléments par la taiille d'un élément :

realloc (tab, sizeof *tab * (nb_case + 1));

de plus, il y a des précautions à prendre...

http://mapage.noos.fr/emdel/notes.htm#realloc

strcpy (tab[nb_case], buf);

Directement ? Tu recopies donc le '\n'...

Il ne faut pas hésiter à écrire du code simple et clair, même si il est un peu plus long et qu'il comporte des blocs en plus. Si c'est correctement indenté, ça reste lisible. Si ça devient illisible, c'est qu'on a loupé un niveau d'abstraction (faire des fonctions intelligemment).

De plus, pour vérifier le fonctionnement, il faut une séquence d'affichage 'a posteriori'.

Ensuite, je ne vois pas l'intérêt d'allouer une taille fixe, surtout si c'est pour faire une copie dedans... Autant allouer directement les bloc et saisir dedans (ensuite, on mémorise son adresse dans le tableau de pointeurs).

Sinon, on fait une copie dynamique de la bonne taille (avec la fonction POSIX.1 strdup(), par exemple ou un équivalent maison)

Enfin, c'est un beau sujet pour créer une 'classe' C :

http://mapage.noos.fr/emdel/tad.htm

J'arrive à un code qui ne plante plus,

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

int main (void)
{
   char **tab = NULL;
   char buf[256];
   int nb_case = 0;

   puts ("Entrez les chaines (ENTREE pour echapper) :");
   /* saisie, tant que l'allocation fonctionne */
   while (fgets (buf, sizeof buf, stdin) != NULL && *buf != '\n')
   {
      tab = realloc (tab, sizeof *tab * (nb_case + 1));
      tab[nb_case] = strdup (buf);
      nb_case++;
   }

   /* affichage */
   {
      int i;
      for (i = 0; i < nb_case; i++)
      {
         printf ("tab[%d] = %s\n", i, tab[i]);
      }
   }

   /* liberation mémoire, d'abord chaque chaine et ensuite le tableau */
   while (nb_case >= 0)
   {
      free (tab[nb_case]);
      nb_case--;
   }
   free (tab);

   return 0;
}

mais il y a encore un problème de libération de mémoire :

Usage xxx[ /T][ /E][ /O][ <options application>]
FRMWRK.DBG_SYSALLOC=1
SYSALLOC Overload (1365 rec)
SYSALLOC Successful initialization: 1365 records available
Entrez les chaines (ENTREE pour echapper) :
hello
wild
world

tab[0] = hello

tab[1] = wild

tab[2] = world

done in 9.416 s
SYSALLOC min=4294967295 max=4294967295 delta=0
SYSALLOC Err: Not-matched list:
SYSALLOC Bloc 5C737265 freed at line 32 of 'C:\dev\mem\main.c' not allocated
SYSALLOC Released Memory
FRMWRK.Execution terminated

Process returned 0 (0x0)   execution time : 9.453 s
Press any key to continue.

J'ai pas assez de neurones pour comprendre du code aussi tordu :

/* liberation mémoire, d'abord chaque chaine et ensuite le tableau */
   while (nb_case >= 0)
   {
      free (tab[nb_case]);
      nb_case--;
   }
   free (tab);

Je me contente de code simple et éprouvé :

/* liberation mémoire, d'abord chaque chaine et ensuite le tableau */
   {
      int i;
      for (i = 0; i < nb_case; i++)
      {
         free (tab[i]);
      }
      free (tab);
   }

et curieusement, ça fonctionne du premier coup :

Usage xxx[ /T][ /E][ /O][ <options application>]
FRMWRK.DBG_SYSALLOC=1
SYSALLOC Overload (1365 rec)
SYSALLOC Successful initialization: 1365 records available
Entrez les chaines (ENTREE pour echapper) :
hello
wild
world

tab[0] = hello

tab[1] = wild

tab[2] = world

done in 11.522 s
SYSALLOC min=4294967295 max=4294967295 delta=0
SYSALLOC All-matched
SYSALLOC Released Memory
FRMWRK.Execution terminated

Process returned 0 (0x0)   execution time : 11.564 s
Press any key to continue.

Music only !

yoch

13 août 2008 à 10:13:06

@tc : Merci d'avoir pris le temps de me conseiller !

13 août 2008 à 10:21:19

Citation : -ed-

Enfin, c'est un beau sujet pour créer une 'classe' C :

http://mapage.noos.fr/emdel/tad.htm

Oui, c'est tout à fait adapté ici.

Thierry

yoch

13 août 2008 à 10:31:50

@ -ed- : Merci infiniment pour tes remarques !

Citation : -ed-

Ton code est trop compact. Il est difficile à lire et certaines variables sont réutilisées.
<...>
Il ne faut pas hésiter à écrire du code simple et clair, même si il est un peu plus long et qu'il comporte des blocs en plus. Si c'est correctement indenté, ça reste lisible. Si ça devient illisible, c'est qu'on a loupé un niveau d'abstraction (faire des fonctions intelligemment).

Mea culpa.

Citation : -ed-

/* saisie, tant que l'allocation fonctionne */
   while (fgets (buf, SIZEBUF, stdin) && *buf != '\n'
          && (tab = realloc (tab, nb_case + 1)) != NULL
          && (tab[nb_case] = malloc (SIZEBUF)) != NULL)
Ça fout la trouille. Que se passe-t-il en cas d'echec d'allocation mémoire ? Comment est libéré ce qui a été alloué avant ?

Je ne comprends pas... Le free n'est pas placé dans le while mais après.

Citation : -ed-

Ensuite, je ne vois pas l'intérêt d'allouer une taille fixe, surtout si c'est pour faire une copie dedans... Autant allouer directement les bloc et saisir dedans (ensuite, on mémorise son adresse dans le tableau de pointeurs).

OK.

Citation : -ed-

J'ai pas assez de neurones pour comprendre du code aussi tordu :

/* liberation mémoire, d'abord chaque chaine et ensuite le tableau */
   while (nb_case >= 0)
   {
      free (tab[nb_case]);
      nb_case--;
   }
   free (tab);

Pas taper !

Le code n'est pas si tordu (sauf que j'ai la mauvaise habitude de réutiliser les variables), une bête erreur d'algo, c'était :

/* liberation mémoire, d'abord chaque chaine et ensuite le tableau */
   while (nb_case)
   {
      free (tab[nb_case]);
      nb_case--;
   }
   free (tab);