1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
4 This file is part of systemd.
6 Copyright 2013 Lennart Poettering
8 systemd is free software; you can redistribute it and/or modify it
9 under the terms of the GNU Lesser General Public License as published by
10 the Free Software Foundation; either version 2.1 of the License, or
11 (at your option) any later version.
13 systemd is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 Lesser General Public License for more details.
18 You should have received a copy of the GNU Lesser General Public License
19 along with systemd; If not, see <http://www.gnu.org/licenses/>.
24 * The prioq object implements a priority queue. That is, it orders objects by
25 * their priority and allows O(1) access to the object with the highest
26 * priority. Insertion and removal are Θ(log n). Optionally, the caller can
27 * provide a pointer to an index which will be kept up-to-date by the prioq.
29 * The underlying algorithm used in this implementation is a Heap.
32 #include "alloc-util.h"
42 compare_func_t compare_func;
43 unsigned n_items, n_allocated;
45 struct prioq_item *items;
48 Prioq *prioq_new(compare_func_t compare_func) {
55 q->compare_func = compare_func;
59 Prioq* prioq_free(Prioq *q) {
69 int prioq_ensure_allocated(Prioq **q, compare_func_t compare_func) {
75 *q = prioq_new(compare_func);
82 static void swap(Prioq *q, unsigned j, unsigned k) {
87 assert(j < q->n_items);
88 assert(k < q->n_items);
90 assert(!q->items[j].idx || *(q->items[j].idx) == j);
91 assert(!q->items[k].idx || *(q->items[k].idx) == k);
93 saved_data = q->items[j].data;
94 saved_idx = q->items[j].idx;
95 q->items[j].data = q->items[k].data;
96 q->items[j].idx = q->items[k].idx;
97 q->items[k].data = saved_data;
98 q->items[k].idx = saved_idx;
101 *q->items[j].idx = j;
104 *q->items[k].idx = k;
107 static unsigned shuffle_up(Prioq *q, unsigned idx) {
115 if (q->compare_func(q->items[k].data, q->items[idx].data) <= 0)
125 static unsigned shuffle_down(Prioq *q, unsigned idx) {
131 k = (idx+1)*2; /* right child */
132 j = k-1; /* left child */
137 if (q->compare_func(q->items[j].data, q->items[idx].data) < 0)
139 /* So our left child is smaller than we are, let's
140 * remember this fact */
145 if (k < q->n_items &&
146 q->compare_func(q->items[k].data, q->items[s].data) < 0)
148 /* So our right child is smaller than we are, let's
149 * remember this fact */
152 /* s now points to the smallest of the three items */
155 /* No swap necessary, we're done */
165 int prioq_put(Prioq *q, void *data, unsigned *idx) {
166 struct prioq_item *i;
171 if (q->n_items >= q->n_allocated) {
173 struct prioq_item *j;
175 n = MAX((q->n_items+1) * 2, 16u);
176 j = realloc(q->items, sizeof(struct prioq_item) * n);
197 static void remove_item(Prioq *q, struct prioq_item *i) {
198 struct prioq_item *l;
203 l = q->items + q->n_items - 1;
206 /* Last entry, let's just remove it */
211 /* Not last entry, let's replace the last entry with
212 * this one, and reshuffle */
222 k = shuffle_down(q, k);
227 _pure_ static struct prioq_item* find_item(Prioq *q, void *data, unsigned *idx) {
228 struct prioq_item *i;
233 if (*idx == PRIOQ_IDX_NULL ||
243 for (i = q->items; i < q->items + q->n_items; i++)
250 int prioq_remove(Prioq *q, void *data, unsigned *idx) {
251 struct prioq_item *i;
256 i = find_item(q, data, idx);
264 int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {
265 struct prioq_item *i;
270 i = find_item(q, data, idx);
275 k = shuffle_down(q, k);
280 void *prioq_peek(Prioq *q) {
288 return q->items[0].data;
291 void *prioq_pop(Prioq *q) {
300 data = q->items[0].data;
301 remove_item(q, q->items);
305 unsigned prioq_size(Prioq *q) {
313 bool prioq_isempty(Prioq *q) {
318 return q->n_items <= 0;