bcb4e51a409d94ae670de96afb8483a4f7855294Stephan Bosch/* Copyright (c) 2003-2018 Dovecot authors, see the included COPYING file */
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen#include "lib.h"
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen#include "array.h"
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen#include "aqueue.h"
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainenstruct aqueue *aqueue_init(struct array *array)
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen{
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen struct aqueue *aqueue;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue = i_new(struct aqueue, 1);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->arr = array;
8b48c53a81bdc67f267ffbcc45ba9860cb49e977Timo Sirainen aqueue->area_size = buffer_get_writable_size(aqueue->arr->buffer) /
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->arr->element_size;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen i_assert(aqueue->area_size > 0);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen return aqueue;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen}
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainenvoid aqueue_deinit(struct aqueue **_aqueue)
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen{
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen struct aqueue *aqueue = *_aqueue;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen *_aqueue = NULL;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen i_free(aqueue);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen}
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainenstatic void aqueue_grow(struct aqueue *aqueue)
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen{
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen unsigned int orig_area_size, count;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen i_assert(aqueue->full && aqueue->head == aqueue->tail);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen orig_area_size = aqueue->area_size;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen (void)array_append_space_i(aqueue->arr);
8b48c53a81bdc67f267ffbcc45ba9860cb49e977Timo Sirainen aqueue->area_size = buffer_get_writable_size(aqueue->arr->buffer) /
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->arr->element_size;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen i_assert(orig_area_size < aqueue->area_size);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen count = I_MIN(aqueue->area_size - orig_area_size, aqueue->head);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen array_copy(aqueue->arr, orig_area_size, aqueue->arr, 0, count);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen if (count < aqueue->area_size - orig_area_size)
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->head = orig_area_size + count;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen else {
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen array_copy(aqueue->arr, 0, aqueue->arr, count,
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->head - count);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->head -= count;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen }
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen i_assert(aqueue->head != aqueue->tail);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->full = FALSE;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen}
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainenvoid aqueue_append(struct aqueue *aqueue, const void *data)
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen{
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen if (aqueue->full) {
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue_grow(aqueue);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen i_assert(!aqueue->full);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen }
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen array_idx_set_i(aqueue->arr, aqueue->head, data);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->head = (aqueue->head + 1) % aqueue->area_size;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->full = aqueue->head == aqueue->tail;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen}
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainenvoid aqueue_delete(struct aqueue *aqueue, unsigned int n)
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen{
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen unsigned int idx, count = aqueue_count(aqueue);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen i_assert(n < count);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->full = FALSE;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen if (n == 0) {
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen /* optimized deletion from tail */
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->tail = (aqueue->tail + 1) % aqueue->area_size;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen return;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen }
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen if (n == count-1) {
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen /* optimized deletion from head */
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->head = (aqueue->head + aqueue->area_size - 1) %
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->area_size;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen return;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen }
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen idx = aqueue_idx(aqueue, n);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen if ((n < count/2 || idx > aqueue->head) && idx > aqueue->tail) {
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen /* move tail forward.
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen ..tail##idx##head.. or ##head..tail##idx## */
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen array_copy(aqueue->arr, aqueue->tail + 1,
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->arr, aqueue->tail,
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen idx - aqueue->tail);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->tail++;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen i_assert(aqueue->tail < aqueue->area_size);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen } else {
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen /* move head backward.
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen ..tail##idx##head.. or ##idx##head..tail## */
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen i_assert(idx < aqueue->head);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen array_copy(aqueue->arr, idx,
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->arr, idx + 1,
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->head - idx);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->head = (aqueue->head + aqueue->area_size - 1) %
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->area_size;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen }
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen i_assert(aqueue->head < aqueue->area_size &&
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->head != aqueue->tail);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen}
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainenvoid aqueue_delete_tail(struct aqueue *aqueue)
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen{
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue_delete(aqueue, 0);
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen}
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainenvoid aqueue_clear(struct aqueue *aqueue)
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen{
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->head = aqueue->tail = 0;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen aqueue->full = FALSE;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen}
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainenunsigned int aqueue_count(const struct aqueue *aqueue)
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen{
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen unsigned int area_size = aqueue->area_size;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen return aqueue->full ? area_size :
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen (area_size - aqueue->tail + aqueue->head) % area_size;
63cde222abaaa2a9bdaa9a143698dbc8b23bd742Timo Sirainen}