1 files changed, 191 insertions, 0 deletions
diff --git a/bytequeue.c b/bytequeue.c
new file mode 100644
index 0000000..538ba42
--- /dev/null
+++ b/bytequeue.c
@@ -0,0 +1,191 @@
+#include <string.h>
+
+#include "bytequeue.h"
+
+struct ByteQueue
+{
+    gsize       segment_size;
+    guint8 *	segment;
+    guint8 *	start;
+    guint8 *	end;
+};
+
+ByteQueue *
+byte_queue_new (void)
+{
+    ByteQueue *queue = g_new0 (ByteQueue, 1);
+
+    queue->segment_size = 0;
+    queue->segment = NULL;
+    queue->start = NULL;
+    queue->end = NULL;
+    
+    return queue;
+}
+
+guint8 *
+byte_queue_free (ByteQueue *queue,
+		 gboolean   free_data)
+{    
+    guint8 *result;
+    
+    if (free_data)
+    {
+	g_free (queue->segment);
+
+	result = NULL;
+    }
+    else
+    {
+	memmove (queue->segment, queue->start, queue->end - queue->start);
+
+	result = queue->segment;
+    }
+    
+    g_free (queue);
+
+    return result;
+}
+
+/* The data returned is owned by the byte queue and becomes invalid
+ * as soon as any method is called on the queue. It is explicitly
+ * allowed to push the returned data back into the queue, and indeed
+ * in that case the queue will avoid copying if it can. The push
+ * must be the first method called on the queue after the read.
+ */
+const guint8 *
+byte_queue_get_data (ByteQueue    *queue,
+		     gsize        *n_bytes)
+{
+    guint8 *result;
+    
+    if (n_bytes)
+	*n_bytes = queue->end - queue->start;
+
+    result = queue->start;
+
+    queue->start = queue->segment;
+    queue->end = queue->segment;
+    
+    return result;
+}
+
+static gboolean
+in_segment (ByteQueue *queue,
+	    const guint8 *bytes,
+	    gsize n_bytes)
+{
+    return bytes >= queue->segment && bytes + n_bytes < queue->end;
+}
+
+static gboolean
+is_empty (ByteQueue *queue)
+{
+    return queue->start == queue->end;
+}
+
+static gsize
+power_of_two_bigger_than (gsize n)
+{
+    gsize result = 1;
+
+    while (result <= n)
+	result *= 2;
+
+    return result;
+}
+
+static void
+ensure_room (ByteQueue *queue,
+	     gsize      extra)
+{
+    gsize old_data_size = queue->end - queue->start;
+    gsize new_data_size = old_data_size + extra;
+
+    if (queue->end + new_data_size > queue->segment + queue->segment_size)
+    {
+	gsize new_segment_size = power_of_two_bigger_than (2 * new_data_size);
+
+	memmove (queue->start, queue->segment, old_data_size);
+
+	if (new_segment_size > queue->segment_size)
+	{
+	    queue->segment_size = new_segment_size;
+	    queue->segment = g_realloc (queue->segment, new_segment_size);
+	}
+
+	queue->start = queue->segment;
+	queue->end = queue->start + new_data_size;
+    }
+}
+
+guint8 *
+byte_queue_alloc_tail (ByteQueue *queue,
+		       gsize	  size)
+{
+    ensure_room (queue, size);
+
+    queue->end += size;
+
+    return queue->end - size;
+}
+
+void
+byte_queue_delete_tail (ByteQueue *queue,
+			gsize	   size)
+{
+    if (queue->end - queue->start < size)
+	queue->end = queue->start;
+    else
+	queue->end -= size;
+}
+
+void
+byte_queue_append (ByteQueue    *queue,
+		   const guint8 *bytes,
+		   gsize         n_bytes)
+{
+    if (in_segment (queue, bytes, n_bytes) && is_empty (queue))
+    {
+	queue->start = (guint8 *)bytes;
+	queue->end = (guint8 *)bytes + n_bytes;
+    }
+    else
+    {
+	guint8 *tail = byte_queue_alloc_tail (queue, n_bytes);
+
+	memcpy (tail, bytes, n_bytes);
+    }
+}
+
+/* Transfer data from @src to @dest, if possible without copying.
+ * The data is appended to @dest's data if @dest is not empty
+ */
+void
+byte_queue_steal_data (ByteQueue    *dest,
+		       ByteQueue    *src)
+{
+    if (is_empty (dest))
+    {
+	if (dest->segment)
+	    g_free (dest->segment);
+	
+	dest->segment_size = src->segment_size;
+	dest->segment = src->segment;
+	dest->start = src->start;
+	dest->end = src->end;
+
+	src->segment_size = 0;
+	src->segment = NULL;
+	src->start = NULL;
+	src->end = NULL;
+    }
+    else
+    {
+	const guint8 *data;
+	gsize size;
+
+	data = byte_queue_get_data (src, &size);
+	byte_queue_append (dest, data, size);
+    }
+}