author | Kim Alvefur <zash@zash.se> |
Fri, 01 Mar 2024 19:22:49 +0100 | |
changeset 13455 | 4a9a69659727 |
parent 12979 | d10957394a3c |
permissions | -rw-r--r-- |
6681
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
1 |
-- Prosody IM |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
2 |
-- Copyright (C) 2008-2015 Matthew Wild |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
3 |
-- Copyright (C) 2008-2015 Waqas Hussain |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
4 |
-- |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
5 |
-- This project is MIT/X11 licensed. Please see the |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
6 |
-- COPYING file in the source package for more information. |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
7 |
-- |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
8 |
|
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
9 |
-- Small ringbuffer library (i.e. an efficient FIFO queue with a size limit) |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
10 |
-- (because unbounded dynamically-growing queues are a bad thing...) |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
11 |
|
12979
d10957394a3c
util: Prefix module imports with prosody namespace
Kim Alvefur <zash@zash.se>
parents:
11118
diff
changeset
|
12 |
local have_utable, utable = pcall(require, "prosody.util.table"); -- For pre-allocation of table |
6681
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
13 |
|
6734
d4a6c9ee4bc5
util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents:
6681
diff
changeset
|
14 |
local function new(size, allow_wrapping) |
6681
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
15 |
-- Head is next insert, tail is next read |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
16 |
local head, tail = 1, 1; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
17 |
local items = 0; -- Number of stored items |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
18 |
local t = have_utable and utable.create(size, 0) or {}; -- Table to hold items |
6915
cb5b14c95b7b
util.queue: Add luacheck annotations
Matthew Wild <mwild1@gmail.com>
parents:
6914
diff
changeset
|
19 |
--luacheck: ignore 212/self |
6681
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
20 |
return { |
6914
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
21 |
_items = t; |
6681
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
22 |
size = size; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
23 |
count = function (self) return items; end; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
24 |
push = function (self, item) |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
25 |
if items >= size then |
6734
d4a6c9ee4bc5
util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents:
6681
diff
changeset
|
26 |
if allow_wrapping then |
d4a6c9ee4bc5
util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents:
6681
diff
changeset
|
27 |
tail = (tail%size)+1; -- Advance to next oldest item |
d4a6c9ee4bc5
util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents:
6681
diff
changeset
|
28 |
items = items - 1; |
d4a6c9ee4bc5
util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents:
6681
diff
changeset
|
29 |
else |
d4a6c9ee4bc5
util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents:
6681
diff
changeset
|
30 |
return nil, "queue full"; |
d4a6c9ee4bc5
util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents:
6681
diff
changeset
|
31 |
end |
6681
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
32 |
end |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
33 |
t[head] = item; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
34 |
items = items + 1; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
35 |
head = (head%size)+1; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
36 |
return true; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
37 |
end; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
38 |
pop = function (self) |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
39 |
if items == 0 then |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
40 |
return nil; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
41 |
end |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
42 |
local item; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
43 |
item, t[tail] = t[tail], 0; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
44 |
tail = (tail%size)+1; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
45 |
items = items - 1; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
46 |
return item; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
47 |
end; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
48 |
peek = function (self) |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
49 |
if items == 0 then |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
50 |
return nil; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
51 |
end |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
52 |
return t[tail]; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
53 |
end; |
11107
73b8aaf55775
util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents:
6915
diff
changeset
|
54 |
replace = function (self, data) |
73b8aaf55775
util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents:
6915
diff
changeset
|
55 |
if items == 0 then |
73b8aaf55775
util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents:
6915
diff
changeset
|
56 |
return self:push(data); |
73b8aaf55775
util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents:
6915
diff
changeset
|
57 |
end |
73b8aaf55775
util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents:
6915
diff
changeset
|
58 |
t[tail] = data; |
73b8aaf55775
util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents:
6915
diff
changeset
|
59 |
return true; |
73b8aaf55775
util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents:
6915
diff
changeset
|
60 |
end; |
6914
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
61 |
items = function (self) |
9930
1bfd28e774db
util.queue: Update :items() to consistently use private data directly
Matthew Wild <mwild1@gmail.com>
parents:
9929
diff
changeset
|
62 |
return function (_, pos) |
1bfd28e774db
util.queue: Update :items() to consistently use private data directly
Matthew Wild <mwild1@gmail.com>
parents:
9929
diff
changeset
|
63 |
if pos >= items then |
6914
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
64 |
return nil; |
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
65 |
end |
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
66 |
local read_pos = tail + pos; |
9930
1bfd28e774db
util.queue: Update :items() to consistently use private data directly
Matthew Wild <mwild1@gmail.com>
parents:
9929
diff
changeset
|
67 |
if read_pos > self.size then |
6914
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
68 |
read_pos = (read_pos%size); |
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
69 |
end |
9930
1bfd28e774db
util.queue: Update :items() to consistently use private data directly
Matthew Wild <mwild1@gmail.com>
parents:
9929
diff
changeset
|
70 |
return pos+1, t[read_pos]; |
6914
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
71 |
end, self, 0; |
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
72 |
end; |
9905
c8b75239846c
util.queue: Add 'consume()' convenience iterator
Matthew Wild <mwild1@gmail.com>
parents:
6915
diff
changeset
|
73 |
consume = function (self) |
c8b75239846c
util.queue: Add 'consume()' convenience iterator
Matthew Wild <mwild1@gmail.com>
parents:
6915
diff
changeset
|
74 |
return self.pop, self; |
c8b75239846c
util.queue: Add 'consume()' convenience iterator
Matthew Wild <mwild1@gmail.com>
parents:
6915
diff
changeset
|
75 |
end; |
6681
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
76 |
}; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
77 |
end |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
78 |
|
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
79 |
return { |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
80 |
new = new; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
81 |
}; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
82 |