prosody
daced16154fa
teal-src/util/smqueue.tl

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

Software / code / prosody

Annotate

teal-src/util/smqueue.tl @ 12055:daced16154fa

util.smqueue: Abstract queue with acknowledgements and overflow Meant to be used in mod_smacks for XEP-0198 Meant to have a larger virtual size than actual number of items stored, on the theory that in most cases, the excess will be acked before needed for a resumption event.
author Kim Alvefur <zash@zash.se>
date Tue, 14 Dec 2021 19:58:53 +0100
child 12057:e880f5a13080
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
12055
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
1 local queue = require "util.queue";
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
2
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
3 local record lib
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
4 -- T would typically be util.stanza
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
5 record smqueue<T>
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
6 _queue : queue.queue<T>
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
7 _head : integer
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
8 _tail : integer
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
9
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
10 enum ack_errors
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
11 "tail"
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
12 "head"
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
13 "pop"
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
14 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
15 push : function (smqueue, T)
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
16 ack : function (smqueue, integer) : { T }, ack_errors
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
17 resumable : function (smqueue) : boolean
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
18 type consume_iter = function (smqueue<T>) : T
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
19 consume : function (smqueue<T>) : consume_iter
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
20
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
21 table : function (smqueue<T>) : { T }
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
22 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
23 new : function <T>(integer) : smqueue<T>
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
24 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
25
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
26 local type smqueue = lib.smqueue;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
27
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
28 function smqueue:push(v)
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
29 self._head = self._head + 1;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
30 -- Wraps instead of errors
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
31 assert(self._queue:push(v));
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
32 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
33
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
34 function smqueue:ack(h : integer) : { any }, smqueue.ack_errors
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
35 if h < self._tail then
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
36 return nil, "tail";
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
37 elseif h > self._head then
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
38 return nil, "head";
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
39 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
40 -- TODO optimize? cache table fields
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
41 local acked = {};
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
42 self._tail = h;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
43 local expect = self._head - self._tail;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
44 while expect < self._queue:count() do
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
45 local v = self._queue:pop();
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
46 if not v then return nil, "pop"; end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
47 table.insert(acked, v);
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
48 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
49 return acked;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
50 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
51
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
52 function smqueue:count_unacked() : integer
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
53 return self._head - self._tail;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
54 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
55
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
56 function smqueue:count_acked() : integer
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
57 return self._tail;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
58 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
59
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
60 function smqueue:resumable() : boolean
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
61 return self._queue:count() >= (self._head - self._tail);
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
62 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
63
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
64 function smqueue:resume() : queue.queue.iterator, any, integer
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
65 return self._queue:items();
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
66 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
67
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
68 function smqueue:consume() : queue.queue.consume_iter
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
69 return self._queue:consume()
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
70 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
71
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
72 -- Compatibility wrapper, meant to look like a plain ol' array
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
73 local record compat_mt
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
74 _queue : smqueue<any>
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
75 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
76
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
77 function compat_mt:__index(i : integer) : any
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
78 if i < self._queue._tail then return nil end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
79 return self._queue._queue._items[(i + self._queue._tail) % self._queue._queue.size];
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
80 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
81
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
82 function compat_mt:__len() : integer
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
83 return self._queue:count_unacked()
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
84 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
85
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
86 function smqueue:table() : { any }
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
87 return setmetatable({ _queue = self }, compat_mt);
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
88 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
89
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
90 local function freeze(q : smqueue<any>) : { string:integer }
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
91 return { head = q._head, tail = q._tail }
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
92 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
93
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
94 local queue_mt = {
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
95 --
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
96 __name = "smqueue";
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
97 __index = smqueue;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
98 __len = smqueue.count_unacked;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
99 __freeze = freeze;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
100 }
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
101
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
102 function lib.new<T>(size : integer) : queue.queue<T>
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
103 assert(size>0);
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
104 return setmetatable({ _head = 0; _tail = 0; _queue = queue.new(size, true) }, queue_mt);
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
105 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
106
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
107 return lib;