#Doubly linked list implementation segfaulting

5 messages · Page 1 of 1 (latest)

jagged jacinth
#

Hey all, I'm currently trying to implement doubly linked lists to use in my game project but I seem to have messed up some code logic as one of my assertions are failing. The function with it is this one:

typedef struct ListNode {
    void* data;
    struct ListNode* next;
    struct ListNode* prev;
} ListNode;
typedef struct List {
    int size;
    ListNode* head;
    ListNode* tail;
    size_t type;
} List;

void list_remove_nth(List* list, int n) {
    assert(n >= 0 && n < list->size);
    ListNode* cur = list->head;
    for (int i = 0; i < n && cur != NULL; i++) 
        cur = cur->next;
    if (cur == list->head) {
        list->head = cur->next;
        if (list->head != NULL)
            list->head->prev = NULL;
        else
            list->tail = NULL;
    } else if (cur == list->tail) {
        list->tail = cur->prev;
        list->tail->next = NULL;
    } else {
        cur->prev->next = cur->next;
        cur->next->prev = cur->prev;
    }
    free(cur);
    list->size--;
}

and I'm using this code to test it:

    List* li = list_init();
    int x = 4;
    int y = 8;
    list_push(li, &x);
    list_push(li, &x);
    list_push(li, &y);
    list_push(li, &x);

    printf("List size is %d\n", li->size);

    ListNode* cur = li->head;
    printf("Getting list elements with while loop\n");
    while (cur != NULL) {
        printf("%d\n", *(int*)cur->data);
        cur = cur->next;
    }

    printf("Getting list elements with for loop\n");
    for (int i = 0; i < li->size - 1; i++) {
        printf("%d: %d\n", i, *(int*)list_get_nth(li, i));
    }

    list_remove_nth(li, 0);
    list_remove_nth(li, 3);
    printf("List size after removing elements: %d\n", li->size);

    printf("New List elements (using for loop):\n");
    for (int i = 0; i < li->size - 1; i++) {
        printf("%d\n", *(int*)list_get_nth(li, i));
    }

    list_cleanup(li);

The full code is in this Pastebin, if anyone would like to see it: https://pastebin.com/NRa8uVz5

opaque havenBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

spare dust
#

only here:

ListNode* cur = list->head;
for (int i = 0; i < n && cur != NULL; i++) 
    cur = cur->next;
if (cur == list->head) {    // (1)
    list->head = cur->next;
#

you have no proof that entering (1) implies cur != NULL (if the list->head is NULL from the start)

#

(not saying it is the segfault you're observing ; but I'd put more assert before accessing mutable things, and likely rephrase parts of the algo)