1 /* SPDX-License-Identifier: LGPL-2.1-or-later */
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
) {
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 SWAP_TWO(q
->items
[j
].data
, q
->items
[k
].data
);
76 SWAP_TWO(q
->items
[j
].idx
, q
->items
[k
].idx
);
85 static unsigned shuffle_up(Prioq
*q
, unsigned idx
) {
87 assert(idx
< q
->n_items
);
94 if (q
->compare_func(q
->items
[k
].data
, q
->items
[idx
].data
) <= 0)
104 static unsigned shuffle_down(Prioq
*q
, unsigned idx
) {
110 k
= (idx
+1)*2; /* right child */
111 j
= k
-1; /* left child */
116 if (q
->compare_func(q
->items
[j
].data
, q
->items
[idx
].data
) < 0)
118 /* So our left child is smaller than we are, let's
119 * remember this fact */
124 if (k
< q
->n_items
&&
125 q
->compare_func(q
->items
[k
].data
, q
->items
[s
].data
) < 0)
127 /* So our right child is smaller than we are, let's
128 * remember this fact */
131 /* s now points to the smallest of the three items */
134 /* No swap necessary, we're done */
144 int prioq_put(Prioq
*q
, void *data
, unsigned *idx
) {
145 struct prioq_item
*i
;
150 if (q
->n_items
>= q
->n_allocated
) {
152 struct prioq_item
*j
;
154 n
= MAX((q
->n_items
+1) * 2, 16u);
155 j
= reallocarray(q
->items
, n
, sizeof(struct prioq_item
));
176 int prioq_ensure_put(Prioq
**q
, compare_func_t compare_func
, void *data
, unsigned *idx
) {
179 r
= prioq_ensure_allocated(q
, compare_func
);
183 return prioq_put(*q
, data
, idx
);
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 static struct prioq_item
* find_item(Prioq
*q
, void *data
, unsigned *idx
) {
217 struct prioq_item
*i
;
225 if (*idx
== PRIOQ_IDX_NULL
||
235 for (i
= q
->items
; i
< q
->items
+ q
->n_items
; i
++)
242 int prioq_remove(Prioq
*q
, void *data
, unsigned *idx
) {
243 struct prioq_item
*i
;
248 i
= find_item(q
, data
, idx
);
256 void prioq_reshuffle(Prioq
*q
, void *data
, unsigned *idx
) {
257 struct prioq_item
*i
;
262 i
= find_item(q
, data
, idx
);
267 k
= shuffle_down(q
, k
);
271 void *prioq_peek_by_index(Prioq
*q
, unsigned idx
) {
275 if (idx
>= q
->n_items
)
278 return q
->items
[idx
].data
;
281 void *prioq_pop(Prioq
*q
) {
290 data
= q
->items
[0].data
;
291 remove_item(q
, q
->items
);
295 unsigned prioq_size(Prioq
*q
) {
303 bool prioq_isempty(Prioq
*q
) {
308 return q
->n_items
<= 0;