voroskoi/skiplist.zig - Change E6N5WBHRYQKCNE5GDHDO46KKQ3HHGUV7TZLHD63TV3P2PQ65VJGAC

sigh...

Created by voroskoi on December 26, 2024

E6N5WBHRYQKCNE5GDHDO46KKQ3HHGUV7TZLHD63TV3P2PQ65VJGAC

Dependencies

In channels

main

Change contents

Replacement in src/lazy.zig at line 207 [4.108]
B:BD[4.6278] → [4.6278:6305]
```
            while (true) {
```
[4.6278]
[5.1703]
```
            FINDNODE: while (true) {
```

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

[4.7274]

[4.7467]

                // Find the new-node's place
                var prev_pred: ?*Node = null;

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

B:BD[4.7468] → [6.779:867]

B:BD[6.867] → [2.543:645]

                    for (0..rlevel + 1) |level| { // +1 because we want to reach rlevel
                        const pred = preds[level];
                        const succ = succs[level];

[4.7468]

[4.7696]

                for (0..rlevel + 1) |level| { // +1 because we want to reach rlevel
                    const pred = preds[level];
                    const succ = succs[level];

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

B:BD[4.7697] → [7.7854:7939]

B:BD[7.8028] → [7.8028:8194]

                        if (pred != prev_pred) { // only count multilayer items once
                            pred.?.lock.lock();
                            locks.set(level);
                            prev_pred = pred;
                        }

[4.7697]

[7.8194]

                    if (pred != prev_pred) { // only count multilayer items once
                        pred.?.lock.lock();
                        locks.set(level);
                        prev_pred = pred;
                    }

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

B:BD[7.8195] → [7.8195:8696]

B:BD[7.8696] → [3.0:94]

∅:D[3.94] → [7.8784:8841]

B:BD[7.8784] → [7.8784:8841]

                        std.debug.assert(pred != null);
                        // Validation checks that for each layer:
                        // 1) level ≤ rlevel
                        // 2) preds[level] and succs[level] are still adjacent at `level`, and
                        // 3) neither is marked.
                        // If validation fails, the thread encountered a conflicting operation, so it releases
                        // the locks it acquired and restarts place finding.
                        const valid = !pred.?.marked and (succ == null or !succ.?.marked) and
                            pred.?.nexts[level] == succ;

[7.8195]

[7.8841]

                    std.debug.assert(pred != null);
                    // Validation checks that for each layer:
                    // 1) level ≤ rlevel
                    // 2) preds[level] and succs[level] are still adjacent at `level`, and
                    // 3) neither is marked.
                    // If validation fails, the thread encountered a conflicting operation, so it releases
                    // the locks it acquired and restarts place finding.
                    const valid = !pred.?.marked and (succ == null or !succ.?.marked) and
                        pred.?.nexts[level] == succ;

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

B:BD[7.8842] → [7.8842:8941]

B:BD[7.8941] → [2.646:697]

∅:D[2.697] → [7.9194:9262]

B:BD[7.9194] → [7.9194:9262]

                        // If !valid cleanup and go to PLACE
                        if (!valid) {
                            locks.release(&preds);
                            break :PLACE;
                        }

[7.8842]

[4.7910]

                    // If !valid cleanup and go to FINDNODE
                    if (!valid) {
                        locks.release(&preds);
                        continue :FINDNODE;

Insertion in src/lazy.zig at line 251 [4.108]
[4.7932]
[4.7932]
```
                }
```

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

B:BD[4.7933] → [7.9263:9343]

B:BD[7.9343] → [6.868:964]

                    // At this point everything is set for adding the new Node.
                    var node = try Node.init(self.allocator, insert_key, insert_value, rlevel);

[4.7933]

[4.8669]

                // At this point everything is set for adding the new Node.
                var node = try Node.init(self.allocator, insert_key, insert_value, rlevel);

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

B:BD[4.8670] → [8.7773:7833]

∅:D[9.1020] → [7.9519:9678]

∅:D[10.1929] → [7.9519:9678]

∅:D[8.7833] → [7.9519:9678]

B:BD[7.9519] → [7.9519:9678]

                    NEXT: for (0..node.nexts.len) |level| {
                        node.nexts[level] = succs[level]; // unlocked, but safe, as not linked yet
                        preds[level].?.nexts[level] = node;

[4.8670]

[8.7834]

                LEVELS: for (0..node.nexts.len) |level| {
                    node.nexts[level] = succs[level]; // unlocked, but safe, as not linked yet
                    preds[level].?.nexts[level] = node;

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

B:BD[8.7835] → [8.7835:7889]

B:BD[8.7889] → [11.150:399]

                        if (builtin.mode == .Debug) {
                            // If the next is not null, make sure its key is set
                            if (node.nexts[level]) |next_node| {
                                std.debug.assert(next_node.key != null);
                            }

[8.7835]

[11.399]

                    if (builtin.mode == .Debug) {
                        // If the next is not null, make sure its key is set
                        if (node.nexts[level]) |next_node| {
                            std.debug.assert(next_node.key != null);
                        }

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

B:BD[11.400] → [11.400:495]

B:BD[11.495] → [2.698:764]

∅:D[2.764] → [8.7948:8003]

B:BD[8.7948] → [8.7948:8003]

B:BD[8.8003] → [8.8003:8087]

B:BD[8.8087] → [8.8087:8179]

                            // Check if all pred nodes were locked when we inserted this node.
                            var lit = locks.bitset.iterator(.{});
                            while (lit.next()) |lvl| {
                                if (preds[lvl].? == preds[level].?) continue :NEXT;
                            }
                            @panic("level is not locked...");

[11.400]

[8.8654]

                        // Check if all pred nodes were locked when we inserted this node.
                        var lit = locks.bitset.iterator(.{});
                        while (lit.next()) |lvl| {
                            if (preds[lvl].? == preds[level].?) continue :LEVELS;

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

[8.8680]

[7.9678]

                        @panic("level is not locked...");

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

∅:D[8.8682] → [7.9700:9746]

B:BD[7.9700] → [7.9700:9746]

                    node.fully_linked = true;

[7.9700]

[4.8791]

                }
                node.fully_linked = true;

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

B:BD[4.8792] → [7.9747:9788]

B:BD[7.9788] → [2.765:808]

                    // cleanup the locks
                    locks.release(&preds);

[4.8792]

[4.9087]

                // cleanup the locks
                locks.release(&preds);

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

B:BD[4.9088] → [7.10064:10115]

                    return true;
                }

[4.9088]

[4.9117]

                return true;

Insertion in src/lazy.zig at line 281 [4.108]
[4.9131]
[4.9131]
```
            unreachable;
```

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

B:BD[12.121] → [12.121:169]

            var node_delete: *Node = undefined;

[12.121]

[4.9346]

            var node_delete: ?*Node = null;

Replacement in src/lazy.zig at line 293 [4.108]
B:BD[4.9724] → [4.9724:9751]
```
            while (true) {
```
[4.9553]
[5.2104]
```
            FINDNODE: while (true) {
```

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

B:BD[12.232] → [12.232:386]

                        node_delete.lock.lock();
                        if (node_delete.marked) {
                            node_delete.lock.unlock();

[12.232]

[4.10300]

                        node_delete.?.lock.lock();
                        // check again if the node is already marked for deletion
                        if (node_delete.?.marked) {
                            node_delete.?.lock.unlock();

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

B:BD[4.10368] → [12.387:438]

                        node_delete.marked = true;

[4.10368]

[4.10421]

                        node_delete.?.marked = true;

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

[4.10860]

[4.11038]

                    var prev_pred: ?*Node = null;

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

B:BD[4.11039] → [9.1276:1341]

B:BD[9.1341] → [2.853:963]

                        for (0..node_delete.nexts.len) |level| {
                            const pred = preds[level];
                            const succ = succs[level];

[4.11039]

[2.963]

                    for (0..node_delete.?.nexts.len) |level| {
                        const pred = preds[level];
                        const succ = succs[level];

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

∅:D[2.964] → [12.928:1163]

B:BD[12.928] → [12.928:1163]

                            if (pred != prev_pred) {
                                pred.?.lock.lock();
                                locks.set(level);
                                prev_pred = pred;
                            }

[2.964]

[12.1163]

                        if (pred != prev_pred) {
                            pred.?.lock.lock();
                            locks.set(level);
                            prev_pred = pred;
                        }

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

B:BD[12.1164] → [3.95:185]

                            const valid = !pred.?.marked and pred.?.nexts[level] == succ;

[12.1164]

[12.1248]

                        const valid = !pred.?.marked and pred.?.nexts[level] == succ;

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

B:BD[12.1249] → [12.1249:1409]

B:BD[12.1409] → [2.965:1020]

∅:D[2.1020] → [12.1629:1705]

B:BD[12.1629] → [12.1629:1705]

                            // If !valid cleanup and go to PLACE
                            if (!valid) {
                                // cleanup the locks
                                locks.release(&preds);
                                break :PLACE;
                            }

[12.1249]

[4.11423]

                        // If !valid cleanup and go to FINDNODE
                        if (!valid) {
                            // cleanup the locks
                            locks.release(&preds);
                            continue :FINDNODE;

Insertion in src/lazy.zig at line 334 [4.108]
[4.11449]
[4.11449]
```
                    }
```

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

B:BD[4.11450] → [12.1706:1788]

B:BD[12.1788] → [9.1342:1408]

B:BD[9.1408] → [8.8683:8748]

∅:D[8.8748] → [12.1914:2010]

B:BD[12.1914] → [12.1914:2010]

                        // At this point everything is set for removing the Node.
                        var level: usize = node_delete.nexts.len;
                        NEXT: while (level > 0) : (level -= 1) {
                            preds[level - 1].?.nexts[level - 1] = node_delete.nexts[level - 1];

[4.11450]

[8.8749]

                    // At this point everything is set for removing the Node.
                    std.debug.assert(node_delete.?.nexts.len >= 1);
                    var level: usize = node_delete.?.nexts.len;
                    LEVELS: while (level > 0) : (level -= 1) {
                        preds[level - 1].?.nexts[level - 1] = node_delete.?.nexts[level - 1];

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

B:BD[8.8750] → [8.8750:8808]

B:BD[8.8808] → [2.1021:1091]

∅:D[2.1091] → [8.8871:8930]

B:BD[8.8871] → [8.8871:8930]

B:BD[8.8930] → [8.8930:9022]

B:BD[8.9022] → [8.9022:9122]

                            if (builtin.mode == .Debug) {
                                var lit = locks.bitset.iterator(.{});
                                while (lit.next()) |lvl| {
                                    if (preds[lvl].? == preds[level - 1].?) continue :NEXT;
                                }
                                @panic("level is not locked...");

[8.8750]

[8.9122]

                        if (builtin.mode == .Debug) {
                            var lit = locks.bitset.iterator(.{});
                            while (lit.next()) |lvl| {
                                if (preds[lvl].? == preds[level - 1].?) continue :LEVELS;

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

[8.9152]

[12.2010]

                            @panic("level is not locked...");

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

B:BD[12.2036] → [12.2036:2147]

                        node_delete.lock.unlock();
                        node_delete.deinit(self.allocator);

[12.2036]

[12.2147]

                    }
                    node_delete.?.lock.unlock();
                    node_delete.?.deinit(self.allocator);

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

B:BD[12.2148] → [12.2148:2188]

B:BD[12.2188] → [2.1092:1139]

                        // Lock cleanup
                        locks.release(&preds);

[12.2148]

[4.11594]

                    // Lock cleanup
                    locks.release(&preds);

Replacement in src/lazy.zig at line 356 [4.108]
B:BD[4.11595] → [12.2377:2414]
∅:D[12.2414] → [4.11791:11813]
B:BD[4.11791] → [4.11791:11813]
```
                        return true;
                    }
```
[4.11595]
[4.11945]
```
                    return true;
```

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

B:BD[4.11970] → [12.2415:2491]

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

[4.11970]

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

Insertion in src/lazy.zig at line 362 [4.108]
[4.12036]
[4.12036]
```
            unreachable;
```

Deletion in src/lazy.zig at line 411 [4.108]

B:BD[4.10860] → [12.517:559]

B:BD[12.667] → [12.667:721]

B:BD[4.7274] → [7.7343:7388]

B:BD[7.7388] → [7.7388:7426]

B:BD[7.7526] → [7.7526:7576]

                    PLACE: while (true) {
                        var prev_pred: ?*Node = null;
                // Find the new-node's place
                PLACE: while (true) {
                    var prev_pred: ?*Node = null;

Solving an order conflict in src/lazy.zig at line 411 [4.108]
[4.14082]