Why does my linked list code result in a Segmentation Fault?

Question

I wrote a quick generic linked list, simple stuff. But I have a bug and I cannot spot what it is complaining about. Pertinent code:

typedef struct _node {
    void *data;
    struct _node *next;
} node;

typedef struct _queue {
    node *root;
    node *last;
    unsigned int length;
} queue;

node * find_node(void *data, int size, queue *q)
{
    node *n;

    for(n=q->root;n;n=n->next)
        if(memcmp(data, n->data, size)==0)
            return (n);

    return (NULL);
}

Testing it:

queue q = {NULL, NULL, 0};
node *n;
int data[QUEUEMAX];
int i;

/* insert bunch of ints into queue */
for(i=0;i<QUEUEMAX;i++) {
    data[i] = give_me_a_number();
    n = alloc_node();
    n->data = data[i];
    insert_into(n, &q);
}

printf("list size = %d.\n", q.length);

/* print out, make sure they're there */   
for(n=q.root;n;n=n->next)
    printf("data = %d\n", (int)n->data); //*(int *)n->data didn't work, segfault?

/* find a specific node */
node *nd = find_node(&data[10], sizeof(int), &q);
/* remove it */
rm_node(nd, &q);

Running it:

$ ./test
list size = 256.
data = 10
data = 11
data = 12
data = 13
data = 14
data = 15
data = 16
... blah blah (256 lines)
Segmentation Fault

gdb says the problem is the memcmp() in find_node(). I think gcc is whining about the n->data being passed to memcmp(). Any ideas? Also, I was getting a segfault trying to do int x = *(int *)n->data but this seems valid to me, non?

How did you implement the insert_into() function? I suspect it doesn't set the last element in the list to point to NULL. — pmg
– pmg, Commented Mar 2, 2011 at 11:46
@pmg that may be a problem but his comment //*(int *)n->data didn't work, segfault? indicates that there is a direct problem with data. — alternative
– alternative, Commented Mar 2, 2011 at 11:49

GrahamS · Accepted Answer · 2011-03-02 11:43:16Z

1

In this code:

n->data = data[i];

You are currently setting the void* data pointer to be data[i] but you really want to set it to the address of data[i] so you need to do:

n->data = &data[i];

That is also why you got a segfault on your cast.

answered Mar 2, 2011 at 11:43

GrahamS

10.4k10 gold badges51 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

tbh Over a year ago

Haha what a dumbo I am. Thank you Graham.

Andrey · Accepted Answer · 2011-03-02 11:42:44Z

0

Segmentation Fault happens when you try to dereference NULL pointer. If you know the line where it happens verify that there no NULL there, example int x = *(int *)n->data will generate SEGFAULT if n is NULL or n->data is NULL

answered Mar 2, 2011 at 11:42

Andrey

60.3k12 gold badges127 silver badges169 bronze badges

1 Comment

alternative Over a year ago

Its actually not NULL in this case. Its just not pointing to a valid memory location because its an int.

theprole · Accepted Answer · 2011-03-02 11:43:37Z

0

Assuming that your memory allocation functions are working, most likely n->data is NULL, and therefore you can't access it. Also, why are you passing the data array as &data[10]? Why not just use data since the identifier of an array is a pointer to its first location?

answered Mar 2, 2011 at 11:43

theprole

2,35424 silver badges25 bronze badges

1 Comment

tbh Over a year ago

I'm passing data[10] for reason whatsoever. Was just to test to remove a specific node from the list. It finds the int stored in data[10] in the list, and gives me the corresponding node.

alternative · Accepted Answer · 2011-03-02 11:46:05Z

0

It looks like you are being inconsistent in whether your data is a pointer or if its a pointer thats being casted to an int. You are passing a int (since the pointer is basically a int cause of the cast).

memcpy naturally wants a void *, not an int.

So the solution really is to pass a pointer to your int in data and make everything else work with that.

answered Mar 2, 2011 at 11:46

alternative

13.1k5 gold badges44 silver badges41 bronze badges

1 Comment

tbh Over a year ago

Yes, this is a consequence of me forgetting the & when setting up the list in the test. Which GrahamS spotted.

Vamana · Accepted Answer · 2011-03-02 11:49:33Z

0

Also, the memcmp call in find_node will sometimes compare too much data. You're using memcmp with the size of the data you're searching for. If the data in the current node is shorter than that, memcmp will go beyond it, into forbidden territory. (The test code you posted won't usually trip this bug, because most of the data fields have the same length.) You need to add a length field to each node, and use the minimum of both lengths in memcmp.

answered Mar 2, 2011 at 11:49

Vamana

5782 silver badges7 bronze badges

Comments

ziu · Accepted Answer · 2011-03-02 11:49:51Z

0

You're assigning an int variable

n->data = data[i];

To what it is supposed to be a pointer

typedef struct _node {
void *data;
struct _node *next;
} node;

answered Mar 2, 2011 at 11:49

ziu

2,7282 gold badges28 silver badges40 bronze badges

Collectives™ on Stack Overflow

Why does my linked list code result in a Segmentation Fault?

6 Answers 6

1 Comment

1 Comment

1 Comment

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

1 Comment

1 Comment

1 Comment

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related