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
) {
40 .compare_func
= compare_func
,
46 Prioq
* prioq_free(Prioq
*q
) {
54 int prioq_ensure_allocated(Prioq
**q
, compare_func_t compare_func
) {
60 *q
= prioq_new(compare_func
);
67 static void swap(Prioq
*q
, unsigned j
, unsigned k
) {
72 assert(j
< q
->n_items
);
73 assert(k
< q
->n_items
);
75 assert(!q
->items
[j
].idx
|| *(q
->items
[j
].idx
) == j
);
76 assert(!q
->items
[k
].idx
|| *(q
->items
[k
].idx
) == k
);
78 saved_data
= q
->items
[j
].data
;
79 saved_idx
= q
->items
[j
].idx
;
80 q
->items
[j
].data
= q
->items
[k
].data
;
81 q
->items
[j
].idx
= q
->items
[k
].idx
;
82 q
->items
[k
].data
= saved_data
;
83 q
->items
[k
].idx
= saved_idx
;
92 static unsigned shuffle_up(Prioq
*q
, unsigned idx
) {
94 assert(idx
< q
->n_items
);
101 if (q
->compare_func(q
->items
[k
].data
, q
->items
[idx
].data
) <= 0)
111 static unsigned shuffle_down(Prioq
*q
, unsigned idx
) {
117 k
= (idx
+1)*2; /* right child */
118 j
= k
-1; /* left child */
123 if (q
->compare_func(q
->items
[j
].data
, q
->items
[idx
].data
) < 0)
125 /* So our left child is smaller than we are, let's
126 * remember this fact */
131 if (k
< q
->n_items
&&
132 q
->compare_func(q
->items
[k
].data
, q
->items
[s
].data
) < 0)
134 /* So our right child is smaller than we are, let's
135 * remember this fact */
138 /* s now points to the smallest of the three items */
141 /* No swap necessary, we're done */
151 int prioq_put(Prioq
*q
, void *data
, unsigned *idx
) {
152 struct prioq_item
*i
;
157 if (q
->n_items
>= q
->n_allocated
) {
159 struct prioq_item
*j
;
161 n
= MAX((q
->n_items
+1) * 2, 16u);
162 j
= reallocarray(q
->items
, n
, sizeof(struct prioq_item
));
183 static void remove_item(Prioq
*q
, struct prioq_item
*i
) {
184 struct prioq_item
*l
;
189 l
= q
->items
+ q
->n_items
- 1;
192 /* Last entry, let's just remove it */
197 /* Not last entry, let's replace the last entry with
198 * this one, and reshuffle */
208 k
= shuffle_down(q
, k
);
213 _pure_
static struct prioq_item
* find_item(Prioq
*q
, void *data
, unsigned *idx
) {
214 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;