prosody
9ea3094b1fca
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 @ 7364:9ea3094b1fca

MUC: Save yourself! (fixes reference to current room)
author Kim Alvefur <zash@zash.se>
date Mon, 18 Apr 2016 19:08:31 +0200
parent 6912:cb5b14c95b7b
child 9901:c8b75239846c
child 11103:73b8aaf55775
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
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
12 local have_utable, utable = pcall(require, "util.table"); -- For pre-allocation of table
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;
6911
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
54 items = function (self)
6912
cb5b14c95b7b util.queue: Add luacheck annotations
Matthew Wild <mwild1@gmail.com>
parents: 6911
diff changeset
55 --luacheck: ignore 431/t
6911
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
56 return function (t, pos)
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
57 if pos >= t:count() then
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
58 return nil;
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
59 end
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
60 local read_pos = tail + pos;
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
61 if read_pos > t.size then
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
62 read_pos = (read_pos%size);
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
63 end
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
64 return pos+1, t._items[read_pos];
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
65 end, self, 0;
56c9bc4ba247 util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents: 6731
diff changeset
66 end;
6678
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
67 };
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
68 end
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
69
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
70 return {
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
71 new = new;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
72 };
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
73