From 254b65a0305911d550d2c69048ba3f09b76bff31 Mon Sep 17 00:00:00 2001 From: Matthew Wild Date: Fri, 26 Jun 2020 16:41:31 +0100 Subject: util.dbuffer: dynamic string buffer Similar to util.ringbuffer (and shares almost identical API). Differences: - size limit is optional and dynamic - does not allocate a fixed buffer of max_size bytes - focus on simply storing references to existing string objects where possible, avoiding unnecessary allocations - references are still stored in a ring buffer to enable use as a fast FIFO Optional second parameter to new() provides the number of ring buffer segments. On Lua 5.2 on my laptop, a segment is ~19 bytes. If the ring buffer fills up, the next write will compact all strings into a single item. --- util/queue.lua | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'util') diff --git a/util/queue.lua b/util/queue.lua index 728e905f..c8e71514 100644 --- a/util/queue.lua +++ b/util/queue.lua @@ -51,6 +51,13 @@ local function new(size, allow_wrapping) end return t[tail]; end; + replace = function (self, data) + if items == 0 then + return self:push(data); + end + t[tail] = data; + return true; + end; items = function (self) --luacheck: ignore 431/t return function (t, pos) -- cgit v1.2.3 From 91d42d3218f128b087cfc31e15baa7579aabb713 Mon Sep 17 00:00:00 2001 From: Matthew Wild Date: Mon, 24 Aug 2020 16:18:13 +0100 Subject: util.dbuffer: Fix :sub() not working with partially-consumed chunks (thanks Zash for test case) This also appears to fix some bugs with chunk-encoded streams in net.http.parser. --- util/dbuffer.lua | 176 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 176 insertions(+) create mode 100644 util/dbuffer.lua (limited to 'util') diff --git a/util/dbuffer.lua b/util/dbuffer.lua new file mode 100644 index 00000000..a50f3a64 --- /dev/null +++ b/util/dbuffer.lua @@ -0,0 +1,176 @@ +local queue = require "util.queue"; + +local dbuffer_methods = {}; +local dynamic_buffer_mt = { __index = dbuffer_methods }; + +function dbuffer_methods:write(data) + if self.max_size and #data + self._length > self.max_size then + return nil; + end + local ok = self.items:push(data); + if not ok then + self:collapse(); + ok = self.items:push(data); + end + if not ok then + return nil; + end + self._length = self._length + #data; + return true; +end + +function dbuffer_methods:read_chunk(requested_bytes) + local chunk, consumed = self.items:peek(), self.front_consumed; + if not chunk then return; end + local chunk_length = #chunk; + local remaining_chunk_length = chunk_length - consumed; + if not requested_bytes then + requested_bytes = remaining_chunk_length; + end + if remaining_chunk_length <= requested_bytes then + self.front_consumed = 0; + self._length = self._length - remaining_chunk_length; + self.items:pop(); + assert(#chunk:sub(consumed + 1, -1) == remaining_chunk_length); + return chunk:sub(consumed + 1, -1), remaining_chunk_length; + end + local end_pos = consumed + requested_bytes; + self.front_consumed = end_pos; + self._length = self._length - requested_bytes; + assert(#chunk:sub(consumed + 1, end_pos) == requested_bytes); + return chunk:sub(consumed + 1, end_pos), requested_bytes; +end + +function dbuffer_methods:read(requested_bytes) + local chunks; + + if requested_bytes and requested_bytes > self._length then + return nil; + end + + local chunk, read_bytes = self:read_chunk(requested_bytes); + if not requested_bytes then + return chunk; + elseif chunk then + requested_bytes = requested_bytes - read_bytes; + if requested_bytes == 0 then -- Already read everything we need + return chunk; + end + chunks = {}; + else + return nil; + end + + -- Need to keep reading more chunks + while chunk do + table.insert(chunks, chunk); + if requested_bytes > 0 then + chunk, read_bytes = self:read_chunk(requested_bytes); + requested_bytes = requested_bytes - read_bytes; + else + break; + end + end + + return table.concat(chunks); +end + +function dbuffer_methods:discard(requested_bytes) + if requested_bytes > self._length then + return nil; + end + + local chunk, read_bytes = self:read_chunk(requested_bytes); + if chunk then + requested_bytes = requested_bytes - read_bytes; + if requested_bytes == 0 then -- Already read everything we need + return true; + end + else + return nil; + end + + while chunk do + if requested_bytes > 0 then + chunk, read_bytes = self:read_chunk(requested_bytes); + requested_bytes = requested_bytes - read_bytes; + else + break; + end + end + return true; +end + +function dbuffer_methods:sub(i, j) + if j == nil then + j = -1; + end + if j < 0 then + j = self._length + (j+1); + end + if i < 0 then + i = self._length + (i+1); + end + if i < 1 then + i = 1; + end + if j > self._length then + j = self._length; + end + if i > j then + return ""; + end + + self:collapse(j); + + return self.items:peek():sub(self.front_consumed+1):sub(i, j); +end + +function dbuffer_methods:byte(i, j) + i = i or 1; + j = j or i; + return string.byte(self:sub(i, j), 1, -1); +end + +function dbuffer_methods:length() + return self._length; +end +dynamic_buffer_mt.__len = dbuffer_methods.length; -- support # operator + +function dbuffer_methods:collapse(bytes) + bytes = bytes or self._length; + + local front_chunk = self.items:peek(); + + if not front_chunk or #front_chunk - self.front_consumed >= bytes then + return; + end + + local front_chunks = { front_chunk:sub(self.front_consumed+1) }; + local front_bytes = #front_chunks[1]; + + while front_bytes < bytes do + self.items:pop(); + local chunk = self.items:peek(); + front_bytes = front_bytes + #chunk; + table.insert(front_chunks, chunk); + end + self.items:replace(table.concat(front_chunks)); + self.front_consumed = 0; +end + +local function new(max_size, max_chunks) + if max_size and max_size <= 0 then + return nil; + end + return setmetatable({ + front_consumed = 0; + _length = 0; + max_size = max_size; + items = queue.new(max_chunks or 32); + }, dynamic_buffer_mt); +end + +return { + new = new; +}; -- cgit v1.2.3