//! generic LRU cache with string keys (ported from zlay, where it holds
//! 250k DID signing keys in production)
//!
//! O(1) get/put/remove via hashmap + intrusive doubly-linked list.
//! thread-safe (internal mutex). keys are duped on insert, freed on eviction.

const std = @import("std");
const Io = std.Io;
const Allocator = std.mem.Allocator;

pub fn LruCache(comptime V: type) type {
    return struct {
        const Self = @This();

        const Node = struct {
            key: []const u8,
            value: V,
            prev: ?*Node = null,
            next: ?*Node = null,
        };

        map: std.StringHashMapUnmanaged(*Node) = .empty,
        head: ?*Node = null, // most recently used
        tail: ?*Node = null, // least recently used
        capacity: u32,
        len: u32 = 0,
        allocator: Allocator,
        mutex: Io.Mutex = Io.Mutex.init,
        io: Io,

        pub fn init(allocator: Allocator, capacity: u32, io: Io) Self {
            return .{
                .allocator = allocator,
                .capacity = capacity,
                .io = io,
            };
        }

        pub fn deinit(self: *Self) void {
            var node = self.head;
            while (node) |n| {
                const next = n.next;
                self.allocator.free(n.key);
                self.allocator.destroy(n);
                node = next;
            }
            self.map.deinit(self.allocator);
        }

        pub fn get(self: *Self, key: []const u8) ?V {
            self.mutex.lockUncancelable(self.io);
            defer self.mutex.unlock(self.io);
            const node = self.map.get(key) orelse return null;
            self.moveToHead(node);
            return node.value;
        }

        pub fn put(self: *Self, key: []const u8, value: V) Allocator.Error!void {
            self.mutex.lockUncancelable(self.io);
            defer self.mutex.unlock(self.io);

            if (self.map.get(key)) |node| {
                // update existing
                node.value = value;
                self.moveToHead(node);
                return;
            }

            // evict if at capacity
            if (self.len >= self.capacity) {
                self.evictTail();
            }

            // allocate node + dupe key
            const duped = try self.allocator.dupe(u8, key);
            errdefer self.allocator.free(duped);
            const node = try self.allocator.create(Node);
            node.* = .{ .key = duped, .value = value };

            self.map.put(self.allocator, duped, node) catch |err| {
                self.allocator.free(duped);
                self.allocator.destroy(node);
                return err;
            };

            // link at head
            node.next = self.head;
            if (self.head) |h| h.prev = node;
            self.head = node;
            if (self.tail == null) self.tail = node;
            self.len += 1;
        }

        pub fn remove(self: *Self, key: []const u8) bool {
            self.mutex.lockUncancelable(self.io);
            defer self.mutex.unlock(self.io);
            const node = self.map.get(key) orelse return false;
            self.unlink(node);
            // fetchRemove uses the node's owned key for lookup, which is valid
            // since we haven't freed it yet
            _ = self.map.remove(node.key);
            self.allocator.free(node.key);
            self.allocator.destroy(node);
            self.len -= 1;
            return true;
        }

        /// check if a key exists without promoting it
        pub fn contains(self: *Self, key: []const u8) bool {
            self.mutex.lockUncancelable(self.io);
            defer self.mutex.unlock(self.io);
            return self.map.contains(key);
        }

        /// entry count (non-blocking — returns 0 if lock is contended)
        pub fn count(self: *Self) u32 {
            if (!self.mutex.tryLock()) return 0;
            defer self.mutex.unlock(self.io);
            return self.len;
        }

        /// internal hashmap capacity (non-blocking — returns 0 if lock is contended)
        pub fn mapCapacity(self: *Self) u32 {
            if (!self.mutex.tryLock()) return 0;
            defer self.mutex.unlock(self.io);
            return self.map.capacity();
        }

        // --- internal (caller holds mutex) ---

        fn moveToHead(self: *Self, node: *Node) void {
            if (self.head == node) return;
            self.unlink(node);
            node.prev = null;
            node.next = self.head;
            if (self.head) |h| h.prev = node;
            self.head = node;
            if (self.tail == null) self.tail = node;
        }

        fn unlink(self: *Self, node: *Node) void {
            if (node.prev) |p| {
                p.next = node.next;
            } else {
                self.head = node.next;
            }
            if (node.next) |n| {
                n.prev = node.prev;
            } else {
                self.tail = node.prev;
            }
            node.prev = null;
            node.next = null;
        }

        fn evictTail(self: *Self) void {
            const t = self.tail orelse return;
            self.unlink(t);
            _ = self.map.remove(t.key);
            self.allocator.free(t.key);
            self.allocator.destroy(t);
            self.len -= 1;
        }
    };
}

// --- tests ---

const testing = std.testing;

test "basic get and put" {
    var cache = LruCache(u64).init(testing.allocator, 3, testing.io);
    defer cache.deinit();

    try cache.put("a", 1);
    try cache.put("b", 2);
    try cache.put("c", 3);

    try testing.expectEqual(@as(u64, 1), cache.get("a").?);
    try testing.expectEqual(@as(u64, 2), cache.get("b").?);
    try testing.expectEqual(@as(u64, 3), cache.get("c").?);
    try testing.expect(cache.get("d") == null);
}

test "eviction order" {
    var cache = LruCache(u64).init(testing.allocator, 2, testing.io);
    defer cache.deinit();

    try cache.put("a", 1);
    try cache.put("b", 2);
    // cache: b(head) → a(tail)

    try cache.put("c", 3); // evicts "a" (LRU)

    try testing.expect(cache.get("a") == null);
    try testing.expectEqual(@as(u64, 2), cache.get("b").?);
    try testing.expectEqual(@as(u64, 3), cache.get("c").?);
}

test "update moves to front" {
    var cache = LruCache(u64).init(testing.allocator, 2, testing.io);
    defer cache.deinit();

    try cache.put("a", 1);
    try cache.put("b", 2);
    // cache: b(head) → a(tail)

    // access "a" — promotes it to head
    _ = cache.get("a");
    // cache: a(head) → b(tail)

    try cache.put("c", 3); // evicts "b" (now LRU)

    try testing.expect(cache.get("b") == null);
    try testing.expectEqual(@as(u64, 1), cache.get("a").?);
    try testing.expectEqual(@as(u64, 3), cache.get("c").?);
}

test "put update existing key" {
    var cache = LruCache(u64).init(testing.allocator, 2, testing.io);
    defer cache.deinit();

    try cache.put("a", 1);
    try cache.put("b", 2);
    try cache.put("a", 10); // update, moves to head

    try testing.expectEqual(@as(u64, 10), cache.get("a").?);

    try cache.put("c", 3); // evicts "b" (LRU)
    try testing.expect(cache.get("b") == null);
    try testing.expectEqual(@as(u64, 10), cache.get("a").?);
}

test "remove" {
    var cache = LruCache(u64).init(testing.allocator, 3, testing.io);
    defer cache.deinit();

    try cache.put("a", 1);
    try cache.put("b", 2);

    try testing.expect(cache.remove("a"));
    try testing.expect(cache.get("a") == null);
    try testing.expectEqual(@as(u32, 1), cache.count());
    try testing.expect(!cache.remove("nonexistent"));
}

test "capacity 1" {
    var cache = LruCache(u64).init(testing.allocator, 1, testing.io);
    defer cache.deinit();

    try cache.put("a", 1);
    try testing.expectEqual(@as(u64, 1), cache.get("a").?);

    try cache.put("b", 2); // evicts "a"
    try testing.expect(cache.get("a") == null);
    try testing.expectEqual(@as(u64, 2), cache.get("b").?);
    try testing.expectEqual(@as(u32, 1), cache.count());
}

test "count" {
    var cache = LruCache(u64).init(testing.allocator, 10, testing.io);
    defer cache.deinit();

    try testing.expectEqual(@as(u32, 0), cache.count());
    try cache.put("a", 1);
    try testing.expectEqual(@as(u32, 1), cache.count());
    try cache.put("b", 2);
    try testing.expectEqual(@as(u32, 2), cache.count());
    _ = cache.remove("a");
    try testing.expectEqual(@as(u32, 1), cache.count());
}

test "contains" {
    var cache = LruCache(u64).init(testing.allocator, 3, testing.io);
    defer cache.deinit();

    try cache.put("a", 1);
    try testing.expect(cache.contains("a"));
    try testing.expect(!cache.contains("b"));
}

test "struct values" {
    const Val = struct { x: u32, y: u32 };
    var cache = LruCache(Val).init(testing.allocator, 2, testing.io);
    defer cache.deinit();

    try cache.put("point1", .{ .x = 1, .y = 2 });
    try cache.put("point2", .{ .x = 3, .y = 4 });

    const v = cache.get("point1").?;
    try testing.expectEqual(@as(u32, 1), v.x);
    try testing.expectEqual(@as(u32, 2), v.y);
}