set

Update's the Node at this Entry in the treap with the new node (null for deleting). new_node can have undefind content because the value will be initialized internally.

Function parameters

Parameters

self:*Entry
new_node:?*Node

Functions in this namespace

Functions

Treap

Source

Implementation

pub fn set(self: *Entry, new_node: ?*Node) void {
    // Update the entry's node reference after updating the treap below.
    defer self.node = new_node;

    if (self.node) |old| {
        if (new_node) |new| {
            self.treap.replace(old, new);
            return;
        }

        self.treap.remove(old);
        self.context = .removed;
        return;
    }

    if (new_node) |new| {
        // A previous treap.remove() could have rebalanced the nodes
        // so when inserting after a removal, we have to re-lookup the parent again.
        // This lookup shouldn't find a node because we're yet to insert it..
        var parent: ?*Node = undefined;
        switch (self.context) {
            .inserted_under => |p| parent = p,
            .removed => assert(self.treap.find(self.key, &parent) == null),
        }

        self.treap.insert(self.key, parent, new);
        self.context = .{ .inserted_under = parent };
    }
}