prosody
343ca80ceb36
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 @ 6678:343ca80ceb36

util.queue: Small fast FIFO/ringbuffer/queue library
author Matthew Wild <mwild1@gmail.com>
date Wed, 13 May 2015 16:57:27 +0100
child 6731:d4a6c9ee4bc5
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
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
14 local function new(size)
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
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
25 return nil, "queue full";
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
26 end
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
27 t[head] = item;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
28 items = items + 1;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
29 head = (head%size)+1;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
30 return true;
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 pop = function (self)
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
33 if items == 0 then
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
34 return nil;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
35 end
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
36 local item;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
37 item, t[tail] = t[tail], 0;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
38 tail = (tail%size)+1;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
39 items = items - 1;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
40 return item;
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 peek = function (self)
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
43 if items == 0 then
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
44 return nil;
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
45 end
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
46 return t[tail];
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 };
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
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
51 return {
343ca80ceb36 util.queue: Small fast FIFO/ringbuffer/queue library
Matthew Wild <mwild1@gmail.com>
parents:
diff changeset
52 new = new;
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