C - dynamically sized array of struct pointers in another struct, segmentation fault

Question

I have segfault while trying to run such code.

struct list;
struct node;

typedef struct list {
    struct node ** links;
    int size;
    int content;
} list;

typedef struct node {

    wchar_t value;
    struct list* children;
    int exists;

} node;


node* newNode(wchar_t value, int exists) {
    node *q = (struct node*)malloc(sizeof(struct node));
    q->value = value;
    q->children = newList();
    q->exists = exists;
    return q;
}

list* newList(){

    list *result = (list*)malloc(sizeof(list));
    result->size = 2;
    result->content = 0;
    result->links = (struct node**) malloc(result->size * sizeof(struct node*));

    return result;

}

void resizeList(list* list_pointer){

    if(list_pointer->size <= list_pointer->content){

        list_pointer->size *= 2;
        list_pointer->links = (struct node**) realloc(list_pointer->links, (list_pointer->size) * sizeof(struct node*));

    }
}

void pushList(list* list_pointer, node* node_pointer){
    if(node_pointer == NULL)
        return;

    resizeList(list_pointer);
    list_pointer->content++;

    int i;
    node* temp_pointer;

    for(i = 0; i < list_pointer->content; i++){

        if(list_pointer->links[i] == NULL){
            list_pointer->links[i] = node_pointer;
            break;
        }

        if(list_pointer->links[i]->value > node_pointer->value){
            temp_pointer = list_pointer->links[i];
            list_pointer->links[i] = node_pointer;
            node_pointer = temp_pointer;
        }
    }

}

Calling.

struct list* l = newList();

struct node* n1 = newNode(L'a', 1);
struct node* n2 = newNode(L'b', 1);
struct node* n3 = newNode(L'c', 1);
struct node* n4 = newNode(L'd', 1);
struct node* n5 = newNode(L'e', 1);
struct node* n6 = newNode(L'f', 1);
struct node* n7 = newNode(L'g', 1);
struct node* n8 = newNode(L'h', 1);

pushList(l, n1);
pushList(l, n2);
pushList(l, n3);
pushList(l, n4);
pushList(l, n5);
pushList(l, n6);
pushList(l, n7);
pushList(l, n8);

After first two pushes it fails.

It's supposed to create list based on values stored in nodes. But... it doesn't. It throws segfault. When I changed allocation of memory from "sizeod(node*)" to "sizeof(node)", it works, but presumably cause of allocation of bigger memory. I want to store POINTERS, not STRUCTS in this array.

I'm figthing that 6 hours with no idea what to do.

First of all, please put all of your code in one only snippet. And then add the code calling these functions — Misery
– Misery, Commented May 30, 2015 at 19:18
It's not supposed to be linked lists - I want to search then O(log n), so I need them as an array, to binsearch. And, as you see, I am sorting them. — Krzysztofik
– Krzysztofik, Commented May 30, 2015 at 19:40
I think I see your problem, you are allocating (and reallocating) list_pointer->links, and after doing that you simply assume all pointers in that array will be NULL. That is a mistake, newly allocated memory is not implicitly zeroed, your code will attept to use those faulty pointers and crash. — Havenard
– Havenard, Commented May 30, 2015 at 19:44

Ewan Mellor · Accepted Answer · 2015-05-30 19:46:54Z

If you are getting a segfault, then you should include the backtrace in your question. That will make it a lot easier to figure out what's going on.

Looking at the code, I see that you're not clearing result->links when you malloc or realloc it, but you are relying on the pointers being NULL inside pushList. You increase list_pointer->content and then check if (list_pointer->links[i] == NULL). That's going to result in undefined behavior for sure.

Memory is not filled with zeros when you use malloc or realloc. If you need that to be the case, you need to do it yourself. (You could use calloc as a replacement for malloc, but that doesn't help you with the realloc.)

This code is fine if you are learning, though I agree with the comment above that it's a bit of a convoluted way of doing it. If this is for production code then you should use an open-source list library because that will already be debugged and tuned for you.

Collectives™ on Stack Overflow

C - dynamically sized array of struct pointers in another struct, segmentation fault

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related