`std.DoublyLinkedList` with nodes created out of scope

Help
,
1

With Zig’s std.DoublyLinkedList how can I access elements that are inserted outside of the function scope? For example I have the following code where I’m playing around with std.DoublyLinkedList while attempting to implement a node for a b+tree I’m building out.

I’ve added code comments to the area of code I’m having troubles with. I think I understand why this doesn’t work, it has to do with scoping. But, what’s a good way to restructure this code so it works as expected :thinking:

Please also let me know if there is anything that’s idiomatic in Zig which I’m not doing, I’m used to Rust and Go so methods on structs are pretty common, not sure if it’s idiomatic zig and I just need to re-structure my code.

const std = @import("std");

pub const NodeType = enum {
    Root,
    Inner,
    Leaf,
};

fn NodePage(comptime key_type: type, comptime value_type: type) type {
    return struct {
        key: key_type,
        value: value_type,
        node: std.DoublyLinkedList.Node = .{},

        const Self = @This();

        pub const empty: Self = .{
            .key = undefined,
            .value = undefined,
        };
    };
}

var node_list: std.DoublyLinkedList = .{};

pub const Node = struct {
    key_type: type,
    value_type: type,
    allocator: std.mem.Allocator,
    node_type: NodeType,
    node_page: type,

    const Self = @This();

    pub fn init(
        comptime key_type: type,
        comptime value_type: type,
        allocator: std.mem.Allocator,
        node_type: NodeType,
    ) Self {
        var node_page: type = undefined;
        if (std.meta.eql(node_type, NodeType.Root) or std.meta.eql(node_type, NodeType.Inner)) {
            node_page = NodePage(key_type, ?*Node);
        } else {
            node_page = NodePage(key_type, value_type);
        }

        return Self{
            .key_type = key_type,
            .value_type = value_type,
            .allocator = allocator,
            .node_type = node_type,
            .node_page = node_page,
        };
    }

    pub fn deinit(self: Self) void {
        self.allocator.destroy(self.list);
    }

    pub fn insert(self: Self, key: self.key_type, value: self.value_type) void {
        if (node_list.len() == 0) {
            var insertion: NodePage(
                self.key_type,
                self.value_type,
            ) = .{
                .key = key,
                .value = value,
            };

            node_list.append(&insertion.node);
            // The following works, since, insertion was created in this scope
            var it = node_list.first;
            while (it) |node| : (it = node.next) {
                const val = @as(*NodePage(self.key_type, self.value_type), @fieldParentPtr("node", node));
                std.debug.print("{any}\n", .{val.key});
                std.debug.print("{any}\n", .{val.value});
                return;
            }
        }
    }

    pub fn get(self: Self, _: self.key_type) ?self.value_type {
        // What is a good way to make it so this scope can see the pointers from 
        // insertion(s)? Obviously this does not work and I get unitialized garbage data here.
        var it = node_list.first;
        while (it) |node| : (it = node.next) {
            const val = @as(*NodePage(self.key_type, self.value_type), @fieldParentPtr("node", node));
            std.debug.print("{any}\n", .{val.key});
            std.debug.print("{any}\n", .{val.value});
            return null;
        }
        return null;
    }
};
2

The problem here is that you’re storing the node on the stack. The typical solution to this is to let the caller handle the node storage and pass it itself to insert. Otherwise, it would also be possible to allocate it non-intrusively on the heap and handle the lifetime accordingly (like you seem to do already in deinit!)

3

Ah okay, so I just need to ensure that I’m allocating the insertions or let the caller handle them? That makes sense. This is supposed to be completely internal to the library so I’ll likely handle them by allocating to the heap.

4

Okay, I would expect something like this to work when managing the lifetimes of the insertion objects:

    pub fn deinit(self: Self) void {
        var it = node_list.first;
        while (it) |node| : (it = node.next) {
            const val = @as(*NodePage(self.key_type, self.value_type), @fieldParentPtr("node", node));
            self.allocator.destroy(val);
        }
    }

    pub fn insert(self: Self, key: self.key_type, value: self.value_type) !void {
        if (node_list.len() == 0) {
            var insertion = try self.allocator.create(NodePage(self.key_type, self.value_type));
            insertion.* = .{
                .key = key,
                .value = value,
            };

            node_list.append(&insertion.node);
        }
    }

    pub fn get(self: Self, _: self.key_type) ?self.value_type {
        var it = node_list.first;
        while (it) |node| : (it = node.next) {
            const val = @as(*NodePage(self.key_type, self.value_type), @fieldParentPtr("node", node));
            std.debug.print("{any}\n", .{val.key});
            std.debug.print("{any}\n", .{val.value});
        }
        return null;
    }

I’m getting a segmentation fault for the deinit traversal

Segmentation fault at address 0x777172b20008
/home/devan/Documents/Projects/zigtree/src/node.zig:60:39: 0x123a02c in deinit__anon_43295 (root.zig)
        while (it) |node| : (it = node.next) {
                                      ^

But when I add a return (keep in mind my list has one item at this point I’ve only inserted one thing) it works fine:

    pub fn deinit(self: Self) void {
        var it = node_list.first;
        while (it) |node| : (it = node.next) {
            const val = @as(*NodePage(self.key_type, self.value_type), @fieldParentPtr("node", node));
            self.allocator.destroy(val);
            return;
        }
    }

Do I need to keep track of how many items the list has? Why does the while loop seem to work fine within the get method?

5

You first destroy the node (by destroying the NodePage that owns the std.DoublyLinkedList.Node) and then you try to use it to access the pointer to the next node, which then accesses memory that is no longer valid.

Instead you can do something like this:

pub fn deinit(self: Self) void {
    var it = node_list.first;
    while (it) |node| {
        it = node.next;
        const val = @as(*NodePage(self.key_type, self.value_type), @fieldParentPtr("node", node));
        self.allocator.destroy(val);
    }
}

To avoid accessing node after it has been destroyed by destroying its containing struct.
The continuation expression runs after the body was evaluated and thus it runs too late, because at that time node.next accesses memory that was destroyed / freed.

Adding the return just causes the continuation expression to never be evaluated because you exit the while loop before it would run.

6

Ah okay I see, thanks! That makes sense.