1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
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;
}
|
