aboutsummaryrefslogtreecommitdiffstats
path: root/util/cache.lua
blob: a5fd5e6dcc27cd238aca7876f3be0ad26521d32e (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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

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

local cache_methods = {};
local cache_mt = { __index = cache_methods };

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 true;
	end
	-- New key
	if v == nil then
		return true;
	end
	-- Check whether we need to remove oldest k/v
	if self._count == self.size then
		local tail = self._tail;
		local on_evict, evicted_key, evicted_value = self._on_evict, tail.key, tail.value;
		if on_evict ~= nil and (on_evict == false or on_evict(evicted_key, evicted_value) == false) then
			-- Cache is full, and we're not allowed to evict
			return false;
		end
		_remove(self, tail);
		self._data[evicted_key] = nil;
	end

	m = { key = k, value = v, prev = nil, next = nil };
	self._data[k] = m;
	_insert(self, m);
	return true;
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

function cache_methods:values()
	local m = self._head;
	return function ()
		if not m then
			return;
		end
		local v = m.value;
		m = m.next;
		return v;
	end
end

function cache_methods:count()
	return self._count;
end

function cache_methods:head()
	local head = self._head;
	if not head then return nil, nil; end
	return head.key, head.value;
end

function cache_methods:tail()
	local tail = self._tail;
	if not tail then return nil, nil; end
	return tail.key, tail.value;
end

function cache_methods:resize(new_size)
	new_size = assert(tonumber(new_size), "cache size must be a number");
	new_size = math.floor(new_size);
	assert(new_size > 0, "cache size must be greater than zero");
	local on_evict = self._on_evict;
	while self._count > new_size do
		local tail = self._tail;
		local evicted_key, evicted_value = tail.key, tail.value;
		if on_evict ~= nil and (on_evict == false or on_evict(evicted_key, evicted_value) == false) then
			-- Cache is full, and we're not allowed to evict
			return false;
		end
		_remove(self, tail);
		self._data[evicted_key] = nil;
	end
	self.size = new_size;
	return true;
end

function cache_methods:table()
	--luacheck: ignore 212/t
	if not self.proxy_table then
		self.proxy_table = setmetatable({}, {
			__index = function (t, k)
				return self:get(k);
			end;
			__newindex = function (t, k, v)
				if not self:set(k, v) then
					error("failed to insert key into cache - full");
				end
			end;
			__pairs = function (t)
				return self:items();
			end;
			__len = function (t)
				return self:count();
			end;
		});
	end
	return self.proxy_table;
end

function cache_methods:clear()
	self._data = {};
	self._count = 0;
	self._head = nil;
	self._tail = nil;
end

local function new(size, on_evict)
	size = assert(tonumber(size), "cache size must be a number");
	size = math.floor(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, _on_evict = on_evict }, cache_mt);
end

return {
	new = new;
}