New LinkedList API footgun

Explain
21

Let’s compare then, here’s stdlib:

pub fn remove(list: *SinglyLinkedList, node: *Node) void {
    if (list.first == node) {
        list.first = node.next;
    } else {
        var current_elm = list.first.?;
        while (current_elm.next != node) {
            current_elm = current_elm.next.?;
        }
        current_elm.next = node.next;
    }
}

Zelda:

pub fn remove(list: *SinglyLinkedList, node: *Node) void {
    if (list.first == node) {
        list.first = @field(node, next);
        @field(node, next) = null;
    } else {
        var current_elm = list.first.?;
        while (@field(current_elm, next)) |next_elm| {
            if (next_elm == node) {
                @field(current_elm, next) = @field(node, next);
                @field(node, next) = null;
            } else {
                current_elm = next_elm;
            }
        }
    }
}

The obvious difference is that Zelda’s has a null check for each iteration (the capture does that). This should be assumed to have some non-zero efficiency cost, although I do wonder if it would be visible: pointer chasing is going to cost a few cycles, and branch prediction will be biased toward the fetch.

But it’s a justifiable choice because, again, there’s no reason to be removing things from a list which aren’t actually there to begin with. I just deeply hate debugging linked list problems so I coded Zelda somewhat defensively, setting the next field to null is another example of that.

Zelda’s version also keeps walking the list, which is silly, I’ll add a break statement there. So I’m glad I checked.

3 Likes