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

I wrote a quick generic linked list, simple stuff. But I have a bug and I cannot spot what it is complain开发者_如何学编程ing 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?

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.

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

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?

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.

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.

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;