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.
41 compare_func_t compare_func;
42 unsigned n_items, n_allocated;
44 struct prioq_item *items;
47 Prioq *prioq_new(compare_func_t compare_func) {
54 q->compare_func = compare_func;
58 Prioq* prioq_free(Prioq *q) {
68 int prioq_ensure_allocated(Prioq **q, compare_func_t compare_func) {
74 *q = prioq_new(compare_func);
81 static void swap(Prioq *q, unsigned j, unsigned k) {
86 assert(j < q->n_items);
87 assert(k < q->n_items);
89 assert(!q->items[j].idx || *(q->items[j].idx) == j);
90 assert(!q->items[k].idx || *(q->items[k].idx) == k);
92 saved_data = q->items[j].data;
93 saved_idx = q->items[j].idx;
94 q->items[j].data = q->items[k].data;
95 q->items[j].idx = q->items[k].idx;
96 q->items[k].data = saved_data;
97 q->items[k].idx = saved_idx;
100 *q->items[j].idx = j;
103 *q->items[k].idx = k;
106 static unsigned shuffle_up(Prioq *q, unsigned idx) {
114 if (q->compare_func(q->items[k].data, q->items[idx].data) <= 0)
124 static unsigned shuffle_down(Prioq *q, unsigned idx) {
130 k = (idx+1)*2; /* right child */
131 j = k-1; /* left child */
136 if (q->compare_func(q->items[j].data, q->items[idx].data) < 0)
138 /* So our left child is smaller than we are, let's
139 * remember this fact */
144 if (k < q->n_items &&
145 q->compare_func(q->items[k].data, q->items[s].data) < 0)
147 /* So our right child is smaller than we are, let's
148 * remember this fact */
151 /* s now points to the smallest of the three items */
154 /* No swap necessary, we're done */
164 int prioq_put(Prioq *q, void *data, unsigned *idx) {
165 struct prioq_item *i;
170 if (q->n_items >= q->n_allocated) {
172 struct prioq_item *j;
174 n = MAX((q->n_items+1) * 2, 16u);
175 j = realloc(q->items, sizeof(struct prioq_item) * n);
196 static void remove_item(Prioq *q, struct prioq_item *i) {
197 struct prioq_item *l;
202 l = q->items + q->n_items - 1;
205 /* Last entry, let's just remove it */
210 /* Not last entry, let's replace the last entry with
211 * this one, and reshuffle */
221 k = shuffle_down(q, k);
226 _pure_ static struct prioq_item* find_item(Prioq *q, void *data, unsigned *idx) {
227 struct prioq_item *i;
232 if (*idx == PRIOQ_IDX_NULL ||
242 for (i = q->items; i < q->items + q->n_items; i++)
249 int prioq_remove(Prioq *q, void *data, unsigned *idx) {
250 struct prioq_item *i;
255 i = find_item(q, data, idx);
263 int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {
264 struct prioq_item *i;
269 i = find_item(q, data, idx);
274 k = shuffle_down(q, k);
279 void *prioq_peek(Prioq *q) {
287 return q->items[0].data;
290 void *prioq_pop(Prioq *q) {
299 data = q->items[0].data;
300 remove_item(q, q->items);
304 unsigned prioq_size(Prioq *q) {
312 bool prioq_isempty(Prioq *q) {
317 return q->n_items <= 0;