由于递归算法，如何修复Segfault(How to fix Segfault due to recursive algorithm)
我试图编写一个完美的迷宫生成器，但是由于递归导致Segfault，当迷宫太大时，我在代码中几乎没有问题。 这是代码的主要部分：
t_maze *init_maze(int w, int h) { t_maze *maze; int j; int i; if ((maze = malloc(sizeof(t_maze))) == NULL) return (NULL); maze->w = w; maze->h = h; if ((maze->cells = malloc(sizeof(char *) * maze->h)) == NULL) return (NULL); j = -1; while (++j < maze->h) { if ((maze->cells[j] = malloc(sizeof(char) * maze->w)) == NULL) return (NULL); i = -1; while (++i < maze->w) maze->cells[j][i] = (j % 2 == 1 || i % 2 == 1) ? (1) : (0); } return (maze); } void detect_neighbours(t_maze *maze, char *neighbours, int x, int y) { int i; // I fill the array with 1 (means there is no neighbours) // If there is a neighours, I set the cell to 0 // In this order: Top, right, bottom, left i = -1; while (++i < 4) neighbours[i] = 1; if (y - 2 >= 0 && x >= 0 && y - 2 < maze->h && x < maze->w && maze->cells[y - 2][x] == 0) neighbours[0] = 0; if (x + 2 >= 0 && x + 2 < maze->w && y >= 0 && y < maze->h && maze->cells[y][x + 2] == 0) neighbours[1] = 0; if (y + 2 < maze->h && y + 2 >= 0 && x >= 0 && x < maze->w && maze->cells[y + 2][x] == 0) neighbours[2] = 0; if (x - 2 >= 0 && x - 2 < maze->w && y >= 0 && y < maze->h && maze->cells[y][x - 2] == 0) neighbours[3] = 0; } int there_is_no_neighbours(char *neighbours) { int i; // this function returns 0 if there is at least 1 neigbours i = -1; while (++i < 4) if (neighbours[i] == 0) i = 41; if (i == 42) return (0); return (1); } void set_maze_protected(t_maze *maze, int y, int x, int val) { // To prevent segfault when I put values in the maze, // I check the x and y keys if (x >= 0 && y >= 0 && x < maze->w && y < maze->h) maze->cells[y][x] = val; } int build_maze(t_maze *maze, int x, int y) { char neighbours[4]; int i; int ret; ret = 0; detect_neighbours(maze, neighbours, x, y); if (there_is_no_neighbours(neighbours) == 1) return (0); i = rand() % 4; while (neighbours[i] == 1) i = rand() % 4; if (i == 0) { set_maze_protected(maze, y - 1, x, 2); set_maze_protected(maze, y - 2, x, 2); ret = build_maze(maze, x, y - 2); } if (i == 1) { set_maze_protected(maze, y, x + 1, 2); set_maze_protected(maze, y, x + 2, 2); ret = build_maze(maze, x + 2, y); } if (i == 2) { set_maze_protected(maze, y + 1, x, 2); set_maze_protected(maze, y + 2, x, 2); ret = build_maze(maze, x, y + 2); } if (i == 3) { set_maze_protected(maze, y, x - 1, 2); set_maze_protected(maze, y, x - 2, 2); ret = build_maze(maze, x - 2, y); } while (ret != 0) ret = build_maze(maze, x, y); return (1); } int main() { t_maze *maze; int w; int h; w = 50; h = 50; srand(time(NULL) * getpid()); if ((maze = init_maze(w, h)) == NULL) return (1); maze->cells[0][0] = 2; build_maze(maze, 0, 0); // display_maze shows values in the 2D array (maze->cells) display_maze(maze); return (0); }我用这个调用主要调用这个函数：
build_maze(maze, 0, 0);函数检测的是单元是否有邻居，如果有，则函数随机调用其中一个，并打开两者之间的门。
例如，如果x和y的参数大于2500，则会发生段错误。 （如果它小于2500，它会工作得很好）
如何解决这个问题？
我了解了尾部呼叫，但我忽略了在这种情况下如何实现，
谢谢，
最好的祝福
I'm trying to code a perfect maze generator, but I have few problems in the code due to the recursion which leads to Segfault when the maze is too big. Here is the main part of the code:
t_maze *init_maze(int w, int h) { t_maze *maze; int j; int i; if ((maze = malloc(sizeof(t_maze))) == NULL) return (NULL); maze->w = w; maze->h = h; if ((maze->cells = malloc(sizeof(char *) * maze->h)) == NULL) return (NULL); j = -1; while (++j < maze->h) { if ((maze->cells[j] = malloc(sizeof(char) * maze->w)) == NULL) return (NULL); i = -1; while (++i < maze->w) maze->cells[j][i] = (j % 2 == 1 || i % 2 == 1) ? (1) : (0); } return (maze); } void detect_neighbours(t_maze *maze, char *neighbours, int x, int y) { int i; // I fill the array with 1 (means there is no neighbours) // If there is a neighours, I set the cell to 0 // In this order: Top, right, bottom, left i = -1; while (++i < 4) neighbours[i] = 1; if (y - 2 >= 0 && x >= 0 && y - 2 < maze->h && x < maze->w && maze->cells[y - 2][x] == 0) neighbours[0] = 0; if (x + 2 >= 0 && x + 2 < maze->w && y >= 0 && y < maze->h && maze->cells[y][x + 2] == 0) neighbours[1] = 0; if (y + 2 < maze->h && y + 2 >= 0 && x >= 0 && x < maze->w && maze->cells[y + 2][x] == 0) neighbours[2] = 0; if (x - 2 >= 0 && x - 2 < maze->w && y >= 0 && y < maze->h && maze->cells[y][x - 2] == 0) neighbours[3] = 0; } int there_is_no_neighbours(char *neighbours) { int i; // this function returns 0 if there is at least 1 neigbours i = -1; while (++i < 4) if (neighbours[i] == 0) i = 41; if (i == 42) return (0); return (1); } void set_maze_protected(t_maze *maze, int y, int x, int val) { // To prevent segfault when I put values in the maze, // I check the x and y keys if (x >= 0 && y >= 0 && x < maze->w && y < maze->h) maze->cells[y][x] = val; } int build_maze(t_maze *maze, int x, int y) { char neighbours[4]; int i; int ret; ret = 0; detect_neighbours(maze, neighbours, x, y); if (there_is_no_neighbours(neighbours) == 1) return (0); i = rand() % 4; while (neighbours[i] == 1) i = rand() % 4; if (i == 0) { set_maze_protected(maze, y - 1, x, 2); set_maze_protected(maze, y - 2, x, 2); ret = build_maze(maze, x, y - 2); } if (i == 1) { set_maze_protected(maze, y, x + 1, 2); set_maze_protected(maze, y, x + 2, 2); ret = build_maze(maze, x + 2, y); } if (i == 2) { set_maze_protected(maze, y + 1, x, 2); set_maze_protected(maze, y + 2, x, 2); ret = build_maze(maze, x, y + 2); } if (i == 3) { set_maze_protected(maze, y, x - 1, 2); set_maze_protected(maze, y, x - 2, 2); ret = build_maze(maze, x - 2, y); } while (ret != 0) ret = build_maze(maze, x, y); return (1); } int main() { t_maze *maze; int w; int h; w = 50; h = 50; srand(time(NULL) * getpid()); if ((maze = init_maze(w, h)) == NULL) return (1); maze->cells[0][0] = 2; build_maze(maze, 0, 0); // display_maze shows values in the 2D array (maze->cells) display_maze(maze); return (0); }I call this function in main with this call:
build_maze(maze, 0, 0);The function detects is the cell has neighbours, and if it has, the function calls one of them randomly and open the door between the two.
If the x and y args are bigger than 2500 for example, it will segfault. (If it is less than 2500, it will work great)
How to fix this ?
I learnt about tail call but I ignore how to implement that in this case,
Thank you,
Best Regards
最满意答案
您可以增加堆栈大小。
在POSIX系统上，您可以使用以下代码。
#include<stdio.h> #include <sys/resource.h> #define required_stack_size 0x8000000 // change this to the stack size you need int main (int argc, char **argv) { struct rlimit rl; int result; if((result = getrlimit(RLIMIT_STACK, &rl)) < 0) { fprintf(stderr, "getrlimit returned result %d\n", result); return -1; } if(rl.rlim_cur<required_stack_size) { rl.rlim_cur = required_stack_size; if((result = setrlimit(RLIMIT_STACK, &rl)) < 0) { fprintf(stderr, "setrlimit returned result = %d\n", result); return -1; } } //the rest code return 0; }You can increase the stack size.
On POSIX systems, you can use the following code.
#include<stdio.h> #include <sys/resource.h> #define required_stack_size 0x8000000 // change this to the stack size you need int main (int argc, char **argv) { struct rlimit rl; int result; if((result = getrlimit(RLIMIT_STACK, &rl)) < 0) { fprintf(stderr, "getrlimit returned result %d\n", result); return -1; } if(rl.rlim_cur<required_stack_size) { rl.rlim_cur = required_stack_size; if((result = setrlimit(RLIMIT_STACK, &rl)) < 0) { fprintf(stderr, "setrlimit returned result = %d\n", result); return -1; } } //the rest code return 0; }更多推荐
发布评论