Liste chainée & boucle infinie

Version imprimable

1 pièce(s) jointe(s)

Bonjour,

Je dois faire un projet en C pour mon école d'ingénieur. Je programme une sorte de shoot-em up. Or, lors de mes tests de collisions j'ai de temps en temps un fonctionnement innatendu de ma fonction,c'est à dire qu'elle se transforeme en boucle infinie...

J'utilise le code suivant :

(list représente une liste simplement chainée).

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
 
void Update_CheckCollision(PlayData* Data)
{
    list PlanesPrev = NULL;
    list MissilePrev = NULL;
    list MissileCurr= Data->missiles;
    list PlanesCurr = Data->planes;
    list tmp;
 
    while (MissileCurr!=NULL)
    {
        list PlanesCurr = Data->planes;
 
        while (PlanesCurr != NULL)
        {
            if(((Missile*)MissileCurr->data)->position.x > ((Plane*)PlanesCurr->data)->position.x - ((Plane*)PlanesCurr->data)->size.x/2  &&
                ((Missile*)MissileCurr->data)->position.x < ((Plane*)PlanesCurr->data)->position.x + ((Plane*)PlanesCurr->data)->size.x/2  &&
                ((Missile*)MissileCurr->data)->position.y > ((Plane*)PlanesCurr->data)->position.y - ((Plane*)PlanesCurr->data)->size.y/2  &&
                ((Missile*)MissileCurr->data)->position.y < ((Plane*)PlanesCurr->data)->position.y + ((Plane*)PlanesCurr->data)->size.y/2)
            {
                if(MissilePrev == NULL)
                {
                    tmp = Data->missiles;
                    if (Data->missiles->next != NULL)
                        Data->missiles = Data->missiles->next;
                    MissileCurr = Data->missiles;
                    free(tmp);
                }
                else
                {
                    MissilePrev->next = MissileCurr->next;
                    free(MissileCurr);
                    MissileCurr = MissilePrev;
                }
                if (--(((Plane*)PlanesCurr->data)->life) <= 0)
                {
                    if (PlanesPrev == NULL)
                        {
                        tmp = Data->planes;
                        if (Data->planes->next != NULL)
                                Data->planes = Data->planes->next;
                            PlanesCurr = Data->planes;
                            free(tmp);
                        }
                    else
                    {
                        PlanesPrev->next = PlanesCurr->next;
                        free(PlanesCurr);
                        PlanesCurr = PlanesPrev;
                    }
                }
            } 
            //printf("%i\t%i\n", PlanesCurr, PlanesCurr->next);
            PlanesPrev = PlanesCurr;
            PlanesCurr = PlanesCurr->next;
        }
        MissilePrev = MissileCurr;
        MissileCurr = MissileCurr->next;
    }
    printf("Done");
}

Si je décommente le printf (printf("%i\t%i\n", PlanesCurr, PlanesCurr->next);), j'obtient :

Pièce jointe 177769

Je me retrouve avec des liste pseudo-circulaires alors que ce sont des listes génériques simples.

Si vous avez une idée d'où pourrait venir mon problème, je suis tout ouïe :)

Merci d'avance de votre aide !

16/05/2015, 10h38
LittleWhite
Bonjour,

Une première erreur :
Code:

1 2 3 4 5 6 list PlanesCurr = Data->planes; list tmp; while (MissileCurr!=NULL) { list PlanesCurr = Data->planes;
Dans un tel cas, le compilateur va faire deux variables PlanesCurr différente et va choisir la variable la plus "proche" du bloc actuel. Mais du coup, lorsque vous sortez du while, il réutilise l'autre variable et donc, utilise une autre valeur.
16/05/2015, 11h52
emixam16

Oh, bien vu !

J'ai changé ça mais l'erreur persiste. A un moment qui me semble aléatoire, la boucle devient infinie (un truc du genre Plane->suivant = UnPlaneQueJ'aiDéjàPassé). Mais comme il n'y a pas moyen d'y aller au déboggeur, et comme cette fonction tourne très rapidement, je ne peux pas non plus y aller au printf.

Si tu as des idées...
16/05/2015, 15h00
LittleWhite

Citation:

Mais comme il n'y a pas moyen d'y aller au déboggeur

Pourquoi donc ?

Y a t-il d'autres fonctions qui affectent la liste chainée ?

Citation:

Citation:

Mais comme il n'y a pas moyen d'y aller au déboggeur

Pourquoi donc ?

Parce que ma fonction peut marcher correctement pendant plusieurs milliers de tours avant que le problème se produise. Et comme il n'y a pas de plantage effectif, simplement cette fonction qui se transforme en boucle infinie, je ne crois pas que le déboggeur de Code Blocks puisse m'aider.

Oui, j'ai d'autres fonctions qui touchent mes listes chaînées , mais je ne pense pas qu'elles soient responsables de ce bug puisque si je rajoute en début de fonction :
Code:

1 2 3 4 5 6 7 8 9 10 11 while (PlanesCurr!=NULL) { printf("[%i;%i]",PlanesCurr,PlanesCurr->data); PlanesCurr = PlanesCurr->next; } while (MissileCurr!=NULL) { printf("{%i;%i}",MissileCurr,MissileCurr->data); MissileCurr = MissileCurr->next; }
je n'ai pas de boucle infinie affichée à l'écran. Ça prouve que mon erreur se trouve à l'intérieur de ma fonction.

Au sinon il y a peut être moyen d'implémenter différemment cette méthode. En effet, ça pourrait permettre de contourner mon problème, et j'ai conscience qu'une gestion de collision qui fait absolument tout les tests possible peut vite devenir lourde. Et puis quand un problème persiste après deux jours, il vaut peut-être mieux le contourner...

Merci de votre aide.

Le débogueur peut aider, car lorsque vous voyez la boucle infinie, vous pouvez le mettre en pause et il s'arrêtera et vous permettra de déboguer, dans la boucle infinie.

Les autres fonctions peuvent créer la boucle infinies, en modifiant la liste chainées et en provoquant le bouclage. Je pense notamment à la destruction/suppression d'un élément, qui causerai ce type de bouclage.
D'ailleurs, vous devriez faire des fonctions de base pour la gestion de la liste : création/ajout/suppression/destruction.
Cette partie là est obscure :
Code:

1 2 3 4 5 6 7 8 if(MissilePrev == NULL) { tmp = Data->missiles; if (Data->missiles->next != NULL) Data->missiles = Data->missiles->next; MissileCurr = Data->missiles; free(tmp); }
Pouvez-vous m'expliquer ce que vous avez voulu faire ... et pourquoi elle est nécessaire ?

18/05/2015, 10h47
tinofutinofu

Salut,

lignes 21 à 28 , dans le cas où Data->missiles->next est NULL, tu ne modifie pas la valeur de Data->missiles
alors que tu affectes sa valeur à MissileCurr (ligne 26) et que tu libère la memoire correspondante à la ligne 27
La variable MissileCurr pointe alors vers un zone mémoire que n'est plus utilisée

Tu devrais supprimer la ligne 24
la variable MissileCurr aurait alors la valeur NULL, lorsque Data->missiles->next est NULL

Bonjour, et merci pour votre aide.

J'ai suivi vos conseils et rien n'y a faire. J'ai même été voir un professeur (quand même docteur en algo) et il à pas su me dire le problème. Voyant que je ne trouverais probablement pas facilement, j'ai donc changé mon implémentation :

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
 
    list MissilePrev;
    list PlanePrev;
    if(!((MissilePrev = malloc(sizeof MissilePrev)) && (PlanePrev = malloc(sizeof PlanePrev))))
    {
        printf("CANT ALLOC !!!!!!\a");
        exit(EXIT_FAILURE);
    }
    list tmp;
    list MemPlane = PlanePrev;
    list MemMissile = MissilePrev;
    MissilePrev->next = Data->missiles;
    PlanePrev->next = Data->planes;
        for(; MissilePrev->next; MissilePrev = MissilePrev->next)
            {
                PlanePrev = MemPlane;
 
                for(; PlanePrev->next; PlanePrev = PlanePrev->next)
                    if(Vector_IsInside(((Plane*)PlanePrev->next->data)->position,
                                             ((Plane*)PlanePrev->next->data)->size,
                                             ((Missile*)MissilePrev->next->data)->position))
                    {
                        if (MissilePrev->next->next)
                        {
                            free(MissilePrev->next->data);
                            MissilePrev->next = MissilePrev->next->next;
                        }
                        else
                        {
                            free(MissilePrev->next->data);
                            MissilePrev->next = NULL;
                            return;
                        }
                        if (--(((Plane*)PlanePrev->next->data)->life) <= 0)
                        {
                            if (PlanePrev->next->next)
                            { 
                                free(PlanePrev->next->data);
                                PlanePrev->next = PlanePrev->next->next;
                            }
                            else
                            { 
                                free(PlanePrev->next->data);
                                PlanePrev->next = NULL;
                                return;
                            }
                        }
 
 
                    }
            }
    free(MemMissile);
    free(MemPlane);

Ce code est fonctionnel. Néenmoins, il reste un problème de taille (c'est le cas de le dire). Comme vous le voyez je libère incorrectement toutes mes structures en faisant free(Mavar->Data). De fait j'ai une fuite mémoire de l'ordre de 20Ko/s (Ça fait pas très professionnel). Si je fais free(Mavar) directement, je retombe de temps en temps sur mon erreur de boucle infinie.

Avez vous des idées de ce qui m’empêche de libérer mes variable et de comment éviter cette fuite mémoire?

Voici mon implémentation de list :

Code:

1
2
3
4
5
6
7
8
 
struct node
{
    void* data;
    struct node *next;
};
typedef struct node node;
typedef node* list;

Et J'ajoute comme ceci des éléments :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
Plane* plane = malloc(sizeof (Plane));
// ...
List_Add(&(Data->playData.planes),plane);
 
 
void List_Add(list *l, void* data)
{
    node *tmp;
    tmp=(node *) malloc(sizeof(node));
    tmp->data = data;
    if (*l == NULL)
    {
        (*l)=tmp;
        (*l)->next=NULL;
    }
    else
    {
        tmp->next=(*l);
        (*l)=tmp;
    }
}

Par ailleurs, si vous êtes disposés à m'aider quelques minutes sur Skype//TeamViewer, ça serait très sympathique ;)

Pour commencer, où la fonction List_Add() est-elle censée ajouter un élément?

En tête de liste?
En queue de liste?
Ailleurs?

Voici un exemple pour toujours insérer en tête de liste:

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
#include <stdlib.h>
#include <stdio.h>
 
struct node
{
    void* data;
    struct node *pNext;
};
typedef struct node node;
 
/*Fonction quick'n'dirty pour malloc() sans vraie gestion d'erreur,
  ça évite au moins les déréférencements de pointeur nul. */
void* mallocOrCrash(size_t taille)
{
	void* ret = malloc(taille);
	if(ret == NULL) {
		fprintf(stderr, "Echec de malloc pour taille=%lu\n", (unsigned long)taille);
		abort();
	}
	return ret;
}
 
void List_InsertHead(node **ppFirst, void* data)
{
	node* pNew = mallocOrCrash(sizeof *pNew);
	pNew->data = data;
 
	/*Insère en tête de liste*/
	pNew->pNext = *ppFirst;
	*ppFirst = pNew;
}

Et pour toujours mettre en queue:

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
#include <stdlib.h>
#include <stdio.h>
 
struct node
{
    void* data;
    struct node *pNext;
};
typedef struct node node;
 
/*Ceci n'est pas une vraie gestion d'erreur, mais ça aide à éliminer les bugs*/
void crashOnNull(void const * p, char const *errorMessage)
{
	if(p == NULL) {
		fputs(message, stderr);
		abort();
	}
}
 
/*Fonction quick'n'dirty pour malloc() sans vraie gestion d'erreur,
  ça évite au moins les déréférencements de pointeur nul. */
void* mallocOrCrash(size_t taille)
{
	void* ret = malloc(taille);
	if(ret == NULL) {
		fprintf(stderr, "Echec de malloc pour taille=%lu\n", (unsigned long)taille);
		abort();
	}
	return ret;
}
 
 
/*A partir d'un pointeur vers un pointeur vers un node,
  retourne un pointeur vers son champ pNext.*/
node **GetPtrNext(node** ppNode)
{
	crashOnNull(ppNode, "GetPtrNext sur un ppNode nul\n");
	crashOnNull(*ppNode, "GetPtrNext sur un *ppNode nul\n");
 
	return &( (*ppNode)->pNext );
}
 
/*À partir d'un pointeur vers n'importe lequel des pointeurs du chaînage d'une liste
  (y compris le premier ou le pointeur nul final), retourne un pointeur vers le pointeur nul final.*/
node** GetTailNullPtr(node **ppFirstOrInside)
{
	node** ppCurrent = ppFirstOrInside;
	crashOnNull(ppFirstOrInside, "ppFirstOrInside peut pointer sur un NULL, mais ne peut pas lui-meme etre nul.\n");
	while(*ppCurrent != NULL)
		ppCurrent = GetPtrNext(ppCurrent);
	return ppCurrent;
}
 
/*Ajoute en queue d'une liste chaînée,
  À partir d'un pointeur vers n'importe lequel des pointeurs du chaînage d'une liste
  (y compris le premier ou le pointeur nul final)*/
void List_AppendTail(node **ppFirstOrInside, void* data)
{
	node **ppTail = GetTailNullPtr(ppFirstOrInside);
	node* pNew = mallocOrCrash(sizeof *pNew);
	pNew->data = data;
 
	/*Insère en queue de liste*/
	pNew->pNext = *ppTail; /*Au fait, cela sera systématiquement NULL,*/
	*ppTail = pNew;
}

Et ça s'utilise ainsi:

Code:

1
2
3
node* pPremier = NULL;
List_InsertHead(&pPremier, "blabla");
List_AppendTail(&pPremier, "toto");

03/06/2015, 12h31
ChipsAlaMenthe

Un conseil qui te sera utile lors de tes prochains programmes C.
Utilise "Valgrind", c'est un logiciel en mode terminal qui te permet de suivre toutes tes fuites mémoires et de les localiser, extrêmement utile et permet parfois de déceler des erreurs insoupçonnées.

Ensuite tu as le logiciel "ddd", qui est le mode graphique de "gdb", c'est un débugguer qui te permet d'afficher ta liste chainée en visuel et donc de connaitre en temps réel l'évolution de ton programme et de ta liste chainée. ^^