如何预测堆栈溢出？堆栈中如何以及哪些内存存储？

Question

我实现了一个 floodfill 递归函数来检查玩家是否能够到达地图出口，或者它是否会被墙壁包围。所以一个简单的地图看起来像这样：

111111111
100010C01
10P000101
10C000E01
100000001
111111111

1

-> 墙；

0

-> 空白区域；

C

-> 收藏品；

P

-> 玩家；

E

-> 退出

还有我的 floodfill 功能：

void    find_accessible_elems(t_map *map, t_elems *elems, size_t i, size_t j)
{
    elems->iterations++;
    if (map->spaces[i][j] == EXIT)
        elems->exit++;
    else if (map->spaces[i][j] == COLLECTIBLE)
        elems->collectibles++;
    map->spaces[i][j] = 'A';
    if (map->spaces[i][j + 1] != 'A' && map->spaces[i][j + 1] != WALL)
        find_accessible_elems(map, elems, i, j + 1);
    if (map->spaces[i][j - 1] != 'A' && map->spaces[i][j - 1] != WALL)
        find_accessible_elems(map, elems, i, j - 1);
    if (map->spaces[i + 1][j] != 'A' && map->spaces[i + 1][j] != WALL)
        find_accessible_elems(map, elems, i + 1, j);
    if (map->spaces[i - 1][j] != 'A' && map->spaces[i - 1][j] != WALL)
        find_accessible_elems(map, elems, i - 1, j);
}

在尝试验证大地图时，我显然遇到了堆栈溢出，因此我做了完全相同的迭代。它正在工作，我只能使用迭代，但它比递归慢得多，这真的很可悲。

void    find_accessible_elems_iter(t_map *map, t_elems *elems)
{
    t_pos_stack *stack;

    stack = new_pos(map->player.pos.x, map->player.pos.y);
    while (stack)
    {
        if (map->spaces[stack->pos.y][stack->pos.x] == 'A' || map->spaces[stack->pos.y][stack->pos.x] == WALL)
        {
            shift_pos(&stack);
            continue ;
        }
        else if (map->spaces[stack->pos.y][stack->pos.x] == EXIT)
            elems->exit++;
        else if (map->spaces[stack->pos.y][stack->pos.x] == COLLECTIBLE)
            elems->collectibles++;
        map->spaces[stack->pos.y][stack->pos.x] = 'A';
        if (map->spaces[stack->pos.y][stack->pos.x + 1] != 'A'
                && map->spaces[stack->pos.y][stack->pos.x + 1] != WALL)
            push_pos(stack, stack->pos.x + 1, stack->pos.y);
        if (map->spaces[stack->pos.y][stack->pos.x - 1] != 'A'
                && map->spaces[stack->pos.y][stack->pos.x - 1] != WALL)
            push_pos(stack, stack->pos.x - 1, stack->pos.y);
        if (map->spaces[stack->pos.y + 1][stack->pos.x] != 'A'
                && map->spaces[stack->pos.y + 1][stack->pos.x] != WALL)
            push_pos(stack, stack->pos.x, stack->pos.y + 1);
        if (map->spaces[stack->pos.y - 1][stack->pos.x] != 'A'
                && map->spaces[stack->pos.y - 1][stack->pos.x] != WALL)
            push_pos(stack, stack->pos.x, stack->pos.y - 1);
        shift_pos(&stack);
        elems->iterations++;
    }
}

我的意愿是仅在必要时使用迭代。为此，我尝试计算该函数将使用多少堆栈内存，并使用保存在 Makefile 上的宏

ulimit -s

中的

MAX_STACK_SIZE_KB

与可用堆栈内存进行比较。

int has_valid_path_map(t_map *map)
{
    t_elems elems;
    t_map   accessible_map;
    size_t  stack_call_size;
    size_t  prev_stack_size;

    copy_map(&accessible_map, map);
    elems.collectibles = 0;
    elems.exit = 0;
    elems.iterations = 0;
    stack_call_size = sizeof(&accessible_map) + sizeof(&elems) + sizeof(map->player.pos.y)
        + sizeof(map->player.pos.x);
    prev_stack_size = 500; // Don't know how to calculate this
    if ((map->max_x * map->max_y - map->walls_amount) * stack_call_size + prev_stack_size > MAX_STACK_SIZE_KB * 1024)
        find_accessible_elems_iter(&accessible_map, &elems);
    else
        find_accessible_elems(&accessible_map, &elems,
            map->player.pos.y, map->player.pos.x);
    terminate_map(&accessible_map);
    return (elems.exit &&
                elems.collectibles == ft_stroccurrences(map->elems, COLLECTIBLE));
}

迭代函数会在堆栈溢出发生之前被调用，这意味着未来的堆栈内存无法很好地计算。

我什至不知道这是否可能，但我的问题是：

• 堆栈中如何以及哪些内存存储？
• 如何计算函数的堆栈内存消耗？

Answer 1

虽然可能有多种方法可以获取递归函数的堆栈限制和堆栈使用，但这通常不是理想的解决方案。一方面，它如何解决您的问题？它只是让您知道是否会出现堆栈溢出。它没有给你解决这个问题的方法。

您可以在不使用递归函数的情况下实现自己的算法递归洪水填充。分配内存作为堆栈。看看你的代码，它只需要是一组位置（每个位置是一个水平坐标和一个垂直坐标）。设置一个变量作为栈顶的索引。将初始元素压入堆栈。编写一个只要堆栈不为空就继续执行的循环：

• 获取栈顶元素并弹出。
• 对该元素执行您想要的任何洪水填充处理。 （算一下里面有没有收藏品？）
• 对于每个将被填充的邻居，将邻居压入堆栈。

现在你的问题是让这个数组达到你需要的大小。您可以将其分配给阵列中洪水填充可能需要的最大深度。或者您可以分配一些适中的大小，然后根据需要使用

realloc

来增长数组。

使用完毕后释放内存。