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 Prioq* prioq_free(Prioq *q) {
58 int prioq_ensure_allocated(Prioq **q, compare_func_t compare_func) {
64 *q = prioq_new(compare_func);
71 static void swap(Prioq *q, unsigned j, unsigned k) {
76 assert(j < q->n_items);
77 assert(k < q->n_items);
79 assert(!q->items[j].idx || *(q->items[j].idx) == j);
80 assert(!q->items[k].idx || *(q->items[k].idx) == k);
82 saved_data = q->items[j].data;
83 saved_idx = q->items[j].idx;
84 q->items[j].data = q->items[k].data;
85 q->items[j].idx = q->items[k].idx;
86 q->items[k].data = saved_data;
87 q->items[k].idx = saved_idx;
96 static unsigned shuffle_up(Prioq *q, unsigned idx) {
104 if (q->compare_func(q->items[k].data, q->items[idx].data) < 0)
114 static unsigned shuffle_down(Prioq *q, unsigned idx) {
120 k = (idx+1)*2; /* right child */
121 j = k-1; /* left child */
126 if (q->compare_func(q->items[j].data, q->items[idx].data) < 0)
128 /* So our left child is smaller than we are, let's
129 * remember this fact */
134 if (k < q->n_items &&
135 q->compare_func(q->items[k].data, q->items[s].data) < 0)
137 /* So our right child is smaller than we are, let's
138 * remember this fact */
141 /* s now points to the smallest of the three items */
144 /* No swap necessary, we're done */
154 int prioq_put(Prioq *q, void *data, unsigned *idx) {
155 struct prioq_item *i;
160 if (q->n_items >= q->n_allocated) {
162 struct prioq_item *j;
164 n = MAX((q->n_items+1) * 2, 16u);
165 j = realloc(q->items, sizeof(struct prioq_item) * n);
186 static void remove_item(Prioq *q, struct prioq_item *i) {
187 struct prioq_item *l;
192 l = q->items + q->n_items - 1;
195 /* Last entry, let's just remove it */
200 /* Not last entry, let's replace the last entry with
201 * this one, and reshuffle */
211 k = shuffle_down(q, k);
216 _pure_ static struct prioq_item* find_item(Prioq *q, void *data, unsigned *idx) {
217 struct prioq_item *i;
222 if (*idx == PRIOQ_IDX_NULL ||
232 for (i = q->items; i < q->items + q->n_items; i++)
239 int prioq_remove(Prioq *q, void *data, unsigned *idx) {
240 struct prioq_item *i;
245 i = find_item(q, data, idx);
253 int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {
254 struct prioq_item *i;
259 i = find_item(q, data, idx);
264 k = shuffle_down(q, k);
269 void *prioq_peek(Prioq *q) {
277 return q->items[0].data;
280 void *prioq_pop(Prioq *q) {
289 data = q->items[0].data;
290 remove_item(q, q->items);
294 unsigned prioq_size(Prioq *q) {
302 bool prioq_isempty(Prioq *q) {
307 return q->n_items <= 0;