Software /
code /
prosody
Annotate
util/queue.lua @ 6820:40d50c239564
Merge 0.10->trunk
author | Matthew Wild <mwild1@gmail.com> |
---|---|
date | Thu, 03 Sep 2015 16:43:46 +0100 |
parent | 6731:d4a6c9ee4bc5 |
child | 6911:56c9bc4ba247 |
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 |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
19 |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
20 return { |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
21 size = size; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
22 count = function (self) return items; end; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
23 push = function (self, item) |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
24 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
|
25 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
|
26 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
|
27 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
|
28 else |
d4a6c9ee4bc5
util.queue: Allow optional wrap-around when pushing, overwriting oldest unread item
Matthew Wild <mwild1@gmail.com>
parents:
6678
diff
changeset
|
29 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
|
30 end |
6678
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
31 end |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
32 t[head] = item; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
33 items = items + 1; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
34 head = (head%size)+1; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
35 return true; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
36 end; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
37 pop = function (self) |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
38 if items == 0 then |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
39 return nil; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
40 end |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
41 local item; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
42 item, t[tail] = t[tail], 0; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
43 tail = (tail%size)+1; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
44 items = items - 1; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
45 return item; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
46 end; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
47 peek = function (self) |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
48 if items == 0 then |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
49 return nil; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
50 end |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
51 return t[tail]; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
52 end; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
53 }; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
54 end |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
55 |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
56 return { |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
57 new = new; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
58 }; |
343ca80ceb36
util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
59 |