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
|
/* Copyright (c) 2007-2018 Dovecot authors, see the included COPYING file */
#include "test-lib.h"
#include "priorityq.h"
struct pq_test_item {
struct priorityq_item item;
int num;
};
static int cmp_int(const void *p1, const void *p2)
{
const struct pq_test_item *i1 = p1, *i2 = p2;
return i1->num - i2->num;
}
void test_priorityq(void)
{
#define PQ_MAX_ITEMS 100
static const int input[] = {
1, 2, 3, 4, 5, 6, 7, 8, -1,
8, 7, 6, 5, 4, 3, 2, 1, -1,
8, 7, 5, 6, 1, 3, 4, 2, -1,
-1
};
static const int output[] = {
1, 2, 3, 4, 5, 6, 7, 8
};
struct pq_test_item *item, items[PQ_MAX_ITEMS];
struct priorityq_item *const *all_items;
unsigned int i, j;
struct priorityq *pq;
pool_t pool;
int prev;
pool = pool_alloconly_create("priorityq items", 1024);
/* simple tests with popping only */
test_begin("priorityq");
for (i = 0; input[i] != -1; i++) {
p_clear(pool);
pq = priorityq_init(cmp_int, 1);
for (j = 0; input[i] != -1; i++, j++) {
test_assert(priorityq_count(pq) == j);
item = p_new(pool, struct pq_test_item, 1);
item->num = input[i];
priorityq_add(pq, &item->item);
}
all_items = priorityq_items(pq);
test_assert(priorityq_count(pq) == N_ELEMENTS(output));
item = (struct pq_test_item *)all_items[0];
test_assert(item->num == output[0]);
for (j = 1; j < N_ELEMENTS(output); j++) {
item = (struct pq_test_item *)all_items[j];
test_assert(item->num > output[0]);
test_assert(item->num <= output[N_ELEMENTS(output)-1]);
}
for (j = 0; j < N_ELEMENTS(output); j++) {
test_assert(priorityq_count(pq) == N_ELEMENTS(output) - j);
item = (struct pq_test_item *)priorityq_peek(pq);
i_assert(item != NULL);
test_assert(output[j] == item->num);
item = (struct pq_test_item *)priorityq_pop(pq);
i_assert(item != NULL);
test_assert(output[j] == item->num);
}
test_assert(priorityq_count(pq) == 0);
test_assert(priorityq_peek(pq) == NULL);
test_assert(priorityq_pop(pq) == NULL);
priorityq_deinit(&pq);
}
test_end();
/* randomized tests, remove elements */
test_begin("priorityq randomized");
for (i = 0; i < 100; i++) {
pq = priorityq_init(cmp_int, 1);
for (j = 0; j < PQ_MAX_ITEMS; j++) {
items[j].num = i_rand_limit(INT_MAX);
priorityq_add(pq, &items[j].item);
}
for (j = 0; j < PQ_MAX_ITEMS; j++) {
if (i_rand_limit(3) == 0) {
priorityq_remove(pq, &items[j].item);
items[j].num = -1;
}
}
prev = 0;
while (priorityq_count(pq) > 0) {
item = (struct pq_test_item *)priorityq_pop(pq);
i_assert(item != NULL);
test_assert(item->num >= 0 && prev <= item->num);
prev = item->num;
item->num = -1;
}
for (j = 0; j < PQ_MAX_ITEMS; j++) {
test_assert(items[j].num == -1);
}
priorityq_deinit(&pq);
}
test_end();
pool_unref(&pool);
}
|
