Mercurial > scansion / changeset

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/scansion/queue.lua	Tue Oct 27 19:35:33 2015 +0000
@@ -0,0 +1,72 @@
+-- Prosody IM
+-- Copyright (C) 2008-2015 Matthew Wild
+-- Copyright (C) 2008-2015 Waqas Hussain
+--
+-- This project is MIT/X11 licensed. Please see the
+-- COPYING file in the source package for more information.
+--
+
+-- Small ringbuffer library (i.e. an efficient FIFO queue with a size limit)
+-- (because unbounded dynamically-growing queues are a bad thing...)
+
+local have_utable, utable = pcall(require, "util.table"); -- For pre-allocation of table
+
+local function new(size, allow_wrapping)
+	-- Head is next insert, tail is next read
+	local head, tail = 1, 1;
+	local items = 0; -- Number of stored items
+	local t = have_utable and utable.create(size, 0) or {}; -- Table to hold items
+
+	return {
+		_items = t;
+		size = size;
+		count = function (self) return items; end;
+		push = function (self, item)
+			if items >= size then
+				if allow_wrapping then
+					tail = (tail%size)+1; -- Advance to next oldest item
+					items = items - 1;
+				else
+					return nil, "queue full";
+				end
+			end
+			t[head] = item;
+			items = items + 1;
+			head = (head%size)+1;
+			return true;
+		end;
+		pop = function (self)
+			if items == 0 then
+				return nil;
+			end
+			local item;
+			item, t[tail] = t[tail], 0;
+			tail = (tail%size)+1;
+			items = items - 1;
+			return item;
+		end;
+		peek = function (self)
+			if items == 0 then
+				return nil;
+			end
+			return t[tail];
+		end;
+		items = function (self)
+			return function (t, pos)
+				if pos >= t:count() then
+					return nil;
+				end
+				local read_pos = tail + pos;
+				if read_pos > t.size then
+					read_pos = (read_pos%size);
+				end
+				return pos+1, t._items[read_pos];
+			end, self, 0;
+		end;
+	};
+end
+
+return {
+	new = new;
+};
+