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