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