Something went wrong. Try again.
jetstream v2 in zig stream.waow.tech
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294//! 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);}