Travelling salesman unexpected segmentation fault

Question

I'm trying to implement my own depth-first search algorithm for the travelling salesman problem in C99, but I'm getting an unexpected segmentation fault.

I have a small series of nodes corresponding (roughly) to places in the UK with symmetric paths between them. The problem occurs early on in the newNode() method, where I create a new node and set up its initial state. This involves creating an array of paths for the node which will specify connected nodes and the "distance" between them, in which the node element of each path is initialised to NULL. The arrays are much larger then I need for the example graph I've implemented currently (see MAX_PATHS), so it's easy to expand later.

The paths array can contain 16 elements in this case. The FOR loop which initialises this array raises a segmentation fault when i = 3. The reason why completely eludes me. I have added some output from gdb below the code. Hopefully it helps, or you may prefer to use your own methods.

Thanks; any help would be greatly appreciated!

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

#define NODES 4
#define MAX_PATHS 16

typedef struct _node_t node_t;
typedef struct _path_t path_t;

struct _node_t
{
    char name[64];
    struct _path_t* paths;
};

struct _path_t
{
    struct _node_t* node;
    int dist;
};

node_t* nodes[NODES];

node_t* newNode(char* name)
{
    node_t* toReturn = (node_t*) malloc(sizeof(node_t*));

    if (toReturn == NULL)
    {
        perror("malloc");
        exit(EXIT_FAILURE);
    }

    printf("toReturn (%p)\n", toReturn);

    strcpy(toReturn->name, name);

    toReturn->paths = (path_t*) malloc(sizeof(path_t) * MAX_PATHS);

    if (toReturn->paths == NULL)
    {
        perror("malloc");
        exit(EXIT_FAILURE);
    }

    printf("toReturn->paths (%p)\n", toReturn->paths);

    for (int i = 0; i < MAX_PATHS; i++)
        toReturn->paths[i].node = NULL; /* !!! */

    return toReturn;
}

void addPath(node_t* node1, node_t* node2, int dist)
{
    int i = 0;

    while (i < MAX_PATHS)
    {
        if (node1->paths[i].node == NULL)
        {
            node1->paths[i].node = node2;
            node1->paths[i].dist = dist;
            break;
        }

        i++;
    }

    if (i == MAX_PATHS)
    {
        fprintf(stderr, "Ran out of paths!!\n");
        exit(EXIT_FAILURE);
    }

    i = 0;

    while (i < MAX_PATHS)
    {
        if (node2->paths[i].node == NULL)
        {
            node2->paths[i].node = node1;
            node2->paths[i].dist = dist;
            break;
        }

        i++;
    }

    if (i == MAX_PATHS)
    {
        fprintf(stderr, "Ran out of paths!!\n");
        exit(EXIT_FAILURE);
    }
}

int getNodeIndex(node_t* node)
{
    for (int i = 0; i < NODES; i++)
        if (nodes[i] == node)
            return i;

    return -1;
}

void depthFirstSearch(node_t* node, int* visited, int depth, int length)
{
    printf("%s\n", node->name);

    int i = 0; /* Path pointer */

    int thisVisited[NODES];
    memcpy(thisVisited, visited, sizeof(int) * NODES);

    /* Set this node as visited */

    visited[getNodeIndex(node)] = 1;

    /* Now traverse all connected nodes that haven't been visited */

    while (node->paths[i].node != NULL)
    {
        if (visited[getNodeIndex(node->paths[i].node)] == 0)
            depthFirstSearch(node->paths[i].node, thisVisited, depth + 1,
                                  node->paths[i].dist);

        i++;
    }

    for (int j = 0; j < depth; j++)
        putchar(' ');
}

int main(int argc, char** argv)
{
    nodes[0] = newNode("Liverpool");
    nodes[1] = newNode("London");
    nodes[2] = newNode("Manchester");
    nodes[3] = newNode("Norwich");

    addPath(nodes[0], nodes[1], 212);
    addPath(nodes[0], nodes[2], 34);
    addPath(nodes[1], nodes[2], 208);
    addPath(nodes[1], nodes[3], 114);
    addPath(nodes[2], nodes[3], 191);

    int visited[NODES] = {0};

    depthFirstSearch(nodes[0], visited, 0, 0);

    return EXIT_SUCCESS;
}

---

After malloc()ing the node and its path array:

(gdb) p toReturn
$16 = (node_t *) 0x602010
(gdb) p toReturn->paths
$17 = (struct _path_t *) 0x602030

Before the FOR loop:

(gdb) p toReturn->paths[0]
$18 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[1]
$19 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[2]
$20 = {node = 0x602030, dist = 0} // (I don't understand this value here.)
(gdb) p toReturn->paths[3]
$21 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[4]
$22 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[5]
$23 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[6]
$24 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[7]
$25 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[8]
$26 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[9]
$27 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[10]
$28 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[11]
$29 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[12]
$30 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[13]
$31 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[14]
$32 = {node = 0x0, dist = 0}
(gdb) p toReturn->paths[15]
$33 = {node = 0x0, dist = 0}

State of toReturn before FOR loop:

(gdb) p *toReturn
$36 = {
  name = "Liverpool", '\000' <repeats 15 times>, "\021\001", '\000' <repeats 37 times>, paths = 0x602030}

It remains unchanged until it unexpectedly changes in the FOR loop when i = 3

(gdb) p *toReturn
$40 = {
  name = "Liverpool", '\000' <repeats 15 times>, "\021\001", '\000' <repeats 37 times>, paths = 0x0}

Answer 1

node_t* toReturn = (node_t*) malloc(sizeof(node_t*));

This looks wrong. You need to allocate the size of node_t not node_t *. While we are at it , do not cast malloc.