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

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

const std = @import("std");
pub fn Lazy(
    comptime K: anytype,
    comptime V: anytype,
    context: anytype,
    comptime lessThan: fn (@TypeOf(context), lhs: K, rhs: K) bool,
) type {
    return struct {
        rnd: std.rand.DefaultPrng,
        allocator: std.mem.Allocator,
        /// Determines average skip size for each level of SkipList. Equals `1/P`.
        skip_size: f32,
        /// Maximum number of levels in the SkipList.
        max_level: usize = undefined,
        /// Starting Node pointer of the SkipList.
        head: *Node,
        pub const Node = struct {
            key: ?K,
            value: V,
            nexts: []?*Node,
            height: usize,
            /// This field it `true` when Node is marked for removal.
            marked: bool = false,
            /// This item is `true` when the `insert` operation has finished updating all levels.
            fully_linked: bool = false,
            lock: std.event.Lock,
            fn init(allocator: std.mem.Allocator, key: K, level: usize) !*@This() {
                var n = try allocator.create(Node);
                n.key = key;
                n.nexts = try allocator.alloc(?*Node, level + 1);
                std.mem.set(?*Node, n.nexts, null);
                n.lock = std.event.Lock{};
                n.height = level;
                return n;
            }
            fn deinit(self: *@This(), allocator: std.mem.Allocator) void {
                allocator.free(self.nexts);
                allocator.destroy(self);
            }
        };
        fn getMaxLevel(self: @This(), n: usize) usize {
            return @floatToInt(usize, std.math.log(f32, self.skip_size, @intToFloat(f32, n)));
        }
        pub fn display(self: @This()) void {
            std.debug.print("SkipList structure - P:{d}, max_level: {d}\n", .{ 1 / self.skip_size, self.max_level });
            var level: usize = self.max_level + 1;
            while (level > 0) : (level -= 1) {
                var node: ?*Node = self.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", .{});
            }
        }
        pub fn init(
            /// Allocator to use when creating SkipList and its Node items.
            allocator: std.mem.Allocator,
            /// Number of items to skip with each level. This is a probabilistic value.
            skip_size: f32,
            /// Maximum number of items to be stored in the SkipList.
            /// This is not a hard limit, but SkipList performance will degrade when badly choosen.
            n_max: usize,
        ) !@This() {
            if (skip_size <= 1) {
                std.log.err("skip_size {d} not allowed, must be > 1", .{skip_size});
                return error.InvalidSkipSize;
            }
            var sl = @This(){
                .rnd = std.rand.DefaultPrng.init(@intCast(u64, std.time.milliTimestamp())),
                .skip_size = skip_size,
                .allocator = allocator,
                .head = undefined,
            };
            sl.max_level = sl.getMaxLevel(n_max);
            sl.head = try Node.init(sl.allocator, 0, sl.max_level);
            sl.head.key = null;
            return sl;
        }
        pub fn deinit(self: @This()) void {
            _ = self;
            var current: *Node = self.head;
            while (current.nexts[0]) |next| {
                self.allocator.free(current.nexts);
                self.allocator.destroy(current);
                current = next;
            }
            self.allocator.free(current.nexts);
            self.allocator.destroy(current);
        }
        fn findNode(self: @This(), key: K, preds: []?*Node, succs: []?*Node) ?usize {
            var found_level: ?usize = null;
            var pred: *Node = self.head;
            var level: usize = self.max_level + 1;
            while (level > 0) : (level -= 1) {
                var curr: ?*Node = pred.nexts[level - 1];
                while (curr != null and lessThan(context, curr.?.key.?, key)) {
                    pred = curr.?;
                    curr = pred.nexts[level - 1];
                }
                // XXX: compiler bug!
                if (found_level == null) {
                    if (curr != null) {
                        if (key == curr.?.key) {
                            found_level = level - 1;
                        }
                    }
                }
                preds[level - 1] = pred;
                succs[level - 1] = curr;
            }
            return found_level;
        }
        pub fn search(self: @This(), search_key: K) !?*Node {
            var preds = try self.allocator.alloc(?*Node, self.max_level + 1);
            std.mem.set(?*Node, preds, null);
            defer self.allocator.free(preds);
            var succs = try self.allocator.alloc(?*Node, self.max_level + 1);
            std.mem.set(?*Node, succs, null);
            defer self.allocator.free(succs);
            const found_level = self.findNode(search_key, preds, succs) orelse return null;
            if (!succs[found_level].?.fully_linked or succs[found_level].?.marked) return null;
            return succs[found_level];
        }
        fn randomLevel(self: *@This()) usize {
            var level: usize = 0;
            const random = self.rnd.random();
            while (random.float(f32) < (1 / self.skip_size) and
                level < self.max_level) level += 1;
            return level;
        }
        pub fn insert(self: *@This(), insert_key: K, insert_value: V) !bool {
            const rlevel = self.randomLevel();
            var preds = try self.allocator.alloc(?*Node, self.max_level + 1);
            std.mem.set(?*Node, preds, null);
            defer self.allocator.free(preds);
            var succs = try self.allocator.alloc(?*Node, self.max_level + 1);
            std.mem.set(?*Node, succs, null);
            defer self.allocator.free(succs);
            while (true) {
                const found_level = self.findNode(insert_key, preds, succs);
                // We have found the key we are trying to insert...
                if (found_level != null) {
                    const node = succs[found_level.?].?;
                    if (!node.marked) {
                        // An other thread adding it, wait for it.
                        while (!node.fully_linked) {}
                        // Item already in the SkipList.
                        return false;
                    }
                    // Marked for deletion, retry adding it.
                    continue;
                }
                // Lock handling part
                var helds = try std.ArrayList(std.event.Lock.Held).initCapacity(self.allocator, rlevel + 1);
                defer {
                    for (helds.items) |held| {
                        held.release();
                    }
                    helds.deinit();
                }
                // var highest_locked: ?usize = null;
                var pred: ?*Node = undefined;
                var succ: ?*Node = undefined;
                var prev_pred: ?*Node = null;
                var valid: bool = true;
                var level: usize = 0;
                while (valid and level <= rlevel) : (level += 1) {
                    pred = preds[level];
                    succ = succs[level];
                    if (pred != prev_pred) {
                        helds.appendAssumeCapacity(pred.?.lock.acquire());
                        // highest_locked = level;
                        prev_pred = pred;
                    }
                    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 (defer) and retries.
                    valid = !pred.?.marked and (succ == null or !succ.?.marked) and
                        pred.?.nexts[level] == succ;
                }
                if (!valid) continue;
                // At this point everything is set for adding the new Node.
                var node = try Node.init(self.allocator, insert_key, rlevel);
                node.value = insert_value;
                level = 0;
                while (level <= rlevel) : (level += 1) {
                    node.nexts[level] = succs[level]; // unlocked, but safe, as not linked yet
                    preds[level].?.nexts[level] = node;
                }
                node.fully_linked = true;
                return true;
            }
        }
        fn remove(self: @This(), remove_key: K) !bool {
            var node_delete: ?*Node = null;
            var node_height: ?usize = null;
            var node_lock: std.event.Lock.Held = undefined;
            var is_marked = false;
            var preds = try self.allocator.alloc(?*Node, self.max_level + 1);
            std.mem.set(?*Node, preds, null);
            defer self.allocator.free(preds);
            var succs = try self.allocator.alloc(?*Node, self.max_level + 1);
            std.mem.set(?*Node, succs, null);
            defer self.allocator.free(succs);
            while (true) {
                const level_found = self.findNode(remove_key, preds, succs);
                if (is_marked or
                    (level_found != null and okDelete(succs[level_found.?].?, level_found.?)))
                {
                    if (!is_marked) {
                        node_delete = succs[level_found.?];
                        node_height = node_delete.?.height;
                        node_lock = node_delete.?.lock.acquire();
                        if (node_delete.?.marked) {
                            node_lock.release();
                            return false;
                        }
                        node_delete.?.marked = true;
                        is_marked = true;
                    }
                    // Lock handling part
                    var helds = try std.ArrayList(std.event.Lock.Held).initCapacity(self.allocator, node_height.? + 1);
                    defer {
                        for (helds.items) |held| {
                            held.release();
                        }
                        helds.deinit();
                    }
                    var pred: ?*Node = null;
                    var succ: ?*Node = null;
                    var prev_pred: ?*Node = null;
                    var valid = true;
                    var level: usize = 0;
                    while (valid and level <= node_height.?) : (level += 1) {
                        pred = preds[level];
                        succ = succs[level];
                        if (pred != prev_pred) {
                            helds.appendAssumeCapacity(pred.?.lock.acquire());
                            prev_pred = pred;
                        }
                        valid = !pred.?.marked and pred.?.nexts[level] == succ;
                    }
                    if (!valid) continue;
                    level = node_height.? + 1;
                    while (level > 0) : (level -= 1) {
                        preds[level - 1].?.nexts[level - 1] = node_delete.?.nexts[level - 1];
                    }
                    node_lock.release();
                    node_delete.?.deinit(self.allocator);
                    return true;
                } else {
                    return false;
                }
            }
        }
        fn okDelete(candidate: *Node, level_found: usize) bool {
            return candidate.*.fully_linked and candidate.*.height == level_found and !candidate.*.marked;
        }
    };
}
// run tests with zig test --test-evented-io -fstage1
test "Lazy" {
    const KeyType = usize;
    const SL = Lazy(KeyType, void, {}, comptime std.sort.asc(KeyType));
    var sl = try SL.init(std.testing.allocator, 2, 16);
    defer sl.deinit();
    try std.testing.expect((try sl.insert(3, {})) == true);
    try std.testing.expect((try sl.insert(6, {})) == true);
    try std.testing.expect((try sl.insert(7, {})) == true);
    try std.testing.expect((try sl.insert(9, {})) == true);
    try std.testing.expect((try sl.insert(12, {})) == true);
    try std.testing.expect((try sl.insert(12, {})) == false);
    try std.testing.expect((try sl.insert(12, {})) == false);
    try std.testing.expect((try sl.insert(19, {})) == true);
    try std.testing.expect((try sl.insert(17, {})) == true);
    try std.testing.expect((try sl.insert(26, {})) == true);
    try std.testing.expect((try sl.insert(21, {})) == true);
    try std.testing.expect((try sl.insert(25, {})) == true);
    try std.testing.expect((try sl.insert(8, {})) == true);
    try std.testing.expect((try sl.insert(42, {})) == true);
    try std.testing.expect((try sl.insert(88, {})) == true);
    try std.testing.expect((try sl.insert(22, {})) == true);
    try std.testing.expect((try sl.insert(66, {})) == true);
    try std.testing.expect((try sl.insert(std.math.minInt(KeyType), {})) == true);
    sl.display();
    try std.testing.expect((try sl.search(12)).?.key.? == 12);
    try std.testing.expect((try sl.search(13)) == null);
    try std.testing.expect((try sl.search(26)).?.key.? == 26);
    try std.testing.expect((try sl.remove(13)) == false);
    try std.testing.expect((try sl.remove(12)) == true);
    try std.testing.expect((try sl.remove(12)) == false);
    try std.testing.expect((try sl.remove(std.math.minInt(KeyType))) == true);
    sl.display();
}