Mercurial > prosody-hg

annotate util/queue.lua @ 14079:0ea2848d7771

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
prosodyctl: Only import "socket" in the root of the module
author Link Mauve <linkmauve@linkmauve.fr>
date Fri, 30 Jan 2026 14:44:04 +0100
parents f50a9746fec0
children
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;
13956
f50a9746fec0 util.queue: Convenience functions for empty/full
Matthew Wild <mwild1@gmail.com>
parents: 12975
diff changeset
24 empty = function () return items == 0; end;
f50a9746fec0 util.queue: Convenience functions for empty/full
Matthew Wild <mwild1@gmail.com>
parents: 12975
diff changeset
25 full = function () return items == size; end;
6678
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
26 push = function (self, item)
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
27 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
28 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
29 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
30 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
31 else
d4a6c9ee4bc5 util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents: 6678
diff changeset
32 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
33 end
6678
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
34 end
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
35 t[head] = item;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
36 items = items + 1;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
37 head = (head%size)+1;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
38 return true;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
39 end;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
40 pop = function (self)
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
41 if items == 0 then
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
42 return nil;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
43 end
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
44 local item;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
45 item, t[tail] = t[tail], 0;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
46 tail = (tail%size)+1;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
47 items = items - 1;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
48 return item;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
49 end;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
50 peek = function (self)
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
51 if items == 0 then
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
52 return nil;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
53 end
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
54 return t[tail];
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
55 end;
11103
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
56 replace = function (self, data)
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
57 if items == 0 then
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
58 return self:push(data);
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
59 end
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
60 t[tail] = data;
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
61 return true;
73b8aaf55775 util.dbuffer: dynamic string buffer
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
62 end;
6911
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
63 items = function (self)
9926
1bfd28e774db util.queue: Update :items() to consistently use private data directly
Matthew Wild <mwild1@gmail.com>
parents: 9925
diff changeset
64 return function (_, pos)
1bfd28e774db util.queue: Update :items() to consistently use private data directly
Matthew Wild <mwild1@gmail.com>
parents: 9925
diff changeset
65 if pos >= items then
6911
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
66 return nil;
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
67 end
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
68 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
69 if read_pos > self.size then
6911
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
70 read_pos = (read_pos%size);
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
71 end
9926
1bfd28e774db util.queue: Update :items() to consistently use private data directly
Matthew Wild <mwild1@gmail.com>
parents: 9925
diff changeset
72 return pos+1, t[read_pos];
6911
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
73 end, self, 0;
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
74 end;
9901
c8b75239846c util.queue: Add 'consume()' convenience iterator
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
75 consume = function (self)
c8b75239846c util.queue: Add 'consume()' convenience iterator
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
76 return self.pop, self;
c8b75239846c util.queue: Add 'consume()' convenience iterator
Matthew Wild <mwild1@gmail.com>
parents: 6912
diff changeset
77 end;
6678
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 end
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
80
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
81 return {
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
82 new = new;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
83 };
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
84