1 /* SPDX-License-Identifier: LGPL-2.1+ */
5 * The prioq object implements a priority queue. That is, it orders objects by
6 * their priority and allows O(1) access to the object with the highest
7 * priority. Insertion and removal are Θ(log n). Optionally, the caller can
8 * provide a pointer to an index which will be kept up-to-date by the prioq.
10 * The underlying algorithm used in this implementation is a Heap.
16 #include "alloc-util.h"
26 compare_func_t compare_func
;
27 unsigned n_items
, n_allocated
;
29 struct prioq_item
*items
;
32 Prioq
*prioq_new(compare_func_t compare_func
) {
39 q
->compare_func
= compare_func
;
43 Prioq
* prioq_free(Prioq
*q
) {
51 int prioq_ensure_allocated(Prioq
**q
, compare_func_t compare_func
) {
57 *q
= prioq_new(compare_func
);
64 static void swap(Prioq
*q
, unsigned j
, unsigned k
) {
69 assert(j
< q
->n_items
);
70 assert(k
< q
->n_items
);
72 assert(!q
->items
[j
].idx
|| *(q
->items
[j
].idx
) == j
);
73 assert(!q
->items
[k
].idx
|| *(q
->items
[k
].idx
) == k
);
75 saved_data
= q
->items
[j
].data
;
76 saved_idx
= q
->items
[j
].idx
;
77 q
->items
[j
].data
= q
->items
[k
].data
;
78 q
->items
[j
].idx
= q
->items
[k
].idx
;
79 q
->items
[k
].data
= saved_data
;
80 q
->items
[k
].idx
= saved_idx
;
89 static unsigned shuffle_up(Prioq
*q
, unsigned idx
) {
91 assert(idx
< q
->n_items
);
98 if (q
->compare_func(q
->items
[k
].data
, q
->items
[idx
].data
) <= 0)
108 static unsigned shuffle_down(Prioq
*q
, unsigned idx
) {
114 k
= (idx
+1)*2; /* right child */
115 j
= k
-1; /* left child */
120 if (q
->compare_func(q
->items
[j
].data
, q
->items
[idx
].data
) < 0)
122 /* So our left child is smaller than we are, let's
123 * remember this fact */
128 if (k
< q
->n_items
&&
129 q
->compare_func(q
->items
[k
].data
, q
->items
[s
].data
) < 0)
131 /* So our right child is smaller than we are, let's
132 * remember this fact */
135 /* s now points to the smallest of the three items */
138 /* No swap necessary, we're done */
148 int prioq_put(Prioq
*q
, void *data
, unsigned *idx
) {
149 struct prioq_item
*i
;
154 if (q
->n_items
>= q
->n_allocated
) {
156 struct prioq_item
*j
;
158 n
= MAX((q
->n_items
+1) * 2, 16u);
159 j
= reallocarray(q
->items
, n
, sizeof(struct prioq_item
));
180 static void remove_item(Prioq
*q
, struct prioq_item
*i
) {
181 struct prioq_item
*l
;
186 l
= q
->items
+ q
->n_items
- 1;
189 /* Last entry, let's just remove it */
194 /* Not last entry, let's replace the last entry with
195 * this one, and reshuffle */
205 k
= shuffle_down(q
, k
);
210 _pure_
static struct prioq_item
* find_item(Prioq
*q
, void *data
, unsigned *idx
) {
211 struct prioq_item
*i
;
219 if (*idx
== PRIOQ_IDX_NULL
||
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;