voroskoi/skiplist.zig - Change YZHIW6KGNEA34657YJAFI7BWYYRA7KBEX6X6IXA2UDCDMWMRBJPQC

fix remove code

Created by voroskoi on December 21, 2024

YZHIW6KGNEA34657YJAFI7BWYYRA7KBEX6X6IXA2UDCDMWMRBJPQC

Dependencies

In channels

main

Change contents

Replacement in src/lazy.zig at line 132 [4.108]
∅:D[3.1402] → [4.4887:4949]
∅:D[5.6171] → [4.4887:4949]
B:BD[4.4887] → [4.4887:4949]
```
        pub fn search(self: @This(), search_key: K) !?*Node {
```
[5.6171]
[2.1393]
```
        pub fn search(self: @This(), search_key: K) ?*Node {
```
Deletion in src/lazy.zig at line 216 [4.108]
∅:D[5.9343] → [4.8592:8593]
B:BD[4.8592] → [4.8592:8593]

Replacement in src/lazy.zig at line 237 [4.108]

B:BD[4.9142] → [2.1926:1986]

∅:D[2.1986] → [4.9198:9286]

∅:D[6.3255] → [4.9198:9286]

∅:D[5.10206] → [4.9198:9286]

B:BD[4.9198] → [4.9198:9286]

B:BD[4.9286] → [5.10207:10255]

        pub fn remove(self: @This(), remove_key: K) !bool {
            var node_delete: ?*Node = null;
            var node_height: ?usize = null;
            var node_lock = std.Thread.Mutex{};

[4.9142]

[4.9346]

        pub fn remove(self: @This(), remove_key: K) bool {
            var node_delete: *Node = undefined;

Replacement in src/lazy.zig at line 251 [4.108]

B:BD[4.10013] → [4.10013:10133]

B:BD[4.10133] → [5.10546:10588]

∅:D[5.10588] → [4.10199:10251]

B:BD[4.10199] → [4.10199:10251]

B:BD[4.10251] → [5.10589:10637]

                        node_delete = succs[level_found.?];
                        node_height = node_delete.?.height;
                        node_lock.lock();
                        if (node_delete.?.marked) {
                            node_lock.unlock();

[4.10013]

[4.10300]

                        node_delete = succs[level_found.?].?;
                        node_delete.lock.lock();
                        if (node_delete.marked) {
                            node_delete.lock.unlock();

Replacement in src/lazy.zig at line 257 [4.108]

B:BD[4.10368] → [4.10368:10421]

                        node_delete.?.marked = true;

[4.10368]

[4.10421]

                        node_delete.marked = true;

Replacement in src/lazy.zig at line 261 [4.108]

B:BD[4.10486] → [4.10486:10528]

B:BD[4.10528] → [2.2179:2296]

∅:D[2.2296] → [4.10648:10676]

∅:D[5.10750] → [4.10648:10676]

B:BD[4.10648] → [4.10648:10676]

B:BD[4.10676] → [5.10751:10846]

∅:D[5.10846] → [4.10771:10859]

B:BD[4.10771] → [4.10771:10859]

                    // Lock handling part
                    var helds = try std.ArrayList(std.Thread.Mutex).initCapacity(self.allocator, node_height.? + 1);
                    defer {
                        for (helds.items) |*held| {
                            held.unlock();
                        }
                        helds.deinit();
                    }

[4.10486]

[4.10859]

                    var locks = std.StaticBitSet(max_level + 1).initEmpty();

Replacement in src/lazy.zig at line 263 [4.108]

B:BD[4.10860] → [4.10860:11038]

                    var pred: ?*Node = null;
                    var succ: ?*Node = null;
                    var prev_pred: ?*Node = null;
                    var valid = true;

[4.10860]

[4.11038]

                    PLACE: while (true) {
                        var pred: ?*Node = undefined;
                        var succ: ?*Node = undefined;
                        var prev_pred: ?*Node = null;
                        var valid = true;

Replacement in src/lazy.zig at line 269 [4.108]

B:BD[4.11039] → [4.11039:11298]

B:BD[4.11298] → [5.10847:10964]

∅:D[5.10964] → [4.11377:11423]

B:BD[4.11377] → [4.11377:11423]

                    var level: usize = 0;
                    while (valid and level <= node_height.?) : (level += 1) {
                        pred = preds[level];
                        succ = succs[level];
                        if (pred != prev_pred) {
                            pred.?.lock.lock();
                            helds.appendAssumeCapacity(pred.?.lock);
                            prev_pred = pred;

[4.11039]

[4.11423]

                        for (0..node_delete.height + 1) |level| {
                            pred = preds[level];
                            succ = succs[level];
                            if (pred != prev_pred) {
                                pred.?.lock.lock();
                                locks.set(level);
                                prev_pred = pred;
                            }
                            valid = !pred.?.marked and pred.?.nexts[level] == succ;
                            // If !valid cleanup and go to PLACE
                            if (!valid) {
                                // cleanup the locks
                                var lit = locks.iterator(.{});
                                while (lit.next()) |lvl| {
                                    preds[lvl].?.lock.unlock();
                                }
                                break :PLACE;
                            }

Replacement in src/lazy.zig at line 291 [4.108]

B:BD[4.11450] → [4.11450:11594]

                        valid = !pred.?.marked and pred.?.nexts[level] == succ;
                    }
                    if (!valid) continue;

[4.11450]

[4.11594]

                        // At this point everything is set for removing the Node.
                        var level: usize = node_delete.height + 1;
                        while (level > 0) : (level -= 1) {
                            preds[level - 1].?.nexts[level - 1] = node_delete.nexts[level - 1];
                        }
                        node_delete.lock.unlock();
                        node_delete.deinit(self.allocator);
                        // Lock cleanup
                        var lit = locks.iterator(.{});
                        while (lit.next()) |lvl| {
                            preds[lvl].?.lock.unlock();
                        }

Replacement in src/lazy.zig at line 305 [4.108]

B:BD[4.11595] → [4.11595:11791]

                    level = node_height.? + 1;
                    while (level > 0) : (level -= 1) {
                        preds[level - 1].?.nexts[level - 1] = node_delete.?.nexts[level - 1];

[4.11595]

[4.11791]

                        return true;

Deletion in src/lazy.zig at line 307 [4.108]
B:BD[4.11813] → [5.10965:11005]
B:BD[5.11005] → [2.2297:2355]
∅:D[2.2355] → [4.11912:11945]
∅:D[5.11058] → [4.11912:11945]
B:BD[4.11912] → [4.11912:11945]
```
                    node_lock.unlock();
                    node_delete.?.deinit(self.allocator);
                    return true;
```

Insertion in src/lazy.zig at line 308 [4.108]

[4.11970]

                    // Already marked for deletion or (not found/!okDelete)

Replacement in src/lazy.zig at line 314 [4.108]

B:BD[4.12047] → [4.12047:12112]

        fn okDelete(candidate: *Node, level_found: usize) bool {

[4.12047]

[4.12112]

        inline fn okDelete(candidate: *Node, level_found: usize) bool {

Replacement in src/lazy.zig at line 349 [4.108]

B:BD[4.13625] → [4.13625:13808]

    try std.testing.expect((try sl.search(12)).?.key.? == 12);
    try std.testing.expect((try sl.search(13)) == null);
    try std.testing.expect((try sl.search(26)).?.key.? == 26);

[4.13625]

[4.13808]

    try std.testing.expect((sl.search(12)).?.key.? == 12);
    try std.testing.expect((sl.search(13)) == null);
    try std.testing.expect((sl.search(26)).?.key.? == 26);

Replacement in src/lazy.zig at line 353 [4.108]

B:BD[4.13809] → [2.3525:3777]

    try std.testing.expect((try sl.remove(13)) == false);
    try std.testing.expect((try sl.remove(12)) == true);
    try std.testing.expect((try sl.remove(12)) == false);
    try std.testing.expect((try sl.remove(std.math.minInt(KeyType))) == true);

[4.13809]

[4.14061]

    try std.testing.expect((sl.remove(13)) == false);
    try std.testing.expect((sl.remove(12)) == true);
    try std.testing.expect((sl.remove(12)) == false);
    try std.testing.expect((sl.remove(std.math.minInt(KeyType))) == true);