priorityq.c revision 2a51b74d417285de5885460c659d92417f64b127
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen/* Copyright (c) 2008-2009 Dovecot authors, see the included COPYING file */
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen#include "lib.h"
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen#include "array.h"
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen#include "priorityq.h"
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen/* Macros for moving inside an array implementation of binary tree where
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen [0] is the root. */
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen#define PARENT_IDX(idx) \
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen (((idx) - 1) / 2)
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen#define LEFT_CHILD_IDX(idx) \
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen ((idx) * 2 + 1)
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen#define RIGHT_CHILD_IDX(idx) \
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen ((idx) * 2 + 2)
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainenstruct priorityq {
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen priorityq_cmp_callback_t *cmp_callback;
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen ARRAY_DEFINE(items, struct priorityq_item *);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen};
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainenstruct priorityq *
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainenpriorityq_init(priorityq_cmp_callback_t *cmp_callback, unsigned int init_size)
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen{
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen struct priorityq *pq;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen pq = i_new(struct priorityq, 1);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen pq->cmp_callback = cmp_callback;
a12399903f415a7e14c2816cffa2f7a09dcbb097Timo Sirainen i_array_init(&pq->items, init_size);
a12399903f415a7e14c2816cffa2f7a09dcbb097Timo Sirainen return pq;
a12399903f415a7e14c2816cffa2f7a09dcbb097Timo Sirainen}
a12399903f415a7e14c2816cffa2f7a09dcbb097Timo Sirainen
a12399903f415a7e14c2816cffa2f7a09dcbb097Timo Sirainenvoid priorityq_deinit(struct priorityq **_pq)
a12399903f415a7e14c2816cffa2f7a09dcbb097Timo Sirainen{
a12399903f415a7e14c2816cffa2f7a09dcbb097Timo Sirainen struct priorityq *pq = *_pq;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen *_pq = NULL;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen array_free(&pq->items);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen i_free(pq);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen}
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainenunsigned int priorityq_count(const struct priorityq *pq)
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen{
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen return array_count(&pq->items);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen}
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainenstatic void heap_items_swap(struct priorityq_item **items,
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen unsigned int idx1, unsigned int idx2)
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen{
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen struct priorityq_item *tmp;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen /* swap the item indexes */
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen i_assert(items[idx1]->idx == idx1);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen i_assert(items[idx2]->idx == idx2);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen items[idx1]->idx = idx2;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen items[idx2]->idx = idx1;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen /* swap the item pointers */
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen tmp = items[idx1];
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen items[idx1] = items[idx2];
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen items[idx2] = tmp;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen}
90adcaa0a00eba29b7fbd50ca66be11c8d086d6aTimo Sirainen
90adcaa0a00eba29b7fbd50ca66be11c8d086d6aTimo Sirainenstatic unsigned int
90adcaa0a00eba29b7fbd50ca66be11c8d086d6aTimo Sirainenheap_item_bubble_up(struct priorityq *pq, unsigned int idx)
90adcaa0a00eba29b7fbd50ca66be11c8d086d6aTimo Sirainen{
90adcaa0a00eba29b7fbd50ca66be11c8d086d6aTimo Sirainen struct priorityq_item **items;
90adcaa0a00eba29b7fbd50ca66be11c8d086d6aTimo Sirainen unsigned int parent_idx, count;
90adcaa0a00eba29b7fbd50ca66be11c8d086d6aTimo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen items = array_get_modifiable(&pq->items, &count);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen while (idx > 0) {
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen parent_idx = PARENT_IDX(idx);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen i_assert(idx < count);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen if (pq->cmp_callback(items[idx], items[parent_idx]) >= 0)
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen break;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen /* wrong order - swap */
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen heap_items_swap(items, idx, parent_idx);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen idx = parent_idx;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen }
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen return idx;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen}
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainenstatic void heap_item_bubble_down(struct priorityq *pq, unsigned int idx)
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen{
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen struct priorityq_item **items;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen unsigned int left_idx, right_idx, min_child_idx, count;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen items = array_get_modifiable(&pq->items, &count);
87460b08cb97b31cde640d4975a6aa2c1d0e7226Timo Sirainen while ((left_idx = LEFT_CHILD_IDX(idx)) < count) {
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen right_idx = RIGHT_CHILD_IDX(idx);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen if (right_idx >= count ||
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen pq->cmp_callback(items[left_idx], items[right_idx]) < 0)
87460b08cb97b31cde640d4975a6aa2c1d0e7226Timo Sirainen min_child_idx = left_idx;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen else
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen min_child_idx = right_idx;
87460b08cb97b31cde640d4975a6aa2c1d0e7226Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen if (pq->cmp_callback(items[min_child_idx], items[idx]) >= 0)
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen break;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
87460b08cb97b31cde640d4975a6aa2c1d0e7226Timo Sirainen /* wrong order - swap */
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen heap_items_swap(items, idx, min_child_idx);
87460b08cb97b31cde640d4975a6aa2c1d0e7226Timo Sirainen idx = min_child_idx;
87460b08cb97b31cde640d4975a6aa2c1d0e7226Timo Sirainen }
87460b08cb97b31cde640d4975a6aa2c1d0e7226Timo Sirainen}
87460b08cb97b31cde640d4975a6aa2c1d0e7226Timo Sirainen
87460b08cb97b31cde640d4975a6aa2c1d0e7226Timo Sirainenvoid priorityq_add(struct priorityq *pq, struct priorityq_item *item)
87460b08cb97b31cde640d4975a6aa2c1d0e7226Timo Sirainen{
87460b08cb97b31cde640d4975a6aa2c1d0e7226Timo Sirainen item->idx = array_count(&pq->items);
87460b08cb97b31cde640d4975a6aa2c1d0e7226Timo Sirainen array_append(&pq->items, &item, 1);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen (void)heap_item_bubble_up(pq, item->idx);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen}
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainenstatic void priorityq_remove_idx(struct priorityq *pq, unsigned int idx)
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen{
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen struct priorityq_item **items;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen unsigned int count;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen items = array_get_modifiable(&pq->items, &count);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen i_assert(idx < count);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen /* move last item over the removed one and fix the heap */
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen count--;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen heap_items_swap(items, idx, count);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen array_delete(&pq->items, count, 1);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen if (count > 0 && idx != count) {
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen if (idx > 0)
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen idx = heap_item_bubble_up(pq, idx);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen heap_item_bubble_down(pq, idx);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen }
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen}
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainenvoid priorityq_remove(struct priorityq *pq, struct priorityq_item *item)
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen{
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen priorityq_remove_idx(pq, item->idx);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen}
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainenstruct priorityq_item *priorityq_peek(struct priorityq *pq)
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen{
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen struct priorityq_item *const *items;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen if (array_count(&pq->items) == 0)
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen return NULL;
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen items = array_idx(&pq->items, 0);
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen return items[0];
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen}
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainen
fdc557286bc9f92c5f3bb49096ff6e2bcec0ea79Timo Sirainenstruct priorityq_item *priorityq_pop(struct priorityq *pq)
910fa4e4204a73d3d24c03f3059dd24e727ca057Timo Sirainen{
910fa4e4204a73d3d24c03f3059dd24e727ca057Timo Sirainen struct priorityq_item *item;
910fa4e4204a73d3d24c03f3059dd24e727ca057Timo Sirainen
910fa4e4204a73d3d24c03f3059dd24e727ca057Timo Sirainen item = priorityq_peek(pq);
910fa4e4204a73d3d24c03f3059dd24e727ca057Timo Sirainen if (item != NULL)
910fa4e4204a73d3d24c03f3059dd24e727ca057Timo Sirainen priorityq_remove_idx(pq, 0);
910fa4e4204a73d3d24c03f3059dd24e727ca057Timo Sirainen return item;
}
struct priorityq_item *const *priorityq_items(struct priorityq *pq)
{
if (array_count(&pq->items) == 0)
return NULL;
return array_idx(&pq->items, 0);
}