zzstoatzz.io
atproto relay implementation in zig
zlay.waow.tech
1//! generic LRU cache with string keys
2//!
3//! O(1) get/put/remove via hashmap + intrusive doubly-linked list.
4//! thread-safe (internal mutex). keys are duped on insert, freed on eviction.
5
6const std = @import("std");
7const Allocator = std.mem.Allocator;
8
9pub fn LruCache(comptime V: type) type {
10 return struct {
11 const Self = @This();
12
13 const Node = struct {
14 key: []const u8,
15 value: V,
16 prev: ?*Node = null,
17 next: ?*Node = null,
18 };
19
20 map: std.StringHashMapUnmanaged(*Node) = .{},
21 head: ?*Node = null, // most recently used
22 tail: ?*Node = null, // least recently used
23 capacity: u32,
24 len: u32 = 0,
25 allocator: Allocator,
26 mutex: std.Thread.Mutex = .{},
27
28 pub fn init(allocator: Allocator, capacity: u32) Self {
29 return .{
30 .allocator = allocator,
31 .capacity = capacity,
32 };
33 }
34
35 pub fn deinit(self: *Self) void {
36 var node = self.head;
37 while (node) |n| {
38 const next = n.next;
39 self.allocator.free(n.key);
40 self.allocator.destroy(n);
41 node = next;
42 }
43 self.map.deinit(self.allocator);
44 }
45
46 pub fn get(self: *Self, key: []const u8) ?V {
47 self.mutex.lock();
48 defer self.mutex.unlock();
49 const node = self.map.get(key) orelse return null;
50 self.moveToHead(node);
51 return node.value;
52 }
53
54 pub fn put(self: *Self, key: []const u8, value: V) Allocator.Error!void {
55 self.mutex.lock();
56 defer self.mutex.unlock();
57
58 if (self.map.get(key)) |node| {
59 // update existing
60 node.value = value;
61 self.moveToHead(node);
62 return;
63 }
64
65 // evict if at capacity
66 if (self.len >= self.capacity) {
67 self.evictTail();
68 }
69
70 // allocate node + dupe key
71 const duped = try self.allocator.dupe(u8, key);
72 errdefer self.allocator.free(duped);
73 const node = try self.allocator.create(Node);
74 node.* = .{ .key = duped, .value = value };
75
76 self.map.put(self.allocator, duped, node) catch |err| {
77 self.allocator.free(duped);
78 self.allocator.destroy(node);
79 return err;
80 };
81
82 // link at head
83 node.next = self.head;
84 if (self.head) |h| h.prev = node;
85 self.head = node;
86 if (self.tail == null) self.tail = node;
87 self.len += 1;
88 }
89
90 pub fn remove(self: *Self, key: []const u8) bool {
91 self.mutex.lock();
92 defer self.mutex.unlock();
93 const node = self.map.get(key) orelse return false;
94 self.unlink(node);
95 // fetchRemove uses the node's owned key for lookup, which is valid
96 // since we haven't freed it yet
97 _ = self.map.remove(node.key);
98 self.allocator.free(node.key);
99 self.allocator.destroy(node);
100 self.len -= 1;
101 return true;
102 }
103
104 /// check if a key exists without promoting it
105 pub fn contains(self: *Self, key: []const u8) bool {
106 self.mutex.lock();
107 defer self.mutex.unlock();
108 return self.map.contains(key);
109 }
110
111 /// entry count (non-blocking — returns 0 if lock is contended)
112 pub fn count(self: *Self) u32 {
113 if (!self.mutex.tryLock()) return 0;
114 defer self.mutex.unlock();
115 return self.len;
116 }
117
118 /// internal hashmap capacity (non-blocking — returns 0 if lock is contended)
119 pub fn mapCapacity(self: *Self) u32 {
120 if (!self.mutex.tryLock()) return 0;
121 defer self.mutex.unlock();
122 return self.map.capacity();
123 }
124
125 // --- internal (caller holds mutex) ---
126
127 fn moveToHead(self: *Self, node: *Node) void {
128 if (self.head == node) return;
129 self.unlink(node);
130 node.prev = null;
131 node.next = self.head;
132 if (self.head) |h| h.prev = node;
133 self.head = node;
134 if (self.tail == null) self.tail = node;
135 }
136
137 fn unlink(self: *Self, node: *Node) void {
138 if (node.prev) |p| {
139 p.next = node.next;
140 } else {
141 self.head = node.next;
142 }
143 if (node.next) |n| {
144 n.prev = node.prev;
145 } else {
146 self.tail = node.prev;
147 }
148 node.prev = null;
149 node.next = null;
150 }
151
152 fn evictTail(self: *Self) void {
153 const t = self.tail orelse return;
154 self.unlink(t);
155 _ = self.map.remove(t.key);
156 self.allocator.free(t.key);
157 self.allocator.destroy(t);
158 self.len -= 1;
159 }
160 };
161}
162
163// --- tests ---
164
165const testing = std.testing;
166
167test "basic get and put" {
168 var cache = LruCache(u64).init(testing.allocator, 3);
169 defer cache.deinit();
170
171 try cache.put("a", 1);
172 try cache.put("b", 2);
173 try cache.put("c", 3);
174
175 try testing.expectEqual(@as(u64, 1), cache.get("a").?);
176 try testing.expectEqual(@as(u64, 2), cache.get("b").?);
177 try testing.expectEqual(@as(u64, 3), cache.get("c").?);
178 try testing.expect(cache.get("d") == null);
179}
180
181test "eviction order" {
182 var cache = LruCache(u64).init(testing.allocator, 2);
183 defer cache.deinit();
184
185 try cache.put("a", 1);
186 try cache.put("b", 2);
187 // cache: b(head) → a(tail)
188
189 try cache.put("c", 3); // evicts "a" (LRU)
190
191 try testing.expect(cache.get("a") == null);
192 try testing.expectEqual(@as(u64, 2), cache.get("b").?);
193 try testing.expectEqual(@as(u64, 3), cache.get("c").?);
194}
195
196test "update moves to front" {
197 var cache = LruCache(u64).init(testing.allocator, 2);
198 defer cache.deinit();
199
200 try cache.put("a", 1);
201 try cache.put("b", 2);
202 // cache: b(head) → a(tail)
203
204 // access "a" — promotes it to head
205 _ = cache.get("a");
206 // cache: a(head) → b(tail)
207
208 try cache.put("c", 3); // evicts "b" (now LRU)
209
210 try testing.expect(cache.get("b") == null);
211 try testing.expectEqual(@as(u64, 1), cache.get("a").?);
212 try testing.expectEqual(@as(u64, 3), cache.get("c").?);
213}
214
215test "put update existing key" {
216 var cache = LruCache(u64).init(testing.allocator, 2);
217 defer cache.deinit();
218
219 try cache.put("a", 1);
220 try cache.put("b", 2);
221 try cache.put("a", 10); // update, moves to head
222
223 try testing.expectEqual(@as(u64, 10), cache.get("a").?);
224
225 try cache.put("c", 3); // evicts "b" (LRU)
226 try testing.expect(cache.get("b") == null);
227 try testing.expectEqual(@as(u64, 10), cache.get("a").?);
228}
229
230test "remove" {
231 var cache = LruCache(u64).init(testing.allocator, 3);
232 defer cache.deinit();
233
234 try cache.put("a", 1);
235 try cache.put("b", 2);
236
237 try testing.expect(cache.remove("a"));
238 try testing.expect(cache.get("a") == null);
239 try testing.expectEqual(@as(u32, 1), cache.count());
240 try testing.expect(!cache.remove("nonexistent"));
241}
242
243test "capacity 1" {
244 var cache = LruCache(u64).init(testing.allocator, 1);
245 defer cache.deinit();
246
247 try cache.put("a", 1);
248 try testing.expectEqual(@as(u64, 1), cache.get("a").?);
249
250 try cache.put("b", 2); // evicts "a"
251 try testing.expect(cache.get("a") == null);
252 try testing.expectEqual(@as(u64, 2), cache.get("b").?);
253 try testing.expectEqual(@as(u32, 1), cache.count());
254}
255
256test "count" {
257 var cache = LruCache(u64).init(testing.allocator, 10);
258 defer cache.deinit();
259
260 try testing.expectEqual(@as(u32, 0), cache.count());
261 try cache.put("a", 1);
262 try testing.expectEqual(@as(u32, 1), cache.count());
263 try cache.put("b", 2);
264 try testing.expectEqual(@as(u32, 2), cache.count());
265 _ = cache.remove("a");
266 try testing.expectEqual(@as(u32, 1), cache.count());
267}
268
269test "contains" {
270 var cache = LruCache(u64).init(testing.allocator, 3);
271 defer cache.deinit();
272
273 try cache.put("a", 1);
274 try testing.expect(cache.contains("a"));
275 try testing.expect(!cache.contains("b"));
276}
277
278test "struct values" {
279 const Val = struct { x: u32, y: u32 };
280 var cache = LruCache(Val).init(testing.allocator, 2);
281 defer cache.deinit();
282
283 try cache.put("point1", .{ .x = 1, .y = 2 });
284 try cache.put("point2", .{ .x = 3, .y = 4 });
285
286 const v = cache.get("point1").?;
287 try testing.expectEqual(@as(u32, 1), v.x);
288 try testing.expectEqual(@as(u32, 2), v.y);
289}