{"header":{"message":"very messy commit, sorry","description":null,"timestamp":"2024-12-21T07:26:28.450810185Z","authors":[{}]},"hash":"VDX2MMS55XMEHH2TEMOOW225K6NGKB4QXPQFQ2WJLVXJK25BSXMQC","authors":[{"login":"voroskoi","key":"Guf8VYJNUiWAqxwLxDSKxmvvtY65ht2zK2q4h6VhxrcZ"}],"deps":{"hashes":[["VDX2MMS55XMEHH2TEMOOW225K6NGKB4QXPQFQ2WJLVXJK25BSXMQC","very messy commit, sorry"],["AA",null],["FFUOEUJREZ6KR4BZFLM7ORBKTNLJC5WVTACO26NTKNQ37MDTKN5AC","fix std.rand usage, remove some comptime"],["7G5Y53RBBKF4QDPTVC2MFG45XHDOLEFPHA4XQIPJNW4RXCULMRQQC","add priority queue code"],["LD2TP6CDUHET2ISQB3P4JOTQTIDDPRLSZJTIYWAO7JTHKUWOF7MQC","Add LazySkipList"],["CNCKEJFP74UCJQ4YJPP6QEHWH2DNWRWDZB2XNXRPTDZBPCXMJDXAC","calculate max_level based on item number, use skip_size instead of P"],["P7OMU7PBSC76C6FLDU3TT6ZRSKMNRTYAA4IM65ICVIHSMNUQWRBAC","work-work"],["GJA75BA6ZNFQL6DG7YSRQKJWGX52YJKL3DZO3OWO6D4HVH6JS7NQC","work on benchmarking"],["XJHUBLK673LN2VVQ5FIOENXMS5OFSFWXM5GSP2X7XEVOL74WV6OAC","Initial import"],["UAUV6SYV72FWMQVALN5YFTANLHIG6B5JHTZLJJUN5SN7SALYAC3AC","Add main.zig"],["2HKNCI4IG65FEWNSRBJ5SESMN4STJ6WSCNODP3UK6LBQMDHYPNTAC","work-work"]],"deps":["FFUOEUJREZ6KR4BZFLM7ORBKTNLJC5WVTACO26NTKNQ37MDTKN5AC","7G5Y53RBBKF4QDPTVC2MFG45XHDOLEFPHA4XQIPJNW4RXCULMRQQC"],"known":["XJHUBLK673LN2VVQ5FIOENXMS5OFSFWXM5GSP2X7XEVOL74WV6OAC","CNCKEJFP74UCJQ4YJPP6QEHWH2DNWRWDZB2XNXRPTDZBPCXMJDXAC","UAUV6SYV72FWMQVALN5YFTANLHIG6B5JHTZLJJUN5SN7SALYAC3AC","LD2TP6CDUHET2ISQB3P4JOTQTIDDPRLSZJTIYWAO7JTHKUWOF7MQC","P7OMU7PBSC76C6FLDU3TT6ZRSKMNRTYAA4IM65ICVIHSMNUQWRBAC","GJA75BA6ZNFQL6DG7YSRQKJWGX52YJKL3DZO3OWO6D4HVH6JS7NQC","2HKNCI4IG65FEWNSRBJ5SESMN4STJ6WSCNODP3UK6LBQMDHYPNTAC"]},"hunks":[{"Replacement":{"inode":{"change":3,"pos":38},"path":"src/skipqueue.zig","line":15,"ins":{"up_context":[{"change":3,"pos":525}],"down_context":[{"change":3,"pos":578}],"flag":"BLOCK","start":0,"end":47,"inode":{"change":3,"pos":38}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":525},"to":{"change":3,"start":525,"end":578},"introduced_by":3}],"inode":{"change":3,"pos":38}},"ins_contents":[{"Add":" break :blk field.type;"}],"del_contents":[{"Del":" break :blk field.field_type;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":38},"path":"src/skipqueue.zig","line":27,"ins":{"up_context":[{"change":3,"pos":884}],"down_context":[{"change":3,"pos":937}],"flag":"BLOCK","start":48,"end":95,"inode":{"change":3,"pos":38}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":884},"to":{"change":3,"start":884,"end":937},"introduced_by":3}],"inode":{"change":3,"pos":38}},"ins_contents":[{"Add":" break :blk field.type;"}],"del_contents":[{"Del":" break :blk field.field_type;\n"}]}},{"Replacement":{"inode":{"change":3,"pos":38},"path":"src/skipqueue.zig","line":35,"ins":{"up_context":[{"change":3,"pos":1062}],"down_context":[{"change":3,"pos":1122}],"flag":"BLOCK","start":96,"end":179,"inode":{"change":3,"pos":38}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":1062},"to":{"change":3,"start":1062,"end":1122},"introduced_by":3}],"inode":{"change":3,"pos":38}},"ins_contents":[{"Add":" skiplist: SkipList.Lazy(.{ .items = MY_SIZE }, K, V, {}, std.sort.asc(K)),"}],"del_contents":[{"Del":" skiplist: SkipList.Lazy(K, V, {}, std.sort.asc(K)),\n"}]}},{"Replacement":{"inode":{"change":3,"pos":38},"path":"src/skipqueue.zig","line":39,"ins":{"up_context":[{"change":3,"pos":1225}],"down_context":[{"change":3,"pos":1376}],"flag":"BLOCK","start":180,"end":317,"inode":{"change":3,"pos":38}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":1225},"to":{"change":3,"start":1225,"end":1376},"introduced_by":3}],"inode":{"change":3,"pos":38}},"ins_contents":[{"Add":" sq.skiplist = try SkipList.Lazy(.{ .items = MY_SIZE }, K, V, {}, comptime std.sort.asc(K))"},{"Add":" .init(allocator);"}],"del_contents":[{"Del":" sq.skiplist = try SkipList.Lazy(K, V, {}, comptime std.sort.asc(K))\n .init(allocator, SkipList.DEFAULT_SKIP_SIZE, MY_SIZE);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":38},"path":"src/skipqueue.zig","line":44,"ins":{"up_context":[{"change":3,"pos":1410}],"down_context":[{"change":3,"pos":1490}],"flag":"BLOCK","start":318,"end":437,"inode":{"change":3,"pos":38}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":1410},"to":{"change":3,"start":1410,"end":1490},"introduced_by":3}],"inode":{"change":3,"pos":38}},"ins_contents":[{"Add":" pub fn deinit(self: @This(), allocator: std.mem.Allocator) void {"},{"Add":" self.skiplist.deinit(allocator);"}],"del_contents":[{"Del":" pub fn deinit(self: @This()) void {\n self.skiplist.deinit();\n"}]}},{"Replacement":{"inode":{"change":3,"pos":38},"path":"src/skipqueue.zig","line":48,"ins":{"up_context":[{"change":3,"pos":1501}],"down_context":[{"change":3,"pos":1617}],"flag":"BLOCK","start":438,"end":595,"inode":{"change":3,"pos":38}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":1501},"to":{"change":3,"start":1501,"end":1617},"introduced_by":3}],"inode":{"change":3,"pos":38}},"ins_contents":[{"Add":" pub fn add(self: *@This(), allocator: std.mem.Allocator, item: T) !void {"},{"Add":" _ = try self.skiplist.insert(allocator, item.key, item.value);"}],"del_contents":[{"Del":" pub fn add(self: *@This(), item: T) !void {\n _ = try self.skiplist.insert(item.key, item.value);\n"}]}},{"Replacement":{"inode":{"change":3,"pos":38},"path":"src/skipqueue.zig","line":52,"ins":{"up_context":[{"change":3,"pos":1628}],"down_context":[{"change":3,"pos":1672}],"flag":"BLOCK","start":596,"end":670,"inode":{"change":3,"pos":38}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":1628},"to":{"change":3,"start":1628,"end":1672},"introduced_by":3}],"inode":{"change":3,"pos":38}},"ins_contents":[{"Add":" pub fn remove(self: *@This(), allocator: std.mem.Allocator) !?T {"}],"del_contents":[{"Del":" pub fn remove(self: *@This()) !?T {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":38},"path":"src/skipqueue.zig","line":56,"ins":{"up_context":[{"change":3,"pos":1817}],"down_context":[{"change":3,"pos":1905}],"flag":"BLOCK","start":671,"end":747,"inode":{"change":3,"pos":38}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":1817},"to":{"change":3,"start":1817,"end":1905},"introduced_by":3}],"inode":{"change":3,"pos":38}},"ins_contents":[{"Add":" item.lock.lock();"},{"Add":" defer item.lock.unlock();"}],"del_contents":[{"Del":" const held = item.lock.acquire();\n defer held.release();\n"}]}},{"Replacement":{"inode":{"change":3,"pos":38},"path":"src/skipqueue.zig","line":68,"ins":{"up_context":[{"change":3,"pos":2169}],"down_context":[{"change":3,"pos":2226}],"flag":"BLOCK","start":748,"end":816,"inode":{"change":3,"pos":38}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2169},"to":{"change":3,"start":2169,"end":2226},"introduced_by":3}],"inode":{"change":3,"pos":38}},"ins_contents":[{"Add":" _ = try self.skiplist.remove(allocator, ret.?.key);"}],"del_contents":[{"Del":" _ = try self.skiplist.remove(ret.?.key);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":50},"path":"src/pugh.zig","line":30,"ins":{"up_context":[{"change":4,"pos":757}],"down_context":[{"change":4,"pos":811}],"flag":"BLOCK","start":817,"end":859,"inode":{"change":4,"pos":50}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":757},"to":{"change":4,"start":757,"end":811},"introduced_by":4}],"inode":{"change":4,"pos":50}},"ins_contents":[{"Add":" @memset(n.forward, null);"}],"del_contents":[{"Del":" std.mem.set(?*Node, n.forward, null);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":50},"path":"src/pugh.zig","line":41,"ins":{"up_context":[{"change":4,"pos":698}],"down_context":[{"change":4,"pos":793}],"flag":"BLOCK","start":860,"end":1000,"inode":{"change":4,"pos":50}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":698},"to":{"change":4,"start":698,"end":793},"introduced_by":4}],"inode":{"change":4,"pos":50}},"ins_contents":[{"Add":" return @as(usize, @intFromFloat("},{"Add":" std.math.log(f32, self.skip_size, @as(f32, @floatFromInt(n))),"},{"Add":" ));"}],"del_contents":[{"Del":" return @floatToInt(usize, std.math.log(f32, self.skip_size, @intToFloat(f32, n)));\n"}]}},{"Replacement":{"inode":{"change":4,"pos":50},"path":"src/pugh.zig","line":60,"ins":{"up_context":[{"change":4,"pos":1248}],"down_context":[{"change":4,"pos":1353}],"flag":"BLOCK","start":1001,"end":1088,"inode":{"change":4,"pos":50}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1248},"to":{"change":2,"start":360,"end":452},"introduced_by":2}],"inode":{"change":4,"pos":50}},"ins_contents":[{"Add":" .rnd = std.rand.DefaultPrng.init(@intCast(std.time.milliTimestamp())),"}],"del_contents":[{"Del":" .rnd = std.rand.DefaultPrng.init(@intCast(u64, std.time.milliTimestamp())),\n"}]}},{"Edit":{"inode":{"change":4,"pos":50},"path":"src/pugh.zig","line":72,"atom":{"EdgeMap":{"edges":[{"previous":"","flag":"DELETED","from":{"change":4,"pos":1625},"to":{"change":4,"start":1747,"end":1769},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1747},"to":{"change":4,"start":1747,"end":1769},"introduced_by":4}],"inode":{"change":4,"pos":50}}},"contents":[{"Del":" _ = self;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":50},"path":"src/pugh.zig","line":110,"ins":{"up_context":[{"change":4,"pos":3097}],"down_context":[{"change":4,"pos":3144}],"flag":"BLOCK","start":1089,"end":1124,"inode":{"change":4,"pos":50}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":3097},"to":{"change":4,"start":3097,"end":3144},"introduced_by":4}],"inode":{"change":4,"pos":50}},"ins_contents":[{"Add":" @memset(update, null);"}],"del_contents":[{"Del":" std.mem.set(?*Node, update, null);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":50},"path":"src/pugh.zig","line":159,"ins":{"up_context":[{"change":4,"pos":2257}],"down_context":[{"change":4,"pos":5070}],"flag":"BLOCK","start":1125,"end":1249,"inode":{"change":4,"pos":50}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":2257},"to":{"change":4,"start":2257,"end":2375},"introduced_by":4}],"inode":{"change":4,"pos":50}},"ins_contents":[{"Add":" std.debug.print(\"SkipList(Pugh) structure - P:{d}, max_level: {d}\\n\", .{ 1 / self.skip_size, self.max_level });"}],"del_contents":[{"Del":" std.debug.print(\"SkipList structure - P:{d}, max_level: {d}\\n\", .{ 1 / self.skip_size, self.max_level });\n"}]}},{"Replacement":{"inode":{"change":4,"pos":50},"path":"src/pugh.zig","line":177,"ins":{"up_context":[{"change":4,"pos":5796}],"down_context":[{"change":4,"pos":5843}],"flag":"BLOCK","start":1250,"end":1285,"inode":{"change":4,"pos":50}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":5796},"to":{"change":4,"start":5796,"end":5843},"introduced_by":4}],"inode":{"change":4,"pos":50}},"ins_contents":[{"Add":" @memset(update, null);"}],"del_contents":[{"Del":" std.mem.set(?*Node, update, null);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":10,"ins":{"up_context":[{"change":4,"pos":1373}],"down_context":[{"change":4,"pos":1373}],"flag":"BLOCK","start":1286,"end":1422,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1373},"to":{"change":4,"start":0,"end":98},"introduced_by":4}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":"const SL = SkipList.Lazy(.{ .items = BENCH_ITEMS, .skip_size = BENCH_SKIP_SIZE }, BENCH_KEY, BENCH_VALUE, {}, std.sort.asc(BENCH_KEY));"}],"del_contents":[{"Del":"const THREADS = 8;\nconst SL = SkipList.Lazy(BENCH_KEY, BENCH_VALUE, {}, std.sort.asc(BENCH_KEY));\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":13,"ins":{"up_context":[{"change":4,"pos":1396}],"down_context":[{"change":4,"pos":24}],"flag":"BLOCK","start":1423,"end":1444,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1396},"to":{"change":4,"start":0,"end":24},"introduced_by":4}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" try benchPugh();"}],"del_contents":[{"Del":" // try benchPugh();\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":27,"ins":{"up_context":[{"change":4,"pos":341}],"down_context":[{"change":4,"pos":1783}],"flag":"BLOCK","start":1445,"end":1524,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":341},"to":{"change":4,"start":1699,"end":1783},"introduced_by":4}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" var rand = std.rand.DefaultPrng.init(@intCast(std.time.milliTimestamp()));"}],"del_contents":[{"Del":" var rand = std.rand.DefaultPrng.init(@intCast(u64, std.time.milliTimestamp()));\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":38,"ins":{"up_context":[{"change":4,"pos":1125}],"down_context":[{"change":4,"pos":1174}],"flag":"BLOCK","start":1525,"end":1602,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1125},"to":{"change":4,"start":2083,"end":2154},"introduced_by":4}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" std.debug.print(\"Pugh: {d} ms\\n\", .{timer.read() / std.time.ns_per_ms});"}],"del_contents":[{"Del":" std.debug.print(\"{d} ms\\n\", .{timer.read() / std.time.ns_per_ms});\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":42,"ins":{"up_context":[{"change":4,"pos":95}],"down_context":[{"change":4,"pos":213}],"flag":"BLOCK","start":1603,"end":1674,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":95},"to":{"change":4,"start":95,"end":213},"introduced_by":4}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);"}],"del_contents":[{"Del":" var gpa = std.heap.GeneralPurposeAllocator(.{}){};\n var arena = std.heap.ArenaAllocator.init(gpa.allocator());\n"}]}},{"Edit":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":44,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":239}],"down_context":[{"change":4,"pos":392}],"flag":"BLOCK","start":1675,"end":1768,"inode":{"change":4,"pos":33}}},"contents":[{"Add":" // var tsa = std.heap.ThreadSafeAllocator{ .child_allocator = std.heap.page_allocator };"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":46,"ins":{"up_context":[{"change":4,"pos":393}],"down_context":[{"change":4,"pos":497}],"flag":"BLOCK","start":1769,"end":1854,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":393},"to":{"change":4,"start":240,"end":338},"introduced_by":4}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" var sl = try SL.init(arena.allocator());"},{"Add":" defer sl.deinit(arena.allocator());"}],"del_contents":[{"Del":" var sl = try SL.init(arena.allocator(), BENCH_SKIP_SIZE, BENCH_ITEMS);\n defer sl.deinit();\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":49,"ins":{"up_context":[{"change":4,"pos":498}],"down_context":[{"change":4,"pos":423}],"flag":"BLOCK","start":1855,"end":1934,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":498},"to":{"change":4,"start":339,"end":423},"introduced_by":4}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" var rand = std.rand.DefaultPrng.init(@intCast(std.time.milliTimestamp()));"}],"del_contents":[{"Del":" var rand = std.rand.DefaultPrng.init(@intCast(u64, std.time.milliTimestamp()));\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":52,"ins":{"up_context":[{"change":4,"pos":620}],"down_context":[{"change":4,"pos":700}],"flag":"BLOCK","start":1935,"end":2012,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":620},"to":{"change":4,"start":455,"end":532},"introduced_by":4}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" // { // single thread"},{"Add":" // var timer = try std.time.Timer.start();"}],"del_contents":[{"Del":" var batch = std.event.Batch(anyerror!void, THREADS, .auto_async).init();\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":55,"ins":{"up_context":[{"change":4,"pos":701}],"down_context":[{"change":4,"pos":902}],"flag":"BLOCK","start":2013,"end":2283,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":701},"to":{"change":4,"start":533,"end":725},"introduced_by":4}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" // var i: usize = 0;"},{"Add":" // while (i < BENCH_ITEMS) : (i += 1) {"},{"Add":" // const key = rnd.intRangeAtMostBiased(BENCH_KEY, std.math.minInt(BENCH_KEY), std.math.maxInt(BENCH_KEY));"},{"Add":" // _ = try sl.insert(tsa.allocator(), key, {});"},{"Add":" // }"}],"del_contents":[{"Del":" // var frames: [BENCH_ITEMS]@Frame(testInsert) = undefined;\n var frames = try std.ArrayList(@Frame(testInsert)).initCapacity(arena.allocator(), BENCH_ITEMS);\n defer frames.deinit();\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":61,"ins":{"up_context":[{"change":4,"pos":903}],"down_context":[{"change":4,"pos":950}],"flag":"BLOCK","start":2284,"end":2736,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":903},"to":{"change":4,"start":726,"end":770},"introduced_by":4}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" // std.debug.print(\"Lazy 1 thread: {d} ms\\n\", .{timer.read() / std.time.ns_per_ms});"},{"Add":" // }"},{"Add":""},{"Add":" { // multithread"},{"Add":" const THREADS = 4;"},{"Add":""},{"Add":" var pool: std.Thread.Pool = undefined;"},{"Add":" try pool.init(std.Thread.Pool.Options{"},{"Add":" .allocator = arena.allocator(),"},{"Add":" .n_jobs = THREADS,"},{"Add":" });"},{"Add":" defer pool.deinit();"},{"Add":" var wg = std.Thread.WaitGroup{};"},{"Add":""},{"Add":" var timer = try std.time.Timer.start();"}],"del_contents":[{"Del":" var timer = try std.time.Timer.start();\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":77,"ins":{"up_context":[{"change":4,"pos":951}],"down_context":[{"change":4,"pos":1396}],"flag":"BLOCK","start":2737,"end":3046,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":951},"to":{"change":4,"start":771,"end":1236},"introduced_by":4}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" for (0..BENCH_ITEMS) |_| {"},{"Add":" const key = rnd.intRangeAtMostBiased("},{"Add":" BENCH_KEY,"},{"Add":" std.math.minInt(BENCH_KEY),"},{"Add":" std.math.maxInt(BENCH_KEY),"},{"Add":" );"},{"Add":" pool.spawnWg(&wg, testIns, .{ std.heap.page_allocator, &sl, key, {} });"},{"Add":" }"}],"del_contents":[{"Del":" var job: usize = 0;\n while (job < BENCH_ITEMS) : (job += 1) {\n const key = rnd.intRangeAtMostBiased(\n BENCH_KEY,\n std.math.minInt(BENCH_KEY),\n std.math.maxInt(BENCH_KEY),\n );\n // frames[job] = async testInsert(&sl, key, {});\n // batch.add(&frames[job]);\n const frame = async testInsert(&sl, key, {});\n frames.appendAssumeCapacity(frame);\n batch.add(&frames.items[job]);\n }\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":86,"ins":{"up_context":[{"change":4,"pos":1397}],"down_context":[{"change":4,"pos":1422}],"flag":"BLOCK","start":3047,"end":3078,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1397},"to":{"change":4,"start":1237,"end":1259},"introduced_by":4}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" pool.waitAndWork(&wg);"}],"del_contents":[{"Del":" try batch.wait();\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":88,"ins":{"up_context":[{"change":4,"pos":1423}],"down_context":[{"change":4,"pos":1343}],"flag":"BLOCK","start":3079,"end":3189,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1423},"to":{"change":4,"start":1260,"end":1343},"introduced_by":4}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" std.debug.print(\"Lazy {d} threads: {d} ms\\n\", .{ THREADS, timer.read() / std.time.ns_per_ms });"},{"Add":" }"}],"del_contents":[{"Del":" std.debug.print(\"Total time: {d} ms\\n\", .{timer.read() / std.time.ns_per_ms});\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":92,"ins":{"up_context":[{"change":4,"pos":1515}],"down_context":[{"change":3,"pos":2350}],"flag":"BLOCK","start":3190,"end":3398,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1515},"to":{"change":4,"start":1515,"end":1751},"introduced_by":4}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":"fn testIns(allocator: std.mem.Allocator, skiplist: *SL, key: BENCH_KEY, val: BENCH_VALUE) void {"},{"Add":" _ = @call(std.builtin.CallModifier.auto, SL.insert, .{ skiplist, allocator, key, val }) catch unreachable;"}],"del_contents":[{"Del":"fn testInsert(skiplist: *SL, key: BENCH_KEY, val: BENCH_VALUE) anyerror!void {\n if (@call(.{}, skiplist.insert, .{ key, val })) {\n // std.debug.print(\"Adding {d} done.\\n\", .{key});\n return;\n } else |err| return err;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":103,"ins":{"up_context":[{"change":3,"pos":2540}],"down_context":[{"change":3,"pos":2563}],"flag":"BLOCK","start":3399,"end":3445,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2540},"to":{"change":3,"start":2540,"end":2563},"introduced_by":3}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" defer sq.deinit(std.heap.page_allocator);"}],"del_contents":[{"Del":" defer sq.deinit();\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":105,"ins":{"up_context":[{"change":3,"pos":2564}],"down_context":[{"change":3,"pos":2736}],"flag":"BLOCK","start":3446,"end":3718,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2564},"to":{"change":3,"start":2564,"end":2736},"introduced_by":3}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" try sq.add(std.heap.page_allocator, .{ .key = 1, .value = 1 });"},{"Add":" try sq.add(std.heap.page_allocator, .{ .key = 2, .value = 2 });"},{"Add":" try sq.add(std.heap.page_allocator, .{ .key = 3, .value = 3 });"},{"Add":" try sq.add(std.heap.page_allocator, .{ .key = 0, .value = 4 });"}],"del_contents":[{"Del":" try sq.add(.{ .key = 1, .value = 1 });\n try sq.add(.{ .key = 2, .value = 2 });\n try sq.add(.{ .key = 3, .value = 3 });\n try sq.add(.{ .key = 0, .value = 4 });\n"}]}},{"Replacement":{"inode":{"change":4,"pos":33},"path":"src/main.zig","line":110,"ins":{"up_context":[{"change":3,"pos":2737}],"down_context":[{"change":4,"pos":1751}],"flag":"BLOCK","start":3719,"end":4099,"inode":{"change":4,"pos":33}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2737},"to":{"change":3,"start":2737,"end":3002},"introduced_by":3}],"inode":{"change":4,"pos":33}},"ins_contents":[{"Add":" std.debug.assert((try sq.remove(std.heap.page_allocator)).?.value == 4);"},{"Add":" std.debug.assert((try sq.remove(std.heap.page_allocator)).?.value == 1);"},{"Add":" std.debug.assert((try sq.remove(std.heap.page_allocator)).?.value == 2);"},{"Add":" std.debug.assert((try sq.remove(std.heap.page_allocator)).?.value == 3);"},{"Add":" std.debug.assert((try sq.remove(std.heap.page_allocator)) == null);"}],"del_contents":[{"Del":" std.debug.assert((try sq.remove()).?.value == 4);\n std.debug.assert((try sq.remove()).?.value == 1);\n std.debug.assert((try sq.remove()).?.value == 2);\n std.debug.assert((try sq.remove()).?.value == 3);\n std.debug.assert((try sq.remove()) == null);\n"}]}},{"Edit":{"inode":{"change":3,"pos":3035},"path":"src/lib.zig","line":1,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3035},"to":{"change":3,"start":3036,"end":3069},"introduced_by":3}],"inode":{"change":3,"pos":3035}}},"contents":[{"Del":"pub const DEFAULT_SKIP_SIZE = 4;\n"}]}},{"Edit":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":2,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":137}],"down_context":[{"change":4,"pos":137}],"flag":"BLOCK","start":4100,"end":4489,"inode":{"change":4,"pos":108}}},"contents":[{"Add":""},{"Add":"pub const Options = struct {"},{"Add":" /// Maximum number of items to be stored in the SkipList."},{"Add":" /// This is not a hard limit, but SkipList performance will degrade when badly choosen."},{"Add":" items: usize,"},{"Add":" /// Number of items to skip with each level. This is a probabilistic value."},{"Add":" skip_size: f32 = 4,"},{"Add":" /// Maximum number of levels in the SkipList."},{"Add":" max_level: ?usize = null,"},{"Add":"};"}]}},{"Edit":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":14,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":151}],"down_context":[{"change":4,"pos":151}],"flag":"BLOCK","start":4490,"end":4518,"inode":{"change":4,"pos":108}}},"contents":[{"Add":" comptime opts: Options,"}]}},{"Edit":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":20,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":299}],"down_context":[{"change":4,"pos":299}],"flag":"BLOCK","start":4519,"end":4608,"inode":{"change":4,"pos":108}}},"contents":[{"Add":" if (opts.skip_size <= 1) {"},{"Add":" @compileError(\"Skip size must be >= 1!\\n\");"},{"Add":" }"}]}},{"Edit":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":24,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":319}],"down_context":[{"change":4,"pos":319}],"flag":"BLOCK","start":4609,"end":4649,"inode":{"change":4,"pos":108}}},"contents":[{"Add":" // XXX: these should be hidden!"}]}},{"Edit":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":26,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":354},"to":{"change":4,"start":354,"end":591},"introduced_by":4}],"inode":{"change":4,"pos":108}}},"contents":[{"Del":" allocator: std.mem.Allocator,\n /// Determines average skip size for each level of SkipList. Equals `1/P`.\n skip_size: f32,\n /// Maximum number of levels in the SkipList.\n max_level: usize = undefined,\n"}]}},{"Edit":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":29,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":664}],"down_context":[{"change":4,"pos":664}],"flag":"BLOCK","start":4650,"end":4810,"inode":{"change":4,"pos":108}}},"contents":[{"Add":" const max_level = opts.max_level orelse"},{"Add":" @as(usize, @intFromFloat(std.math.log(f32, opts.skip_size, @as(f32, @floatFromInt(opts.items)))));"},{"Add":""}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":41,"ins":{"up_context":[{"change":4,"pos":1039}],"down_context":[{"change":4,"pos":1073}],"flag":"BLOCK","start":4811,"end":4847,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1039},"to":{"change":4,"start":1039,"end":1073},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" lock: std.Thread.Mutex,"}],"del_contents":[{"Del":" lock: std.event.Lock,\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":47,"ins":{"up_context":[{"change":4,"pos":1305}],"down_context":[{"change":4,"pos":1400}],"flag":"BLOCK","start":4848,"end":4933,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1305},"to":{"change":4,"start":1305,"end":1400},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" @memset(n.nexts, null);"},{"Add":" n.lock = std.Thread.Mutex{};"}],"del_contents":[{"Del":" std.mem.set(?*Node, n.nexts, null);\n n.lock = std.event.Lock{};\n"}]}},{"Edit":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":59,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1661},"to":{"change":4,"start":1661,"end":1717},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1717},"to":{"change":4,"start":1717,"end":1812},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1812},"to":{"change":4,"start":1812,"end":1823},"introduced_by":4}],"inode":{"change":4,"pos":108}}},"contents":[{"Del":" fn getMaxLevel(self: @This(), n: usize) usize {\n"},{"Del":" return @floatToInt(usize, std.math.log(f32, self.skip_size, @intToFloat(f32, n)));\n"},{"Del":" }\n\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":60,"ins":{"up_context":[{"change":4,"pos":1868}],"down_context":[{"change":4,"pos":2037}],"flag":"BLOCK","start":4934,"end":5099,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1868},"to":{"change":4,"start":1868,"end":1986},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":1986},"to":{"change":4,"start":1986,"end":2037},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" std.debug.print(\"SkipList(Lazy) structure - P:{d}, max_level: {d}\\n\", .{ 1 / opts.skip_size, max_level });"},{"Add":" var level: usize = max_level + 1;"}],"del_contents":[{"Del":" std.debug.print(\"SkipList structure - P:{d}, max_level: {d}\\n\", .{ 1 / self.skip_size, self.max_level });\n"},{"Del":" var level: usize = self.max_level + 1;\n"}]}},{"Edit":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":75,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":2546}],"down_context":[{"change":4,"pos":2546}],"flag":"BLOCK","start":5100,"end":5198,"inode":{"change":4,"pos":108}}},"contents":[{"Add":" /// Make sure it is threadsafe if You want to use the SkipList from multiple threads!"}]}},{"Edit":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":77,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":2588},"to":{"change":4,"start":2588,"end":2900},"introduced_by":4}],"inode":{"change":4,"pos":108}}},"contents":[{"Del":" /// Number of items to skip with each level. This is a probabilistic value.\n skip_size: f32,\n /// Maximum number of items to be stored in the SkipList.\n /// This is not a hard limit, but SkipList performance will degrade when badly choosen.\n n_max: usize,\n"}]}},{"Edit":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":78,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":2921},"to":{"change":4,"start":2921,"end":3100},"introduced_by":4}],"inode":{"change":4,"pos":108}}},"contents":[{"Del":" if (skip_size <= 1) {\n std.log.err(\"skip_size {d} not allowed, must be > 1\", .{skip_size});\n return error.InvalidSkipSize;\n }\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":79,"ins":{"up_context":[{"change":4,"pos":3130}],"down_context":[{"change":4,"pos":3302}],"flag":"BLOCK","start":5199,"end":5286,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":3130},"to":{"change":4,"start":3130,"end":3222},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":3222},"to":{"change":4,"start":3222,"end":3302},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" .rnd = std.rand.DefaultPrng.init(@intCast(std.time.milliTimestamp())),"}],"del_contents":[{"Del":" .rnd = std.rand.DefaultPrng.init(@intCast(u64, std.time.milliTimestamp())),\n"},{"Del":" .skip_size = skip_size,\n .allocator = allocator,\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":82,"ins":{"up_context":[{"change":4,"pos":3352}],"down_context":[{"change":4,"pos":3470}],"flag":"BLOCK","start":5287,"end":5349,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":3352},"to":{"change":4,"start":3352,"end":3470},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" sl.head = try Node.init(allocator, 0, max_level);"}],"del_contents":[{"Del":" sl.max_level = sl.getMaxLevel(n_max);\n sl.head = try Node.init(sl.allocator, 0, sl.max_level);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":87,"ins":{"up_context":[{"change":4,"pos":3536}],"down_context":[{"change":4,"pos":3602}],"flag":"BLOCK","start":5350,"end":5424,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":3536},"to":{"change":4,"start":3536,"end":3580},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":3580},"to":{"change":4,"start":3580,"end":3602},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" pub fn deinit(self: @This(), allocator: std.mem.Allocator) void {"}],"del_contents":[{"Del":" pub fn deinit(self: @This()) void {\n"},{"Del":" _ = self;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":90,"ins":{"up_context":[{"change":4,"pos":3692}],"down_context":[{"change":4,"pos":3793}],"flag":"BLOCK","start":5425,"end":5516,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":3692},"to":{"change":4,"start":3692,"end":3793},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" allocator.free(current.nexts);"},{"Add":" allocator.destroy(current);"}],"del_contents":[{"Del":" self.allocator.free(current.nexts);\n self.allocator.destroy(current);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":95,"ins":{"up_context":[{"change":4,"pos":3840}],"down_context":[{"change":4,"pos":3933}],"flag":"BLOCK","start":5517,"end":5600,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":3840},"to":{"change":4,"start":3840,"end":3933},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" allocator.free(current.nexts);"},{"Add":" allocator.destroy(current);"}],"del_contents":[{"Del":" self.allocator.free(current.nexts);\n self.allocator.destroy(current);\n"}]}},{"Edit":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":99,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":3944}],"down_context":[{"change":4,"pos":3944}],"flag":"BLOCK","start":5601,"end":5736,"inode":{"change":4,"pos":108}}},"contents":[{"Add":" /// findNode finds the node with the matching `key` value. It also fills in preds and succs slices"},{"Add":" /// in the process."}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":106,"ins":{"up_context":[{"change":4,"pos":4117}],"down_context":[{"change":4,"pos":4168}],"flag":"BLOCK","start":5737,"end":5783,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":4117},"to":{"change":4,"start":4117,"end":4168},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" var level: usize = max_level + 1;"}],"del_contents":[{"Del":" var level: usize = self.max_level + 1;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":114,"ins":{"up_context":[{"change":4,"pos":4457}],"down_context":[{"change":4,"pos":4728}],"flag":"BLOCK","start":5784,"end":6059,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":4457},"to":{"change":4,"start":4457,"end":4728},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" if (found_level == null and curr != null and key == curr.?.key) {"},{"Add":" found_level = level - 1;"},{"Add":" // NOTE: We could return at this point, but see Section 3.4"},{"Add":" // for optimizations based on this lazy method."}],"del_contents":[{"Del":" // XXX: compiler bug!\n if (found_level == null) {\n if (curr != null) {\n if (key == curr.?.key) {\n found_level = level - 1;\n }\n }\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":127,"ins":{"up_context":[{"change":4,"pos":4887}],"down_context":[{"change":4,"pos":4887}],"flag":"BLOCK","start":6060,"end":6171,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":4887},"to":{"change":4,"start":1346,"end":1402},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" // TODO: do we really need preds and succs here?"},{"Add":" // findNode fills them, but it is unused here"}],"del_contents":[{"Del":" // XXX: do we really need preds and succs here?\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":130,"ins":{"up_context":[{"change":4,"pos":4949}],"down_context":[{"change":4,"pos":5119}],"flag":"BLOCK","start":6172,"end":6265,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":4949},"to":{"change":4,"start":4949,"end":5073},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":5073},"to":{"change":4,"start":5073,"end":5119},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" var preds: [max_level + 1]?*Node = undefined;"},{"Add":" @memset(&preds, null);"}],"del_contents":[{"Del":" var preds = try self.allocator.alloc(?*Node, self.max_level + 1);\n std.mem.set(?*Node, preds, null);\n"},{"Del":" defer self.allocator.free(preds);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":133,"ins":{"up_context":[{"change":4,"pos":5120}],"down_context":[{"change":4,"pos":5290}],"flag":"BLOCK","start":6266,"end":6359,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":5120},"to":{"change":4,"start":5120,"end":5244},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":5244},"to":{"change":4,"start":5244,"end":5290},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" var succs: [max_level + 1]?*Node = undefined;"},{"Add":" @memset(&succs, null);"}],"del_contents":[{"Del":" var succs = try self.allocator.alloc(?*Node, self.max_level + 1);\n std.mem.set(?*Node, succs, null);\n"},{"Del":" defer self.allocator.free(succs);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":136,"ins":{"up_context":[{"change":4,"pos":5291}],"down_context":[{"change":4,"pos":5383}],"flag":"BLOCK","start":6360,"end":6454,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":5291},"to":{"change":4,"start":5291,"end":5383},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" const found_level = self.findNode(search_key, &preds, &succs) orelse return null;"}],"del_contents":[{"Del":" const found_level = self.findNode(search_key, preds, succs) orelse return null;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":145,"ins":{"up_context":[{"change":4,"pos":5657}],"down_context":[{"change":4,"pos":5773}],"flag":"BLOCK","start":6455,"end":6566,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":5657},"to":{"change":4,"start":5657,"end":5773},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" while (random.float(f32) < (1 / opts.skip_size) and"},{"Add":" level < max_level) level += 1;"}],"del_contents":[{"Del":" while (random.float(f32) < (1 / self.skip_size) and\n level < self.max_level) level += 1;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":150,"ins":{"up_context":[{"change":4,"pos":5810}],"down_context":[{"change":4,"pos":5888}],"flag":"BLOCK","start":6567,"end":6675,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":5810},"to":{"change":4,"start":5810,"end":5888},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" pub fn insert(self: *@This(), allocator: std.mem.Allocator, insert_key: K, insert_value: V) !bool {"}],"del_contents":[{"Del":" pub fn insert(self: *@This(), insert_key: K, insert_value: V) !bool {\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":153,"ins":{"up_context":[{"change":4,"pos":5936}],"down_context":[{"change":4,"pos":6106}],"flag":"BLOCK","start":6676,"end":6772,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":5936},"to":{"change":4,"start":5936,"end":6060},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":6060},"to":{"change":4,"start":6060,"end":6106},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" var preds: [max_level + 1]?*Node = undefined;"},{"Add":" // @memset(&preds, null);"}],"del_contents":[{"Del":" var preds = try self.allocator.alloc(?*Node, self.max_level + 1);\n std.mem.set(?*Node, preds, null);\n"},{"Del":" defer self.allocator.free(preds);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":156,"ins":{"up_context":[{"change":4,"pos":6107}],"down_context":[{"change":4,"pos":6277}],"flag":"BLOCK","start":6773,"end":6869,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":6107},"to":{"change":4,"start":6107,"end":6231},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":6231},"to":{"change":4,"start":6231,"end":6277},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" var succs: [max_level + 1]?*Node = undefined;"},{"Add":" // @memset(&succs, null);"}],"del_contents":[{"Del":" var succs = try self.allocator.alloc(?*Node, self.max_level + 1);\n std.mem.set(?*Node, succs, null);\n"},{"Del":" defer self.allocator.free(succs);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":160,"ins":{"up_context":[{"change":4,"pos":6305}],"down_context":[{"change":4,"pos":6551}],"flag":"BLOCK","start":6870,"end":7058,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":6305},"to":{"change":4,"start":6305,"end":6551},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" if (self.findNode(insert_key, &preds, &succs)) |fl| {"},{"Add":" // We have found the key we are trying to insert..."},{"Add":" const node = succs[fl].?;"}],"del_contents":[{"Del":" const found_level = self.findNode(insert_key, preds, succs);\n\n // We have found the key we are trying to insert...\n if (found_level != null) {\n const node = succs[found_level.?].?;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":173,"ins":{"up_context":[{"change":4,"pos":6939}],"down_context":[{"change":4,"pos":7273}],"flag":"BLOCK","start":7059,"end":7342,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":6939},"to":{"change":4,"start":6939,"end":7273},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" // FIXME: hardcoded!"},{"Add":" const bits = comptime blk: {"},{"Add":" break :blk @as(usize, @intFromFloat(std.math.log(f32, 4, @as(f32, @floatFromInt(100_000)))));"},{"Add":" };"},{"Add":" var locks = std.StaticBitSet(bits + 1).initEmpty();"}],"del_contents":[{"Del":" // Lock handling part\n var helds = try std.ArrayList(std.event.Lock.Held).initCapacity(self.allocator, rlevel + 1);\n defer {\n for (helds.items) |held| {\n held.release();\n }\n helds.deinit();\n }\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":179,"ins":{"up_context":[{"change":4,"pos":7274}],"down_context":[{"change":4,"pos":7328}],"flag":"BLOCK","start":7343,"end":7576,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":7274},"to":{"change":4,"start":7274,"end":7328},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" // Find the new-node's place"},{"Add":" PLACE: while (true) {"},{"Add":" var pred: ?*Node = undefined;"},{"Add":" var succ: ?*Node = undefined;"},{"Add":" var prev_pred: ?*Node = null;"}],"del_contents":[{"Del":" // var highest_locked: ?usize = null;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":185,"ins":{"up_context":[{"change":4,"pos":7329}],"down_context":[{"change":4,"pos":7467}],"flag":"BLOCK","start":7577,"end":7621,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":7329},"to":{"change":4,"start":7329,"end":7467},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" var valid: bool = true;"}],"del_contents":[{"Del":" var pred: ?*Node = undefined;\n var succ: ?*Node = undefined;\n var prev_pred: ?*Node = null;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":187,"ins":{"up_context":[{"change":4,"pos":7468}],"down_context":[{"change":4,"pos":7508}],"flag":"BLOCK","start":7622,"end":7712,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":7468},"to":{"change":4,"start":7468,"end":7508},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" // std.debug.print(\"\\n{any} locks:\\n\", .{std.Thread.getCurrentId()});"}],"del_contents":[{"Del":" var valid: bool = true;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":189,"ins":{"up_context":[{"change":4,"pos":7509}],"down_context":[{"change":4,"pos":7696}],"flag":"BLOCK","start":7713,"end":7853,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":7509},"to":{"change":4,"start":7509,"end":7696},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" for (0..rlevel + 1) |level| {"},{"Add":" pred = preds[level];"},{"Add":" succ = succs[level];"}],"del_contents":[{"Del":" var level: usize = 0;\n while (valid and level <= rlevel) : (level += 1) {\n pred = preds[level];\n succ = succs[level];\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":193,"ins":{"up_context":[{"change":4,"pos":7697}],"down_context":[{"change":4,"pos":7910}],"flag":"BLOCK","start":7854,"end":9262,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":7697},"to":{"change":4,"start":7697,"end":7910},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" if (pred != prev_pred) { // only count multilayer items once"},{"Add":" // std.debug.print(\"\\t{d} {any}\\n\", .{ level, pred.?.key });"},{"Add":" pred.?.lock.lock();"},{"Add":" locks.set(level);"},{"Add":" prev_pred = pred;"},{"Add":" }"},{"Add":""},{"Add":" std.debug.assert(pred != null);"},{"Add":" // Validation checks that for each layer:"},{"Add":" // 1) level ≤ rlevel"},{"Add":" // 2) preds[level] and succs[level] are still adjacent at `level`, and"},{"Add":" // 3) neither is marked."},{"Add":" // If validation fails, the thread encountered a conflicting operation, so it releases"},{"Add":" // the locks it acquired and restarts place finding."},{"Add":" valid = !pred.?.marked and (succ == null or !succ.?.marked) and"},{"Add":" pred.?.nexts[level] == succ;"},{"Add":""},{"Add":" // If !valid cleanup and go to PLACE"},{"Add":" if (!valid) {"},{"Add":" // cleanup the locks"},{"Add":" var lit = locks.iterator(.{});"},{"Add":" while (lit.next()) |lvl| {"},{"Add":" preds[lvl].?.lock.unlock();"},{"Add":" }"},{"Add":" break :PLACE;"},{"Add":" }"}],"del_contents":[{"Del":" if (pred != prev_pred) {\n helds.appendAssumeCapacity(pred.?.lock.acquire());\n // highest_locked = level;\n prev_pred = pred;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":221,"ins":{"up_context":[{"change":4,"pos":7933}],"down_context":[{"change":4,"pos":8592}],"flag":"BLOCK","start":9263,"end":9343,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":7933},"to":{"change":4,"start":7933,"end":8592},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" // At this point everything is set for adding the new Node."}],"del_contents":[{"Del":" std.debug.assert(pred != null);\n // Validation checks that for each layer:\n // 1) level ≤ rlevel\n // 2) preds[level] and succs[level] are still adjacent at `level`, and\n // 3) neither is marked.\n // If validation fails, the thread encountered a conflicting operation, so it releases\n // the locks it acquired (defer) and retries.\n valid = !pred.?.marked and (succ == null or !succ.?.marked) and\n pred.?.nexts[level] == succ;\n }\n if (!valid) continue;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":223,"ins":{"up_context":[{"change":4,"pos":8593}],"down_context":[{"change":4,"pos":8669}],"flag":"BLOCK","start":9344,"end":9468,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":8593},"to":{"change":4,"start":8593,"end":8669},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" var node = try Node.init(allocator, insert_key, rlevel);"},{"Add":" node.value = insert_value;"}],"del_contents":[{"Del":" // At this point everything is set for adding the new Node.\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":226,"ins":{"up_context":[{"change":4,"pos":8670}],"down_context":[{"change":4,"pos":8791}],"flag":"BLOCK","start":9469,"end":9746,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":8670},"to":{"change":4,"start":8670,"end":8791},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" for (0..rlevel + 1) |level| {"},{"Add":" node.nexts[level] = succs[level]; // unlocked, but safe, as not linked yet"},{"Add":" preds[level].?.nexts[level] = node;"},{"Add":" }"},{"Add":" node.fully_linked = true;"}],"del_contents":[{"Del":" var node = try Node.init(self.allocator, insert_key, rlevel);\n node.value = insert_value;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":232,"ins":{"up_context":[{"change":4,"pos":8792}],"down_context":[{"change":4,"pos":9087}],"flag":"BLOCK","start":9747,"end":10063,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":8792},"to":{"change":4,"start":8792,"end":9087},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" // cleanup the locks"},{"Add":" var lit = locks.iterator(.{});"},{"Add":" while (lit.next()) |lvl| {"},{"Add":" // std.debug.print(\"\\tfinal unlocks {d} {any}\\n\", .{ lvl, preds[lvl].?.key });"},{"Add":" preds[lvl].?.lock.unlock();"},{"Add":" }"}],"del_contents":[{"Del":" level = 0;\n while (level <= rlevel) : (level += 1) {\n node.nexts[level] = succs[level]; // unlocked, but safe, as not linked yet\n preds[level].?.nexts[level] = node;\n }\n node.fully_linked = true;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":239,"ins":{"up_context":[{"change":4,"pos":9088}],"down_context":[{"change":4,"pos":9117}],"flag":"BLOCK","start":10064,"end":10115,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":9088},"to":{"change":4,"start":9088,"end":9117},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" return true;"},{"Add":" }"}],"del_contents":[{"Del":" return true;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":244,"ins":{"up_context":[{"change":4,"pos":9142}],"down_context":[{"change":4,"pos":9198}],"flag":"BLOCK","start":10116,"end":10206,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":9142},"to":{"change":3,"start":3195,"end":3255},"introduced_by":3}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" pub fn remove(self: @This(), allocator: std.mem.Allocator, remove_key: K) !bool {"}],"del_contents":[{"Del":" pub fn remove(self: @This(), remove_key: K) !bool {\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":247,"ins":{"up_context":[{"change":4,"pos":9286}],"down_context":[{"change":4,"pos":9346}],"flag":"BLOCK","start":10207,"end":10255,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":9286},"to":{"change":4,"start":9286,"end":9346},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" var node_lock = std.Thread.Mutex{};"}],"del_contents":[{"Del":" var node_lock: std.event.Lock.Held = undefined;\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":250,"ins":{"up_context":[{"change":4,"pos":9382}],"down_context":[{"change":4,"pos":9552}],"flag":"BLOCK","start":10256,"end":10399,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":9382},"to":{"change":4,"start":9382,"end":9506},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":9506},"to":{"change":4,"start":9506,"end":9552},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" var preds = try allocator.alloc(?*Node, max_level + 1);"},{"Add":" @memset(preds, null);"},{"Add":" defer allocator.free(preds);"}],"del_contents":[{"Del":" var preds = try self.allocator.alloc(?*Node, self.max_level + 1);\n std.mem.set(?*Node, preds, null);\n"},{"Del":" defer self.allocator.free(preds);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":254,"ins":{"up_context":[{"change":4,"pos":9553}],"down_context":[{"change":4,"pos":9723}],"flag":"BLOCK","start":10400,"end":10545,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":9553},"to":{"change":4,"start":9553,"end":9677},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":9677},"to":{"change":4,"start":9677,"end":9723},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" const succs = try allocator.alloc(?*Node, max_level + 1);"},{"Add":" @memset(succs, null);"},{"Add":" defer allocator.free(succs);"}],"del_contents":[{"Del":" var succs = try self.allocator.alloc(?*Node, self.max_level + 1);\n std.mem.set(?*Node, succs, null);\n"},{"Del":" defer self.allocator.free(succs);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":267,"ins":{"up_context":[{"change":4,"pos":10133}],"down_context":[{"change":4,"pos":10199}],"flag":"BLOCK","start":10546,"end":10588,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":10133},"to":{"change":4,"start":10133,"end":10199},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" node_lock.lock();"}],"del_contents":[{"Del":" node_lock = node_delete.?.lock.acquire();\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":269,"ins":{"up_context":[{"change":4,"pos":10251}],"down_context":[{"change":4,"pos":10300}],"flag":"BLOCK","start":10589,"end":10637,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":10251},"to":{"change":4,"start":10251,"end":10300},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" node_lock.unlock();"}],"del_contents":[{"Del":" node_lock.release();\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":277,"ins":{"up_context":[{"change":4,"pos":10528}],"down_context":[{"change":4,"pos":10648}],"flag":"BLOCK","start":10638,"end":10750,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":10528},"to":{"change":4,"start":10528,"end":10648},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" var helds = try std.ArrayList(std.Thread.Mutex).initCapacity(allocator, node_height.? + 1);"}],"del_contents":[{"Del":" var helds = try std.ArrayList(std.event.Lock.Held).initCapacity(self.allocator, node_height.? + 1);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":279,"ins":{"up_context":[{"change":4,"pos":10676}],"down_context":[{"change":4,"pos":10771}],"flag":"BLOCK","start":10751,"end":10846,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":10676},"to":{"change":4,"start":10676,"end":10771},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" for (helds.items) |*held| {"},{"Add":" held.unlock();"}],"del_contents":[{"Del":" for (helds.items) |held| {\n held.release();\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":295,"ins":{"up_context":[{"change":4,"pos":11298}],"down_context":[{"change":4,"pos":11377}],"flag":"BLOCK","start":10847,"end":10964,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":11298},"to":{"change":4,"start":11298,"end":11377},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" pred.?.lock.lock();"},{"Add":" helds.appendAssumeCapacity(pred.?.lock);"}],"del_contents":[{"Del":" helds.appendAssumeCapacity(pred.?.lock.acquire());\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":308,"ins":{"up_context":[{"change":4,"pos":11813}],"down_context":[{"change":4,"pos":11912}],"flag":"BLOCK","start":10965,"end":11058,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":11813},"to":{"change":4,"start":11813,"end":11854},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":11854},"to":{"change":4,"start":11854,"end":11912},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" node_lock.unlock();"},{"Add":" node_delete.?.deinit(allocator);"}],"del_contents":[{"Del":" node_lock.release();\n"},{"Del":" node_delete.?.deinit(self.allocator);\n"}]}},{"Edit":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":322,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":12238},"to":{"change":4,"start":12238,"end":12293},"introduced_by":4}],"inode":{"change":4,"pos":108}}},"contents":[{"Del":"\n// run tests with zig test --test-evented-io -fstage1\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":325,"ins":{"up_context":[{"change":4,"pos":12335}],"down_context":[{"change":4,"pos":12486}],"flag":"BLOCK","start":11059,"end":11311,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":12335},"to":{"change":4,"start":12335,"end":12407},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":12407},"to":{"change":4,"start":2155,"end":2211},"introduced_by":4},{"previous":"","flag":"DELETED","from":{"change":4,"pos":2211},"to":{"change":4,"start":12463,"end":12486},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":12463},"to":{"change":4,"start":12463,"end":12486},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" const SL = Lazy(Options{ .items = 16, .skip_size = 4 }, KeyType, void, {}, comptime std.sort.asc(KeyType));"},{"Add":" var sl = try SL.init(std.testing.allocator);"},{"Add":" defer sl.deinit(std.testing.allocator);"},{"Add":" errdefer sl.deinit(std.testing.allocator);"}],"del_contents":[{"Del":" const SL = Lazy(KeyType, void, {}, comptime std.sort.asc(KeyType));\n"},{"Del":" var sl = try SL.init(std.testing.allocator, 4, 16);\n"},{"Del":" defer sl.deinit();\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":330,"ins":{"up_context":[{"change":4,"pos":12487}],"down_context":[{"change":4,"pos":13521}],"flag":"BLOCK","start":11312,"end":12737,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":12487},"to":{"change":4,"start":12487,"end":12973},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":12973},"to":{"change":4,"start":12973,"end":13217},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":13217},"to":{"change":4,"start":13217,"end":13277},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":13277},"to":{"change":4,"start":13277,"end":13521},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 3, {})) == true);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 6, {})) == true);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 7, {})) == true);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 9, {})) == true);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 12, {})) == true);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 12, {})) == false);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 12, {})) == false);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 19, {})) == true);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 8, {})) == true);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 17, {})) == true);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 26, {})) == true);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 21, {})) == true);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 25, {})) == true);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 42, {})) == true);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 88, {})) == true);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 22, {})) == true);"},{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, 66, {})) == true);"}],"del_contents":[{"Del":" try std.testing.expect((try sl.insert(3, {})) == true);\n try std.testing.expect((try sl.insert(6, {})) == true);\n try std.testing.expect((try sl.insert(7, {})) == true);\n try std.testing.expect((try sl.insert(9, {})) == true);\n try std.testing.expect((try sl.insert(12, {})) == true);\n try std.testing.expect((try sl.insert(12, {})) == false);\n try std.testing.expect((try sl.insert(12, {})) == false);\n try std.testing.expect((try sl.insert(19, {})) == true);\n"},{"Del":" try std.testing.expect((try sl.insert(17, {})) == true);\n try std.testing.expect((try sl.insert(26, {})) == true);\n try std.testing.expect((try sl.insert(21, {})) == true);\n try std.testing.expect((try sl.insert(25, {})) == true);\n"},{"Del":" try std.testing.expect((try sl.insert(8, {})) == true);\n"},{"Del":" try std.testing.expect((try sl.insert(42, {})) == true);\n try std.testing.expect((try sl.insert(88, {})) == true);\n try std.testing.expect((try sl.insert(22, {})) == true);\n try std.testing.expect((try sl.insert(66, {})) == true);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":348,"ins":{"up_context":[{"change":4,"pos":13522}],"down_context":[{"change":4,"pos":13605}],"flag":"BLOCK","start":12738,"end":12844,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":13522},"to":{"change":4,"start":13522,"end":13605},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" try std.testing.expect((try sl.insert(std.testing.allocator, std.math.minInt(KeyType), {})) == true);"}],"del_contents":[{"Del":" try std.testing.expect((try sl.insert(std.math.minInt(KeyType), {})) == true);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":108},"path":"src/lazy.zig","line":356,"ins":{"up_context":[{"change":4,"pos":13809}],"down_context":[{"change":4,"pos":14061}],"flag":"BLOCK","start":12845,"end":13189,"inode":{"change":4,"pos":108}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":13809},"to":{"change":4,"start":13809,"end":14061},"introduced_by":4}],"inode":{"change":4,"pos":108}},"ins_contents":[{"Add":" try std.testing.expect((try sl.remove(std.testing.allocator, 13)) == false);"},{"Add":" try std.testing.expect((try sl.remove(std.testing.allocator, 12)) == true);"},{"Add":" try std.testing.expect((try sl.remove(std.testing.allocator, 12)) == false);"},{"Add":" try std.testing.expect((try sl.remove(std.testing.allocator, std.math.minInt(KeyType))) == true);"}],"del_contents":[{"Del":" try std.testing.expect((try sl.remove(13)) == false);\n try std.testing.expect((try sl.remove(12)) == true);\n try std.testing.expect((try sl.remove(12)) == false);\n try std.testing.expect((try sl.remove(std.math.minInt(KeyType))) == true);\n"}]}},{"Replacement":{"inode":{"change":4,"pos":8644},"path":"build.zig","line":3,"ins":{"up_context":[{"change":4,"pos":8674}],"down_context":[{"change":4,"pos":2504}],"flag":"BLOCK","start":13190,"end":13225,"inode":{"change":4,"pos":8644}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":8674},"to":{"change":4,"start":8674,"end":8717},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":8717},"to":{"change":4,"start":2212,"end":2504},"introduced_by":4}],"inode":{"change":4,"pos":8644}},"ins_contents":[{"Add":"pub fn build(b: *std.Build) void {"}],"del_contents":[{"Del":"pub fn build(b: *std.build.Builder) void {\n"},{"Del":" // Standard target options allows the person running `zig build` to choose\n // what target to build for. Here we do not override the defaults, which\n // means any target is allowed, and the default is native. Other options\n // for restricting supported target set are available.\n"}]}},{"Edit":{"inode":{"change":4,"pos":8644},"path":"build.zig","line":5,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":2553}],"down_context":[{"change":4,"pos":2553}],"flag":"BLOCK","start":13226,"end":13278,"inode":{"change":4,"pos":8644}}},"contents":[{"Add":" const optimize = b.standardOptimizeOption(.{});"}]}},{"Replacement":{"inode":{"change":4,"pos":8644},"path":"build.zig","line":7,"ins":{"up_context":[{"change":4,"pos":2554}],"down_context":[{"change":4,"pos":8907}],"flag":"BLOCK","start":13279,"end":13462,"inode":{"change":4,"pos":8644}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":4,"pos":2554},"to":{"change":4,"start":8717,"end":8907},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":8717},"to":{"change":4,"start":8717,"end":8907},"introduced_by":4}],"inode":{"change":4,"pos":8644}},"ins_contents":[{"Add":" const exe = b.addExecutable(.{"},{"Add":" .name = \"skiplist.zig\","},{"Add":" .root_source_file = b.path(\"src/main.zig\"),"},{"Add":" .target = target,"},{"Add":" .optimize = optimize,"},{"Add":" });"}],"del_contents":[{"Del":" // Standard release options allow the person running `zig build` to select\n // between Debug, ReleaseSafe, ReleaseFast, and ReleaseSmall.\n const mode = b.standardReleaseOptions();\n"}]}},{"Replacement":{"inode":{"change":4,"pos":8644},"path":"build.zig","line":14,"ins":{"up_context":[{"change":4,"pos":8908}],"down_context":[{"change":4,"pos":9023}],"flag":"BLOCK","start":13463,"end":13681,"inode":{"change":4,"pos":8644}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":8908},"to":{"change":4,"start":2555,"end":2721},"introduced_by":4}],"inode":{"change":4,"pos":8644}},"ins_contents":[{"Add":" // This declares intent for the executable to be installed into the"},{"Add":" // standard location when the user invokes the \"install\" step (the default"},{"Add":" // step when running `zig build`)."},{"Add":" b.installArtifact(exe);"}],"del_contents":[{"Del":" const exe = b.addExecutable(\"skiplist.zig\", \"src/main.zig\");\n exe.setTarget(target);\n exe.setBuildMode(mode);\n exe.use_stage1 = true;\n exe.install();\n"}]}},{"Replacement":{"inode":{"change":4,"pos":8644},"path":"build.zig","line":19,"ins":{"up_context":[{"change":4,"pos":9024}],"down_context":[{"change":4,"pos":2753}],"flag":"BLOCK","start":13682,"end":14242,"inode":{"change":4,"pos":8644}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":9024},"to":{"change":4,"start":2722,"end":2753},"introduced_by":4}],"inode":{"change":4,"pos":8644}},"ins_contents":[{"Add":" // This *creates* a Run step in the build graph, to be executed when another"},{"Add":" // step is evaluated that depends on it. The next line below will establish"},{"Add":" // such a dependency."},{"Add":" const run_cmd = b.addRunArtifact(exe);"},{"Add":""},{"Add":" // By making the run step depend on the install step, it will be run from the"},{"Add":" // installation directory rather than directly from within the cache directory."},{"Add":" // This is not necessary, however, if the application depends on other installed"},{"Add":" // files, this ensures they will be present and in the expected location."}],"del_contents":[{"Del":" const run_cmd = exe.run();\n"}]}},{"Edit":{"inode":{"change":4,"pos":8644},"path":"build.zig","line":29,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":2800}],"down_context":[{"change":4,"pos":2800}],"flag":"BLOCK","start":14243,"end":14389,"inode":{"change":4,"pos":8644}}},"contents":[{"Add":""},{"Add":" // This allows the user to pass arguments to the application in the build"},{"Add":" // command itself, like this: `zig build run -- arg1 arg2 etc`"}]}},{"Edit":{"inode":{"change":4,"pos":8644},"path":"build.zig","line":36,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":9110}],"down_context":[{"change":4,"pos":2863}],"flag":"BLOCK","start":14390,"end":14615,"inode":{"change":4,"pos":8644}}},"contents":[{"Add":" // This creates a build step. It will be visible in the `zig build --help` menu,"},{"Add":" // and can be selected like this: `zig build run`"},{"Add":" // This will evaluate the `run` step rather than the default, which is \"install\"."}]}},{"Replacement":{"inode":{"change":4,"pos":8644},"path":"build.zig","line":42,"ins":{"up_context":[{"change":4,"pos":2953}],"down_context":[{"change":4,"pos":3069}],"flag":"BLOCK","start":14616,"end":14942,"inode":{"change":4,"pos":8644}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":2953},"to":{"change":4,"start":2953,"end":3069},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":3069},"to":{"change":4,"start":1403,"end":1474},"introduced_by":4}],"inode":{"change":4,"pos":8644}},"ins_contents":[{"Add":" // Creates a step for unit testing. This only builds the test executable"},{"Add":" // but does not run it."},{"Add":" const exe_unit_tests = b.addTest(.{"},{"Add":" .root_source_file = b.path(\"src/lib.zig\"),"},{"Add":" .target = target,"},{"Add":" .optimize = optimize,"},{"Add":" });"},{"Add":""},{"Add":" const run_exe_unit_tests = b.addRunArtifact(exe_unit_tests);"}],"del_contents":[{"Del":" const exe_tests = b.addTest(\"src/main.zig\");\n exe_tests.setTarget(target);\n exe_tests.setBuildMode(mode);\n"},{"Del":" exe_tests.use_stage1 = true;\n exe_tests.test_evented_io = true;\n"}]}},{"Edit":{"inode":{"change":4,"pos":8644},"path":"build.zig","line":52,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":3070}],"down_context":[{"change":4,"pos":3070}],"flag":"BLOCK","start":14943,"end":15129,"inode":{"change":4,"pos":8644}}},"contents":[{"Add":" // Similar to creating the run step earlier, this exposes a `test` step to"},{"Add":" // the `zig build --help` menu, providing a way for the user to request"},{"Add":" // running the unit tests."}]}},{"Replacement":{"inode":{"change":4,"pos":8644},"path":"build.zig","line":56,"ins":{"up_context":[{"change":4,"pos":3126}],"down_context":[{"change":4,"pos":9211}],"flag":"BLOCK","start":15130,"end":15180,"inode":{"change":4,"pos":8644}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":3126},"to":{"change":4,"start":3126,"end":3167},"introduced_by":4}],"inode":{"change":4,"pos":8644}},"ins_contents":[{"Add":" test_step.dependOn(&run_exe_unit_tests.step);"}],"del_contents":[{"Del":" test_step.dependOn(&exe_tests.step);\n"}]}}],"owner":"voroskoi","repo":"skiplist.zig","token":"mvWQOmFYI5w/NGVTmttQ7cWcf2ueziVF9KyqGi/lNfY=","login":null}

…

Dependencies

Change contents