Mercurial > dovecot > original-hg > dovecot-1.2
changeset 7049:bbeee3db9967 HEAD
Added queue implementation.
author | Timo Sirainen <tss@iki.fi> |
---|---|
date | Sat, 29 Dec 2007 04:11:59 +0200 |
parents | 2eeb9b2d8f9a |
children | 0dcea80312b0 |
files | src/lib/Makefile.am src/lib/array.h src/lib/queue.c src/lib/queue.h src/tests/test-lib.c |
diffstat | 5 files changed, 244 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- 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 @@ primes.c \ printf-format-fix.c \ process-title.c \ + queue.c \ randgen.c \ read-full.c \ restrict-access.c \ @@ -159,6 +160,7 @@ primes.h \ printf-format-fix.h \ process-title.h \ + queue.h \ randgen.h \ read-full.h \ restrict-access.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_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) {
--- /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; +}
--- /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
--- 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 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 @@ test_base64_encode, test_base64_decode, test_bsearch_insert_pos, + test_queue, test_seq_range_array, test_str_sanitize,