1 files changed, 124 insertions, 0 deletions
diff --git a/src/lib/aqueue.c b/src/lib/aqueue.c
new file mode 100644
index 0000000..c770bb7
--- /dev/null
+++ b/src/lib/aqueue.c
@@ -0,0 +1,124 @@
+/* Copyright (c) 2003-2018 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "array.h"
+#include "aqueue.h"
+
+struct aqueue *aqueue_init(struct array *array)
+{
+	struct aqueue *aqueue;
+
+	aqueue = i_new(struct aqueue, 1);
+	aqueue->arr = array;
+	aqueue->area_size = buffer_get_writable_size(aqueue->arr->buffer) /
+		aqueue->arr->element_size;
+	i_assert(aqueue->area_size > 0);
+	return aqueue;
+}
+
+void aqueue_deinit(struct aqueue **_aqueue)
+{
+	struct aqueue *aqueue = *_aqueue;
+
+	*_aqueue = NULL;
+	i_free(aqueue);
+}
+
+static void aqueue_grow(struct aqueue *aqueue)
+{
+	unsigned int orig_area_size, count;
+
+	i_assert(aqueue->full && aqueue->head == aqueue->tail);
+
+	orig_area_size = aqueue->area_size;
+	(void)array_append_space_i(aqueue->arr);
+	aqueue->area_size = buffer_get_writable_size(aqueue->arr->buffer) /
+		aqueue->arr->element_size;
+	i_assert(orig_area_size < aqueue->area_size);
+
+	count = I_MIN(aqueue->area_size - orig_area_size, aqueue->head);
+	array_copy(aqueue->arr, orig_area_size, aqueue->arr, 0, count);
+	if (count < aqueue->area_size - orig_area_size)
+		aqueue->head = orig_area_size + count;
+	else {
+		array_copy(aqueue->arr, 0, aqueue->arr, count,
+			   aqueue->head - count);
+		aqueue->head -= count;
+	}
+
+	i_assert(aqueue->head != aqueue->tail);
+	aqueue->full = FALSE;
+}
+
+void aqueue_append(struct aqueue *aqueue, const void *data)
+{
+	if (aqueue->full) {
+		aqueue_grow(aqueue);
+		i_assert(!aqueue->full);
+	}
+
+	array_idx_set_i(aqueue->arr, aqueue->head, data);
+	aqueue->head = (aqueue->head + 1) % aqueue->area_size;
+	aqueue->full = aqueue->head == aqueue->tail;
+}
+
+void aqueue_delete(struct aqueue *aqueue, unsigned int n)
+{
+	unsigned int idx, count = aqueue_count(aqueue);
+
+	i_assert(n < count);
+
+	aqueue->full = FALSE;
+	if (n == 0) {
+		/* optimized deletion from tail */
+		aqueue->tail = (aqueue->tail + 1) % aqueue->area_size;
+		return;
+	}
+	if (n == count-1) {
+		/* optimized deletion from head */
+		aqueue->head = (aqueue->head + aqueue->area_size - 1) %
+			aqueue->area_size;
+		return;
+	}
+
+	idx = aqueue_idx(aqueue, n);
+	if ((n < count/2 || idx > aqueue->head) && idx > aqueue->tail) {
+		/* move tail forward.
+		   ..tail##idx##head.. or ##head..tail##idx## */
+		array_copy(aqueue->arr, aqueue->tail + 1,
+			   aqueue->arr, aqueue->tail,
+			   idx - aqueue->tail);
+		aqueue->tail++;
+		i_assert(aqueue->tail < aqueue->area_size);
+	} else {
+		/* move head backward.
+		   ..tail##idx##head.. or ##idx##head..tail## */
+		i_assert(idx < aqueue->head);
+		array_copy(aqueue->arr, idx,
+			   aqueue->arr, idx + 1,
+			   aqueue->head - idx);
+		aqueue->head = (aqueue->head + aqueue->area_size - 1) %
+			aqueue->area_size;
+	}
+	i_assert(aqueue->head < aqueue->area_size &&
+		 aqueue->head != aqueue->tail);
+}
+
+void aqueue_delete_tail(struct aqueue *aqueue)
+{
+	aqueue_delete(aqueue, 0);
+}
+
+void aqueue_clear(struct aqueue *aqueue)
+{
+	aqueue->head = aqueue->tail = 0;
+	aqueue->full = FALSE;
+}
+
+unsigned int aqueue_count(const struct aqueue *aqueue)
+{
+	unsigned int area_size = aqueue->area_size;
+
+	return aqueue->full ? area_size :
+		(area_size - aqueue->tail + aqueue->head) % area_size;
+}