2 This file is part of systemd.
4 Copyright 2013 Lennart Poettering
6 systemd is free software; you can redistribute it and/or modify it
7 under the terms of the GNU Lesser General Public License as published by
8 the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version.
11 systemd is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public License
17 along with systemd; If not, see <http://www.gnu.org/licenses/>.
22 * The prioq object implements a priority queue. That is, it orders objects by
23 * their priority and allows O(1) access to the object with the highest
24 * priority. Insertion and removal are Θ(log n). Optionally, the caller can
25 * provide a pointer to an index which will be kept up-to-date by the prioq.
27 * The underlying algorithm used in this implementation is a Heap.
33 #include "alloc-util.h"
43 compare_func_t compare_func
;
44 unsigned n_items
, n_allocated
;
46 struct prioq_item
*items
;
49 Prioq
*prioq_new(compare_func_t compare_func
) {
56 q
->compare_func
= compare_func
;
60 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;