voroskoi/skiplist.zig - Change FFUOEUJREZ6KR4BZFLM7ORBKTNLJC5WVTACO26NTKNQ37MDTKN5AC

fix std.rand usage, remove some comptime

Created by voroskoi on August 17, 2022

FFUOEUJREZ6KR4BZFLM7ORBKTNLJC5WVTACO26NTKNQ37MDTKN5AC

Dependencies

In channels

main

Change contents

Deletion in src/pugh.zig at line 3 [3.50]

B:BD[3.80] → [2.20:121]

/// Pugh creates a SkipList which implementation details match the original paper from William Pugh.

Deletion in src/pugh.zig at line 4 [3.50]
B:BD[2.134] → [2.134:177]
```
    /// K is the key type of the SkipList.
```
Deletion in src/pugh.zig at line 5 [3.50]
B:BD[3.118] → [2.178:230]
```
    /// V is the stored value type of the SkipList.
```

Deletion in src/pugh.zig at line 7 [3.50]

B:BD[3.165] → [2.231:303]

    /// lessThan returns if `lhs` parameter key is less than `rhs` key.

Replacement in src/pugh.zig at line 10 [3.50]
B:BD[3.261] → [3.261:291]
```
        rnd: std.rand.Random,
```
[3.261]
[3.291]
```
        rnd: std.rand.DefaultPrng,
```

Replacement in src/pugh.zig at line 47 [3.50]

B:BD[2.943] → [2.943:1052]

            /// Number of items to skip with each level. Probabilistic!
            comptime skip_size: f32,

[2.943]

[2.1052]

            /// Number of items to skip with each level. This is a probabilistic value.
            skip_size: f32,

Replacement in src/pugh.zig at line 51 [3.50]
B:BD[2.1222] → [2.1222:1257]
```
            comptime n_max: usize,
```
[2.1222]
[2.1257]
```
            n_max: usize,
```

Replacement in src/pugh.zig at line 53 [3.50]

B:BD[2.1278] → [2.1278:1352]

∅:D[2.1352] → [3.1123:1218]

B:BD[3.1123] → [3.1123:1218]

            if (skip_size <= 1) @compileError("`skip_size must be > 1`");
            var rnd_tmp = std.rand.DefaultPrng.init(@intCast(u64, std.time.milliTimestamp()));

[2.1278]

[3.1218]

            if (skip_size <= 1) {
                std.log.err("skip_size {d} not allowed, must be > 1", .{skip_size});
                return error.InvalidSkipSize;
            }

Replacement in src/pugh.zig at line 58 [3.50]

B:BD[3.1248] → [3.1248:1289]

                .rnd = rnd_tmp.random(),

[3.1248]

[2.1353]

                .rnd = std.rand.DefaultPrng.init(@intCast(u64, std.time.milliTimestamp())),

Replacement in src/pugh.zig at line 64 [3.50]

B:BD[2.1444] → [2.1444:1580]

            // XXX: removing `catch` causing segfault
            sl.head = Node.init(sl.allocator, 0, sl.max_level) catch unreachable;

[2.1444]

[3.1522]

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

Replacement in src/pugh.zig at line 96 [3.50]

B:BD[3.2616] → [3.2616:2662]

        fn randomLevel(self: @This()) usize {

[3.2616]

[3.2662]

        fn randomLevel(self: *@This()) usize {

Replacement in src/pugh.zig at line 98 [3.50]

B:BD[3.2696] → [2.1688:2132]

            // while (self.rnd.float(f32) < (1.0 / self.skip_size) and
            //     level < self.max_level) level += 1;
            while (level < self.max_level) {
                const r = self.rnd.float(f32);
                // FIXME: strange r values...
                std.debug.print("r: {d}\n", .{r});
                if (r < 1 / self.skip_size) level += 1 else break;
            }
            std.debug.print("{d}\n", .{level});

[3.2696]

[3.2784]

            const random = self.rnd.random();
            while (random.float(f32) < (1 / self.skip_size) and
                level < self.max_level) level += 1;