Stack overflow error, despite heap allocation (C)

0

I'm currently working on a program that has to solve a 10x10 char maze, for example this one:

      1   2   3   4   5   6   7   8   9  10
___________________________________________
 1|   +  []   +  []   +  []   +   +   +  []
 2|   +  []   +   +  []   +   +  []  []  []
 3|   +   +  []  []  []   +  []  []   +   +
 4|  []  []  []  []   +   +   +  []  []   +
 5|   +  []   +  []   +  []   +   +   +  []
 6|   +   +   +   +   +   +  []  []   +  []
 7|  []   +   +   +  []  []   +   +   +  []
 8|   +   +   +  []   +   +   +  []  []   +
 9|   +   +   +  []  []   +   +  []  []   +
10|   +  []   +  []   +   +  []   +   +   +

Ignore the numbers, they are just coordinates. As for [] it's just the way the maze is printed. In actuality wherever there's a + then that means path, wherever there's [] that means there's an obstacle.

I'm using the backtrack algorithm:

void backtrack(int curX, int curY, char(*char_maze)[10], int position)
{
    if (curX < 0 || curY < 0 ||
        curX > 9 || curY > 9) {
        //out of bounds
        return;
    }
    Node tmp;
    tmp.x = curX, tmp.y = curY;
    queue(&head, &tmp);
    position++;
    if (char_maze[curX][curY] == finish) {
        //destination found TODO print path
        printf("route found");
    }
    if (char_maze[curX][curY] == path) {
        char_maze[curX][curY] = visited;
    }
    backtrack(curX, curY - 1, char_maze, position);
    backtrack(curX - 1, curY, char_maze, position);
    backtrack(curX, curY + 1, char_maze, position);
    backtrack(curX + 1, curY, char_maze, position);

    char_maze[curX][curY] = path;
    if (position) {
        del_nth(head, position);
    }
    if (!position) {
        del_first(&head);
    }
    position--;
}

The correct route will consist of a linked list, here's a node of that list:

typedef struct coords {
    int     x;
    int     y;
    struct coords * next;
}Node;

whenever backtrack(...) stumbles over a passable cell, it's supposed to mark it as visited and add it to the list. Adding to the list is done by these 2 functions:

void queue(Node ** head, Node * object)
{
    Node * tmp = (Node *)malloc(sizeof(Node)); //this is the problematic line
    *tmp = *object;
    Node * last = get_last(*(head));
    if (!last) {
        (*head) = tmp;
        tmp->next = NULL;
    }
    else {
        last->next = tmp;
        tmp->next = NULL;
    }
}

and

Node * get_last(Node * head)
{
    while (1) {
        if (head) {
            head = head->next;
        }
        else {
            return NULL;
        }
    }
return head;
}

and also under the appropriate conditions backtrack(...) should unmark a cell and delete it from the list. Deletion is done using these 2 functions:

void del_nth(Node * head, int index)
{
    Node * previous;
    for (int i = 0; i < index - 1; i++) {
        head = head->next;
    }
    previous = head;
    head = head->next;
    previous->next = head->next;
    free(head);
}

and

void del_first(Node ** head)
{
    Node * del = (*head);
    (*head) = (*head)->next;
    free(del);
}

path, visited, finish and so on are const char-s, which represent the cells of the maze.

backtrack(...)

is called with 2 coordinates set by the user, the maze itself and position which is set to 0.

Now that I explained how the code works, the problem. I've ran this code through the Visual Studio Debugger and I got a Stack overflow (parameters: 0x00000001, 0x00492FFC). exception on this line

Node * tmp = (Node *) malloc(sizeof(Node)); 

which is a part of the queue(...) function. This doesn't make any sense to me, since malloc() allocates on the heap. I'm stumped, I'm out of explanations, I have no idea why this happens. I included all of the code used in the backtrack(...) function because the problem may actually be there. It wouldn't be the first time a debugger pointed out a wrong line. Anyway, many thanks for your help in advance.

c
recursion
heap
backtracking
asked on Stack Overflow Feb 11, 2019 by Mark Ceitlin • edited Feb 11, 2019 by Mark Ceitlin

0 Answers

Nobody has answered this question yet.


User contributions licensed under CC BY-SA 3.0