prosody
8e402a2ae1b8
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 @ 12701:8e402a2ae1b8

util.jwt: Overhaul of tests to use declarative approach Now we can consistently apply the same tests to every algorithm, instead of duplicating code.
author Matthew Wild <mwild1@gmail.com>
date Sat, 02 Jul 2022 14:22:20 +0100
parent 12058:4860da718e87
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
12057
e880f5a13080 util.smqueue: Add missing method to Teal record spec
Kim Alvefur <zash@zash.se>
parents: 12055
diff changeset
17 resumable : function (smqueue<T>) : boolean
e880f5a13080 util.smqueue: Add missing method to Teal record spec
Kim Alvefur <zash@zash.se>
parents: 12055
diff changeset
18 resume : function (smqueue<T>) : queue.queue.iterator, any, integer
12055
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
19 type consume_iter = function (smqueue<T>) : T
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
20 consume : function (smqueue<T>) : consume_iter
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
21
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
22 table : function (smqueue<T>) : { T }
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
23 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
24 new : function <T>(integer) : smqueue<T>
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
25 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
26
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
27 local type smqueue = lib.smqueue;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
28
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
29 function smqueue:push(v)
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
30 self._head = self._head + 1;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
31 -- Wraps instead of errors
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
32 assert(self._queue:push(v));
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
33 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
34
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
35 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
36 if h < self._tail then
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
37 return nil, "tail";
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
38 elseif h > self._head then
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
39 return nil, "head";
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
40 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
41 -- TODO optimize? cache table fields
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
42 local acked = {};
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
43 self._tail = h;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
44 local expect = self._head - self._tail;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
45 while expect < self._queue:count() do
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
46 local v = self._queue:pop();
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
47 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
48 table.insert(acked, v);
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
49 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
50 return acked;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
51 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
52
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
53 function smqueue:count_unacked() : integer
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
54 return self._head - self._tail;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
55 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
56
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
57 function smqueue:count_acked() : integer
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
58 return self._tail;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
59 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
60
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
61 function smqueue:resumable() : boolean
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
62 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
63 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
64
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
65 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
66 return self._queue:items();
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
67 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
68
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
69 function smqueue:consume() : queue.queue.consume_iter
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
70 return self._queue:consume()
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
71 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
72
12058
4860da718e87 util.smqueue: Simplify compat table, fix dependent modules (thanks Martin)
Kim Alvefur <zash@zash.se>
parents: 12057
diff changeset
73 -- Compatibility layer, plain ol' table
12055
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
74 function smqueue:table() : { any }
12058
4860da718e87 util.smqueue: Simplify compat table, fix dependent modules (thanks Martin)
Kim Alvefur <zash@zash.se>
parents: 12057
diff changeset
75 local t : { any } = {};
4860da718e87 util.smqueue: Simplify compat table, fix dependent modules (thanks Martin)
Kim Alvefur <zash@zash.se>
parents: 12057
diff changeset
76 for i, v in self:resume() do
4860da718e87 util.smqueue: Simplify compat table, fix dependent modules (thanks Martin)
Kim Alvefur <zash@zash.se>
parents: 12057
diff changeset
77 t[i] = v;
4860da718e87 util.smqueue: Simplify compat table, fix dependent modules (thanks Martin)
Kim Alvefur <zash@zash.se>
parents: 12057
diff changeset
78 end
4860da718e87 util.smqueue: Simplify compat table, fix dependent modules (thanks Martin)
Kim Alvefur <zash@zash.se>
parents: 12057
diff changeset
79 return t;
12055
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 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
83 return { head = q._head, tail = q._tail }
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 local queue_mt = {
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
87 --
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
88 __name = "smqueue";
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
89 __index = smqueue;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
90 __len = smqueue.count_unacked;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
91 __freeze = freeze;
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
92 }
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 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
95 assert(size>0);
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
96 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
97 end
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
98
daced16154fa util.smqueue: Abstract queue with acknowledgements and overflow
Kim Alvefur <zash@zash.se>
parents:
diff changeset
99 return lib;