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.
35 #include "alloc-util.h"
45 compare_func_t compare_func;
46 unsigned n_items, n_allocated;
48 struct prioq_item *items;
51 Prioq *prioq_new(compare_func_t compare_func) {
58 q->compare_func = compare_func;
62 Prioq* prioq_free(Prioq *q) {
72 int prioq_ensure_allocated(Prioq **q, compare_func_t compare_func) {
78 *q = prioq_new(compare_func);
85 static void swap(Prioq *q, unsigned j, unsigned k) {
90 assert(j < q->n_items);
91 assert(k < q->n_items);
93 assert(!q->items[j].idx || *(q->items[j].idx) == j);
94 assert(!q->items[k].idx || *(q->items[k].idx) == k);
96 saved_data = q->items[j].data;
97 saved_idx = q->items[j].idx;
98 q->items[j].data = q->items[k].data;
99 q->items[j].idx = q->items[k].idx;
100 q->items[k].data = saved_data;
101 q->items[k].idx = saved_idx;
104 *q->items[j].idx = j;
107 *q->items[k].idx = k;
110 static unsigned shuffle_up(Prioq *q, unsigned idx) {
118 if (q->compare_func(q->items[k].data, q->items[idx].data) <= 0)
128 static unsigned shuffle_down(Prioq *q, unsigned idx) {
134 k = (idx+1)*2; /* right child */
135 j = k-1; /* left child */
140 if (q->compare_func(q->items[j].data, q->items[idx].data) < 0)
142 /* So our left child is smaller than we are, let's
143 * remember this fact */
148 if (k < q->n_items &&
149 q->compare_func(q->items[k].data, q->items[s].data) < 0)
151 /* So our right child is smaller than we are, let's
152 * remember this fact */
155 /* s now points to the smallest of the three items */
158 /* No swap necessary, we're done */
168 int prioq_put(Prioq *q, void *data, unsigned *idx) {
169 struct prioq_item *i;
174 if (q->n_items >= q->n_allocated) {
176 struct prioq_item *j;
178 n = MAX((q->n_items+1) * 2, 16u);
179 j = realloc(q->items, sizeof(struct prioq_item) * n);
200 static void remove_item(Prioq *q, struct prioq_item *i) {
201 struct prioq_item *l;
206 l = q->items + q->n_items - 1;
209 /* Last entry, let's just remove it */
214 /* Not last entry, let's replace the last entry with
215 * this one, and reshuffle */
225 k = shuffle_down(q, k);
230 _pure_ static struct prioq_item* find_item(Prioq *q, void *data, unsigned *idx) {
231 struct prioq_item *i;
236 if (*idx == PRIOQ_IDX_NULL ||
246 for (i = q->items; i < q->items + q->n_items; i++)
253 int prioq_remove(Prioq *q, void *data, unsigned *idx) {
254 struct prioq_item *i;
259 i = find_item(q, data, idx);
267 int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {
268 struct prioq_item *i;
273 i = find_item(q, data, idx);
278 k = shuffle_down(q, k);
283 void *prioq_peek(Prioq *q) {
291 return q->items[0].data;
294 void *prioq_pop(Prioq *q) {
303 data = q->items[0].data;
304 remove_item(q, q->items);
308 unsigned prioq_size(Prioq *q) {
316 bool prioq_isempty(Prioq *q) {
321 return q->n_items <= 0;