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 static void swap(Prioq *q, unsigned j, unsigned k) {
61 assert(j < q->n_items);
62 assert(k < q->n_items);
64 assert(!q->items[j].idx || *(q->items[j].idx) == j);
65 assert(!q->items[k].idx || *(q->items[k].idx) == k);
67 saved_data = q->items[j].data;
68 saved_idx = q->items[j].idx;
69 q->items[j].data = q->items[k].data;
70 q->items[j].idx = q->items[k].idx;
71 q->items[k].data = saved_data;
72 q->items[k].idx = saved_idx;
81 static unsigned shuffle_up(Prioq *q, unsigned idx) {
89 if (q->compare_func(q->items[k].data, q->items[idx].data) < 0)
99 static unsigned shuffle_down(Prioq *q, unsigned idx) {
105 k = (idx+1)*2; /* right child */
106 j = k-1; /* left child */
111 if (q->compare_func(q->items[j].data, q->items[idx].data) < 0)
113 /* So our left child is smaller than we are, let's
114 * remember this fact */
119 if (k < q->n_items &&
120 q->compare_func(q->items[k].data, q->items[s].data) < 0)
122 /* So our right child is smaller than we are, let's
123 * remember this fact */
126 /* s now points to the smallest of the three items */
129 /* No swap necessary, we're done */
139 int prioq_put(Prioq *q, void *data, unsigned *idx) {
140 struct prioq_item *i;
145 if (q->n_items >= q->n_allocated) {
147 struct prioq_item *j;
149 n = MAX((q->n_items+1) * 2, 16);
150 j = realloc(q->items, sizeof(struct prioq_item) * n);
171 static void remove_item(Prioq *q, struct prioq_item *i) {
172 struct prioq_item *l;
177 l = q->items + q->n_items - 1;
180 /* Last entry, let's just remove it */
185 /* Not last entry, let's replace the last entry with
186 * this one, and reshuffle */
196 k = shuffle_down(q, k);
201 static struct prioq_item* find_item(Prioq *q, void *data, unsigned *idx) {
202 struct prioq_item *i;
207 assert(*idx < q->n_items);
209 assert(i->data == data);
213 for (i = q->items; i < q->items + q->n_items; i++)
220 int prioq_remove(Prioq *q, void *data, unsigned *idx) {
221 struct prioq_item *i;
225 i = find_item(q, data, idx);
233 int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {
234 struct prioq_item *i;
239 i = find_item(q, data, idx);
244 k = shuffle_down(q, k);
249 void *prioq_peek(Prioq *q) {
255 return q->items[0].data;
258 void *prioq_pop(Prioq *q) {
266 data = q->items[0].data;
267 remove_item(q, q->items);
271 unsigned prioq_size(Prioq *q) {
277 bool prioq_isempty(Prioq *q) {
280 return q->n_items <= 0;