New Object in C gets initialized to existing object

Question

I'm trying to implement a circular doubly linked list in C. Inserting one element was fine, but when inserting the second element, curr had the same address as prev.

struct ListNode {
    void *item;
    struct ListNode *next;
    struct ListNode *prev;
};

struct List {
    int num_members;
    ListNode head;

    /* function pointers */
    ...
};

int  ListAppend(List* list, void* item){
    ListNode* node = &(list->head);
    ListInsertBefore(list,item,node);
    
    return 0;
}

int  ListInsertBefore(List* list, void* item, ListNode* node){
    ListNode* prev = node->prev;
    ListNode curr;
    curr.item = item;
    
    node->prev = &curr;
    curr.next = node;
    prev->next = &curr;
    curr.prev = prev;

    list->num_members += 1;

    return 0;
}

Output of GDB：

62      curr.item = item;
7: node = (ListNode *) 0xbfffef08
8: *node = {item = 0x0, next = 0xbfffee70, prev = 0xbfffee70}
9: &curr = (ListNode *) 0xbfffee70
10: curr = {item = 0x0, next = 0xbfffef08, prev = 0xbfffef08}
11: prev = (ListNode *) 0xbfffee70
12: *prev = {item = 0x0, next = 0xbfffef08, prev = 0xbfffef08}

`curr` is a local variable. Its memory becomes invalid after the function returns, but you're saving a pointer to it when you do `node->prev = &curr` and `prev->next = &curr`. This causes undefined behavior. You need to allocate it dynamically with `malloc()`. — Barmar, Aug 28 '22 at 22:51
I don't see anything that checks that the list might be empty... — Fe2O3, Aug 28 '22 at 23:15
@TedLyngmo `ListAppend` would be a reasonable call to push the first item (and all others) onto the list... What? Is there another function (not shown) to handle the 1st item differently? — Fe2O3, Aug 29 '22 at 08:12
@Fe2O3 If you look at `List`, you'll see that it contains `ListNode head;`. That's what makes it work without handling he first node differently. `ListAppend` therefore works fine just as it is. — Ted Lyngmo, Aug 29 '22 at 08:19
@TedLyngmo Well, blow me down. Too quick off the mark, I overlooked that `head` is a struct, not a pointer to struct... So, there can be a node with 'indeterminant' pointer (`item`) in the ring... Would be 'tricky' to handle some searches (such as find nth VALID node before/after current node... Anyway, I stand corrected. Thanks `:-)` — Fe2O3, Aug 29 '22 at 08:31
@Fe2O3 :-) No problem. Yes, The `List` needs to be properly initialized for it to work. `List list = {0, {&list.head, &list.head}};` - or dynamically like I did it in my answer. — Ted Lyngmo, Aug 29 '22 at 08:45

Kingsley · Answer 1 · 2022-08-29T00:17:27.497

Generally when you add to a linked list like this, there's two cases to handle. The first is when the list is empty. Here the procedure is something like:

Allocate a new Node
Make the Node point to the payload Item
Because it's a doubly linked, circular list:
- The Node's prev and next point to itself (as the only node)
Make the List point to the new Node
Increment the list-size counter

When the list is not empty, now the code needs to interleave the new node into the head of the list. Additionally the current head & tail nodes need to point to the new node too.

Allocate a new Node
Make the Node point to the payload Item
Because it's a doubly linked, circular list:
- The new Node's next points to the List's head
- The new Node's prev points to the List's tail (list->head->prev)
- The List's head node (list->head) prev points to the new node
- The List's tail node (list->head->prev) next points to the new node
- The List's head points to the new node
Increment the list-size counter

It will really really help if you draw this out on paper for each step. Draw arrows for your pointers.

To help you debug this, when you create a new List and ListNode set all the pointers to NULL, and use the assert() function to check pointers you're assuming to be non-null are in-fact what you think they are.

score 0 · Accepted Answer · answered Aug 29 '22 at 06:37

ListNode curr in ListInsertBefore is a local variable that will get destroyed at the end of the function scope. Taking, storing and dereferencing its address outside the function scope make the program have undefined behavior. You need to allocate memory dynamically with malloc, example:

ListNode *ListInsertBefore(List *list, void* item, ListNode *node) {
    ListNode* curr = malloc(sizeof *curr); // allocate memory dynamically
    if(curr) {
        *curr = (ListNode) {item, node, node->prev};

        node->prev->next = curr;
        node->prev = curr;

        list->num_members++;
    }
    return curr;
}

Note: I made it return a pointer to the newly created ListNode instead of always returning 0. You can now use that return value to check if insertion actually succeeded.

Also note: Memory allocated dynamically also needs to be released using free:

List *ListCreate() {
    List *list = malloc(sizeof *list);
    if(list) *list = (List) {0, {NULL, &list->head, &list->head}};
    return list;
}

void ListFree(List *list) {
    for(ListNode *next, *curr = list->head.next; curr != &list->head; curr = next) {
        next = curr->next;
        free(curr);
    }
    free(list);
}

Demo

New Object in C gets initialized to existing object

2 Answers2