Can someone explain to me why this initialization is incorrect?

Help
, ,
1

Hi, so basically I’m running into an issue, as a teaching exercise I’m trying to implement a simple linked list but, the problem is that my implementation panics, and I think I know why I’m just unsure why my approach doesn’t work I’ve commended the code with how I transpile that in my brain into C

const std = @import("std");

pub fn List(comptime T: type) type {
    return struct {
        const Self = @This();
        head: ?*Node = null,
        tail: ?*Node = null,
        size: usize = 0,

        pub const Node = struct {
            next: ?*Node = null,
            data: T = undefined,

            pub fn create(allocator: std.mem.Allocator) !?*Node {
                return (try allocator.create(Node));
            }

            pub fn destroy(node: *Node, allocator: std.mem.Allocator) void {
                allocator.destroy(node);
            }
        };

        // to me this is the equivalent of C where you do :
        // list *list_create(void) {
        //       list *list = (list*) malloc(sizeof(list));
        //       if (!list) 
        //             return null;
        //        else
        //              return list;
        // }
        pub fn init(allocator: std.mem.Allocator) !?*Self {
            return (try allocator.create(Self));
        }

        // to me this is the equivalent of C where you do :
        // list list_create(void) {
        //           return (list){.head = NULL, .tail = NULL .size = 0};
        // }
        pub fn correct_init() Self {
            return Self{
                .head = null,
                .tail = null,
                .size = 0,
            };
        }

        pub fn deinit(list: *Self, allocator: std.mem.Allocator) void {
            var curr: ?*Node = list.head;
            var temp: *Node = undefined;
            while (curr) |node| {
                temp = node;
                curr = node.next;
                temp.destroy(allocator);
            }
            allocator.destroy(list);
        }
    };
}

test "list_type_size" {
    try std.testing.expect(@sizeOf(List(i32)) == 24);
}

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();
    const maybe_list = try List(i32).init(allocator);
    if (maybe_list) |list| {
        defer list.deinit(allocator);
    }
}

I’m looking for explanation about my init function specifically, when using lldb the panics occurs when I try to access the member function deinit, I’ve looked at the standard std.SinglyLinkedList implementation, and I can’t figure where is the memory coming from, I’ve tried to look into the forum, and found a few post that where trying to explain it but it’s still doesn’t click for me, so if anyone would be kind enough to explain to me why my approach doesn’t work, I would really appreciate. Thanks

2

Add initialization in init.

    pub fn init(allocator: std.mem.Allocator) !?*Self {
        var self = try allocator.create(Self);
        self.head = null;
        self.tail = null;
        self.size = 0;
        return self;
    }

Explanation is here: Allocation is not Initialization

4 Likes
3

Hmm ok, so if I understand this correctly my problem wasn’t about the way I was doing my memory allocation, rather that my memory was uninitialized ? which meant that when calling the deinit function, none of my optionals were set to null, they had uninitialized values, which caused the panic am I understanding this correctly ?

4

Yes, you are understanding this correctly.

1 Like
5

Great and thanks for the explaination, now about the standard SinglyLinkedList implementation, I’ve said that I find it confusing that there is no allocators, or memory allocation, is it because this “externalization” of the allocation of nodes, allows the user to use an array list as an underlying “source” of nodes to improve locality and cache coherence because I’ve never thought about doing this in C but that would be pretty cool or is there another reason ?

6

I don’t think so, but it is also a win.

The typical implementations are managed and unmanaged.
Managed means keeping the allocator in the node. Increasing 50% the storage of the data structure is a really bad idea.
Unmanaged means that you pass the allocator in the call that is needed, but each time is needed you can just pass the allocated node instead.

1 Like
7

This makes a ton of sense, I’m glad I’ve asked this question, because coming from C the way of “initializing” in Zig is not very intuitive, at least not to me, If I don’t see some memory allocation explicitly I’ve trouble thinking about the lifetime and how it all works, with reference.

But last question if I can bother you again, about my first example, I had a more “canonical” instantiation function called correct_init(), When you call that sort of function, is the C translation comment just above it correct, in that you just return an “instance” of the type with some values, but it’s just on the stack ?, like you are just copying values locally ? or is there some part that I’m missing ?

1 Like
8

Yes, conceptually it is in the stack and copied to the caller provided destination, actually the optimizer inlines the call and sets directly the target value.

const global = Node.correct_init();

fn foo() void {
    const stack_local = Node.correct_init();
    ...
}
9

As to heap allocated objects, the ways are absolutely the same - after allocation fill the memory with what you need initially. In C calloc() or malloc()/memset(0) pair is used frequently, so your head, tail and size are kinda automatically zero, no need to zero them explicitly with individual assignments.

1 Like