LinkedList auto node creation garbles up the node

Hello again, I was playing with the SinglyLinkedList and reading through the code and thought I’d try something to test my understanding and I found out I don’t understand anything… When I try to create a Node within a function in the LinkedList struct/namespace, it does not complain, neither comptime nor runtime, but just creates a garbled up Node with a .next value even though that should be null. What is happening here and why?

const std = @import("std");

fn LinkedList(comptime T: type) type {
    return struct {
        pub const Node = struct {
            value: T,
            next: ?*Node = null,
            pub fn insertAfter(self: *Node, new_node: *Node) *Node {
                new_node.next = self.next;
                self.next = new_node;
                return new_node;
            }
        };
        pub fn appendValue(node: *Node, v: T) *Node {
            var new_node = Node{ .value = v };
            return node.insertAfter(&new_node);
        }
    };
}

pub fn main() !void {
    const IntegerLinkedList = LinkedList(i32);
    var node1 = IntegerLinkedList.Node{ .value = 2 };
    std.debug.print("LIST 1 {}\n", .{node1});

    var node2 = IntegerLinkedList.Node{ .value = 9 };
    _ = node1.insertAfter(&node2);
    std.debug.print("LIST 2 {}\n", .{node1});

    _ = IntegerLinkedList.appendValue(&node2, 14);
    std.debug.print("LIST 3 {}", .{node1});
}

The output:

LIST 1 linked-list.LinkedList(i32).Node{ .value = 2, .next = null }
LIST 2 linked-list.LinkedList(i32).Node{ .value = 2, .next = linked-list.LinkedList(i32).Node{ .value = 9, .next = null } }
LIST 3 linked-list.LinkedList(i32).Node{ .value = 2, .next = linked-list.LinkedList(i32).Node{ .value = 9, .next = linked-list.LinkedList(i32).Node{ .value = 43671756, .next = linked-list.LinkedList(i32).Node{ ... } } } }%

Node creation and insertAfter works as expected, but the appendValue function does something weird. What am I missing?

the append function makes a new node on the stack and you are taking a pointer to it and returning. after you return all that stack data is invalid.

answer this: where dos the memory come from for that new node in the append call? The stack makes space for a node and fills in the value, but you need a longer term storage, not stack storage.

you should use an allocator and create a node struct with it. that way the data wil be on the heap and its lifetime will extend until you destroy it.

insertafter is diffeent. you are taking a pointer to a node in the main() stack frame. if you could return from main and check the list, both those nodes would be invalid too.

3 Likes

Ohhh… I understand. Totally makes sense. Thanks.

1 Like

small warning:

a lot of memory sanitizers, allocation libraries, and languages will fill in a memory region you free’d or the stack you just returned from with garbage when in debug mode so that things blow up quickly and you immediately see the issue (I’m not sure if zig does this, but its garbage value is 0xaaaa… so if you see that either the memory is uninitialized or you free’d it and are still trying to use it).

But in release modes, things won’t do that, and that stack value can look valid for a while after returning from a function. It you had 20 variables or large arrrays on the stack, that will not be overwritten until the stack gets that deep again and it might be far away from the original code, but it is a time bomb.

So just be wary that sometimes bugs like that can hang around for while. The best defense is to just learn how the machine works and how the stack works. It super easy and pretty trivial once you get used to it, but then things like this will only ever happen when other people do weird shit with libraries or data structures (like pointers to themselves around, ugh).

2 Likes

Yeah, got it. I read about the 0xaa already, that helps a lot spotting it. I knew all about the machine, but more than a decade of js/ts fried my brain I guess. Happy to re-learn all this again.

1 Like