util/queue.lua

   1 -- Prosody IM
   2 -- Copyright (C) 2008-2015 Matthew Wild
   3 -- Copyright (C) 2008-2015 Waqas Hussain
   4 --
   5 -- This project is MIT/X11 licensed. Please see the
   6 -- COPYING file in the source package for more information.
   7 --
   8
   9 -- Small ringbuffer library (i.e. an efficient FIFO queue with a size limit)
  10 -- (because unbounded dynamically-growing queues are a bad thing...)
  11
  12 local have_utable, utable = pcall(require, "util.table"); -- For pre-allocation of table
  13
  14 local function new(size, allow_wrapping)
  15         -- Head is next insert, tail is next read
  16         local head, tail = 1, 1;
  17         local items = 0; -- Number of stored items
  18         local t = have_utable and utable.create(size, 0) or {}; -- Table to hold items
  19         --luacheck: ignore 212/self
  20         return {
  21                 _items = t;
  22                 size = size;
  23                 count = function (self) return items; end;
  24                 push = function (self, item)
  25                         if items >= size then
  26                                 if allow_wrapping then
  27                                         tail = (tail%size)+1; -- Advance to next oldest item
  28                                         items = items - 1;
  29                                 else
  30                                         return nil, "queue full";
  31                                 end
  32                         end
  33                         t[head] = item;
  34                         items = items + 1;
  35                         head = (head%size)+1;
  36                         return true;
  37                 end;
  38                 pop = function (self)
  39                         if items == 0 then
  40                                 return nil;
  41                         end
  42                         local item;
  43                         item, t[tail] = t[tail], 0;
  44                         tail = (tail%size)+1;
  45                         items = items - 1;
  46                         return item;
  47                 end;
  48                 peek = function (self)
  49                         if items == 0 then
  50                                 return nil;
  51                         end
  52                         return t[tail];
  53                 end;
  54                 items = function (self)
  55                         --luacheck: ignore 431/t
  56                         return function (t, pos)
  57                                 if pos >= t:count() then
  58                                         return nil;
  59                                 end
  60                                 local read_pos = tail + pos;
  61                                 if read_pos > t.size then
  62                                         read_pos = (read_pos%size);
  63                                 end
  64                                 return pos+1, t._items[read_pos];
  65                         end, self, 0;
  66                 end;
  67         };
  68 end
  69
  70 return {
  71         new = new;
  72 };
  73