Zelda II: The Adventure of Link

Showcase
1

Announcing the rebirth of Zelda, a type-safe intrusive linked list mixin (well, two of them). The original Zelda had its own showcase, but under the circumstances I felt a clean break with the past was indicated.

usingnamespace is gone (but not forgotten). Technically OG Zelda did not depend on the presence of usingnamespace in the language, the implementation didn’t use it, user code could stick with the List types or manually import the functions into the namespace. Still, what fun is that?

zelda 0.2.0 makes use of the approved zero-width field hack, with acceptable results.

While I was at it, I took the opportunity to rectify some names, clarify the invariants, add a few more operations, and enhance the library with sorting, and, for doubly-linked lists, matching and filtering as well.

Singly-linked lists will most likely gain matching and filtering abilities as well, I’m just out of time for now.

I know most of you don’t use linked lists, and when you do, you hand-roll them in the finest C style. Well that’s the nice thing about mixins: if and when you realize that it would be real handy to sort your list, bring in Zelda, which will do that. No need to touch your already-written list traversals.

Or just roll with Zelda from go. Up to you.

15 Likes
2

Hey, cool idea. Just the other day, I was writing my third list traversal of the day, and I thought that I should really find some way of reusing the code. I couldn’t put everything in one function, because each of them had something slightly different from the others.

Just a heads up:

fn insertSortFn(orderFn: fn (*Node, *Node) callconv(.@"inline") bool) fn (*Node, *Node) *Node {
            return struct {
                pub fn insert(head: *Node, node: *Node) *Node {
                    orderGuard();
                    if (orderFn(node, head)) {
                        @field(node, next) = head;
                        return node;
                    }
                    var m_next = @field(head, next);
                    var last = head;
                    var limit: (if (has_limit) usize else void) = if (has_limit) 0 else {};
                    while (m_next) |next_node| {
                        if (has_limit) limit += 1;
                        if (orderFn(node, next_node)) {
                            @field(last, next) = node;
                            @field(node, next) = next_node;
                            return head;
                        }
                        last = next_node;
                        m_next = @field(next_node, next);
                        if (has_limit) if (limit >= seek_limit) @panic("insertSorted exceeded seek limit");
                    }
                    @field(last, next) = node;
                    return head;
                }
            }.insert;
        }

This will insert a node at the wrong place if the new node is ordered before the first node.
The correct and most optimal way to traverse a singly-linked list when you need both the current and previous nodes is through Linus’ good taste algorithm. I can’t found the link right now because I’m on regulated wifi that blocks all social media, but the idea is to create a dummy node in the stack. Make the dummy point to the first node. Set current_node to the first node and previous_node to the dummy. Now start iterating from current_node. At the end of the algorithm, dummy.next will be pointing to the new head of the list, which might not be the same one that you had initially.

3

This prevents that, no?

    if (orderFn(node, head)) {
         @field(node, next) = head;
         return node;
    }

I added a test which seems to confirm the correct behavior. What’s going on there could be clearer, I admit.

But that’s why insertions always return and reassign the .first field of a List, because it can change. I think that’s what you’re actually concerned about, but it works, just differently from what you’re expecting.

I’m certainly interested in reading it when you get a chance. That’s part of why the singly-linked lists don’t have matching, filter, a “taker”, it’s all just incrementally more annoying to do because of the need to track the previous node at all times, nodes can’t remove themselves without help. I do intend to get back to it!

That’s basically how reversal works, which is straight out of the standard library. Zelda singly-linked lists maintain a tail reference, so there’s a little fixup which needs to happen.

Well, it’s not a dummy node, it’s an indirect pointer which can be kept updated. Related tech.

Linked lists don’t encapsulate very well, it’s true. Zelda is a nice collection of various generic operations on lists, and I’m pleased with how the Matcher code turned out, filter is a fairly linked-list-friendly operation which is just gnarly enough that delegating it to a library helps out. At least that’s the premise.

I wrote a more generic iterator and ended up deleting it, because it provides next to no convenience or safety, ended up just being a fancy way to capture next. That isn’t a useful thing to do.

1 Like
4

My bad, I missed that part.
With that said, I see your code at lot of special cases, you check if the list is not null, if the node should come before the head and all that.
With Linus’s good taste code every corner case becomes a regular case:
I first heard about from his TED interview. The interview is for laymen, so he doesn’t go too in depth into it.
This article discusses it more thoroughly.

3 Likes
5

NGL, I thought there was a link to download the Zelda game in this post, so I clicked on it.

2 Likes
6

This turned out to be a good tip.

At first I thought, because Zelda singly-linked lists maintain a reference to the last element, this wasn’t going to be helpful there. But then I thought about it some more:

pub fn removeUncheckedOld(list: *List, node: *Node) void {
    if (list.first == node) {
        list.first = @field(node, next);
        if (list.last == node) {
            assert(list.first == null); // no-coverage
            list.last = list.first;
        }
        @field(node, next) = null;
    } else {
        var current = list.first.?;
        while (true) {
            const next_node = @field(current, next).?;
            if (next_node == node) {
                @field(current, next) = @field(node, next);
                @field(node, next) = null;
                if (list.last == node) {
                    list.last = current;
                }
                return;
            }
            current = next_node;
        }
    }
}

pub fn removeUncheckedNew(list: *List, node: *Node) void {
    var cursor = &list.first;
    while (cursor.* != node) : (cursor = &@field(cursor.*.?, next)) {}
    if (list.last == node) {
        if (list.first != list.last)
            list.last = @fieldParentPtr(next, cursor)
        else
            list.last = null;
    }
    cursor.* = @field(node, next);
    @field(node, next) = null;
}

Point taken!

2 Likes