Mercurial > prosody-hg

comparison util/cache.lua @ 6933:d636815d81c3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
util.cache: Ordered key->value data structure, with size limit (same as pubsub)
author Matthew Wild <mwild1@gmail.com>
date Tue, 24 Nov 2015 10:44:41 +0000
parents
children 0a31ec3193f0
comparison
equal deleted inserted replaced
6927:566e1cfcb814 6933:d636815d81c3
1 local cache_methods = {};
2 local cache_mt = { __index = cache_methods };
3
4 local function new(size)
5 assert(size > 0, "cache size must be greater than zero");
6 local data = {};
7 return setmetatable({ data = data, count = 0, size = size, head = nil, tail = nil }, cache_mt);
8 end
9
10 local function _remove(list, m)
11 if m.prev then
12 m.prev.next = m.next;
13 end
14 if m.next then
15 m.next.prev = m.prev;
16 end
17 if list.tail == m then
18 list.tail = m.prev;
19 end
20 if list.head == m then
21 list.head = m.next;
22 end
23 list.count = list.count - 1;
24 end
25
26 local function _insert(list, m)
27 if list.head then
28 list.head.prev = m;
29 end
30 m.prev, m.next = nil, list.head;
31 list.head = m;
32 if not list.tail then
33 list.tail = m;
34 end
35 list.count = list.count + 1;
36 end
37
38 function cache_methods:set(k, v)
39 local m = self.data[k];
40 if m then
41 -- Key already exists
42 if v ~= nil then
43 -- Bump to head of list
44 _remove(self, m);
45 _insert(self, m);
46 m.value = v;
47 else
48 -- Remove from list
49 _remove(self, m);
50 self.data[k] = nil;
51 end
52 return;
53 end
54 -- New key
55 if v == nil then
56 return;
57 end
58 -- Check whether we need to remove oldest k/v
59 if self.count == self.size then
60 self.data[self.tail.key] = nil;
61 _remove(self, self.tail);
62 end
63
64 m = { key = k, value = v, prev = nil, next = nil };
65 self.data[k] = m;
66 _insert(self, m);
67 end
68
69 function cache_methods:get(k)
70 local m = self.data[k];
71 if m then
72 return m.value;
73 end
74 return nil;
75 end
76
77 function cache_methods:items()
78 local m = self.head;
79 return function ()
80 if not m then
81 return;
82 end
83 local k, v = m.key, m.value;
84 m = m.next;
85 return k, v;
86 end
87 end
88
89 return {
90 new = new;
91 }