LRU cache

lru.zig

const std = @import("std");
const debug = std.debug;
const mem = std.mem;
const net = std.net;
const time = std.time;

const dprint = debug.print;
const assert = debug.assert;

pub fn Lru(comptime T: type, comptime key_size: u16) type {
    return struct {
        const Self = @This();
        allocator: mem.Allocator,
        items: []Item,
        count: usize,
        queue: Queue,
        map: Map,

        // why `void`? We don't need the `data` field
        const Queue = std.TailQueue(void);
        const Map = std.StringHashMap(*Item);

        const Item = struct {
            key: [key_size]u8,
            key_len: u16,
            data: T,
            node: Queue.Node,

            fn setKey(self: *Item, key: []const u8) void {
                const len = key.len;
                assert(len < key_size);

                mem.copyForwards(u8, &self.key, key);
                self.key_len = @intCast(u16, len);
            }

            fn getKey(self: *Item) []const u8 {
                return self.key[0..self.key_len];
            }
        };

        pub fn init(allocator: mem.Allocator, capacity: usize) !Self {
            return .{
                .allocator = allocator,
                .items = try allocator.alloc(Item, capacity),
                .count = 0,
                .queue = .{},
                .map = Map.init(allocator),
            };
        }

        pub fn deinit(self: *Self) void {
            self.map.deinit();
            self.allocator.free(self.items);
            self.* = undefined;
        }

        pub fn put(self: *Self, key: []const u8, data: T) !void {
            if (self.map.get(key)) |v| {
                self.queue.remove(&v.node);
                v.data = data;
                self.queue.append(&v.node);
            } else {
                var item: *Item = undefined;
                if (self.count < self.items.len) {
                    item = &self.items[self.count];
                    self.count += 1;
                } else {
                    item = @fieldParentPtr(Item, "node", self.queue.pop().?);
                    const res = self.map.remove(item.getKey());
                    assert(res);
                }

                item.setKey(key);
                item.data = data;
                self.queue.append(&item.node);
                try self.map.put(item.getKey(), item);
            }

            assert(self.map.count() <= self.items.len);
        }

        pub fn getPtr(self: *Self, key: []const u8) ?*T {
            if (self.map.get(key)) |v| {
                self.queue.remove(&v.node);
                self.queue.prepend(&v.node);

                assert(self.map.count() <= self.items.len);
                return &v.data;
            }

            return null;
        }

        pub fn remove(self: *Self, key: []const u8, comptime cmp_fn: fn (T) bool) bool {
            if (self.map.get(key)) |v| {
                if (cmp_fn(v.data)) {
                    assert(self.count > 0);

                    const res = self.map.remove(v.getKey());
                    assert(res);

                    self.count -= 1;
                    var last = &self.items[self.count];

                    self.queue.insertBefore(&v.node, &last.node);
                    self.queue.remove(&v.node);

                    // swap remove
                    v.* = last.*;
                    return true;
                }
            }

            return false;
        }
    };
}