Pourquoi ai-je une erreur de segmentation avec ce code?

Question

Essayer de créer un simple rectangle/bin packer en C. Prend une zone donnée et trouve le placement pour un rectangle de taille donnée. Environ après 4 récursions est quand je reçois le défaut de segmentation.

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

typedef struct node_type PackNode; 
struct node_type { 
int x , y; 
int width , height; 
int used; 
struct node_type *left; 
struct node_type *right; 
}; 

typedef struct point_type PackPoint; 
struct point_type { 
int x,y; 
}; 


PackNode _clone(PackNode *node) { 
PackNode clone; 
clone.used = 0; 
clone.x = node->x; 
clone.y = node->y; 
clone.width = node->width; 
clone.height= node->height; 
clone.left = NULL; 
clone.right= NULL; 
return clone; 
} 
PackNode root; 
int rcount; 

PackPoint* recursiveFind(PackNode *node, int w, int h) { 
PackPoint rp; 
PackPoint *p = NULL; 
rcount++; 
printf ("rcount = %u\n", rcount); 


//left is not null go to left, if left didn't work try right. 
if (node->left!=NULL) { 
    //move down to left branch 

    p = recursiveFind(node->left, w, h); 
    if (p!=NULL) { 
    return p; 
    } else { 
    p = recursiveFind(node->right, w, h); 
    return p; 
    } 

} else { 
    //If used just return null and possible go to the right branch; 
    if (node->used==1 || w > node->width || h > node->height) { 

    return p; 
    } 

    //if current node is exact size and hasn't been used it return the x,y of the mid-point of the rectangle 
    if (w==node->width && h == node->height) { 

    node->used=1; 


    rp.x = node->x+(w/2); 
    rp.y = node->y+(h/2); 

    p = &rp; 
    return p; 
    } 


    //If rectangle wasn't exact fit, create branches from cloning it's parent. 

    PackNode l_clone = _clone(node); 
    PackNode r_clone = _clone(node); 
    node->left = &l_clone; 
    node->right = &r_clone; 

    //adjust branches accordingly, split up the current unused areas 
    if ((node->width - w) > (node->height - h)) 
    { 
    node->left->width = w; 
    node->right->x = node->x + w; 
    node->right->width = node->width - w; 

    } else { 
    node->left->height = h; 
    node->right->y = node->y + h; 
    node->right->height = node->height - h; 
    } 

    p = recursiveFind(node->left, w, h); 
    return p; 
} 
return p; 
} 





int main(void) { 
root = malloc(
root.x=0; 
root.y=0; 
root.used=0; 
root.width=1000; 
root.height=1000; 
root.left=NULL; 
root.right=NULL; 


int i; 
PackPoint *pnt; 
int rw; 
int rh; 
for (i=0;i<10;i++) { 
    rw = random()%20+1; 
    rh = random()%20+1; 
    pnt = recursiveFind(&root, rw, rh); 
    printf("pnt.x,y: %d,%d\n",pnt->x,pnt->y); 
} 



return 0; 

} 

Answer 1

Sans regarder attentivement votre code, vous pouvez essayer d'utiliser un outil tel que Valgrind ou GDB pour identifier le numéro de ligne/expression provoquant la faute de segmentation. Vous pouvez travailler en arrière à partir de là.

"Donnez un poisson à un homme; tu l'as nourri pour aujourd'hui. Apprendre à un homme à pêcher; et vous l'avez nourri pendant toute une vie »

Answer 2

if (node->left!=NULL) { 
    //move down to left branch 

    p = recursiveFind(node->left, w, h); 
    if (p!=NULL) { 
    return p; 
    } else { 
    p = recursiveFind(node->right, w, h); 

Vous ne vérifie jamais si node-> NULL est juste, alors la récursion suivante peut déréférence NULL.

Answer 3

vous retournez un pointeur vers une variable locale dans ce cas:

//if current node is exact size and hasn't been used it return the x,y of the mid-point of the rectangle 
    if (w==node->width && h == node->height) { 

    node->used=1; 


    rp.x = node->x+(w/2); 
    rp.y = node->y+(h/2); 

    p = &rp; 
    return p; 
    } 

C'est un gros no-no. La variable locale n'est plus valide après le retour de la fonction, de sorte que le pointeur que vous retournez pointe vers la pile de la mémoire qui est potentiellement utilisée pour autre chose. Lorsque vous commencez à faire des choses avec cela, vous corrompez votre pile, et votre programme va commencer à se comporter de manière très erratique.

Pour résoudre ce problème, vous devez faire l'une des quelques petites choses: (1) ont recursiveFind() retourner une PackNode en valeur, au lieu d'un pointeur vers un PackNode; (2) utiliser une instance globale/statique PackNode, et renvoyer un pointeur sur celle-ci (notez que cela fait recursiveFind() non thread-safe); ou (3) renvoyer un pointeur vers une instance allouée dynamiquement d'un PackNode (par exemple alloué avec malloc()); cela nécessite alors que l'appelant de recursiveFind() appelle free() sur le pointeur retourné à un moment ultérieur quand il n'est plus nécessaire.

De même, ce code est également erroné:

//If rectangle wasn't exact fit, create branches from cloning it's parent. 

    PackNode l_clone = _clone(node); 
    PackNode r_clone = _clone(node); 
    node->left = &l_clone; 
    node->right = &r_clone; 

Vous devez allouer l_clone et r_clone sur le tas, pas sur la pile, parce qu'encore une fois, dès que cette fonction retourne, ces node pointeurs ne plus être valide. Je recommande d'avoir _clone() retourner un pointeur vers un PackNode (alloué avec malloc()) au lieu d'un objet complet PackNode par valeur. Si vous faites cela, cependant, le code appelant doit savoir appeler free() sur le pointeur retourné à un moment ultérieur lorsque l'objet n'est plus nécessaire. [De plus, les identifiants à portée globale commençant par un trait de soulignement sont réservés par l'implémentation, donc vous devriez éviter d'utiliser de tels noms; vous devez renommer _clone() en quelque chose comme clone() ou clonePackNode()].