Journal Petit problème en C (free)

Posté par  .
Étiquettes : aucune
0
19
nov.
2003
Cher journal,

j'ai un petit problème que je ne comprends vraiment pas dans un programme en C.
J'ai les structures de données suivantes :

typedef struct _node {
int value;
struct _node *next;
struct _node *previous;
} node;

typedef node* list;

typedef struct {
int nb_rows;
int nb_columns;
list *matrix;
/* array of linked lists
each list corresponds to a column,
each value of a node in this list
gives the positions of a 1 in this column */
} ldpc_matrix;

(c'est une matrice binaire creuse)

et une fonction :

void add_rows(ldpc_matrix *m, int i1, int i2){
int j;
list l, l1;
int value_i2;

for(j=0; j<m->nb_columns; j++){
l = m->matrix[j];
l1 = NULL;
value_i2 = 0;
while(l!=NULL){
if(l->value==i2)
value_i2 = 1;
if(l->value==i1)
l1 = l;
l = l->next;
}
if((l1!=NULL) && (value_i2==1)){
if(l1->previous){
l1->previous->next = l1->next;
}
else{
m->matrix[j] = l1->next;
}
free(l1);
} else {
if((l1==NULL) && (value_i2==1)){
l1 = m->matrix[j];
m->matrix[j] = (node*) malloc(sizeof(node));
m->matrix[j]->value = i1;
m->matrix[j]->next = l1;
m->matrix[j]->previous = NULL;
}
}
}
}

qui est censée remplacer la ligne i1 par la somme des lignes i1 et i2.

Ce qui se passe, c'est que pour des petites matrices (genre 6x12) ca fonctionne très bien, et quand je l'utilise sur une matrice plus grosse (5001x10002) le programme part en boucle infinie sur le free(l1), et toujours sur la même valeur de i1 et i2 : 4921 et 4796.
Ce qui m'embète c'est d'une part que ces valeurs ne me semblent pas vraiment particulières, et qu'il y ait un problème sur free, alors que tout est bien alloué avec malloc, et que je ne vois pas ce qui peut le faire partir en boucle infinie...

  • # Re: Petit problème en C (free)

    Posté par  . Évalué à 5.

    Tu ne veux pas nous retaper ton code en utilisant la balise <pre> et en enlevant les retours chariots ?
    Là, ça me donne mal au coeur.

  • # Re: Petit problème en C (free)

    Posté par  . Évalué à 1.

    Je pense a un petit soucis d'occupation memoire, parce que la, tu te mets a en occuper un paquet...

  • # Re: Petit problème en C (free)

    Posté par  . Évalué à 3.

    vu qu'on arrive pas à lire ton code commence par utiliser des debugueurs mémoires comme ElectricFence et Valgrind, essaye aussi GDB / DDD

    mets l& à NULL après l'avoir libéré, initialise toujours tes varaibles à la création

  • # Re: Petit problème en C (free)

    Posté par  . Évalué à 3.

    Il me semble que quand tu modifies la liste pour supprimer un element dans le premier cas if((l1!=NULL) && (value_i2==1)), tu ne fais que la moitié des mises à jour requises pour une liste doublement chainee.

    Tu a fais l1->previous->next = l1->next, mais il faudrait aussi faire un
    if (l1->next) { l1->next->previous = l1->previous; }

    La ta liste devient corrompue, et probablement qu'à un moment dans ton test avec une grosse matrice, il y a un cas ou 2 elements consécutifs d'une meme liste sont modifiés, ou le "previous" de l'un est resté un pointeur sur l'ancien element a present désalloué.

    Quant tu dis que ton plantage se fait toujours sur les memes valeurs, c'est parceque tes matrices de test sont toujours les mêmes ? Si tu les remplis aleatoirement, est-ce que tu initialise la graine du generateur avec la valeur de time() par exemple ? (sinon, une série de random() sera toujours la meme d'une execution à l'autre).

    • [^] # Re: Petit problème en C (free)

      Posté par  . Évalué à 1.

      Effectivement...
      Au départ la liste était simplement chainée, et est passée en doublement chainée il y a pas longtemps et j'avais oublié ca.
      Mais si j'essaye d'accéder à un bloc déja désalloué, je devrais me prendre une segfault plutôt qu'un bloquage, non?
      En tout cas, même après la modif ca continue à bloquer.
      Ma grosse matrice de test est effectivement toujours la même, fournie par le prof qui nous a demandé ce programme.
      Je vais regarder si y'a pas encore le même type de problème qui traine, et essayer avec une matrice aléatoire voire ce que ca donne.

  • # Re: Petit problème en C (free)

    Posté par  . Évalué à 1.

    voila le code un peu mieux formaté... 
    

typedef struct _node {
  int value;
  struct _node *next;
  struct _node *previous;
} node;

typedef node* list;

typedef struct {
  int nb_rows;
  int nb_columns;
  list *matrix;
  /* array of linked lists
     each list corresponds to a column,
     each value of a node in this list
     gives the positions of a 1 in this column */
} ldpc_matrix;

void add_rows(ldpc_matrix *m, int i1, int i2){
  int j;
  list l, l1;
  int value_i2;

  for(j=0; j<m->nb_columns; j++){
    l = m->matrix[j];
    l1 = NULL;
    value_i2 = 0;
    while(l!=NULL){
      if(l->value==i2)
	value_i2 = 1;
      if(l->value==i1)
	l1 = l;
      l = l->next;
    }
    if((l1!=NULL) && (value_i2==1)){
      if(l1->previous){
	l1->previous->next = l1->next;
	if(l1->next)
	  l1->next->previous = l1->previous;
      }
      else{
	m->matrix[j] = l1->next;
      }
      free(l1);
    } else {
      if((l1==NULL) && (value_i2==1)){
	l1 = m->matrix[j];
	m->matrix[j] = (node*) malloc(sizeof(node));
	m->matrix[j]->value = i1;
	m->matrix[j]->next = l1;
	m->matrix[j]->previous = NULL;
      }
    }
  }
}

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.