aboutsummaryrefslogtreecommitdiffstats
path: root/util/cache.lua
blob: 9453697ce8a00459afe152d53bdc2af3e6b2e5ca (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
local cache_methods = {};
local cache_mt = { __index = cache_methods };

local function new(size)
	assert(size > 0, "cache size must be greater than zero");
	local data = {};
	return setmetatable({ data = data, count = 0, size = size, head = nil, tail = nil }, cache_mt);
end

local function _remove(list, m)
	if m.prev then
		m.prev.next = m.next;
	end
	if m.next then
		m.next.prev = m.prev;
	end
	if list.tail == m then
		list.tail = m.prev;
	end
	if list.head == m then
		list.head = m.next;
	end
	list.count = list.count - 1;
end

local function _insert(list, m)
	if list.head then
		list.head.prev = m;
	end
	m.prev, m.next = nil, list.head;
	list.head = m;
	if not list.tail then
		list.tail = m;
	end
	list.count = list.count + 1;
end

function cache_methods:set(k, v)
	local m = self.data[k];
	if m then
		-- Key already exists
		if v ~= nil then
			-- Bump to head of list
			_remove(self, m);
			_insert(self, m);
			m.value = v;
		else
			-- Remove from list
			_remove(self, m);
			self.data[k] = nil;
		end
		return;
	end
	-- New key
	if v == nil then
		return;
	end
	-- Check whether we need to remove oldest k/v
	if self.count == self.size then
		self.data[self.tail.key] = nil;
		_remove(self, self.tail);
	end

	m = { key = k, value = v, prev = nil, next = nil };
	self.data[k] = m;
	_insert(self, m);
end

function cache_methods:get(k)
	local m = self.data[k];
	if m then
		return m.value;
	end
	return nil;
end

function cache_methods:items()
	local m = self.head;
	return function ()
		if not m then
			return;
		end
		local k, v = m.key, m.value;
		m = m.next;
		return k, v;
	end
end

return {
	new = new;
}