1 files changed, 106 insertions, 0 deletions
diff --git a/src/lib/test-priorityq.c b/src/lib/test-priorityq.c
new file mode 100644
index 0000000..a4eb90f
--- /dev/null
+++ b/src/lib/test-priorityq.c
@@ -0,0 +1,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);
+}