--- a/src/lib/Makefile.am	Thu Jan 03 21:18:39 2008 +0200
+++ b/src/lib/Makefile.am	Thu Jan 03 23:18:46 2008 +0200
@@ -78,6 +78,7 @@
 	primes.c \
 	printf-format-fix.c \
 	process-title.c \
+	priorityq.c \
 	randgen.c \
 	read-full.c \
 	restrict-access.c \
@@ -161,6 +162,7 @@
 	primes.h \
 	printf-format-fix.h \
 	process-title.h \
+	priorityq.h \
 	randgen.h \
 	read-full.h \
 	restrict-access.h \

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib/priorityq.c	Thu Jan 03 23:18:46 2008 +0200
@@ -0,0 +1,158 @@
+/* Copyright (c) 2008 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "array.h"
+#include "priorityq.h"
+
+/* Macros for moving inside an array implementation of binary tree where
+   [0] is the root. */
+#define PARENT_IDX(idx) \
+	(((idx) - 1) / 2)
+#define LEFT_CHILD_IDX(idx) \
+	((idx) * 2 + 1)
+#define RIGHT_CHILD_IDX(idx) \
+	((idx) * 2 + 2)
+
+struct priorityq {
+	priorityq_cmp_callback_t *cmp_callback;
+
+	ARRAY_DEFINE(items, struct priorityq_item *);
+};
+
+struct priorityq *
+priorityq_init(priorityq_cmp_callback_t *cmp_callback, unsigned int init_size)
+{
+	struct priorityq *pq;
+
+	pq = i_new(struct priorityq, 1);
+	pq->cmp_callback = cmp_callback;
+	i_array_init(&pq->items, init_size);
+	return pq;
+}
+
+void priorityq_deinit(struct priorityq **_pq)
+{
+	struct priorityq *pq = *_pq;
+
+	*_pq = NULL;
+	array_free(&pq->items);
+	i_free(pq);
+}
+
+unsigned int priorityq_count(const struct priorityq *pq)
+{
+	return array_count(&pq->items);
+}
+
+static void heap_items_swap(struct priorityq_item **items,
+			    unsigned int idx1, unsigned int idx2)
+{
+	struct priorityq_item *tmp;
+
+	/* swap the item indexes */
+	i_assert(items[idx1]->idx == idx1);
+	i_assert(items[idx2]->idx == idx2);
+
+	items[idx1]->idx = idx2;
+	items[idx2]->idx = idx1;
+
+	/* swap the item pointers */
+	tmp = items[idx1];
+	items[idx1] = items[idx2];
+	items[idx2] = tmp;
+}
+
+static unsigned int
+heap_item_bubble_up(struct priorityq *pq, unsigned int idx)
+{
+	struct priorityq_item **items;
+	unsigned int parent_idx;
+
+	items = array_idx_modifiable(&pq->items, 0);
+	while (idx > 0) {
+		parent_idx = PARENT_IDX(idx);
+		if (pq->cmp_callback(items[idx], items[parent_idx]) >= 0)
+			break;
+
+		/* wrong order - swap */
+		heap_items_swap(items, idx, parent_idx);
+		idx = parent_idx;
+	}
+	return idx;
+}
+
+static void heap_item_bubble_down(struct priorityq *pq, unsigned int idx)
+{
+	struct priorityq_item **items;
+	unsigned int left_idx, right_idx, min_child_idx, count;
+
+	items = array_get_modifiable(&pq->items, &count);
+	while ((left_idx = LEFT_CHILD_IDX(idx)) < count) {
+		right_idx = RIGHT_CHILD_IDX(idx);
+		if (right_idx >= count ||
+		    pq->cmp_callback(items[left_idx], items[right_idx]) < 0)
+			min_child_idx = left_idx;
+		else
+			min_child_idx = right_idx;
+
+		if (pq->cmp_callback(items[min_child_idx], items[idx]) >= 0)
+			break;
+
+		/* wrong order - swap */
+		heap_items_swap(items, idx, min_child_idx);
+		idx = min_child_idx;
+	}
+}
+
+void priorityq_add(struct priorityq *pq, struct priorityq_item *item)
+{
+	item->idx = array_count(&pq->items);
+	array_append(&pq->items, &item, 1);
+	(void)heap_item_bubble_up(pq, item->idx);
+}
+
+static void priorityq_remove_idx(struct priorityq *pq, unsigned int idx)
+{
+	struct priorityq_item **items;
+	unsigned int count;
+
+	items = array_get_modifiable(&pq->items, &count);
+	i_assert(idx < count);
+
+	/* move last item over the removed one and fix the heap */
+	count--;
+	heap_items_swap(items, idx, count);
+	array_delete(&pq->items, count, 1);
+
+	if (count > 0) {
+		if (idx > 0)
+			idx = heap_item_bubble_up(pq, idx);
+		heap_item_bubble_down(pq, idx);
+	}
+}
+
+void priorityq_remove(struct priorityq *pq, struct priorityq_item *item)
+{
+	priorityq_remove_idx(pq, item->idx);
+}
+
+struct priorityq_item *priorityq_peek(struct priorityq *pq)
+{
+	struct priorityq_item *const *items;
+
+	if (array_count(&pq->items) == 0)
+		return NULL;
+
+	items = array_idx(&pq->items, 0);
+	return items[0];
+}
+
+struct priorityq_item *priorityq_pop(struct priorityq *pq)
+{
+	struct priorityq_item *item;
+
+	item = priorityq_peek(pq);
+	if (item != NULL)
+		priorityq_remove_idx(pq, 0);
+	return item;
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lib/priorityq.h	Thu Jan 03 23:18:46 2008 +0200
@@ -0,0 +1,35 @@
+#ifndef PRIORITYQ_H
+#define PRIORITYQ_H
+
+/* Priority queue implementation using heap. The items you add to the queue
+   must begin with a struct priorityq_item. This is necessary for
+   priorityq_remove() to work fast. */
+
+struct priorityq_item {
+	/* Current index in the queue array, updated automatically. */
+	unsigned int idx;
+	/* [your own data] */
+};
+
+/* Returns <0, 0 or >0 */
+typedef int priorityq_cmp_callback_t(const void *p1, const void *p2);
+
+/* Create a new priority queue. Callback is used to compare added items. */
+struct priorityq *
+priorityq_init(priorityq_cmp_callback_t *cmp_callback, unsigned int init_size);
+void priorityq_deinit(struct priorityq **pq);
+
+/* Return number of items in the queue. */
+unsigned int priorityq_count(const struct priorityq *pq);
+
+/* Add a new item to the queue. */
+void priorityq_add(struct priorityq *pq, struct priorityq_item *item);
+/* Remove the specified item from the queue. */
+void priorityq_remove(struct priorityq *pq, struct priorityq_item *item);
+
+/* Return the item with the highest priority. Returns NULL if queue is empty. */
+struct priorityq_item *priorityq_peek(struct priorityq *pq);
+/* Like priorityq_peek(), but also remove the returned item from the queue. */
+struct priorityq_item *priorityq_pop(struct priorityq *pq);
+
+#endif

--- a/src/tests/test-lib.c	Thu Jan 03 21:18:39 2008 +0200
+++ b/src/tests/test-lib.c	Thu Jan 03 23:18:46 2008 +0200
@@ -6,9 +6,12 @@
 #include "base64.h"
 #include "bsearch-insert-pos.h"
 #include "aqueue.h"
+#include "priorityq.h"
 #include "seq-range-array.h"
 #include "str-sanitize.h"
 
+#include <stdlib.h>
+
 static void test_base64_encode(void)
 {
 	static const char *input[] = {
@@ -212,7 +215,7 @@
 
 	for (i = 0; i < 64; i++) {
 		for (j = 1; j <= 128; j++) {
-			pool = pool_alloconly_create("test", i);
+			pool = pool_alloconly_create(MEMPOOL_GROWING"test", i);
 			mem[0] = p_malloc(pool, j);
 			memset(mem[0], j, j);
 
@@ -233,6 +236,101 @@
 	test_out("mempool_alloconly", success);
 }
 
+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;
+}
+
+static 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];
+	unsigned int i, j;
+	struct priorityq *pq;
+	pool_t pool;
+	int prev;
+	bool success = TRUE;
+
+	pool = pool_alloconly_create("priorityq items", 1024);
+
+	/* simple tests with popping only */
+	for (i = 0; input[i] != -1; i++) {
+		p_clear(pool);
+		pq = priorityq_init(cmp_int, 1);
+		for (j = 0; input[i] != -1; i++, j++) {
+			if (priorityq_count(pq) != j)
+				success = FALSE;
+			item = p_new(pool, struct pq_test_item, 1);
+			item->num = input[i];
+			priorityq_add(pq, &item->item);
+		}
+		for (j = 0; j < N_ELEMENTS(output); j++) {
+			if (priorityq_count(pq) != N_ELEMENTS(output) - j)
+				success = FALSE;
+
+			item = (struct pq_test_item *)priorityq_peek(pq);
+			if (output[j] != item->num)
+				success = FALSE;
+			item = (struct pq_test_item *)priorityq_pop(pq);
+			if (output[j] != item->num)
+				success = FALSE;
+		}
+		if (priorityq_count(pq) != 0)
+			success = FALSE;
+		if (priorityq_peek(pq) != NULL || priorityq_pop(pq) != NULL)
+			success = FALSE;
+		priorityq_deinit(&pq);
+	}
+	test_out("priorityq(1)", success);
+
+	/* randomized tests, remove elements */
+	success = TRUE;
+	for (i = 0; i < 100; i++) {
+		pq = priorityq_init(cmp_int, 1);
+		for (j = 0; j < PQ_MAX_ITEMS; j++) {
+			items[j].num = rand();
+			priorityq_add(pq, &items[j].item);
+		}
+		for (j = 0; j < PQ_MAX_ITEMS; j++) {
+			if (rand() % 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);
+			if (item->num < 0 || prev > item->num)
+				success = FALSE;
+			prev = item->num;
+			item->num = -1;
+		}
+		for (j = 0; j < PQ_MAX_ITEMS; j++) {
+			if (items[j].num != -1)
+				success = FALSE;
+		}
+		priorityq_deinit(&pq);
+	}
+	test_out("priorityq(2)", success);
+	pool_unref(&pool);
+}
+
 static void test_seq_range_array(void)
 {
 	static const unsigned int input_min = 1, input_max = 5;
@@ -319,6 +417,7 @@
 		test_base64_decode,
 		test_bsearch_insert_pos,
 		test_mempool_alloconly,
+		test_priorityq,
 		test_seq_range_array,
 		test_str_sanitize,