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
|
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
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;
}
|
