prosody
e0a0af42b09f
util/cache.lua

Find changesets by keywords by author, files, the commit message, revision number or hash, or revset expression.

Software / code / prosody

Annotate

util/cache.lua @ 7016:e0a0af42b09f

util.cache (and tests): Call on_evict after insertion of the new key, so inside on_evict we can be more certain about the current state of the cache (i.e. full, new item added, old item removed)
author Matthew Wild <mwild1@gmail.com>
date Tue, 22 Dec 2015 20:10:07 +0000
parent 6945:d779c55058c6
child 7289:42e7545d5ae3
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
1
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
2 local function _remove(list, m)
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
3 if m.prev then
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
4 m.prev.next = m.next;
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
5 end
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
6 if m.next then
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
7 m.next.prev = m.prev;
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
8 end
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
9 if list._tail == m then
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
10 list._tail = m.prev;
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
11 end
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
12 if list._head == m then
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
13 list._head = m.next;
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
14 end
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
15 list._count = list._count - 1;
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
16 end
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
17
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
18 local function _insert(list, m)
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
19 if list._head then
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
20 list._head.prev = m;
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
21 end
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
22 m.prev, m.next = nil, list._head;
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
23 list._head = m;
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
24 if not list._tail then
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
25 list._tail = m;
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
26 end
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
27 list._count = list._count + 1;
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
28 end
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
29
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
30 local cache_methods = {};
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
31 local cache_mt = { __index = cache_methods };
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
32
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
33 function cache_methods:set(k, v)
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
34 local m = self._data[k];
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
35 if m then
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
36 -- Key already exists
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
37 if v ~= nil then
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
38 -- Bump to head of list
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
39 _remove(self, m);
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
40 _insert(self, m);
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
41 m.value = v;
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
42 else
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
43 -- Remove from list
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
44 _remove(self, m);
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
45 self._data[k] = nil;
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
46 end
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
47 return true;
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
48 end
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
49 -- New key
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
50 if v == nil then
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
51 return true;
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
52 end
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
53 -- Check whether we need to remove oldest k/v
7016
e0a0af42b09f util.cache (and tests): Call on_evict after insertion of the new key, so inside on_evict we can be more certain about the current state of the cache (i.e. full, new item added, old item removed)
Matthew Wild <mwild1@gmail.com>
parents: 6945
diff changeset
54 local on_evict, evicted_key, evicted_value;
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
55 if self._count == self.size then
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
56 local tail = self._tail;
7016
e0a0af42b09f util.cache (and tests): Call on_evict after insertion of the new key, so inside on_evict we can be more certain about the current state of the cache (i.e. full, new item added, old item removed)
Matthew Wild <mwild1@gmail.com>
parents: 6945
diff changeset
57 on_evict, evicted_key, evicted_value = self._on_evict, tail.key, tail.value;
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
58 _remove(self, tail);
7016
e0a0af42b09f util.cache (and tests): Call on_evict after insertion of the new key, so inside on_evict we can be more certain about the current state of the cache (i.e. full, new item added, old item removed)
Matthew Wild <mwild1@gmail.com>
parents: 6945
diff changeset
59 self._data[evicted_key] = nil;
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
60 end
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
61
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
62 m = { key = k, value = v, prev = nil, next = nil };
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
63 self._data[k] = m;
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
64 _insert(self, m);
7016
e0a0af42b09f util.cache (and tests): Call on_evict after insertion of the new key, so inside on_evict we can be more certain about the current state of the cache (i.e. full, new item added, old item removed)
Matthew Wild <mwild1@gmail.com>
parents: 6945
diff changeset
65 if on_evict and evicted_key then
e0a0af42b09f util.cache (and tests): Call on_evict after insertion of the new key, so inside on_evict we can be more certain about the current state of the cache (i.e. full, new item added, old item removed)
Matthew Wild <mwild1@gmail.com>
parents: 6945
diff changeset
66 on_evict(evicted_key, evicted_value, self);
e0a0af42b09f util.cache (and tests): Call on_evict after insertion of the new key, so inside on_evict we can be more certain about the current state of the cache (i.e. full, new item added, old item removed)
Matthew Wild <mwild1@gmail.com>
parents: 6945
diff changeset
67 end
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
68 return true;
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
69 end
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
70
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
71 function cache_methods:get(k)
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
72 local m = self._data[k];
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
73 if m then
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
74 return m.value;
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
75 end
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
76 return nil;
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
77 end
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
78
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
79 function cache_methods:items()
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
80 local m = self._head;
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
81 return function ()
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
82 if not m then
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
83 return;
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
84 end
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
85 local k, v = m.key, m.value;
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
86 m = m.next;
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
87 return k, v;
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
88 end
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
89 end
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
90
6945
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
91 function cache_methods:count()
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
92 return self._count;
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
93 end
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
94
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
95 local function new(size, on_evict)
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
96 size = assert(tonumber(size), "cache size must be a number");
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
97 size = math.floor(size);
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
98 assert(size > 0, "cache size must be greater than zero");
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
99 local data = {};
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
100 return setmetatable({ _data = data, _count = 0, size = size, _head = nil, _tail = nil, _on_evict = on_evict }, cache_mt);
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
101 end
d779c55058c6 util.cache: Small update to prefix private fields with an underscore, add a :count() method (same as util.queue) and add an optional on_evict callback
Matthew Wild <mwild1@gmail.com>
parents: 6943
diff changeset
102
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
103 return {
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
104 new = new;
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
105 }