segmentation fault testing linked list

Question

I am trying to build and test a linked list in C. But I can't seem to figure out why I am getting segmentation fault from running the test (test_linked_list.c). The problem seems to be from the list_delete function when running gdb, but I can't find where the problem is. Why is this wrong?

linkedlist.c:

#include <stdio.h>
#include <string.h>
#include "linked_list.h"

void list_init(list_t *h) {
    *h = NULL;
}

int list_size(const list_t *h) {
    node_t *p = *h;
    int r = 0;
    do {
        r += 1;
        p = p->next;
    } while (p);
    return r;
}

int list_empty(const list_t *h) {
    return (*h == NULL);
}

void list_insert(list_t *h, node_t *n) {
    n->next = *h;
    *h = n;
}

node_t *list_find(const list_t *h, int id) {
    node_t *p = *h;
    while (p) {
        if (p->id == id)
            return p;
        p = p->next;
    }
}

node_t *list_find_before(const list_t *h, int id) {
    node_t *p = *h;
    while (p && p->next) {
        if (p->next->id == id)
            return p;
        p = p->next;
    }
    return NULL;
}

node_t *list_delete(list_t *h, int id) {
    node_t *r = NULL;
    if (*h && (*h)->id == id) {
        r = *h;
        *h = NULL;
        return r;
    }
    // Here we have a syntax bug
    node_t *p = list_find_before(h, id);
    if (p) {
        r = p->next;
        p->next = p->next->next;
        r->next = NULL; 
    }
    return r;
}

void print_list(const list_t *h) {
    node_t *p = *h;
    while (p) {
        printf("%d: %s says %s\n", p->id, p->name, p->msg);
        p = p->next;
    }
}

test_linked_list.c:

#include <stdlib.h>
#include "linked_list.h"
#include <string.h>
#include <assert.h>
#include <stdio.h>

void test_delete_one() {
    list_t h;
    list_init(&h);
    node_t n;
    n.id = 0;
    strcpy(n.name, "hello");
    strcpy(n.msg, "world");
    list_insert(&h, &n);
    node_t *f = list_delete(&h, 0);
    assert(f == &n);
}

void test_delete() {
    list_t h;
    list_init(&h);
    node_t n[3];
    int i;
    for (i = 0; i < 3; i++) {
        n[i].id = i;
        list_insert(&h, &n[i]);
    }
    list_delete(&h, 1);
    assert(list_size(&h) == 2);
}

void core_dump_test() {
    int size = 0;
    list_t h;
    list_init(&h);
    size = list_size(&h);   
    printf("list size is: %d\n", size);
}

int main() {
    test_delete();
    test_delete_one();
    core_dump_test();
    printf("Pass\n");
}

Please try to create a [mre] to show us. And please use a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) to catch the crash and see where in *your* code it happens. — Some programmer dude, Feb 07 '23 at 15:20
As a hint: In the `core_dump_test` where is `h` pointing after you called `list_init(&h)`? Do `list_size` dereference this pointer? — Some programmer dude, Feb 07 '23 at 15:21
I was worried about the missing deallocations, then I noticed that there isn't a single allocation, too. Please post a [mre]. — Bob__, Feb 07 '23 at 15:24

Vlad from Moscow · Answer 1 · 2023-02-07T15:31:44.187

There are wrong several functions.

For example list_size

int list_size(const list_t *h) {
    node_t *p = *h;
    int r = 0;
    do {
        r += 1;
        p = p->next;
    } while (p);
    return r;
}

can invoke undefined behavior for an empty list.

Or another example. The function list_find

node_t *list_find(const list_t *h, int id) {
    node_t *p = *h;
    while (p) {
        if (p->id == id) return p;
        p = p->next;
    }
}

returns nothin in case when a specified value is not found in the list.

Or the function list_find_before

node_t *list_find_before(const list_t *h, int id) {
    node_t *p = *h;
    while (p && p->next) {
        if (p->next->id == id) return p;
        p = p->next;
    }
 
   return NULL;
}

ignores the first node of the list.

And so on.

As for the function list_delete when even in its beginning it has a bug setting *h to NULL

node_t *list_delete(list_t *h, int id) {
    node_t *r = NULL;
    if (*h && (*h)->id == id) {
        r = *h;
        *h = NULL;
        return r;
    }
    //...

Pay attention to that nodes must be allocated dynamically. Otherwise your list does not make sense.

chqrlie · Answer 2 · 2023-02-07T16:19:52.860

The reason you get a segmentation fault in core_dump_test() is list_size cannot handle an empty list: it reads p->next without checking for p != NULL. As a rule of thumb, you should avoid do/while loops as they tend to hide bugs efficiently.

Here is a modified version:

int list_size(const list_t *h) {
    int r = 0;
    for (const node_t *p = *h; p; p = p->next) {
        r += 1;
    }
    return r;
}

Here are modified versions of other functions with problems:

list_find has a missing return statement:

node_t *list_find(const list_t *h, int id) {
    for (const node_t *p = *h; p; p = p->next) {
        if (p->id == id)
            return p;
    }
    return NULL;   // was missing
}

list_delete truncates the list if the matching node is the first one. Also the syntax bug comes from your compiler rejecting the c99 syntax.

node_t *list_delete(list_t *h, int id) {
    node_t *p;
    node_t *r = *h;
    if (r && r->id == id) {
        *h = r->next;
        r->next = NULL;
        return r;
    }
    p = list_find_before(h, id);
    if (p) {
        r = p->next;
        p->next = r->next;
        r->next = NULL; 
        return r;
    }
    return NULL;  // no matching node
}

segmentation fault testing linked list

2 Answers2