1 /* SPDX-License-Identifier: LGPL-2.1+ */
3 This file is part of systemd.
5 Copyright 2013 Lennart Poettering
10 * The prioq object implements a priority queue. That is, it orders objects by
11 * their priority and allows O(1) access to the object with the highest
12 * priority. Insertion and removal are Θ(log n). Optionally, the caller can
13 * provide a pointer to an index which will be kept up-to-date by the prioq.
15 * The underlying algorithm used in this implementation is a Heap.
21 #include "alloc-util.h"
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
) {
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
= reallocarray(q
->items
, n
, sizeof(struct prioq_item
));
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
== PRIOQ_IDX_NULL
||
230 for (i
= q
->items
; i
< q
->items
+ q
->n_items
; i
++)
237 int prioq_remove(Prioq
*q
, void *data
, unsigned *idx
) {
238 struct prioq_item
*i
;
243 i
= find_item(q
, data
, idx
);
251 int prioq_reshuffle(Prioq
*q
, void *data
, unsigned *idx
) {
252 struct prioq_item
*i
;
257 i
= find_item(q
, data
, idx
);
262 k
= shuffle_down(q
, k
);
267 void *prioq_peek(Prioq
*q
) {
275 return q
->items
[0].data
;
278 void *prioq_pop(Prioq
*q
) {
287 data
= q
->items
[0].data
;
288 remove_item(q
, q
->items
);
292 unsigned prioq_size(Prioq
*q
) {
300 bool prioq_isempty(Prioq
*q
) {
305 return q
->n_items
<= 0;