dovecot: Added queue implementation.
dovecot at dovecot.org
dovecot at dovecot.org
Sat Dec 29 04:15:01 EET 2007
details: http://hg.dovecot.org/dovecot/rev/bbeee3db9967
changeset: 7049:bbeee3db9967
user: Timo Sirainen <tss at iki.fi>
date: Sat Dec 29 04:11:59 2007 +0200
description:
Added queue implementation.
diffstat:
5 files changed, 244 insertions(+)
src/lib/Makefile.am | 2
src/lib/array.h | 11 ++++
src/lib/queue.c | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++
src/lib/queue.h | 40 ++++++++++++++++
src/tests/test-lib.c | 68 +++++++++++++++++++++++++++
diffs (truncated from 303 to 300 lines):
diff -r 2eeb9b2d8f9a -r bbeee3db9967 src/lib/Makefile.am
--- a/src/lib/Makefile.am Sat Dec 29 01:03:21 2007 +0200
+++ b/src/lib/Makefile.am Sat Dec 29 04:11:59 2007 +0200
@@ -77,6 +77,7 @@ liblib_a_SOURCES = \
primes.c \
printf-format-fix.c \
process-title.c \
+ queue.c \
randgen.c \
read-full.c \
restrict-access.c \
@@ -159,6 +160,7 @@ headers = \
primes.h \
printf-format-fix.h \
process-title.h \
+ queue.h \
randgen.h \
read-full.h \
restrict-access.h \
diff -r 2eeb9b2d8f9a -r bbeee3db9967 src/lib/array.h
--- a/src/lib/array.h Sat Dec 29 01:03:21 2007 +0200
+++ b/src/lib/array.h Sat Dec 29 04:11:59 2007 +0200
@@ -246,6 +246,17 @@ array_insert_space_i(struct array *array
ARRAY_TYPE_CAST_MODIFIABLE(array) \
array_insert_space_i(&(array)->arr, idx)
+static inline void
+array_copy(struct array *dest, unsigned int dest_idx,
+ const struct array *src, unsigned int src_idx, unsigned int count)
+{
+ i_assert(dest->element_size == src->element_size);
+
+ buffer_copy(dest->buffer, dest_idx * dest->element_size,
+ dest->buffer, src_idx * src->element_size,
+ count * dest->element_size);
+}
+
static inline unsigned int
array_count_i(const struct array *array)
{
diff -r 2eeb9b2d8f9a -r bbeee3db9967 src/lib/queue.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib/queue.c Sat Dec 29 04:11:59 2007 +0200
@@ -0,0 +1,123 @@
+/* Copyright (c) 2003-2007 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "array.h"
+#include "queue.h"
+
+struct queue *queue_init(struct array *array)
+{
+ struct queue *queue;
+
+ queue = i_new(struct queue, 1);
+ queue->arr = array;
+ queue->area_size =
+ buffer_get_size(queue->arr->buffer) / queue->arr->element_size;
+ i_assert(queue->area_size > 0);
+ return queue;
+}
+
+void queue_deinit(struct queue **_queue)
+{
+ struct queue *queue = *_queue;
+
+ *_queue = NULL;
+ i_free(queue);
+}
+
+static void queue_grow(struct queue *queue)
+{
+ unsigned int orig_area_size, count;
+
+ i_assert(queue->full && queue->head == queue->tail);
+
+ orig_area_size = queue->area_size;
+ (void)array_append_space_i(queue->arr);
+ queue->area_size =
+ buffer_get_size(queue->arr->buffer) / queue->arr->element_size;
+ i_assert(orig_area_size < queue->area_size);
+
+ count = I_MIN(queue->area_size - orig_area_size, queue->head);
+ array_copy(queue->arr, orig_area_size, queue->arr, 0, count);
+ if (count < queue->area_size - orig_area_size)
+ queue->head = orig_area_size + count;
+ else {
+ array_copy(queue->arr, 0, queue->arr, count,
+ queue->head - count);
+ queue->head -= count;
+ }
+
+ i_assert(queue->head != queue->tail);
+ queue->full = FALSE;
+}
+
+void queue_append(struct queue *queue, const void *data)
+{
+ if (queue->full) {
+ queue_grow(queue);
+ i_assert(!queue->full);
+ }
+
+ array_idx_set_i(queue->arr, queue->head, data);
+ queue->head = (queue->head + 1) % queue->area_size;
+ queue->full = queue->head == queue->tail;
+}
+
+void queue_delete(struct queue *queue, unsigned int n)
+{
+ unsigned int idx, count = queue_count(queue);
+
+ i_assert(n < count);
+
+ queue->full = FALSE;
+ if (n == 0) {
+ /* optimized deletion from tail */
+ queue->tail = (queue->tail + 1) % queue->area_size;
+ return;
+ }
+ if (n == count-1) {
+ /* optimized deletion from head */
+ queue->head = (queue->head + queue->area_size - 1) %
+ queue->area_size;
+ return;
+ }
+
+ idx = queue_idx(queue, n);
+ if ((n < count/2 || idx > queue->head) && idx > queue->tail) {
+ /* move tail forward.
+ ..tail##idx##head.. or ##head..tail##idx## */
+ array_copy(queue->arr, queue->tail + 1,
+ queue->arr, queue->tail,
+ idx - queue->tail);
+ queue->tail++;
+ i_assert(queue->tail < queue->area_size);
+ } else {
+ /* move head backward.
+ ..tail##idx##head.. or ##idx##head..tail## */
+ i_assert(idx < queue->head);
+ array_copy(queue->arr, idx,
+ queue->arr, idx + 1,
+ queue->head - idx);
+ queue->head = (queue->head + queue->area_size - 1) %
+ queue->area_size;
+ }
+ i_assert(queue->head < queue->area_size && queue->head != queue->tail);
+}
+
+void queue_delete_tail(struct queue *queue)
+{
+ queue_delete(queue, 0);
+}
+
+void queue_clear(struct queue *queue)
+{
+ queue->head = queue->tail = 0;
+ queue->full = FALSE;
+}
+
+unsigned int queue_count(const struct queue *queue)
+{
+ unsigned int area_size = queue->area_size;
+
+ return queue->full ? area_size :
+ (area_size - queue->tail + queue->head) % area_size;
+}
diff -r 2eeb9b2d8f9a -r bbeee3db9967 src/lib/queue.h
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib/queue.h Sat Dec 29 04:11:59 2007 +0200
@@ -0,0 +1,40 @@
+#ifndef QUEUE_H
+#define QUEUE_H
+
+/* Dynamically growing queue. Use the array directly to access the data,
+ for example:
+
+ count = queue_count(queue);
+ for (i = 0; i < count; i++) {
+ data = array[queue_idx(i)];
+ }
+*/
+
+struct queue {
+ struct array *arr;
+ unsigned int head, tail, area_size;
+ bool full;
+};
+
+struct queue *queue_init(struct array *array);
+void queue_deinit(struct queue **queue);
+
+/* Append item to head */
+void queue_append(struct queue *queue, const void *data);
+/* Delete last item from tail */
+void queue_delete_tail(struct queue *queue);
+/* Remove item from n'th position */
+void queue_delete(struct queue *queue, unsigned int n);
+/* Clear the entire queue */
+void queue_clear(struct queue *queue);
+
+/* Returns the number of items in queue. */
+unsigned int queue_count(const struct queue *queue);
+
+/* Returns array index of n'th element in queue. */
+static inline unsigned int queue_idx(const struct queue *queue, unsigned int n)
+{
+ return (queue->tail + n) % queue->area_size;
+}
+
+#endif
diff -r 2eeb9b2d8f9a -r bbeee3db9967 src/tests/test-lib.c
--- a/src/tests/test-lib.c Sat Dec 29 01:03:21 2007 +0200
+++ b/src/tests/test-lib.c Sat Dec 29 04:11:59 2007 +0200
@@ -5,6 +5,7 @@
#include "str.h"
#include "base64.h"
#include "bsearch-insert-pos.h"
+#include "queue.h"
#include "seq-range-array.h"
#include "str-sanitize.h"
@@ -123,6 +124,72 @@ static void test_bsearch_insert_pos(void
}
}
+static bool queue_is_ok(struct queue *queue, unsigned int deleted_n)
+{
+ const unsigned int *p;
+ unsigned int n, i, count;
+
+ count = queue_count(queue);
+ for (i = 0, n = 1; i < count; i++, n++) {
+ p = array_idx_i(queue->arr, queue_idx(queue, i));
+ if (i == deleted_n)
+ n++;
+ if (*p != n)
+ return FALSE;
+ }
+ return TRUE;
+}
+
+static const unsigned int queue_input[] = { 1, 2, 3, 4, 5, 6 };
+static const char *test_queue2(unsigned int initial_size)
+{
+ ARRAY_DEFINE(queue_array, unsigned int);
+ unsigned int i, j, k;
+ struct queue *queue;
+
+ for (i = 0; i < N_ELEMENTS(queue_input); i++) {
+ for (k = 0; k < N_ELEMENTS(queue_input); k++) {
+ t_array_init(&queue_array, initial_size);
+ queue = queue_init(&queue_array.arr);
+ queue->head = queue->tail = initial_size - 1;
+ for (j = 0; j < k; j++) {
+ queue_append(queue, &queue_input[j]);
+ if (queue_count(queue) != j + 1) {
+ return t_strdup_printf("Wrong count after append %u vs %u)",
+ queue_count(queue), j + 1);
+ }
+ if (!queue_is_ok(queue, -1U))
+ return "Invalid data after append";
+ }
+
+ if (k != 0 && i < k) {
+ queue_delete(queue, i);
+ if (queue_count(queue) != k - 1)
+ return "Wrong count after delete";
+ if (!queue_is_ok(queue, i))
+ return "Invalid data after delete";
+ }
+ }
+ }
+ queue_clear(queue);
+ if (queue_count(queue) != 0)
+ return "queue_clear() broken";
+ return NULL;
+}
+
+static void test_queue(void)
+{
+ unsigned int i;
+ const char *reason = NULL;
+
+ for (i = 1; i <= N_ELEMENTS(queue_input) + 1 && reason == NULL; i++) {
+ T_FRAME(
+ reason = test_queue2(i);
+ );
+ }
+ test_out_reason("queue", reason == NULL, reason);
+}
+
static void test_seq_range_array(void)
{
static const unsigned int input_min = 1, input_max = 5;
@@ -207,6 +274,7 @@ int main(void)
test_base64_encode,
test_base64_decode,
test_bsearch_insert_pos,
+ test_queue,
More information about the dovecot-cvs
mailing list