prosody
7d4c292f178e
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 @ 11115:7d4c292f178e 0.11

util.indexedbheap: Fix heap datastructure corruption in :reschedule(smaller_value)
author Waqas Hussain <waqas20@gmail.com>
date Tue, 29 Sep 2020 21:27:16 -0500
parent 8398:3eff1b60269a
child 11198:c4c06fbb7d87
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
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
54 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
55 local tail = self._tail;
7290
70ab13e81cf5 util.cache: Change behaviour of on_evict (and tests). Now accepts false instead of a function (never evict), or on_evict can return false to prevent eviction.
Matthew Wild <mwild1@gmail.com>
parents: 7289
diff changeset
56 local on_evict, evicted_key, evicted_value = self._on_evict, tail.key, tail.value;
70ab13e81cf5 util.cache: Change behaviour of on_evict (and tests). Now accepts false instead of a function (never evict), or on_evict can return false to prevent eviction.
Matthew Wild <mwild1@gmail.com>
parents: 7289
diff changeset
57 if on_evict ~= nil and (on_evict == false or on_evict(evicted_key, evicted_value) == false) then
70ab13e81cf5 util.cache: Change behaviour of on_evict (and tests). Now accepts false instead of a function (never evict), or on_evict can return false to prevent eviction.
Matthew Wild <mwild1@gmail.com>
parents: 7289
diff changeset
58 -- Cache is full, and we're not allowed to evict
70ab13e81cf5 util.cache: Change behaviour of on_evict (and tests). Now accepts false instead of a function (never evict), or on_evict can return false to prevent eviction.
Matthew Wild <mwild1@gmail.com>
parents: 7289
diff changeset
59 return false;
70ab13e81cf5 util.cache: Change behaviour of on_evict (and tests). Now accepts false instead of a function (never evict), or on_evict can return false to prevent eviction.
Matthew Wild <mwild1@gmail.com>
parents: 7289
diff changeset
60 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
61 _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
62 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
63 end
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
64
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
65 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
66 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
67 _insert(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
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
7354
8ca7f1c2c660 util.cache: Add method for iterating over values
Kim Alvefur <zash@zash.se>
parents: 7290
diff changeset
91 function cache_methods:values()
8ca7f1c2c660 util.cache: Add method for iterating over values
Kim Alvefur <zash@zash.se>
parents: 7290
diff changeset
92 local m = self._head;
8ca7f1c2c660 util.cache: Add method for iterating over values
Kim Alvefur <zash@zash.se>
parents: 7290
diff changeset
93 return function ()
8ca7f1c2c660 util.cache: Add method for iterating over values
Kim Alvefur <zash@zash.se>
parents: 7290
diff changeset
94 if not m then
8ca7f1c2c660 util.cache: Add method for iterating over values
Kim Alvefur <zash@zash.se>
parents: 7290
diff changeset
95 return;
8ca7f1c2c660 util.cache: Add method for iterating over values
Kim Alvefur <zash@zash.se>
parents: 7290
diff changeset
96 end
8ca7f1c2c660 util.cache: Add method for iterating over values
Kim Alvefur <zash@zash.se>
parents: 7290
diff changeset
97 local v = m.value;
8ca7f1c2c660 util.cache: Add method for iterating over values
Kim Alvefur <zash@zash.se>
parents: 7290
diff changeset
98 m = m.next;
8ca7f1c2c660 util.cache: Add method for iterating over values
Kim Alvefur <zash@zash.se>
parents: 7290
diff changeset
99 return v;
8ca7f1c2c660 util.cache: Add method for iterating over values
Kim Alvefur <zash@zash.se>
parents: 7290
diff changeset
100 end
8ca7f1c2c660 util.cache: Add method for iterating over values
Kim Alvefur <zash@zash.se>
parents: 7290
diff changeset
101 end
8ca7f1c2c660 util.cache: Add method for iterating over values
Kim Alvefur <zash@zash.se>
parents: 7290
diff changeset
102
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
103 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
104 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
105 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
106
7289
42e7545d5ae3 util.cache: Add head() and tail() methods (and tests)
Matthew Wild <mwild1@gmail.com>
parents: 7016
diff changeset
107 function cache_methods:head()
42e7545d5ae3 util.cache: Add head() and tail() methods (and tests)
Matthew Wild <mwild1@gmail.com>
parents: 7016
diff changeset
108 local head = self._head;
42e7545d5ae3 util.cache: Add head() and tail() methods (and tests)
Matthew Wild <mwild1@gmail.com>
parents: 7016
diff changeset
109 if not head then return nil, nil; end
42e7545d5ae3 util.cache: Add head() and tail() methods (and tests)
Matthew Wild <mwild1@gmail.com>
parents: 7016
diff changeset
110 return head.key, head.value;
42e7545d5ae3 util.cache: Add head() and tail() methods (and tests)
Matthew Wild <mwild1@gmail.com>
parents: 7016
diff changeset
111 end
42e7545d5ae3 util.cache: Add head() and tail() methods (and tests)
Matthew Wild <mwild1@gmail.com>
parents: 7016
diff changeset
112
42e7545d5ae3 util.cache: Add head() and tail() methods (and tests)
Matthew Wild <mwild1@gmail.com>
parents: 7016
diff changeset
113 function cache_methods:tail()
42e7545d5ae3 util.cache: Add head() and tail() methods (and tests)
Matthew Wild <mwild1@gmail.com>
parents: 7016
diff changeset
114 local tail = self._tail;
42e7545d5ae3 util.cache: Add head() and tail() methods (and tests)
Matthew Wild <mwild1@gmail.com>
parents: 7016
diff changeset
115 if not tail then return nil, nil; end
42e7545d5ae3 util.cache: Add head() and tail() methods (and tests)
Matthew Wild <mwild1@gmail.com>
parents: 7016
diff changeset
116 return tail.key, tail.value;
42e7545d5ae3 util.cache: Add head() and tail() methods (and tests)
Matthew Wild <mwild1@gmail.com>
parents: 7016
diff changeset
117 end
42e7545d5ae3 util.cache: Add head() and tail() methods (and tests)
Matthew Wild <mwild1@gmail.com>
parents: 7016
diff changeset
118
8397
99d85731e3ee util.cache: Add a method to resize the cache
Kim Alvefur <zash@zash.se>
parents: 8396
diff changeset
119 function cache_methods:resize(new_size)
99d85731e3ee util.cache: Add a method to resize the cache
Kim Alvefur <zash@zash.se>
parents: 8396
diff changeset
120 new_size = assert(tonumber(new_size), "cache size must be a number");
99d85731e3ee util.cache: Add a method to resize the cache
Kim Alvefur <zash@zash.se>
parents: 8396
diff changeset
121 new_size = math.floor(new_size);
99d85731e3ee util.cache: Add a method to resize the cache
Kim Alvefur <zash@zash.se>
parents: 8396
diff changeset
122 assert(new_size > 0, "cache size must be greater than zero");
8398
3eff1b60269a util.cache: Call on-eviction callback when shrinking
Kim Alvefur <zash@zash.se>
parents: 8397
diff changeset
123 local on_evict = self._on_evict;
8397
99d85731e3ee util.cache: Add a method to resize the cache
Kim Alvefur <zash@zash.se>
parents: 8396
diff changeset
124 while self._count > new_size do
99d85731e3ee util.cache: Add a method to resize the cache
Kim Alvefur <zash@zash.se>
parents: 8396
diff changeset
125 local tail = self._tail;
8398
3eff1b60269a util.cache: Call on-eviction callback when shrinking
Kim Alvefur <zash@zash.se>
parents: 8397
diff changeset
126 local evicted_key, evicted_value = tail.key, tail.value;
3eff1b60269a util.cache: Call on-eviction callback when shrinking
Kim Alvefur <zash@zash.se>
parents: 8397
diff changeset
127 if on_evict ~= nil and (on_evict == false or on_evict(evicted_key, evicted_value) == false) then
3eff1b60269a util.cache: Call on-eviction callback when shrinking
Kim Alvefur <zash@zash.se>
parents: 8397
diff changeset
128 -- Cache is full, and we're not allowed to evict
3eff1b60269a util.cache: Call on-eviction callback when shrinking
Kim Alvefur <zash@zash.se>
parents: 8397
diff changeset
129 return false;
3eff1b60269a util.cache: Call on-eviction callback when shrinking
Kim Alvefur <zash@zash.se>
parents: 8397
diff changeset
130 end
8397
99d85731e3ee util.cache: Add a method to resize the cache
Kim Alvefur <zash@zash.se>
parents: 8396
diff changeset
131 _remove(self, tail);
99d85731e3ee util.cache: Add a method to resize the cache
Kim Alvefur <zash@zash.se>
parents: 8396
diff changeset
132 self._data[evicted_key] = nil;
99d85731e3ee util.cache: Add a method to resize the cache
Kim Alvefur <zash@zash.se>
parents: 8396
diff changeset
133 end
99d85731e3ee util.cache: Add a method to resize the cache
Kim Alvefur <zash@zash.se>
parents: 8396
diff changeset
134 self.size = new_size;
99d85731e3ee util.cache: Add a method to resize the cache
Kim Alvefur <zash@zash.se>
parents: 8396
diff changeset
135 return true;
99d85731e3ee util.cache: Add a method to resize the cache
Kim Alvefur <zash@zash.se>
parents: 8396
diff changeset
136 end
99d85731e3ee util.cache: Add a method to resize the cache
Kim Alvefur <zash@zash.se>
parents: 8396
diff changeset
137
7435
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
138 function cache_methods:table()
7702
9385c367e920 util.cache: Ignore unused argument [luacheck]
Kim Alvefur <zash@zash.se>
parents: 7435
diff changeset
139 --luacheck: ignore 212/t
7435
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
140 if not self.proxy_table then
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
141 self.proxy_table = setmetatable({}, {
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
142 __index = function (t, k)
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
143 return self:get(k);
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
144 end;
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
145 __newindex = function (t, k, v)
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
146 if not self:set(k, v) then
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
147 error("failed to insert key into cache - full");
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
148 end
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
149 end;
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
150 __pairs = function (t)
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
151 return self:items();
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
152 end;
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
153 __len = function (t)
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
154 return self:count();
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
155 end;
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
156 });
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
157 end
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
158 return self.proxy_table;
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
159 end
8603b16e85c7 util.cache: Add support for creating a proxy table to a cache, that looks and acts (mostly) like a normal table. No tests yet.
Matthew Wild <mwild1@gmail.com>
parents: 7354
diff changeset
160
8396
fbe1f99fb245 util.cache: Add method for removing all data (does not call eviction callback)
Kim Alvefur <zash@zash.se>
parents: 7702
diff changeset
161 function cache_methods:clear()
fbe1f99fb245 util.cache: Add method for removing all data (does not call eviction callback)
Kim Alvefur <zash@zash.se>
parents: 7702
diff changeset
162 self._data = {};
fbe1f99fb245 util.cache: Add method for removing all data (does not call eviction callback)
Kim Alvefur <zash@zash.se>
parents: 7702
diff changeset
163 self._count = 0;
fbe1f99fb245 util.cache: Add method for removing all data (does not call eviction callback)
Kim Alvefur <zash@zash.se>
parents: 7702
diff changeset
164 self._head = nil;
fbe1f99fb245 util.cache: Add method for removing all data (does not call eviction callback)
Kim Alvefur <zash@zash.se>
parents: 7702
diff changeset
165 self._tail = nil;
fbe1f99fb245 util.cache: Add method for removing all data (does not call eviction callback)
Kim Alvefur <zash@zash.se>
parents: 7702
diff changeset
166 end
fbe1f99fb245 util.cache: Add method for removing all data (does not call eviction callback)
Kim Alvefur <zash@zash.se>
parents: 7702
diff changeset
167
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
168 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
169 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
170 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
171 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
172 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
173 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
174 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
175
6933
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
176 return {
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
177 new = new;
d636815d81c3 util.cache: Ordered key->value data structure, with size limit (same as pubsub)
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
178 }