Почему я получаю ошибку сегментации с этим кодом?

Question

Попытка сделать простой упаковщик прямоугольника / бункера в C. Занимает заданную область и находит расположение для прямоугольника любого заданного размера.

Примерно после 4-х рекурсий возникает ошибка сегментации.

#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

 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);

Вы никогда не проверяете, является ли node-> right значением NULL, поэтому следующая рекурсия может разыменовать NULL.

Answer 2

Вы возвращаете указатель на локальную переменную в этом случае:

  //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;
  }

Это большой нет-нет . Локальная переменная больше не действительна после возврата функции, поэтому возвращаемый вами указатель указывает на стековую память, которая теперь потенциально используется для чего-то другого. Когда вы начинаете что-то делать с этим, вы повреждаете свой стек, и ваша программа начинает работать очень хаотично.

Чтобы это исправить, вам нужно выполнить одно из следующих действий: (1) иметь recursiveFind() возвращать PackNode по значению вместо указателя на PackNode; (2) использовать глобальный / статический PackNode экземпляр и вернуть на него указатель (обратите внимание, что тогда это делает recursiveFind() не-поточно-безопасным); или (3) вернуть указатель на динамически распределенный экземпляр PackNode (например, выделенный с malloc()); тогда для этого требуется, чтобы вызывающий recursiveFind() вызывал free() на возвращенном указателе в более поздний момент, когда он больше не нужен.

Аналогично, этот код также неверен:

  //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;

Вам нужно разместить l_clone и r_clone в куче, а не в стеке, потому что, опять же, как только эта функция вернется, эти node указатели больше не будут действительными. Я бы рекомендовал, чтобы _clone() возвращал указатель на PackNode (выделенный с malloc()) вместо полного PackNode объекта по значению. Однако, если вы это сделаете, вызывающему коду нужно знать, чтобы вызвать free() в возвращенном указателе в какой-то более поздний момент, когда объект больше не нужен.

[Кроме того, идентификаторы в глобальной области видимости, начинающиеся с подчеркивания, зарезервированы реализацией, поэтому вам следует избегать использования таких имен; Вы должны переименовать _clone() в что-то вроде clone() или clonePackNode()].

Answer 3

Не присматриваясь к своему коду, вы можете попытаться использовать инструмент, такой как Valgrind или GDB, для определения номера строки / выражения, вызывающего ошибку сегментации. Вы можете работать в обратном направлении оттуда.

«Дай человеку рыбу; ты накормил его на сегодня. Научить человека ловить рыбу; и ты накормил его на всю жизнь »