prosody
eca44e058eed
util/queue.lua

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

Software / code / prosody

Annotate

util/queue.lua @ 13196:eca44e058eed

util.human.io: Use tail call in test to get correct line numbers This is probably not guaranteed to work and might vary with Lua version, but it's good enough for me to get accurate line numbers out of Busted that don't all point to the test() function.
author Kim Alvefur <zash@zash.se>
date Sun, 16 Jul 2023 18:42:58 +0200
parent 12975:d10957394a3c
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6678
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
12975
d10957394a3c util: Prefix module imports with prosody namespace
Kim Alvefur <zash@zash.se>
parents: 11114
diff changeset
12 local have_utable, utable = pcall(require, "prosody.util.table"); -- For pre-allocation of table
6678
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
13
6731
d4a6c9ee4bc5 util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents: 6678
diff changeset
14 local function new(size, allow_wrapping)
6678
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
6912
cb5b14c95b7b util.queue: Add luacheck annotations
Matthew Wild <mwild1@gmail.com>
parents: 6911
diff changeset
19 --luacheck: ignore 212/self
6678
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
20 return {
6911
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
21 _items = t;
6678
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
6731
d4a6c9ee4bc5 util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents: 6678
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: 6678
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: 6678
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: 6678
diff changeset
29 else
d4a6c9ee4bc5 util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents: 6678
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: 6678
diff changeset
31 end
6678
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;
11103
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
54 replace = function (self, data)
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
55 if items == 0 then
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
56 return self:push(data);
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
57 end
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
58 t[tail] = data;
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
59 return true;
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
60 end;
6911
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
61 items = function (self)
9926
1bfd28e774db util.queue: Update :items() to consistently use private data directly
Matthew Wild <mwild1@gmail.com>
parents: 9925
diff changeset
62 return function (_, pos)
1bfd28e774db util.queue: Update :items() to consistently use private data directly
Matthew Wild <mwild1@gmail.com>
parents: 9925
diff changeset
63 if pos >= items then
6911
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
64 return nil;
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
65 end
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
66 local read_pos = tail + pos;
9926
1bfd28e774db util.queue: Update :items() to consistently use private data directly
Matthew Wild <mwild1@gmail.com>
parents: 9925
diff changeset
67 if read_pos > self.size then
6911
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
68 read_pos = (read_pos%size);
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
69 end
9926
1bfd28e774db util.queue: Update :items() to consistently use private data directly
Matthew Wild <mwild1@gmail.com>
parents: 9925
diff changeset
70 return pos+1, t[read_pos];
6911
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
71 end, self, 0;
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
72 end;
9901
c8b75239846c util.queue: Add 'consume()' convenience iterator
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
73 consume = function (self)
c8b75239846c util.queue: Add 'consume()' convenience iterator
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
74 return self.pop, self;
c8b75239846c util.queue: Add 'consume()' convenience iterator
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
75 end;
6678
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