voroskoi/skiplist.zig - Change ZXJGCQSAYBMPR75JD2NSK6UX5MD4X7O3BL2VCP6PR4EZCFJKMKXAC

Adjust randomLevel() and max_level

Created by voroskoi on December 25, 2024

ZXJGCQSAYBMPR75JD2NSK6UX5MD4X7O3BL2VCP6PR4EZCFJKMKXAC

Dependencies

In channels

main

Change contents

Insertion in src/lazy.zig at line 2 [4.108]
[4.137]
[5.4100]
```
const log = std.log.scoped(.LazySkipList);
```

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

[4.664]

[5.4650]

        /// This must be > 0 as level is in [0..max_level) and Node.height is in [1..max_level] range.

Insertion in src/lazy.zig at line 39 [4.108]
[4.741]
[4.741]
```
            /// Next Node for each level.
```

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

[4.770]

            /// Human readable height, starts with 1.

Insertion in src/lazy.zig at line 47 [4.108]
[4.1039]
[5.4811]
```
            /// Locking state.
```

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

[4.1158]

                std.debug.assert(level < max_level);

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

B:BD[4.1239] → [4.1239:1305]

                n.nexts = try allocator.alloc(?*Node, level + 1);

[4.1239]

[5.4848]

                n.nexts = try allocator.alloc(?*Node, level + 1); // level can be 0

Replacement in src/lazy.zig at line 57 [4.108]
∅:D[5.4933] → [4.1400:1434]
B:BD[4.1400] → [4.1400:1434]
```
                n.height = level;
```
[5.4933]
[4.1434]
```
                n.height = level + 1; // level can be 0
```

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

B:BD[4.1660] → [3.4584:4734]


        /// getHead returns the head element.
        pub fn getHead(self: @This()) *Node {
            _ = self;
            return head;
        }

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

B:BD[4.1823] → [4.1823:1868]

B:BD[4.1868] → [6.678:700]

∅:D[6.700] → [5.4934:5099]

B:BD[4.1868] → [5.4934:5099]

∅:D[5.5099] → [4.2037:2084]

B:BD[4.2037] → [4.2037:2084]

B:BD[4.2084] → [6.701:759]

∅:D[6.759] → [4.2147:2449]

B:BD[4.2147] → [4.2147:2449]

        pub fn display(self: @This()) void {
            _ = self;
            std.debug.print("SkipList(Lazy) structure - P:{d}, max_level: {d}\n", .{ 1 / opts.skip_size, max_level });
            var level: usize = max_level + 1;
            while (level > 0) : (level -= 1) {
                var node: ?*Node = head.nexts[level - 1];
                std.debug.print("Level {d}: ", .{level - 1});
                while (node != null) {
                    std.debug.print("{any} ", .{node.?.key});
                    node = node.?.nexts[level - 1];
                }
                std.debug.print("\n", .{});
            }
        }

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

[4.2921]

[6.760]

            std.debug.assert(max_level > 0);

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

B:BD[6.915] → [6.915:974]

            head = try Node.init(allocator, 0, max_level);

[6.915]

[6.974]

            head = try Node.init(allocator, 0, max_level - 1);

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

[6.1283]

[4.3933]

        }
        /// Returns the head node element.
        pub fn getHead(self: @This()) *Node {
            _ = self;
            return head;
        }
        pub fn display(self: @This()) void {
            _ = self;
            std.debug.print("SkipList(Lazy) structure - P:{d}, max_level: {d}\n", .{ 1 / opts.skip_size, max_level });
            var level: usize = max_level;
            while (level > 0) : (level -= 1) {
                var node: ?*Node = head.nexts[level - 1];
                std.debug.print("Level {d}: ", .{level - 1});
                while (node != null) {
                    std.debug.print("{any} ", .{node.?.key});
                    node = node.?.nexts[level - 1];
                }
                std.debug.print("\n", .{});
            }

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

B:BD[4.4117] → [5.5737:5783]

            var level: usize = max_level + 1;

[4.4117]

[4.4168]

            var level: usize = max_level;

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

∅:D[6.1415] → [5.6172:6230]

B:BD[4.4949] → [5.6172:6230]

B:BD[4.5120] → [5.6266:6324]

            var preds: [max_level + 1]?*Node = undefined;
            var succs: [max_level + 1]?*Node = undefined;

[6.1415]

[4.5290]

            var preds: [max_level]?*Node = undefined;
            var succs: [max_level]?*Node = undefined;

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

B:BD[5.6519] → [5.6519:6566]

                level < max_level) level += 1;

[5.6519]

[4.5773]

                level < max_level - 1) level += 1;
            std.debug.assert(level < max_level);

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

B:BD[4.5936] → [5.6676:6734]

B:BD[4.6107] → [5.6773:6831]

            var preds: [max_level + 1]?*Node = undefined;
            var succs: [max_level + 1]?*Node = undefined;

[4.5936]

[4.6277]

            var preds: [max_level]?*Node = undefined;
            var succs: [max_level]?*Node = undefined;

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

B:BD[4.6939] → [6.1769:1842]

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

[4.6939]

[4.7273]

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

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

B:BD[4.7509] → [5.7713:7763]

                    for (0..rlevel + 1) |level| {

[4.7468]

[5.7763]

                    for (0..rlevel + 1) |level| { // we want to reach rlevel!

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

B:BD[4.8670] → [5.9469:9519]

                    for (0..rlevel + 1) |level| {

[4.8670]

[5.9519]

                    for (0..node.height) |level| {

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

B:BD[4.9382] → [6.1987:2103]

            var preds: [max_level + 1]?*Node = undefined;
            var succs: [max_level + 1]?*Node = undefined;

[4.9382]

[4.9552]

            var preds: [max_level]?*Node = undefined;
            var succs: [max_level]?*Node = undefined;

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

B:BD[4.10486] → [2.439:516]

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

[4.10486]

[4.10859]

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

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

B:BD[4.11039] → [2.764:830]

                        for (0..node_delete.height + 1) |level| {

[4.11039]

[2.830]

                        for (0..node_delete.height) |level| {

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

B:BD[2.1788] → [2.1788:1855]

                        var level: usize = node_delete.height + 1;

[2.1788]

[2.1855]

                        var level: usize = node_delete.height;

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

∅:D[2.2564] → [4.12112:12219]

B:BD[4.12112] → [4.12112:12219]

            return candidate.*.fully_linked and candidate.*.height == level_found and !candidate.*.marked;

[2.2564]

[4.12219]

            return candidate.*.fully_linked and candidate.*.height - 1 == level_found and !candidate.*.marked;