author | Matthew Wild <mwild1@gmail.com> |
Sun, 18 Oct 2015 21:54:17 +0100 | |
changeset 6915 | cb5b14c95b7b |
parent 6914 | 56c9bc4ba247 |
child 9905 | c8b75239846c |
child 11107 | 73b8aaf55775 |
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 |
|
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 |
|
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; |
6914
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
54 |
items = function (self) |
6915
cb5b14c95b7b
util.queue: Add luacheck annotations
Matthew Wild <mwild1@gmail.com>
parents:
6914
diff
changeset
|
55 |
--luacheck: ignore 431/t |
6914
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
56 |
return function (t, pos) |
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
57 |
if pos >= t:count() then |
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
58 |
return nil; |
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
59 |
end |
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
60 |
local read_pos = tail + pos; |
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
61 |
if read_pos > t.size then |
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
62 |
read_pos = (read_pos%size); |
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
63 |
end |
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
64 |
return pos+1, t._items[read_pos]; |
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
65 |
end, self, 0; |
56c9bc4ba247
util.queue: Add :items() iterator
Matthew Wild <mwild1@gmail.com>
parents:
6734
diff
changeset
|
66 |
end; |
6681
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 |