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/>.
31 compare_func_t compare_func;
32 unsigned n_items, n_allocated;
34 struct prioq_item *items;
37 Prioq *prioq_new(compare_func_t compare_func) {
44 q->compare_func = compare_func;
48 void prioq_free(Prioq *q) {
56 int prioq_ensure_allocated(Prioq **q, compare_func_t compare_func) {
62 *q = prioq_new(compare_func);
69 static void swap(Prioq *q, unsigned j, unsigned k) {
74 assert(j < q->n_items);
75 assert(k < q->n_items);
77 assert(!q->items[j].idx || *(q->items[j].idx) == j);
78 assert(!q->items[k].idx || *(q->items[k].idx) == k);
80 saved_data = q->items[j].data;
81 saved_idx = q->items[j].idx;
82 q->items[j].data = q->items[k].data;
83 q->items[j].idx = q->items[k].idx;
84 q->items[k].data = saved_data;
85 q->items[k].idx = saved_idx;
94 static unsigned shuffle_up(Prioq *q, unsigned idx) {
102 if (q->compare_func(q->items[k].data, q->items[idx].data) < 0)
112 static unsigned shuffle_down(Prioq *q, unsigned idx) {
118 k = (idx+1)*2; /* right child */
119 j = k-1; /* left child */
124 if (q->compare_func(q->items[j].data, q->items[idx].data) < 0)
126 /* So our left child is smaller than we are, let's
127 * remember this fact */
132 if (k < q->n_items &&
133 q->compare_func(q->items[k].data, q->items[s].data) < 0)
135 /* So our right child is smaller than we are, let's
136 * remember this fact */
139 /* s now points to the smallest of the three items */
142 /* No swap necessary, we're done */
152 int prioq_put(Prioq *q, void *data, unsigned *idx) {
153 struct prioq_item *i;
158 if (q->n_items >= q->n_allocated) {
160 struct prioq_item *j;
162 n = MAX((q->n_items+1) * 2, 16u);
163 j = realloc(q->items, sizeof(struct prioq_item) * n);
184 static void remove_item(Prioq *q, struct prioq_item *i) {
185 struct prioq_item *l;
190 l = q->items + q->n_items - 1;
193 /* Last entry, let's just remove it */
198 /* Not last entry, let's replace the last entry with
199 * this one, and reshuffle */
209 k = shuffle_down(q, k);
214 _pure_ static struct prioq_item* find_item(Prioq *q, void *data, unsigned *idx) {
215 struct prioq_item *i;
220 if (*idx > q->n_items)
229 for (i = q->items; i < q->items + q->n_items; i++)
236 int prioq_remove(Prioq *q, void *data, unsigned *idx) {
237 struct prioq_item *i;
242 i = find_item(q, data, idx);
250 int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {
251 struct prioq_item *i;
256 i = find_item(q, data, idx);
261 k = shuffle_down(q, k);
266 void *prioq_peek(Prioq *q) {
274 return q->items[0].data;
277 void *prioq_pop(Prioq *q) {
286 data = q->items[0].data;
287 remove_item(q, q->items);
291 unsigned prioq_size(Prioq *q) {
299 bool prioq_isempty(Prioq *q) {
304 return q->n_items <= 0;