voroskoi/skiplist.zig - Change P7OMU7PBSC76C6FLDU3TT6ZRSKMNRTYAA4IM65ICVIHSMNUQWRBAC

work-work

Created by voroskoi on August 24, 2022

P7OMU7PBSC76C6FLDU3TT6ZRSKMNRTYAA4IM65ICVIHSMNUQWRBAC

Dependencies

In channels

main

Change contents

Replacement in src/pugh.zig at line 89 [4.50]

B:BD[4.2378] → [3.0:74]

                    if (lessThan(context, next.key.?, search_key)) break;

[4.2378]

[4.2453]

                    if (!lessThan(context, next.key.?, search_key)) break;

Insertion in src/pugh.zig at line 221 [4.50]

[4.7560]


test "Pugh" {
    const KeyType = usize;
    const SL = Pugh(KeyType, void, {}, comptime std.sort.asc(KeyType));
    var sl = try SL.init(std.testing.allocator, 4, 16);
    defer sl.deinit();
    try sl.insert(3, {});
    try sl.insert(6, {});
    try sl.insert(7, {});
    try sl.insert(9, {});
    try sl.insert(0, {});
    try sl.insert(std.math.minInt(KeyType), {});
    try sl.insert(12, {});
    try sl.insert(12, {}); // does nothing
    try sl.insert(12, {}); // does nothing
    try sl.insert(19, {});
    try sl.insert(17, {});
    try sl.insert(26, {});
    try sl.insert(21, {});
    try sl.insert(25, {});
    sl.display();
    try std.testing.expectEqual(@as(KeyType, 12), sl.search(12).?.key.?);
    try std.testing.expectEqual(@as(KeyType, 26), sl.search(26).?.key.?);
    try std.testing.expectEqual(@as(?*SL.Node, null), sl.search(13));
    try std.testing.expectEqual(true, try sl.remove(12));
    try std.testing.expectEqual(false, try sl.remove(12));
    _ = try sl.remove(std.math.minInt(KeyType));
}

Deletion in src/main.zig at line 2 [2.33]
B:BD[2.62] → [2.62:101]
```
const Pugh = @import("pugh.zig").Pugh;
```
Replacement in src/main.zig at line 3 [2.33]
B:BD[2.102] → [2.102:131]
```
const DEFAULT_SKIP_SIZE = 4;
```
[2.102]
[2.131]
```
pub const io_mode = std.io.Mode.evented;
```

Replacement in src/main.zig at line 5 [2.33]

B:BD[2.132] → [2.132:317]

test "Pugh" {
    const KeyType = usize;
    const SL = Pugh(KeyType, void, {}, comptime std.sort.asc(KeyType));
    var sl = try SL.init(std.testing.allocator, DEFAULT_SKIP_SIZE, 16);

[2.132]

[2.317]

const SkipList = struct {
    pub usingnamespace @import("pugh.zig");
    pub usingnamespace @import("lazy.zig");
};
const BENCH_ITEMS = 100_000;
const BENCH_KEY = usize;
const BENCH_VALUE = void;
const BENCH_SKIP_SIZE = 4;
pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    var arena = std.heap.ArenaAllocator.init(gpa.allocator());
    defer arena.deinit();
    var sl = try SkipList.Pugh(BENCH_KEY, BENCH_VALUE, {}, comptime std.sort.asc(BENCH_KEY))
        .init(arena.allocator(), BENCH_SKIP_SIZE, BENCH_ITEMS);

Replacement in src/main.zig at line 24 [2.33]

B:BD[2.341] → [2.341:768]

    try sl.insert(3, {});
    try sl.insert(6, {});
    try sl.insert(7, {});
    try sl.insert(9, {});
    try sl.insert(0, {});
    try sl.insert(std.math.minInt(KeyType), {});
    try sl.insert(12, {});
    try sl.insert(12, {}); // does nothing
    try sl.insert(12, {}); // does nothing
    try sl.insert(19, {});
    try sl.insert(17, {});
    try sl.insert(26, {});
    try sl.insert(21, {});
    try sl.insert(25, {});

[2.341]

[2.768]

    var rand = std.rand.DefaultPrng.init(@intCast(u64, std.time.milliTimestamp()));
    const rnd = rand.random();

Replacement in src/main.zig at line 27 [2.33]
B:BD[2.769] → [2.769:787]
```
    sl.display();
```
[2.769]
[2.787]
```
    var timer = try std.time.Timer.start();
```

Replacement in src/main.zig at line 29 [2.33]

B:BD[2.788] → [2.788:1124]

    try std.testing.expectEqual(@as(KeyType, 12), sl.search(12).?.key.?);
    try std.testing.expectEqual(@as(KeyType, 26), sl.search(26).?.key.?);
    try std.testing.expectEqual(@as(?*SL.Node, null), sl.search(13));
    try std.testing.expectEqual(true, try sl.remove(12));
    try std.testing.expectEqual(false, try sl.remove(12));

[2.788]

[2.1124]

    var i: usize = 0;
    while (i < BENCH_ITEMS) : (i += 1) {
        const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY) + 1, std.math.maxInt(BENCH_KEY) - 1);
        try sl.insert(key, {});
    }

Replacement in src/main.zig at line 35 [2.33]

B:BD[2.1125] → [2.1125:1174]

    _ = try sl.remove(std.math.minInt(KeyType));

[2.1125]

[2.1174]

    std.debug.print("{d} ms\n", .{timer.read() / std.time.ns_per_ms});

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

B:BD[3.12407] → [3.12407:12463]

    var sl = try SL.init(std.testing.allocator, 2, 16);

[3.12407]

[3.12463]

    var sl = try SL.init(std.testing.allocator, 4, 16);

Insertion in build.zig at line 4 [4.8644]

[4.8717]

    // Standard target options allows the person running `zig build` to choose
    // what target to build for. Here we do not override the defaults, which
    // means any target is allowed, and the default is native. Other options
    // for restricting supported target set are available.
    const target = b.standardTargetOptions(.{});

Replacement in build.zig at line 14 [4.8644]

B:BD[4.8908] → [4.8908:9023]

    const lib = b.addStaticLibrary("skiplist.zig", "src/main.zig");
    lib.setBuildMode(mode);
    lib.install();

[4.8908]

[4.9023]

    const exe = b.addExecutable("skiplist.zig", "src/main.zig");
    exe.setTarget(target);
    exe.setBuildMode(mode);
    exe.use_stage1 = true;
    exe.install();

Replacement in build.zig at line 20 [4.8644]

B:BD[4.9024] → [4.9024:9109]

    const main_tests = b.addTest("src/main.zig");
    main_tests.setBuildMode(mode);

[4.9024]

[4.9109]

    const run_cmd = exe.run();
    run_cmd.step.dependOn(b.getInstallStep());
    if (b.args) |args| {
        run_cmd.addArgs(args);
    }

Replacement in build.zig at line 26 [4.8644]

B:BD[4.9110] → [4.9110:9211]

    const test_step = b.step("test", "Run library tests");
    test_step.dependOn(&main_tests.step);

[4.9110]

[4.9211]

    const run_step = b.step("run", "Run the app");
    run_step.dependOn(&run_cmd.step);
    const exe_tests = b.addTest("src/main.zig");
    exe_tests.setTarget(target);
    exe_tests.setBuildMode(mode);
    const test_step = b.step("test", "Run unit tests");
    test_step.dependOn(&exe_tests.step);

Insertion in .ignore at line 3 [4.9246]
[4.9265]
```
**/zig-out
```