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
  20         return {
  21                 size = size;
  22                 count = function (self) return items; end;
  23                 push = function (self, item)
  24                         if items >= size then
  25                                 if allow_wrapping then
  26                                         tail = (tail%size)+1; -- Advance to next oldest item
  27                                         items = items - 1;
  28                                 else
  29                                         return nil, "queue full";
  30                                 end
  31                         end
  32                         t[head] = item;
  33                         items = items + 1;
  34                         head = (head%size)+1;
  35                         return true;
  36                 end;
  37                 pop = function (self)
  38                         if items == 0 then
  39                                 return nil;
  40                         end
  41                         local item;
  42                         item, t[tail] = t[tail], 0;
  43                         tail = (tail%size)+1;
  44                         items = items - 1;
  45                         return item;
  46                 end;
  47                 peek = function (self)
  48                         if items == 0 then
  49                                 return nil;
  50                         end
  51                         return t[tail];
  52                 end;
  53         };
  54 end
  55
  56 return {
  57         new = new;
  58 };
  59