用 Lua 实现 LRU

lru.lua

local lru = {}
local lru_mt = { __index = lru }

local function addnode(self, node)
    local head = self._head
    node._next = head
    if head then
        head._pre = node
    end
    self._head = node
    if self._tail == nil then
        self._tail = node
    end

    local key = node.key
    self.map[key] = node
end

local function delnode(self, node)
    local head = self._head
    if node == head then
        self._head = node._next
    end

    local tail = self._tail
    if node == tail then
        self._tail = node._pre
    end

    local pre = node._pre
    local next = node._next
    if pre then
        pre._next = next
    end
    if next then
        next._pre = pre
    end

    local key = node.key
    self.map[key] = nil
    node._pre = nil
    node._next = nil
end

local function tohead(self, node)
    delnode(self, node)
    addnode(self, node)
end

function lru.new(size)
    local self = setmetatable({}, lru_mt)
    self.map = {}
    self.size = size
    self.count = 0
    return self
end

function lru.get(self, key)
    local node = self.map[key]
    if node == nil then
        return
    end

    tohead(self, node)

    return self.map[key].value
end

function lru.set(self, key, value)
    local node = self.map[key]
    if node then
        node.value = value
        tohead(self, node)
        return
    end

    local newnode = {
        key = key,
        value = value,
    }
    addnode(self, newnode)

    self.count = self.count + 1
    if self.count > self.size then
        delnode(self, self._tail)
        self.count = self.count - 1
    end
end

function lru.dump(self)
    local node = self._head
    while node do
        print(node.key, node.value)
        node = node._next
    end
end

return lru

output.txt

10      10
9       9
8       8
7       7
6       nil
5       nil
4       nil
3       nil
2       nil
1       nil
dump cache1:
k7      7
k8      8
k9      9
k10     10
dump cache2:
k10     10
k9      9
k8      8
k7      7
k6      6

test.lua

local lru = require "lru"

local cache1 = lru.new(4)
local cache2 = lru.new(5)

for i=1,10 do
    cache1:set("k"..i, i)
end
assert(cache1.count == 4)
for i=10,1,-1 do
    local v = cache1:get("k"..i)
    print(i, v)
end
print("dump cache1:")
cache1:dump()

for i=1,10 do
    cache2:set("k"..i, i)
end
assert(cache2.count == 5)
print("dump cache2:")
cache2:dump()