prosody
187112928174
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 @ 6879:187112928174

util-src/Makefile: Move Lua include path into CFLAGS variable
author Kim Alvefur <zash@zash.se>
date Sun, 27 Sep 2015 00:04:14 +0200
parent 6731:d4a6c9ee4bc5
child 6911:56c9bc4ba247
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
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